Mathematics desk
< July 3	<< Jun \| July \| Aug >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 4

n, 2n±1, 4n±3, 8n±7, ... all composite

Does there exist an odd composite number n such that iterating either the function f (n) = 2n + 1 or the function g (n) = 2n − 1 never yields a prime number? GeoffreyT2000 (talk) 20:43, 4 July 2018 (UTC)[reply]

Unlikely, one should expect that the number of primes within k iterates diverges as

2\log(k)/\log(2)

. Count Iblis (talk) 21:31, 4 July 2018 (UTC)[reply]

Independent of the starting number n? No chance that's right. --2601:142:3:F83A:BC7C:4FF3:BC84:995E (talk) 16:26, 5 July 2018 (UTC)[reply]

The sequence of composite numbers of the form

47\cdot 2^{n}+1

seems to be very long! --69.140.156.31 (talk) 19:42, 5 July 2018 (UTC)[reply]

OEIS:A032373 ("Numbers n such that 47*2^n+1 is prime"): 583, 1483, 6115. PrimeHunter (talk) 18:59, 6 July 2018 (UTC)[reply]

If you can read French, this describes the meta-situation fairly well. It is easy to make conjectures on the distribution of prime numbers of the kind "every number from the following formula is not prime" or "there is a formula of such and such form that produces only prime numbers", and hard to prove or disprove them, even if such conjectures are usually wrong. Tigraan^{Click here to contact me} 09:36, 6 July 2018 (UTC)[reply]

Your title sequence (with plus signs) follows the pattern for k=0, 1, ...:

2^{k}n+(2^{k}-1)=2^{k}(n+1)-1=[2^{k/2}(n+1)^{1/2}+1][2^{k/2}(n+1)^{1/2}-1].

This shows that if n is such that n+1 is a square, then all even iterates are composite with the above factorization. Loraof (talk) 15:38, 6 July 2018 (UTC)[reply]

f(n) gives the sequence 2^m*(n+1)−1, m = 0, 1, 2, ...

Let k be the largest odd divisor of n+1. If k is a Riesel number then f(n) always gives composite numbers.

g(n) gives the sequence 2^m*(n−1)+1, m = 0, 1, 2, ...

Let k be the largest odd divisor of n−1. If k is a Sierpinski number then g(n) always gives composite numbers.

There are infinitely many Sierpinski numbers and Riesel numbers. For example, k = 509203 is a Riesel number with covering set M = {3, 5, 7, 13, 17, 241}, so n = 2k-1 = 1018405 works for f(n) and always gives a prime factor in M. k = 78557 is a Sierpinski number with covering set M = {3, 5, 7, 13, 19, 37, 73}, so n = 2k+1 = 157115 works for g(n) and always gives a prime factor in M. A Brier number is a number which is both a Riesel number and a Sierpinski number. There are infinitely many Brier numbers, but they don't work in this variation if you simultaneously want f(n) and g(n) to produce composite numbers. The problem with the above attempt is that the odd part of n-1 is a Sierpinski number while the odd part of another number n+1 is a Riesel number. At http://www.primepuzzles.net/problems/prob_029.htm Yves Gallot computed the Brier number 623506356601958507977841221247. We cannot use this number itself but his covering sets and the Chinese remainder theorem can be used to compute n = 245242137182683342233839022329913069. f(n) always gives a prime factor in {3, 7, 73, 13, 19, 241, 37, 109, 97, 673}. g(n) always gives a prime factor in {3, 5, 17, 257, 65537, 641, 6700417}. As a quick sanity check, I tested that the first million numbers for my three n values give a prime factor in the covering set. There are infinitely many solutions. PrimeHunter (talk) 18:59, 6 July 2018 (UTC)[reply]