Problems & Puzzles: Puzzles

Puzzle 390. 493009335 Farideh Firoozbakht sent the following curio & puzzle: 493009335 is the smallest number n such that, if sum of its prime factors subtracted from it produces the previous prime and if added to the sum of its prime factors produces the next prime. She found a second case, but not the second largest necessarily. Question. What are the first four cases?

---

Contributions came from Bernardo Boncompagni & Farideh too.

***

Bernardo wrote:

I started an exhaustive search but I obtained no other results smaller
than 20.8G. So I tried another approach* and found the following results
in about 18 CPU-hours. Add or subtract the second number to get the
previous and the next primes.

493009335+/-74
74584470673440+/-107
29708664179040+/-131
22783170619755+/-134
392639817827808000+/-137
57778369263965306880+/-149
4231766601562500+/-151
3005042747034746880+/-157
2422025079345703125+/-158
4565429327600289843750+/-161
793909226880000000+/-163
196297776675000000000+/-163
17770045462866210937500+/-167
5386817368758583296+/-167
2483105089119961743360+/-167
6019499255719683686400000+/-167
125246087976593928960+/-169
121606461138443148000+/-173
4336704655360000+/-177
3376889528320000000+/-177
10830667148437500000+/-179
289653022575820800+/-179
942082620099149168640+/-179
20945838983085023035392000+/-181
2058498610053984752472+/-185
80513880157470703125000+/-187
419333676546595907174400+/-187

The smallest four (but not necessarily the smallest ever) are

493009335+/-74
22783170619755+/-134
29708664179040+/-131
74584470673440+/-107

This approach is based on the size of the prime gap in the middle of
which the number must be found, and indeed the previous list is ordered
by gap size, that is, if I programmed the algorithm correctly, these are
all possible results for a prime gap up to 374=187*2. Unfortunately, I
found no way to prove that the smallest numbers found with this approach
are actually the smallest ever, anyway some considerations may be done:
1) for a gap size of n, the smallest possible candidate is n-4 (for
example, if you take a gap size of 18=2*9, the smallest possible
candidate is 14=2*7 - Hey! 14-9=5 and 14+9=23! Too bad there's another
bunch of prime numbers in the middle...). This tells us that we are sure
to have found all possible results up to 370. Well, this is not much...
2) If Legendre's conjecture holds, we are sure to find a prime number
between n^2 and (n+1)^2. It is easy to see that this brings the smallest
possible candidate to (n^2)/4: in our case, 34969. Not much yet...
3) Luckily, we already know (see http://www.trnicely.net/gaps/gaplist.html#MainTable) that the first
occurrence of a 374-size gap is at 10726904659 (which actually holds a
382-size gap), so we are sure we won't find any more solutions below
10.7G, which is a much better value, but we already knew that anyway!
4) Consulting the webpage cited at point 3, if the above mentioned
values are actually the smallest ones, we would have to test up to a gap
of size 778 only to be sure that the second smallest solution is
actually the smallest ever.

***

Farideh wrote:

n=29708664179040 has the same property. So I have found only three numbers 493009335, 29708664179040 & 5288621846615767660 with the mentioned property. I don't know after 493009335 what are the next three terms.

***

So, the first four terms, are?...

***

Jack Brennen wrote (Feb. 2007):

I took Bernardo's list and went a bit further, but with the restriction
that I didn't search for n >= 10^20. This prunes the tree quite a bit
so I got much further.

Using his format, here are the solutions I found < 10^20:

493009335+/-74
74584470673440+/-107
29708664179040+/-131
22783170619755+/-134
392639817827808000+/-137
57778369263965306880+/-149
4231766601562500+/-151
3005042747034746880+/-157
2422025079345703125+/-158
793909226880000000+/-163
5386817368758583296+/-167
3376889528320000000+/-177
4336704655360000+/-177
289653022575820800+/-179
10830667148437500000+/-179
364377487500000000+/-193
19782863226089964+/-193
4769650187980177500+/-199
4675864537093750+/-207
73806786545611392000+/-209
5288621846615767660+/-219
1445468651627464800+/-221
2360775414449700864+/-223
7926122833920000000+/-223
28372570445354945040+/-223
32279229875759343750+/-223
3047571475298634375+/-226

