Problems & Puzzles: Puzzles

Puzzle 1120 F(n) = 2^n - A(n) Martin Hopf sent the following nice puzzle:   There are currently 51 known Mersenne primes of the form M(p) = 2^p-1. Q. Find a function F(n) = 2^n - A(n) with at least 52 primes and A(n) <= 2^(n-1) for n > 1.

---

During the week ending on Feb 3, 2023, contributions came from Michael Branicky, Emmanuel Vantieghem, Alain Rochelli, Giorgos Galageropoulos, Jan van Delden, Martin Hopf, J-M Rebert, Oscar Volpatti

***

Michael wrote:

A(n) = min_{0 <= k <= 2^(n-1)} such that 2^n - k is prime produces a prime for each n by the Bertrand-Chebyshev Theorem.

Also, A(n) = min {2^(n-1), 3} works since OEIS A050414 (Numbers k such that 2^k - 3 is prime) has 65 terms.

***

Emmanuel wrote:

Let's define the function  F  as follows :
   F(1) = 1  and for  n > 1  as  2^n - A(n), where  A(n)  is defined by
   A(n) = 1            when  2^n - 1  is prime
        = 2^(n-1) - k  when  2^n - 1  is composite and  k  the smallest positive integer such that 2^(n-1) + k is prime.
Then, F(n)  is prime for ALL n > 1.

Here are the first 100 values of  F :
1, 3, 7, 11, 31, 37, 127, 131, 257, 521, 1031, 2053, 8191, 8209, 16411, 32771, 131071, 131101, 524287, 524309, 1048583, 2097169, 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459, 536870923, 2147483647, 2147483659, 4294967311, 8589934609, 17179869209, 34359738421, 68719476767, 137438953481, 274877906951, 549755813911, 1099511627791, 2199023255579, 4398046511119, 8796093022237, 17592186044423, 35184372088891, 70368744177679, 140737488355333, 281474976710677, 562949953421381, 1125899906842679, 2251799813685269, 4503599627370517, 9007199254740997, 18014398509482143, 36028797018963971, 72057594037928017, 144115188075855881, 288230376151711813, 576460752303423619, 2305843009213693951, 2305843009213693967, 4611686018427388039, 9223372036854775837, 18446744073709551629, 36893488147419103363, 73786976294838206473, 147573952589676412931, 295147905179352825889, 590295810358705651741, 1180591620717411303449, 2361183241434822606859, 4722366482869645213711, 9444732965739290427421, 18889465931478580854821, 37778931862957161709601, 75557863725914323419151, 151115727451828646838283, 302231454903657293676551, 604462909807314587353111, 1208925819614629174706189, 2417851639229258349412369, 4835703278458516698824713, 9671406556917033397649483, 19342813113834066795298819, 38685626227668133590597803, 77371252455336267181195291, 154742504910672534362390567, 618970019642690137449562111, 618970019642690137449562141, 1237940039285380274899124357, 2475880078570760549798248507, 4951760157141521099596496921, 9903520314283042199192993897, 19807040628566084398385987713, 39614081257132168796771975177, 79228162514264337593543950397, 158456325028528675187087900777, 316912650057057350374175801351, 633825300114114700748351602943

 

Mathematica needs less than one second to prove that these numbers are all prime.
However, when  n  is big, the evaluation of  A  may become more and more hard since the primality should be proved !
Observe that the primality of numbers of the form  2^n - 1 (Mersenne primes) is always certified by the Lucas-Lehmer test.

 

***

Alain wrote:

Let A(n) = 2^(n-1) - 3 for n > 1
 

Then F(n) = 2^n - A(n) = 2^n - 2^(n-1) + 3 = 2^(n-1) + 3
 

For F(n) prime, I got the following 58 solutions, sequence number/ value of n :
 

