# Thread: [SOLVED] Recursive sequence and primes

1. ## [SOLVED] Recursive sequence and primes

I don't speak English well, but I have a serious problem.

Let $\displaystyle k > 1$. The sequence is defined by recursive equation $\displaystyle a_0 = 1, a_{n+1} = 10^{k}a_n+1$ for $\displaystyle n>=0$.

We must prove that this sequence contains only finitely many primes.

2. Originally Posted by bogdany
I don't speak English well, but I have a serious problem.

Let $\displaystyle k > 1$. The sequence is defined by recursive equation $\displaystyle a_0 = 1, a_{n+1} = 10^{k}a_n+1$ for $\displaystyle n>=0$.

We must prove that this sequence contains only finitely many primes.

I wonder if you might get more responses if this were posted in the Number Theory subforum.

There is, however, a very easy answer. What's an easy test for divisibility by 3 based on a number's decimal digits?

EDIT: Sorry, I completely forgot what the question asked momentarily, and the above gives a reason for there being infinitely many composites. I'll have to revisit the question. (And I may not be able to find an answer.)

(By the way, does anyone know how to get strikethrough text formatting? I tried searching but couldn't find a way. So I made my wrong answer gray instead.)

Edit 2: If the right answer involves divisibility tests for small primes then this link ("Divisibility by prime numbers under 50" by Stu Savory) might be helpful (or might not).

3. Every third element of this sequence is divisible by 3, but it's still not enough.

Thanks for this useful link, but I think that it isn't helpful in this problem.

For examle the smallest (except 1) divisor of 10001 is 73

4. Hello.

Maybe it helps to write the sequence in closed form:

$\displaystyle a_n=\frac{1-10^{k(1+n)}}{1-10^k}=1+10^k+10^{2k}+\ldots+10^{nk}$

5. Originally Posted by roninpro
Hello.

Maybe it helps to write the sequence in closed form:

$\displaystyle a_n=\frac{1-10^{k(1+n)}}{1-10^k}=1+10^k+10^{2k}+\ldots+10^{nk}$
Working off what roninpro wrote, for every odd k and odd n pair $\displaystyle a_n$ is divisible by 11.

6. For sufficiently large n, every odd n, $\displaystyle a_n$ is divisbile by $\displaystyle 10^k+1$.

7. Originally Posted by gmatt
For sufficiently large n, every odd n, $\displaystyle a_n$ is divisbile by $\displaystyle 10^k+1$.
I think we can prove this using induction. Or have you other idea?

But we still have a problem with even n, where $\displaystyle a_n$ isn't divisbile by 3.

8. The problem is that some of the terms are composite but have extremely weird prime factors. Does anybody know if this goes away when $\displaystyle n$ gets large?

9. Originally Posted by bogdany
I don't speak English well, but I have a serious problem.

Let $\displaystyle k > 1$. The sequence is defined by recursive equation $\displaystyle a_0 = 1, a_{n+1} = 10^{k}a_n+1$ for $\displaystyle n>=0$.

We must prove that this sequence contains only finitely many primes.

Aren't these primes all in the form $\displaystyle 4k+3$? Doesn't that help us tremendously? (I really don't know, but I know you can do a lot more with that than with $\displaystyle 1,11,111,\cdots$)

10. Maybe I don't understand you, but f.e. 101 is prime, but it isn't in the form $\displaystyle 4k+3$.

And I also think that $\displaystyle k\neq1$ is better for us.

11. Originally Posted by bogdany
I think we can prove this using induction. Or have you other idea?

But we still have a problem with even n, where $\displaystyle a_n$ isn't divisbile by 3.
Actually the proof is very simple.

$\displaystyle a_n = \frac{10^{k(1+n)} - 1}{10^k-1}$

use the fact that

$\displaystyle \gcd (10^k-1,10^k+1)=1$

and

$\displaystyle 10^k \equiv -1 \bmod(10^k+1)$.

You use the first fact to show that an inverse exists for $\displaystyle 10^k-1 \bmod{10^k+1}$ and the second fact to show that the numerator is 0.

Actually this sort of reasoning outlines a possible line of attack for the n even case.

We want to find $\displaystyle b$ such that

$\displaystyle a_n = \frac{10^{k(1+n)} - 1}{10^k-1} \equiv 0 \bmod{b}$

thus if we can find a $\displaystyle b$ that satisfies

$\displaystyle 10^{k(1+n)}-1 \equiv 0 \bmod{b}$

and

$\displaystyle \gcd(10^k-1,b) = 1$

then we are done.

Following this logic, it would probably be best to find $\displaystyle b$ such that $\displaystyle \gcd(10^k-1,b) = 1$

12. I think the key is $\displaystyle k \neq 1$

From $\displaystyle \frac{ a^{kp} -1 }{a^k - 1}~ , a=10$ , $\displaystyle p$ is prime . we get

$\displaystyle \frac{(1 + a + a^2 + a^3 + ... + a^{p-1} ) (1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p} ) }{ 1 + a + a^2 + a^3 + ... + a^{k-1}}$

If $\displaystyle p > k$ , then we have the inequality

$\displaystyle 1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p} >1 + a + a^2 + a^3 + ... + a^{p-1} > 1 + a + a^2 + a^3 + ... + a^{k-1}$

