Problems & Puzzles: Puzzles

Puzzle 754. Quantity of primes in P+Q For sure you know that if S=P+Q, being P and Q consecutive primes then S has at least 3 prime factors. I have computed the champions P&Q for the quantity C of prime factors  in S. Here are my results:   C P Q S 3  3  5  8  4  11  13  24  5  53  59  112  7  61  67  128  8  191  193  384  9  953  967  1920  10  1151  1153  2304  11  3833  3847  7680  13  4093  4099  8192  14  30713  30727  61440  15  36857  36871  73728  16  110587  110597  221184  17  360439  360457  720896  18  663547  663557  1327104  20  786431  786433  1572864  21  3932153  3932167  7864320  22  5242877  5242883  10485760  23  9437179  9437189  18874368  24  63700991  63700993  127401984  25  138412031  138412033  276824064  26  169869311  169869313  339738624  27  436207613  436207619  872415232  29  1358954453  1358954539  2717908992  30  1879048183  1879048201  3758096384    Q1. Please send the next few champions for this table. Q2. Redo this table considering only "distinct prime factors"

---

Contributions came from Torbjörn Alm, Vicente Felipe Izquierdo, Jean Brette, Jan van Delden, Fred Schneider & Hakan Summakoglu.

***

Torbjörn wrote:

Q2. The first 5 solutions :

Unique solution: 3 factors  P=13  Q=17  S= 30
2*3*5
Unique solution: 4 factors  P=103  Q=107  S= 210
2*3*5*7
Unique solution: 5 factors  P=1783  Q=1787  S= 3570
2*3*5*7*17
Unique solution: 6 factors  P=15013  Q=15017  S= 30030
2*3*5*7*11*13
Unique solution: 7 factors  P=285283  Q=285287  S= 570570
2*3*5*7*11*13*19

***

Vicente wrote:

Q1:

Valores no indicados en tu lista:

Prime[21]       ,  6,          71,          73,         144   

Prime[917]      , 12,        7159,        7177,       14336

Prime[153385]   , 19,     2064379,     2064389,     4128768

Prime[184328921], 28,  3875536883,  3875536909,  7751073792

 

Nuevos Resultados:

Prime[457932095], 31, 10066329587, 10066329613, 20132659200

Prime[370110664], 32,  8053063661,  8053063699, 16106127360

 

 

Q2:

Prime[2], 1,  2, 3,  5

Prime[4], 2,  5, 7, 12

Prime[7], 3, 13, 17, 30

Prime[28], 4, 103, 107, 210

Prime[277], 5, 1783, 1787, 3570

Prime[1756], 6, 15013, 15017, 30030

Prime[24866], 7, 285283, 285287, 570570

Prime[646030], 8, 9699667, 9699713, 19399380

Prime[7946522], 9, 140645501, 140645509, 281291010

 

Buscando en OEIS los primeros primos de la secuencia, están indicados en https://oeis.org/A230518

***

Jean wrote:

Question  Q1 :

 

Question Q1 : 

You find below my best values (P, Q, S) for C = 6, 12, 19 and 28, which are not in your datas,

and for C from 31 to 41.

As before, I am not sure that they are really the best.

 

 

 

C	P	Q	S		Factors of S	LogS/C
6	71	73	144		24  * 32	0,82830
12	7159	7177	14336		211 *  7	0,79754
19	2064379	2064389	4128768		216 * 32 * 7	0,80176
28	3875536883	3875536909	7751073792		225 * 3 * 7 * 11	0,81325
----	-----------------------	-----------------------	----------------------		---------------------	---------------
31	10066329587	10066329613	20132659200		228 * 3 * 52	0,76534
32	10871635967	10871635969	21743271936		228 * 34	0,74383
33	14495514619	14495514629	28991029248		230 * 33	0,73000
34	97844723701	97844723723	195689447424		228 * 36	0,76469
35	195689447417	195689447431	391378894848		229 * 36	0,76265
36	193273528303	193273528337	386547056640		233 * 32 * 5	0,74112
37	446676598751	446676598817	893353197568		236 * 13	0,74373
38	515396075501	515396075539	1030792151040		236 * 3 * 5	0,72793
39	927712935923	927712935949	1855425871872		236 * 33	0,72433
40	15307263442931	15307263442957	30614526885888		235 * 34 * 11	0,77631
41	15461882265563	15461882265637	30923764531200		237 * 32 * 52	0,75762

 

 

2) I have also looked for a relation between  C and S.

My answer : With your datas, all the ratios   Log S / C   are very close to   0,765.

The minimum is 0,69314 = Log 2  when S is a power of 2 (of course), and the max is   0,84   , with a mean value 0,765.

Q2 :

Find the smallest P and Q consecutive primes such that S = P + Q has exactly C distinct prime