1/ 2 ;  2/ 3 ;  3/ 4 ;  4/ 5 ;  5/ 7 ;  6/ 8 ;  7/ 13 ;  8/ 16 ;  9/ 17 ;  10/ 18 ;  11/ 29 ;  12/ 31 ;  13/ 56 ;  14/ 68 ;  15/ 85 ;  16/ 229 ;  17/ 391 ;
 

18/ 785 ;  19/ 1111 ;  20/ 1705 ;  21/ 2009 ;  22/ 2140 ;  23/ 2192 ;  24/ 2368 ;  25/ 2371 ;  26/ 4003 ;  27/ 4061 ;  28/ 4063 ;  29/ 4553 ;
 

30/ 5548 ;  31/ 8740 ;  32/ 17188 ;  33/ 17221 ;  34/ 17935 ;  35/ 20725 ;  36/ 22733 ;  37/ 25928 ;  38/ 31855 ;  39/ 33029 ;  40/ 35755 ;
 

41/ 38245 ;  42/ 39797 ;  43/ 40348 ;  44/ 55457 ;  45/ 58313 ;  46/ 122551 ;  47/ 205963 ;  48/ 235327 ;  49/ 363121 ;  50/ 479845 ;
 

51/ 685579 ;  52/ 742453 ;  53/ 1213816 ;  54/ 1434401 ;  55/ 1594948 ;  56/ 1875553 ;  57/ 1940813 ;  58/ 2205445

...

The values tested are taken from OEIS A057732. I used PARI code with the ispseudoprime function for only the first 48 values of n.

The largest case 2^2205444+3 has 663906 digits.

 

***

Giorgos wrote:

F(n) = 2^n - A(n)
 

We choose A(n) = 2^(n - 1) - 120 n + 75

A(n) < 2^(n-1) for n>1

F(n) = 2^n - ( 2^(n - 1) - 120 n + 75)
 

F(n) is prime for at least 65 values of n:

n=2,5,6,7,8,10,11,12,13,16,18,19,22,24,27,28,31,40,47,52,60,65,66,118,119,125,149,154,169,189,240,320,
342,363,514,528,539,776,816,982,1106,1217,1316,1533,2131,2415,2630,2875,3206,4262,5025,6034,
6718,7054,9471,12683,13372,13561,14222,20517,20917,24656,33101,34892,56582...

***

Jan wrote:

A function f(x): x->y is a relation where we assign a unique value y to each value x, where we pick x from a set. In this case we are asked to pick x as an integer greater than 1.

 

Here we can define F(n) as the largest prime that is smaller than 2^n, which will automatically ensure that A(n)=2^n-F(n) < 2^(n-1) by Bertrands postulate, since there is always a prime between k and 2k, for k>1. Set k=2^(n-1).  If we define F(n)=prevprime(2^n) then this formula is valid for n greater than 1. An explicit formular for 2<=n<=N can be found by using Lagrange’s interpolating polynomial.

 

As an alternative we could define F(n) as any other prime p for which 2^(n-1)<p<2^n; as n grows there is quite a range to manoeuver, but we should fix F(2)=3.

 

Finding an explicit elementary function for fixed N with N\ge 53 consisting of few parts is quite the challenge though.

 

***

Martin wrote:

This is about finding a function F(n) = 2^n - A(n) growing similar
to M(p) = 2^p-1 and containing at least 52 (proven) primes.

Let A(n) = 2^m-1 with m = floor(C*n),
floor() denotes the floor function and
C is a rational constant with 0.5 < C < 1.

Then F(n) = 2^n - 2^m + 1 can be written as a
Proth number of the form k*2^m + 1 with k < 2^n
F(n) = (2^(n-m) - 1)*2^m + 1.  

This benefits, as proving Proth primes with a deterministic
N-1 Pocklington test is satisfied, if N-1 is factored to at least 50%.

I finally choosed C = 0.637628

F(n) = 2^n - 2^floor(0.637628*n) + 1
giving 55 primes for n <= 20,000:

