From: erick@sfu.ca (Erick Bryce Wong)
Subject: Re: New (unsolved?) problem
Date: 17 Dec 1999 20:08:17 GMT
Newsgroups: sci.math
Keywords: f(x)=2x+1 => f^n(x) prime for some n?
JEFFREY HARRIS wrote:
> I have come up with a problem that I have not seen before, and I was
>wondering if it had any references/previous results. Here it is:
>
>For every number, do repeated applications of the function f(n) = 2n+1
>eventually result in a prime? For instance, 9 is not prime, but 2*9+1 =
>19 is. Any help would be greatly appreciated
This is equivalent to asking, for every k is there a prime of the form
k*2^n - 1? If it were true it would imply the infinitude of Mersenne
primes, which is still unsolved. But it turns out the answer is no, and
a simple proof can be found here (it's actually for k*2^n + 1, but the
exact same argument applies here):
I think k=9223372036854775807 will work in this case.
-- Erick
==============================================================================
From: Kurt Foster
Subject: Re: New (unsolved?) problem
Date: Sat, 18 Dec 1999 00:07:17 GMT
Newsgroups: sci.math
In <385AA7CD.165892D0@home.com>, JEFFREY HARRIS said:
. Hello again!
. I have come up with a problem that I have not seen before, and I was
. wondering if it had any references/previous results. Here it is:
. For every number, do repeated applications of the function f(n) = 2n+1
. eventually result in a prime? For instance, 9 is not prime, but 2*9+1 =
. 19 is. Any help would be greatly appreciated
An old problem of Sierpinski is to find the smallest value of k for
which k * 2^n + 1 is composite for every positive integer n. There are k
with the property that no term of this sequence is prime - in fact, there
are finite sets of primes {p_1, p_2, ... p_r} for which all k in certain
congruence classes (mod p_1 * p_2 *... * p_r) yield sequences for which
gcd(k* 2^(n-1) - 1, p_1 * p_2 * ... * p_r) > 1 for every n. AFAIK, the
question Sierpinski asked has not yet been settled.
The sequences arising in your problem are quite similar: If the initial
number is k-1, then the n-th number is
k * 2^(n-1) - 1
Finite sets of primes and corresponding values of k can be found, similar
to the situation with the Sierpinski problem.
==============================================================================
From: erick@sfu.ca (Erick Bryce Wong)
Subject: Re: New (unsolved?) problem
Date: 18 Dec 1999 11:53:24 GMT
Newsgroups: sci.math
Dan Hoey wrote:
>erick@sfu.ca (Erick Bryce Wong) wrote:
>>
>
>I can't find it. Did you spell it right?
The link seems to work fine for me...Strange.
>>I think k=9223372036854775807 will work in this case.
[which was wrong]
>
>At any rate, if you start at k=200883553191612792 you always
>get composite numbers--they will all be divisible by 3, 5, 17, 257,
>65537, 641, or 6700417, in a cycle of period 64. Is this the
>approach you were using?
Thanks, yes I was following this approach. I wrote a rather hasty 5-minute
Maple program and didn't have a chance to test it extensively. I noticed
later that the first 2n+1 iterate wasn't divisible by any of the Fermat-ish
primes, so I must have erred somewhere :).
-- Erick
==============================================================================
From: Kurt Foster
Subject: Re: New (unsolved?) problem
Date: Sat, 18 Dec 1999 15:40:00 GMT
Newsgroups: sci.math
In <83fsjk$nfs$1@morgoth.sfu.ca>, Erick Bryce Wong said:
. Dan Hoey wrote:
.. At any rate, if you start at k=200883553191612792 you always get
.. composite numbers--they will all be divisible by 3, 5, 17, 257, 65537,
.. 641, or 6700417, in a cycle of period 64. Is this the approach you
.. were using?
. Thanks, yes I was following this approach. I wrote a rather hasty
. 5-minute Maple program and didn't have a chance to test it extensively.
. I noticed later that the first 2n+1 iterate wasn't divisible by any of
. the Fermat-ish primes, so I must have erred somewhere :).
You might try using the primes 3, 5, 17, 7, 13 and 241. We have
2^2 == 1 (mod 3)
2^4 == 1 (mod 5)
2^8 == 1 (mod 17)
2^3 == 1 (mod 7)
2^12 == 1 (mod 13)
2^24 == 1 (mod 241)
Clearly, if
k == 2^(2-a) (mod 3); 2^(4-b) (mod 5); 2^(8-c) (mod17);
2^(3-d) (mod 7); 2^(12-e) (mod 13); and 2^(24-f) (mod 241)
then k*2^n - 1 == 0
(mod 3), if n == a (mod 2);
(mod 5), if n == b (mod 4);
etc
Clearly, a, b and c can be chosen in 2*2*2 = 8 different ways so as to
cover all but one congruence class (mod 8), which leaves 3 congruence
classes (mod 24). Then, d, e and f can be chosen in 3*2*1 = 6 different
ways to cover these.
So, it appears there are 48 values of k (mod 5592405) such that
gcd(k*2^n - 1, 5592405) > 1 for every positive integer n.
For 24 of these, k is even; for the other 24, k is odd.