factors

Here are the best answers I have found. (My search is not systematic, so I do not know if they are

really the smallest solutions). The fourth column gives the values Log S / C logC, which are very

close to 1.

C P Q S LogS / C LogC

3 13 17 30 1,032

4 103 107 210 0 ,964

5 1783 1787 3570 1,016

6 15013 15017 30030 0,959

7 285283 285287 570570 0,973

8 10140583 10140587 20281170 1,011

9 140645501 140645509 281291010 0,984

10 5766465703 5766465707 11532931410 1,006

11 100280245063 100280245067 200560490130 0,986

12 8019184758583 8019184758587 16038369517170 1,019

13 242577912812233 242577912812237 485155825624470 1,014

14 12871749052126963 12871749052126967 25743498104253930 1,023

15 438272504610946003 438272504610946007 876545009221892010 1,017



The factorizations of the successive S’s (P# means 2*3*5*7*11*...*P)

30 = 5#

210 = 7#

3570 = 7# * 17

30030 = 13#

570570 = 19# / 17

20281170 = 23# / 11

281291010 = 29# / 23

11532931410 = 19# * 29 * 41

200560490130 = 31#

16038369517170 = 67* 37# / 31

485155825624470 = 31# 41* 59

25743498104253930 = 43# * 61 / 31

876545009221892010 = 43# *67

***

Jan wrote

Q1: 

From the given table by Carlos it’s clear that iterating over p will take some time. At first I used a sieve to speed things up and found all solutions C<=30, including the trivial case P=2, Q=3 P+Q=5, where C=1. However it is much faster by iterating over S, since S should have a particular form in order to have a fixed number of prime factors (counted with multiplicity) and be as small as possible: S=2^k*B, where nopf(S)=k+nopf(B). Given C, we could reserve several prime factors, say 5, for B en leave k=C-5 factors equal to 2. Choose the bound B large enough, say 250 (using the given table 29 would be enough..), and construct an increasing list of possible products of 5 prime-factors (including 2!) <= 2^5*B. This gives a list of increasing values of S to try, with Q=prevprime(S/2) and R=nextprime(S/2) and Q+R=S. The first hit is enough, since the primegap is (very) small compared to 2^C, and will give (an upperbound on) S.

 

F = S/2^C, the realised value of B
D = Q-S/2, 2D=Q-P

 

 C    F         D S

 

 3:   1.0000    1 2^3

4:   1.5000    1 2^3*3

5:   3.5000    3 2^4*7

6:   2.2500    1 2^4*3^2

 7:   1.0000    3 2^7

8:   1.5000    1 2^7*3

9:   3.7500    7 2^7*3*5

10:   2.2500    1 2^8*3^2

11:   3.7500    7 2^9*3*5

12:   3.5000    9 2^11*7

13:   1.0000    3 2^13

14:   3.7500    7 2^12*3*5

15:   2.2500    7 2^13*3^2

16:   3.3750    5 2^13*3^3

17:   5.5000    9 2^16*11

18:   5.0625    5 2^14*3^4

19:   7.8750    5 2^16*3^2*7

20:   1.5000    1 2^19*3

21:   3.7500    7 2^19*3*5

22:   2.5000    3 2^21*5

23:   2.2500    5 2^21*3^2

24:   7.5938    1 2^19*3^5

25:   8.2500    1 2^23*3*11

26:   5.0625    1 2^22*3^4

27:   6.5000    3 2^26*13

28:  28.8750   13 2^25*3*7*11

29:   5.0625   43 2^25*3^4

30:   3.5000    9 2^29*7

31:   9.3750   13 2^28*3*5^2

32:   3.7500   19 2^30*3*5

33:   3.3750    5 2^30*3^3

34:  15.6250    9 2^31*5^3

35:  23.5000    3 2^34*47

36:   5.6250   17 2^33*3^2*5

37:   6.5000   33 2^36*13

38:   3.7500   19 2^36*3*5

39:   3.3750   13 2^36*3^3

40:  27.8438   13 2^35*3^4*11

41:  14.0625   37 2^37*3^2*5^2

42:   5.2500   11 2^40*3*7

43:   9.7500    7 2^41*3*13

44:   8.7500    9 2^42*5*7

45:   5.6250    7 2^42*3^2*5

46:   2.2500    1 2^44*3^2

47:   9.3750    1 2^44*3*5^2

48:  18.3750    1 2^45*3*7^2

49:   5.6250   19 2^46*3^2*5

50:  12.2500   15 2^48*7^2

51:  20.6250   13 2^48*3*5*11

52:  11.8125    5 2^48*3^3*7

53:   6.5000   45 2^52*13

54:   9.7500    5 2^52*3*13

55:   5.6250   23 2^52*3^2*5

56:   7.5938   25 2^51*3^5

57:  20.6250   31 2^54*3*5*11

58:   1.5000   35 2^57*3

59:  14.2500   49 2^57*3*19

60:   5.2500   11 2^58*3*7

61:  15.5000   39 2^60*31

62:  21.2500    9 2^60*5*17

63:   2.2500    7 2^61*3^2

64:   3.7500   49 2^62*3*5

65:   3.7500   13 2^63*3*5

66:   2.2500    1 2^64*3^2

67:  12.2500   57 2^65*7^2

68:   5.2500    5 2^66*3*7

69:  12.3750    1 2^66*3^2*11

70:  23.4375   41 2^66*3*5^3

71:  14.0625   31 2^67*3^2*5^2

72:  27.7500   11 2^70*3*37

73:  21.9375    5 2^69*3^3*13

74:  48.1250   39 2^71*5*7*11

75:  13.1250   13 2^72*3*5*7

76:  19.1250   11 2^73*3^2*17

77:   1.0000   15 2^77

78:  17.2500   31 2^76*3*23

79:   8.4375   23 2^75*3^3*5

80:  35.1562   53 2^75*3^2*5^3

81:   5.6250  109 2^78*3^2*5

82:   9.7500  121 2^80*3*13

83:   5.2500   17 2^81*3*7

84:   5.2500    5 2^82*3*7

85:  13.1250   59 2^82*3*5*7

86:  12.6562    1 2^81*3^4*5

87:   5.6250   53 2^84*3^2*5

88:  20.6250    1 2^85*3*5*11

89:   3.3750   55 2^86*3^3

90:  14.0625   11 2^86*3^2*5^2

91:  12.2500   27 2^89*7^2

92:  11.8125  131 2^88*3^3*7

93:  12.7500   35 2^91*3*17

94:   5.6250   47 2^91*3^2*5

95:  21.3750    5 2^92*3^2*19

96:  14.5000   45 2^95*29

97:  19.2500  129 2^95*7*11

98:  12.7500    5 2^96*3*17

99:  13.1250   11 2^96*3*5*7

100: 35.5000   57 2^99*71

 

Note C=3 is the only solution where P is Mersenne and Q is Fermat.

I redid the experiment, now reserving more factors k>5, depending on F. (*)
In this case S had to adjusted downwards only in 4 cases marked red above,
so the table above is correct, but should be changed for the following 4 values:

 

34:  11.3906   11 2^28*3^6

35:  11.3906    7 2^29*3^6

73:  17.0859  115 2^66*3^7

85:  11.3906    7 2^79*3^6

 

(*)

For instance with a bound 10 and just reserving 1 factor would give the products 2,3,5,7,9,11,13,17,19 (the bound for the product is 2*10=20). Introducing an extra factor 2 (multiply by 2) we would get the products 4,6,10,14,18,22,26,34,38 from these. However we’re missing out on a few here: the products 9,15,21,25,33,35,39 (the bound for the product is now 4*10=40). If upon using 1 factor we found 19 we’re done (19>the one’s we didn’t consider), but if we found 5, we should also test 9, since 9<10.

 

 

If we write 2^C*F=2^(C-k)*2^k*F and solve 2^k*F=3^k we get an upperbound on the number of factors k we have to reserve for other primes. With F=13.125 (C=85) we get k=trunc(ln(F)/ln(1.5))=6.
This also means that if we choose a bound equal to 250 we actually had to choose k=13 to be absolutely sure we get a minimum value for S in one go. However as we saw this bound 250 was way too high.
In fact the first failure with B=250 and k=5 occurs for C=428. Where either the bound should be increased, or k:

 

428: 351.8438  197 2^423*3^4*139 (B>351, k=5)

428: 205.0781  137 2^422*3*5^4*7 (B>205, k=6)

***

Fred wrote:

1) After fiddling with my C++ program, I was able to generate these in about a second.