# F(n) = 2^n - 2^floor(0.637628*n) + 1 = Proth prime
========================================
1 F(1) = 2^1-2^0+1 = 2
2 F(2) = 2^2-2^1+1 = 3
3 F(3) = 2^3-2^1+1 = 7
4 F(4) = 2^4-2^2+1 = 13
5 F(7) = 2^7-2^4+1 = (2^3-1)*2^4+1
6 F(13) = 2^13-2^8+1 = (2^5-1)*2^8+1
7 F(15) = 2^15-2^9+1 = (2^6-1)*2^9+1
8 F(16) = 2^16-2^10+1 = (2^6-1)*2^10+1
9 F(19) = 2^19-2^12+1 = (2^7-1)*2^12+1
10 F(26) = 2^26-2^16+1 = (2^10-1)*2^16+1
11 F(29) = 2^29-2^18+1 = (2^11-1)*2^18+1
12 F(31) = 2^31-2^19+1 = (2^12-1)*2^19+1
13 F(32) = 2^32-2^20+1 = (2^12-1)*2^20+1
14 F(44) = 2^44-2^28+1 = (2^16-1)*2^28+1
15 F(64) = 2^64-2^40+1 = (2^24-1)*2^40+1
16 F(66) = 2^66-2^42+1 = (2^24-1)*2^42+1
17 F(101) = 2^101-2^64+1 = (2^37-1)*2^64+1
18 F(113) = 2^113-2^72+1 = (2^41-1)*2^72+1
19 F(143) = 2^143-2^91+1 = (2^52-1)*2^91+1
20 F(158) = 2^158-2^100+1 = (2^58-1)*2^100+1
21 F(226) = 2^226-2^144+1 = (2^82-1)*2^144+1
22 F(286) = 2^286-2^182+1 = (2^104-1)*2^182+1
23 F(290) = 2^290-2^184+1 = (2^106-1)*2^184+1
24 F(298) = 2^298-2^190+1 = (2^108-1)*2^190+1
25 F(324) = 2^324-2^206+1 = (2^118-1)*2^206+1
26 F(423) = 2^423-2^269+1 = (2^154-1)*2^269+1
27 F(528) = 2^528-2^336+1 = (2^192-1)*2^336+1
28 F(537) = 2^537-2^342+1 = (2^195-1)*2^342+1
29 F(556) = 2^556-2^354+1 = (2^202-1)*2^354+1
30 F(635) = 2^635-2^404+1 = (2^231-1)*2^404+1
31 F(842) = 2^842-2^536+1 = (2^306-1)*2^536+1
32 F(843) = 2^843-2^537+1 = (2^306-1)*2^537+1
33 F(871) = 2^871-2^555+1 = (2^316-1)*2^555+1
34 F(1019) = 2^1019-2^649+1 = (2^370-1)*2^649+1
35 F(1582) = 2^1582-2^1008+1 = (2^574-1)*2^1008+1
36 F(1721) = 2^1721-2^1097+1 = (2^624-1)*2^1097+1
37 F(2250) = 2^2250-2^1434+1 = (2^816-1)*2^1434+1
38 F(2426) = 2^2426-2^1546+1 = (2^880-1)*2^1546+1
39 F(2542) = 2^2542-2^1620+1 = (2^922-1)*2^1620+1
40 F(2555) = 2^2555-2^1629+1 = (2^926-1)*2^1629+1
41 F(2861) = 2^2861-2^1824+1 = (2^1037-1)*2^1824+1
42 F(3034) = 2^3034-2^1934+1 = (2^1100-1)*2^1934+1
43 F(3199) = 2^3199-2^2039+1 = (2^1160-1)*2^2039+1
44 F(3521) = 2^3521-2^2245+1 = (2^1276-1)*2^2245+1
45 F(4954) = 2^4954-2^3158+1 = (2^1796-1)*2^3158+1
46 F(5362) = 2^5362-2^3418+1 = (2^1944-1)*2^3418+1
47 F(5446) = 2^5446-2^3472+1 = (2^1974-1)*2^3472+1
48 F(6704) = 2^6704-2^4274+1 = (2^2430-1)*2^4274+1
49 F(7285) = 2^7285-2^4645+1 = (2^2640-1)*2^4645+1
50 F(7315) = 2^7315-2^4664+1 = (2^2651-1)*2^4664+1
51 F(10210) = 2^10210-2^6510+1 = (2^3700-1)*2^6510+1
52 F(12296) = 2^12296-2^7840+1 = (2^4456-1)*2^7840+1
53 F(13796) = 2^13796-2^8796+1 = (2^5000-1)*2^8796+1
54 F(14155) = 2^14155-2^9025+1 = (2^5130-1)*2^9025+1
55 F(17330) = 2^17330-2^11050+1 = (2^6280-1)*2^11050+1

