29
$\begingroup$

31,331,3331, 33331,333331,3333331,33333331 are prime. This law can continue it? Will there emerge a composite number? Without using a computer how to judge.

$\endgroup$
59
$\begingroup$

333333331 is not prime; it is divisible by 17. This does not require a computer. Euler did calculations like this all the time.

What's more, in your sequence 31, 331, 3331, 33331, …, every 15th number is divisible by 31.

Proof: An noted in lab bhattacharjee's answer, the sequence has the form $$ a_n = \frac{10^{n+1}-7}{3} $$ Now, 15 is the multiplicative order of $10 \pmod{31}$, so $$ a_{15k+1} = \frac{10^{15k+2}-7}{3} \equiv \frac{10^2-7}{3} \equiv 0 \pmod{31}. $$

It has been proven that for all sequences that look like $ab$, $abb$, $abbb$, $abbbb$, … or $ab$, $aab$, $aaab$, $aaaab$, … where the $a$ and $b$ are digits, that periodically the numbers in the sequence are divisible by the first number $ab$.

As an easy exercise, show that in the sequence 11, 111, 1111, 11111, …, that every second term is divisible by 11.

$\endgroup$
12
$\begingroup$

HINT:

$$\underbrace{33\cdots33}_{n \text{ digits}}1=10\frac{10^n-1}3+1=\frac{10^{n+1}-7}3$$

We need to find a prime divisor$(p)$ of $\frac{10^{n+1}-7}3$

Observe that $p>11$

Another way will be to find $p$ such that $10$ is a primitive root

$\endgroup$
3
$\begingroup$

A little bit off-topic answer:

You can't assume that statements that hold for small number will hold for big number, especially for sequences with primality, because even with computer technology the prime number are one of the biggest mysteries of the maths world. There is one brilliant saying, I can't remember exactly, but one great mathematician (I think it was Polya) once said "An intuition isn't a proof. Which is right for you case.

Also one another good quote is "There'll never be enough small number to prove that something holds generally.". This two quotes describe your problem, even if every number till the $1000^{th}$ one is prime, that doesn't prove that the next one isn't. Luckily in this problem the break happens at the $8^{th}$ number, and as other users proved, there are infinite amount of composite numbers in the sequence.

And at last I think you might be interested in the piece "Law of Small Numbers" by Richard Guy. There are lot of examples like yours, actually this example is included into the book. You can see that the conjectures are proven for some sequences, but the most of them are false. And for some examples the first off-example happens quite late.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.