For 31 factors, min solution: 16106127360 = 8053063661 + 8053063699 = 2^30 * 3 * 5

For 32 factors, min solution: 16106127360 = 8053063661 + 8053063699 = 2^30 * 3 * 5

For 33 factors, min solution: 28991029248 = 14495514619 + 14495514629 = 2^30 * 3^3

For 34 factors, min solution: 195689447424 = 97844723701 + 97844723723 = 2^28 * 3^6

For 35 factors, min solution: 386547056640 = 193273528303 + 193273528337 = 2^33 * 3^2 * 5

For 36 factors, min solution: 386547056640 = 193273528303 + 193273528337 = 2^33 * 3^2 * 5

For 37 factors, min solution: 893353197568 = 446676598751 + 446676598817 = 2^36 * 13

For 38 factors, min solution: 1030792151040 = 515396075501 + 515396075539 = 2^36 * 3 * 5

For 39 factors, min solution: 1855425871872 = 927712935923 + 927712935949 = 2^36 * 3^3

For 40 factors, min solution: 23089744183296 = 11544872091637 + 11544872091659 = 2^40 * 3 * 7

For 41 factors, min solution: 23089744183296 = 11544872091637 + 11544872091659 = 2^40 * 3 * 7

For 42 factors, min solution: 23089744183296 = 11544872091637 + 11544872091659 = 2^40 * 3 * 7