This list is complete (for n < 10^20) for sum-of-prime-factors up to 230.

It's always possible that we'll find an outlier somewhere, but I really
suspect we've found the four smallest. At this point, to prove it, it's
probably more efficient to find all of the gaps > 460 which are less than
the 74584470673440 value, and check them individually. The algorithm
which Bernardo and I used gets bogged down checking thousands (millions?)
of possibilities where n+sopfr(n) and n-sopfr(n) are both prime but where
they are not consecutive primes.
 

***

On Nov 29, 2018 Paul Cleary wrote:

Here are a few more solutions to puzzle 390.

 

My approach was to start with the sum of prime factors, so for instance using the first solution we have 74, therefore no prime factor can be greater than this and so, find the integer partitions of 74 using only primes up to 73.  There are 6336 in total, multiply all of the partition elements, for example the 500th partition is {37,11,7,3,3,3,3,3,2,2}  whose product of elements is 2769228. and test for consecutive primes at n+- 74, using this method I was able to verify there was no solution with a +- difference below 74. The algorithm was able to find solutions with a sum of 2 to 100 in just over 16 seconds though it was beginning to slow down at this point.  So looking at a sopf above 230 we find the following. 

 

 

 

1700768573600003260416, +/- 233

6944299324784640000000, +/- 233

201274493117197500000000, +/- 233

1111024454777954331199200, +/- 233

4762611902812746548966400, +/- 233

8259885498046875000000000, +/- 233

10103450471357687808000000, +/- 233

87369279290590552819200000, +/- 233

96668027534724933385458360, +/- 233

117210369435301793484288000, +/- 233

198314164224000000000000000, +/- 233

433002009582900884208060000, +/- 233

1491718932269862912000000000, +/- 233

3183819259921544270315520000, +/- 233

4961093762155463067685910976, +/- 233

145745545201826783896063180800, +/- 233

 

942688910111132390109990912, +/- 235

 

at 233 there were 31366563 numbers to check for a +- prime or a total of 62733126 in total, this was about 2 hours. I don't think my pc would be able to go much past this not because its slow but because at each integer partition calculation it approaches 32 gb of memory used.

1061266828961574167625, +/- 236

 

a few more...

 

127114329057156367646720, +/- 237

834877919562136450000000, +/- 237

 

282827809247016745800, +/- 239

353744000916114332160, +/- 239

590375532683426660352, +/- 239

2877014077876207269000000, +/- 239

15884402327749467832320000, +/- 239

73029628682226562500000000, +/- 239

82270363175454706237440000, +/- 239

95767436943360000000000000, +/- 239

112753910584916285435412480, +/- 239

280399713795121368164062500, +/- 239

595708377609945600000000000, +/- 239

2176541458238089646550000000, +/- 239

11583818393849856000000000000, +/- 239

19384054498575698310943987500, +/- 239

24609788060188293457031250000, +/- 239

26288547704940158195674152960, +/- 239

484912789882390169347099852800, +/- 239

6459944260083541920000000000000, +/- 239

25730559162957203220241406250000, +/- 239

1448639583592974999949456441344000, +/- 239

...

32852299999805964288000, +/- 241

51304019877987895738368, +/- 241

199787554742747400000000, +/- 241

1450598279217146740961280, +/- 241

2884152758367496244428800, +/- 241

427793347492181211340800000, +/- 241

722795521264060198192939008, +/- 241

3957949849678478555523534198, +/- 241

17935032767367135519100108800, +/- 241

43171297312458748232017968750, +/- 241

53017303161621093750000000000, +/- 241

287136423010236141060468750000, +/- 241

2050147134702039859200000000000, +/- 241

2932539616315296000000000000000, +/- 241

454252239692643325936521764044800, +/- 241

 

12459985156227150948856905, +/- 242

 

***

 

---