***

Jean- Marc wrote:

Q. Find a function F(n) = 2^n - A(n) with at least 52 primes and A(n) <= 2^(n-1) for n > 1. 

1. Define A such that : 

If n < 3, A(n) = 0, 

If n >= 3 and n%2 =1, A(n) = 3,

If n >= 3 and n%2 = 0, A(n) = 5.
 

Cf. 

 

n A(n) <= 2^(n-1)

1 0 <= 1

2 0 <= 2

3 3 <= 4

4 5 <= 8

And for n >= 4, A(n) <= 5 <= 2^(4-1) <= 8 <= 2^(n-1), because : 

n → 2^(n-1) is an increasing function.

 

counter F(n) is a d-digit prime.
 

1  F(1) is a 1-digit prime.

2  F(3) is a 1-digit prime.

3  F(4) is a 2-digit prime.

4  F(5) is a 2-digit prime.

5  F(6) is a 2-digit prime.

6  F(8) is a 3-digit prime.

7  F(9) is a 3-digit prime.

8  F(10) is a 4-digit prime.

9  F(12) is a 4-digit prime.

10  F(18) is a 6-digit prime.

11  F(20) is a 7-digit prime.

12  F(26) is a 8-digit prime.

13  F(29) is a 9-digit prime.

14  F(32) is a 10-digit prime.

15  F(36) is a 11-digit prime.

16  F(56) is a 17-digit prime.

17  F(66) is a 20-digit prime.

18  F(118) is a 36-digit prime.

19  F(130) is a 40-digit prime.

20  F(150) is a 46-digit prime.

21  F(166) is a 50-digit prime.

22  F(206) is a 63-digit prime.

23  F(213) is a 65-digit prime.

24  F(221) is a 67-digit prime.

25  F(226) is a 69-digit prime.

26  F(233) is a 71-digit prime.

27  F(545) is a 165-digit prime.

28  F(550) is a 166-digit prime.

29  F(689) is a 208-digit prime.

30  F(706) is a 213-digit prime.

31  F(810) is a 244-digit prime.

32  F(1136) is a 342-digit prime.

33  F(1228) is a 370-digit prime.

34  F(1818) is a 548-digit prime.

35  F(2321) is a 699-digit prime.

36  F(2368) is a 713-digit prime.

37  F(2400) is a 723-digit prime.

38  F(3128) is a 942-digit prime.

39  F(3237) is a 975-digit prime.

40  F(4532) is a 1365-digit prime.

41  F(5112) is a 1539-digit prime.

42  F(8492) is a 2557-digit prime.

43  F(16028) is a 4825-digit prime.

44  F(16386) is a 4933-digit prime.

45  F(17392) is a 5236-digit prime.

46  F(18582) is a 5594-digit prime.

47  F(20757) is a 6249-digit prime.

48  F(21986) is a 6619-digit prime.

49  F(24292) is a 7313-digit prime.

50  F(27618) is a 8314-digit prime.

51  F(30041) is a 9044-digit prime.

52  F(30918) is a 9308-digit prime.

53  F(32762) is a 9863-digit prime.

