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.
29
$\begingroup$
$\endgroup$
asked Oct 28 '13 at 9:58
-
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 Fischer Oct 28 '13 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 McQuillan Oct 28 '13 at 10:06
-
1$\begingroup$ Here's a generalization of this problem on mathoverflow: mathoverflow.net/questions/50071/prepending-strings-to-primes $\endgroup$ – Matthew Piziak Oct 28 '13 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 bhattacharjee Oct 28 '13 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$ – CoffeeCat Jul 30 '14 at 18:11
59
$\begingroup$
$\endgroup$
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.
12
$\begingroup$
$\endgroup$
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
answered Oct 28 '13 at 10:08
-
$\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$ – lab bhattacharjee Oct 28 '13 at 10:16
3
$\begingroup$
$\endgroup$
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.
answered Oct 28 '13 at 23:10
