4

Let $a$ be a natural number greater than $1$.

Consider the sets $ S(a):=\{f_n(a); n\in \mathbb{N}\}$,

with $f_0(a):=a$, $\ \ f_1(a):=2a-1\ \ $ and for $n>1$, $\ \ f_n(a):=f_1(f_{n-1}(a))$ .

Question: Is there always a prime number in $S(a)$, whatever $a$?

This question is raised, because for some $a$, the smallest prime in $S(a)$ can apparently be quite big, and it may take a large $n$ to find it.

Examples:

With $a = 95$, the first prime in $S(95)$ is reached when $n=582$, and it is a $178$ digits prime. \begin{align*}f_{582}(95)= &148793969526219687690798316645419749525135019619289042892300334\\ &545486970624089571289662346878443815865741959129891309426553781\\ &2046389415279164757669092989298186306341246574002177\end{align*}

With $a = 767$, the first prime in $S(767)$ seems to be a huge $1928$ digits prime.

Any reference on this question is also welcome.

As @lulu pointed out, $S(a)= \{ (a-1)2^n +1)\}$ is a set of Proth numbers.

So the question is equivalent to whether there exists a $k$-Proth prime, i.e. a prime of the form $k\cdot2^m+1$, for any odd $k$.

René Gy
  • 3,716
  • 1
    Aren't these sets of the form ${(a-1)\times 2^n+1}_{n=0}^{\infty}$? If so, I doubt it is known whether or not the set always contains a prime. – lulu Apr 30 '18 at 16:57
  • @lulu, right. Then these are Proth numbers. I will edit my question in order to mention this. – René Gy Apr 30 '18 at 17:32

1 Answers1

4

Yes, the primes of the form $k\times 2^n+1$ has been studied and it is known that there are integers $k$ such that $k\times 2^n+1$ is never prime. They are called Sierpinski number.

The smallest proven Sierpinski number is $78557$ because $78557\times 2^n+1$ is always the multiple of $3, 5, 7, 13, 19, 37$ or $73$. Distributed computer search is ongoing and there are only $5$ numbers such that $k<78557$ and no explicit $a_k$ such that $k \times 2^{a_k}+1$ is found. Also you can read more on the answers of this question and other related questions.

didgogns
  • 3,597