3
$\begingroup$

Let $a_1=k,a_{n}=2a_{n-1}+1(n\geq 2).$

If $k=1$ then $a_n=1,3,7,15,31,63,\cdots$ here $3,7,31$ are prime numbers. I'm interested in this problem:

Does there exist $k\in\mathbb N$ such that $a_n,n=1,2,3,\cdots$ are all composite numbers?

If $k=147$ then $a_n,n=1,2,\cdots 2551$ are all composite, but $a_{2552}$ is prime. So I doubt the existence of such number.

$\endgroup$
3
$\begingroup$

The numbers you mention are Riesel numbers http://en.wikipedia.org/wiki/Riesel_number and there is the similar Sierpinski numbers where it is $2a_{n-1}-1$ instead. http://en.wikipedia.org/wiki/Sierpinski_number

$\endgroup$
  • $\begingroup$ Thank you! But that is the case $k=1$ which I have excluded. $\endgroup$ – lsr314 Nov 5 '13 at 15:03
  • 1
    $\begingroup$ If you rename your number $k-1$, the next term is $2k-1$, then $4k-1,8k-1$, and so on. That is why those pages talk about $k2^n-1$. The first starting point where they are all composite is 509202, where every number in the sequence is a multiple of either 2,3,5,7,13,17 or 241. $\endgroup$ – Empy2 Nov 5 '13 at 15:17
2
$\begingroup$

I'll just add the proof that for $a_1=1018405=2\cdot509203-1=2\cdot c-1$ all $a_n$ are composite.

First note that $a_1=2\cdot c-1, \ a_2=2a_1+1=2^2\cdot c-1$ and inductively $a_n=2a_{n-1}+1=2\cdot(2^{n-1}\cdot c-1)+1=2^n\cdot c-1$ for all $n\geq 1$.
Now if $p$ is a prime such that $a_m\equiv a_{m+l}\equiv0\pmod p$ with $m\in\mathbb N$ minimum then it's not so hard to see that $a_{n}\equiv0\pmod p$ for all $n\equiv m\pmod l$.
By a direct computation we see that $$ a_2\equiv a_4\equiv 0\pmod 3\\ a_1\equiv a_5\equiv 0\pmod 5\\ a_2\equiv a_5\equiv 0\pmod 7\\ a_7\equiv a_{19}\equiv 0\pmod {13}\\ a_7\equiv a_{15}\equiv 0\pmod {17}\\ a_3\equiv a_{27}\equiv 0\pmod {241}. $$ Since the solution of the system of the consequences $$ n\equiv 0\pmod 2\\ n\equiv 1\pmod 4\\ n\equiv 2\pmod 3\\ n\equiv 7\pmod {12}\\ n\equiv 7\pmod 8\\ n\equiv 3\pmod {24} $$ is $n\in\mathbb N$ it follows that $a_n\equiv0\pmod {5592405}$ for all $n\in\mathbb N$(note that ${5592405=3\cdot5\cdot7\cdot13\cdot17\cdot241}$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.