For $\displaystyle \frac{ a^{kp} -1 }{a^k - 1}$ to be prime , we must have

$\displaystyle 1 + a + a^2 + a^3 + ... + a^{p-1} = A$ ,

$\displaystyle 1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p} = BC$

and $\displaystyle 1 + a + a^2 + a^3 + ... + a^{k-1} = AB$ which gives $\displaystyle 1 + a + a^2 + a^3 + ... + a^{k-1} > 1 + a + a^2 + a^3 + ... + a^{p-1}$ , a contradiction .

Since $\displaystyle k$ is finite , it is impossible to find a prime in $\displaystyle \frac{ a^{kp} -1 }{a^k - 1}$ for $\displaystyle p > k$.

ps: Oh , I have just realized that $\displaystyle p$ is prime is unnecessary .

13. Originally Posted by simplependulum
For $\displaystyle \frac{ a^{kp} -1 }{a^k - 1}$ to be prime , we must have

$\displaystyle 1 + a + a^2 + a^3 + ... + a^{p-1} = A$ ,

$\displaystyle 1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p} = BC$

and $\displaystyle 1 + a + a^2 + a^3 + ... + a^{k-1} = AB$ which gives $\displaystyle 1 + a + a^2 + a^3 + ... + a^{k-1} > 1 + a + a^2 + a^3 + ... + a^{p-1}$ , a contradiction .
I don't know why this should be (this A, B and C).

14. Originally Posted by bogdany
I don't know why this should be (this A, B and C).

We know
$\displaystyle \frac{(1 + a + a^2 + a^3 + ... + a^{p-1} ) (1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p} ) }{ 1 + a + a^2 + a^3 + ... + a^{k-1}}$
is an integer .

Therefore, the denominator is divisible by the numerator .

I let $\displaystyle 1 + a + a^2 + a^3 + ... + a^{p-1} = AB$

and $\displaystyle 1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p} = CD$

as the product of two integers that one is cancelled by the numerator and one remains .

Let $\displaystyle 1 + a + a^2 + a^3 + ... + a^{k-1} = AC$ or $\displaystyle AD , BC ,BD$ whatever you like .

After the division ,we obtain the quotient $\displaystyle BD$ , if it is a prime , then either $\displaystyle B$ or $\displaystyle D$ is one , let $\displaystyle B=1$ so we have $\displaystyle 1 + a + a^2 + a^3 + ... + a^{k-1} = AC \geq A = AB = 1 + a + a^2 + a^3 + ... + a^{p-1}$ , a contradiction because we always have $\displaystyle 1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p} >1 + a + a^2 + a^3 + ... + a^{p-1} > 1 + a + a^2 + a^3 + ... + a^{k-1}$ for $\displaystyle p>k$ so $\displaystyle B \neq 1$ . Similar work on letting $\displaystyle D = 1$ , we will have another contradiction so the quotient is not a prime for all $\displaystyle n > k$ .