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.
-
1$\begingroup$ It won't continue for long. $n \mapsto 10\cdot n + 21$ has good chances to become a multiple of almost any prime dividing neither of $10$ and $21$. $\endgroup$– Daniel FischerOct 28, 2013 at 10:02
-
$\begingroup$ You might be interested in "suffix primes": johndcook.com/blog/2013/03/12/a-suffix-prime - there are a finite number of them. $\endgroup$– Colin McQuillanOct 28, 2013 at 10:06
-
1$\begingroup$ Here's a generalization of this problem on mathoverflow: mathoverflow.net/questions/50071/prepending-strings-to-primes $\endgroup$– Matthew PiziakOct 28, 2013 at 13:18
-
$\begingroup$ homepage2.nifty.com/m_kamada/math/33331.htm redhotpawn.com/board/showthread.php?threadid=61054 and primes.utm.edu/curios/page.php/33333331.html $\endgroup$– lab bhattacharjeeOct 28, 2013 at 18:19
-
$\begingroup$ If you have a pattern or formula you can be near certain it will not generate only primes since there is no simple method like this known to generate primes. So given the choice of trying to prove the pattern continues or look for a counterexample, look for the counterexample. $\endgroup$– CoffeeCatJul 30, 2014 at 18:11
4 Answers
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.
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
-
$\begingroup$ As $3$ is a primitive root of $17,$ so will be $3^3=27\equiv10\pmod{17}$ and find this dbfin.com/2012/04/… $\endgroup$ Oct 28, 2013 at 10:16
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.
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