54  F(42689) is a 12851-digit prime.

55  F(44629) is a 13435-digit prime.

56  F(48212) is a 14514-digit prime.

57  F(52790) is a 15892-digit prime.
 

2. Polynomial interpolation

Let A(x) = 

2245500427241/3638198539625553671742990428416510340161994713503671255040000000000*x^53 - 18541485714646747/20164543792735969642915159214100941743822376360220819456000000000000*x^52 + 34135047800674897/51276653001235777858652661701464568960768916364197888000000000000*x^51 - 5691292451426663/18230225695332694132035529370268592713912672269107200000000000*x^50 + 295450603734764161/2770164086683571434712343817781990331176711186546688000000000*x^49 - 107555133906889786973/3800178242613083470672129300216339297506577455513600000000000*x^48 + 31671288530582738109898937/5213844548865150521762161399896817516179024268964659200000000000*x^47 - 6012895978107230375153381/5546643137090585661449107872230656932105344966983680000000000*x^46 + 3333254835842896008704629/20308075559141732398898335458968080300614535348224000000000*x^45 - 7374845746911908899654821817/344511996092582960338453905107494219385425153228800000000000*x^44 + 23474832188675680834250598892417/9646335890592322889476709343009838142791904290406400000000000*x^43 - 390060827579425517347504699403/1602381377174804466690483279569740555281047224320000000000*x^42 + 1144762773479668740837510672271/53024256481057165988666901251216869283845562695680000000*x^41 - 62766590945425046396637801498689/36740754213592825657335713172960691022620262400000000000*x^40 + 165837885457686376970725448623158389/1367886541490686739857729628900998034996015923200000000000*x^39 - 5824403675977476184301760165727933/751586011808069637284466829066482436810997760000000000*x^38 + 4615018834960980652921991690845300393/10306513553614038593941896372882866080856408064000000000*x^37 - 4819752834151885105330524383952685151/205455511917352204638341479650804154289356800000000000*x^36 + 312040748555677762247069180309406691741163/279328182646746841772749593889693292431618867200000000000*x^35 - 71653606031637415009588079946204921922273/1478796261071012691738086085298376254049746944000000000*x^34 + 1668013384316506109524995881596368371723279/869880153571183936316521226646103678852792320000000000*x^33 - 18681341829933382368926060558719653887570263/269459960107691817007668747321132699353088000000000000*x^32 + 57164316265910365358376095539395005031531412321/24935714079643175887079164194913969093214208000000000000*x^31 - 12357517811962231241941042720859557817759613269/178112243426022684907708315677956922094387200000000000*x^30 + 21940093079619679811331971792145422451856505574247/11410582762844717285927425535592632257054821580800000000*x^29 - 600132217486035197158835863390507651495843794963967/12295886597893014316732139585767922690791833600000000000*x^28 + 225958156229671381492801314140364282185343511214263/199123669601506304724407118797861096207155200000000000*x^27 - 50220819634371815115026902297645474571419635931217/2078763583751988895474579811626022432931840000000000*x^26 + 516501692500770122211098069933411110431251573021722373/1097171419504299739031483224576214640101425152000000000*x^25 - 4109325409995969512272787445047801701984088562911294623/489808669421562383496197868114381535759564800000000000*x^24 + 1262643712986345338185893331557634300161359671684074574753/9242476631693829323363038033114851587810918400000000000*x^23 - 938120709220149286220525639242254319069419141203758633097/462123831584691466168151901655742579390545920000000000*x^22 + 785194222146402538058198673410142275421433443494115151487/28567655043417290635849390284173177635051929600000000*x^21 - 1348890895039409238353471605880400206974657334459165521853/3985442946905313983795952885626838397747200000000000*x^20 + 63059461675679254885178809377096131468505985462859681241371/16672549102164165799784767249888845181747200000000000*x^19 - 8308538048154994693869859153365794631909847812605887197893/217163454692054260417364615439728655728640000000000*x^18 + 57087383132002352486993636673607377458779509664040163488318551/163442325729585731784471371100303074034450432000000000*x^17 - 2766795773588982390630025149749424752585083783079256598171476829/964763728264915777894449065522622312008908800000000000*x^16 + 3130656482314944134365105375585741097656464808104034838534999327/148425188963833196599146010080403432616755200000000000*x^15 - 3632643564182165713643577956491524130507538032928739324497/26264831442344534090556884514590687232000000000*x^14 + 27185990338920127144566936795433656258598817453932122851783302151/33807959708428672558694368962758559651594240000000000*x^13 - 1726689760628804677946946620675769891996645315446505683917730617/419245532098569848198094853208811503616000000000000*x^12 + 2961649314358894986312442771344837465693119066378186525620214064821/160609152023943030936979246492902879657984000000000000*x^11 - 15951559263598116764337380468872236622398803140509652194178907143/223068266699920876301360064573476221747200000000000*x^10 + 28218479151882004832956905986638799759320547945148235950022687933/118813203105431540429987571235977861267456000000000*x^9 - 62169142901240615275077069325013498633281390506637072500683117/93313940931018488267599365636722030592000000000*x^8 + 4862670224568671364336867216739598052534446180794370867843688239/3135348415282221205791338685393860227891200000000*x^7 - 2038330357624981405352421570305523676688748936639049496480843/696151622818709356917011140464434196480000000*x^6 + 9550717356822931040673071849172619480223849969272908517310977/2197850123470496683980849457751999391744000000*x^5 - 7191280538562207511861597711373164380707894435464357891/1483269978586610978823054649708454400000*x^4 + 13769975750719659065707171537234727591776423615122287/3630381066470726171944539352433280000*x^3 - 18142366943876076417141811799317612916219623/9876781895856665589161762400*x^2 + 541735283033357229337623457310998241/1324591602621272785800*x + 1, if x is an integer such that 1 <= x <= 53, or 0 if x > 53.

 

