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.

***

 Records   |  Conjectures  |  Problems  |  Puzzles