31,331,3331, 33331,333331,3333331,33333331 are prime

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.

Solution 1:

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.

Solution 2:

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

Solution 3:

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.

Solution 4:

There is a note in OEIS sequence A123568 Prime numbers of the form $\frac{(10^n - 7)}{3}$. which says:

Note that each $n$ from 2 to 8 gives primes, but after that the $n$ that correspond to primes are progressively further apart. Singh (1997) gives this as an example of why mathematicians don't trust a preponderance of evidence as proof: in the 17th century, when factoring numbers with as few as eight digits wasn't as easy as it is today, the pattern suggested that all numbers of this form are prime. - Alonso del Arte, Nov 11 2012