For 43 factors, min solution: 85761906966528 = 42880953483257 + 42880953483271 = 2^41 * 3 * 13

For 44 factors, min solution: 153931627888640 = 76965813944311 + 76965813944329 = 2^42 * 5 * 7

For 45 factors, min solution: 158329674399744 = 79164837199871 + 79164837199873 = 2^44 * 3^2

For 46 factors, min solution: 158329674399744 = 79164837199871 + 79164837199873 = 2^44 * 3^2

For 47 factors, min solution: 1319413953331200 = 659706976665599 + 659706976665601 = 2^44 * 3 * 5^2

For 48 factors, min solution: 3166593487994880 = 1583296743997421 + 1583296743997459 = 2^46 * 3^2 * 5

For 49 factors, min solution: 3166593487994880 = 1583296743997421 + 1583296743997459 = 2^46 * 3^2 * 5

For 50 factors, min solution: 13792273858822144 = 6896136929411057 + 6896136929411087 = 2^48 * 7^2

For 51 factors, min solution: 46443371157258240 = 23221685578629107 + 23221685578629133 = 2^48 * 3 * 5 * 11

For 52 factors, min solution: 53198770598313984 = 26599385299156987 + 26599385299156997 = 2^48 * 3^3 * 7

For 53 factors, min solution: 58546795155816448 = 29273397577908179 + 29273397577908269 = 2^52 * 13

For 54 factors, min solution: 175640385467449344 = 87820192733724667 + 87820192733724677 = 2^52 * 3 * 13

For 55 factors, min solution: 202661983231672320 = 101330991615836137 + 101330991615836183 = 2^52 * 3^2 * 5

For 56 factors, min solution: 432345564227567616 = 216172782113783773 + 216172782113783843 = 2^57 * 3

For 57 factors, min solution: 432345564227567616 = 216172782113783773 + 216172782113783843 = 2^57 * 3

For 58 factors, min solution: 432345564227567616 = 216172782113783773 + 216172782113783843 = 2^57 * 3

For 59 factors, min solution: 6052837899185946624 = 3026418949592973301 + 3026418949592973323 = 2^58 * 3 * 7

 

For 60 factors, min solution: 6052837899185946624 = 3026418949592973301 + 3026418949592973323 = 2^58 * 3 * 7

 

2) DPF stands for distinct prime factors

Min solution for 1 DPF: 8 = 3 + 5 = 2^3

Min solution for 2 DPF: 12 = 5 + 7 = 2^2 * 3

Min solution for 3 DPF: 30 = 13 + 17 = 2 * 3 * 5

Min solution for 4 DPF: 210 = 103 + 107 = 2 * 3 * 5 * 7

Min solution for 5 DPF: 3570 = 1783 + 1787 = 2 * 3 * 5 * 7 * 17

Min solution for 6 DPF: 30030 = 15013 + 15017 = 2 * 3 * 5 * 7 * 11 * 13

Min solution for 7 DPF: 570570 = 285283 + 285287 = 2 * 3 * 5 * 7 * 11 * 13 * 19

Min solution for 8 DPF: 19399380 = 9699667 + 9699713 = 2^2 * 3 * 5 * 7 * 11 * 13 * 17 * 19

Min solution for 9 DPF: 281291010 = 140645501 + 140645509 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 29

Min solution for 10 DPF: 8254436190 = 4127218087 + 4127218103 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 37

Min solution for 11 DPF: 200560490130 = 100280245063 + 100280245067 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31

Min solution for 12 DPF: 11250796526970 = 5625398263453 + 5625398263517 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 37 * 47

Min solution for 13 DPF: 405332750552730 = 202666375276361 + 202666375276369 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 43 * 47

Min solution for 14 DPF: 23204648147550870 = 11602324073775431 + 11602324073775439 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 53 * 59

Min solution for 15 DPF: 876545009221892010 = 438272504610946003 + 438272504610946007 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 67

***

Hakan wrote:

Q2:

c p q s

1 2 3 5

2 5 7 12

3 13 17 30

4 103 107 210

5 1783 1787 3570

6 15013 15017 30030

7 285283 285287 570570

8 9699667 9699713 19399380

9 140645501 140645509 281291010

10 4127218087 4127218103 8254436190

 

***