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.