n F(n) = 2^n - A(n) prime

1 2

2 3

3 7

4 13

5 31

6 61

7 127

8 251

9 509

10 1021

11 2039

12 4093

13 8191

14 16381

15 32749

16 65521

17 131071

18 262139

19 524287

20 1048573

21 2097143

22 4194301

23 8388593

24 16777213

25 33554393

26 67108859

27 134217689

28 268435399

29 536870909

30 1073741789

31 2147483647

32 4294967291

33 8589934583

34 17179869143

35 34359738337

36 68719476731

37 137438953447

38 274877906899

39 549755813881

40 1099511627689

41 2199023255531

42 4398046511093

43 8796093022151

44 17592186044399

45 35184372088777

46 70368744177643

47 140737488355213

48 281474976710597

49 562949953421231

50 1125899906842597

51 2251799813685119

52 4503599627370449

53 9007199254740881

 

F(n) = 2^n - A(n) is prime for n = 1 to 53.

***

Oscar wrote:

A(n) = 3
F(n) = 2^n - 3
66 known primes or prps with n <= 2086750
OEIS sequence A050414

A(n) = 2^(n-1) - 555
F(n) = 2^(n-1) + 555
80 known primes or prps with n <= 21131
sequence not in OEIS:
2, 4, 5, 6, 7, 8, 9, 11, 13, 14, 18, 21, 24, 29, 32, 34, 35, 37, 41, 49, 53, 56, 68, 81, 91, 109, 116, 126, 133, 146, 163, 196, 214, 235, 259, 263, 289, 364, 371, 502, 504, 529, 573, 623, 628, 635, 657, 658, 667, 743, 918, 1077, 1192, 1348, 1437, 1518, 1561, 1802, 3062, 3597, 3981, 4614, 4653, 5186, 5494, 5658, 6077, 6085, 6724, 7672, 7733, 9298, 10445, 11166, 12103, 15133, 17423, 17856, 18265, 21131...

***