# 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 $k > 1$. The sequence is defined by recursive equation $a_0 = 1,
a_{n+1} = 10^{k}a_n+1$
for $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 $k > 1$. The sequence is defined by recursive equation $a_0 = 1,
a_{n+1} = 10^{k}a_n+1$
for $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:

$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:

$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 $a_n$ is divisible by 11.

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

7. Originally Posted by gmatt
For sufficiently large n, every odd n, $a_n$ is divisbile by $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 $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 $n$ gets large?

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

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

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

Aren't these primes all in the form $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 $1,11,111,\cdots$)

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

And I also think that $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 $a_n$ isn't divisbile by 3.
Actually the proof is very simple.

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

use the fact that

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

and

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

You use the first fact to show that an inverse exists for $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 $b$ such that

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

thus if we can find a $b$ that satisfies

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

and

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

then we are done.

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

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

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

$\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 $p > k$ , then we have the inequality

$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 $\frac{ a^{kp} -1 }{a^k - 1}$ to be prime , we must have

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

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

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

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

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

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

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

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

and $1 + a + a^2 + a^3 + ... + a^{k-1} = AB$ which gives $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
$
\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 $1 + a + a^2 + a^3 + ... + a^{p-1} = AB$

and $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 $1 + a + a^2 + a^3 + ... + a^{k-1} = AC$ or $AD , BC ,BD$ whatever you like .

After the division ,we obtain the quotient $BD$ , if it is a prime , then either $B$ or $D$ is one , let $B=1$ so we have $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 $
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 $p>k$ so $B \neq 1$ . Similar work on letting $D = 1$ , we will have another contradiction so the quotient is not a prime for all $n > k$ .