Problems & Puzzles:
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.
I started an exhaustive search but I obtained no other results
than 20.8G. So I tried another approach* and found the following
in about 18 CPU-hours. Add or subtract the second number to get the
previous and the next primes.
The smallest four (but not necessarily the smallest ever) are
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
by gap size, that is, if I programmed the algorithm correctly, these
all possible results for a prime gap up to 374=187*2. Unfortunately,
found no way to prove that the smallest numbers found with this
are actually the smallest ever, anyway some considerations may be
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
bunch of prime numbers in the middle...). This tells us that we are
to have found all possible results up to 370. Well, this is not
2) If Legendre's conjecture holds, we are sure to find a prime
between n^2 and (n+1)^2. It is easy to see that this brings the
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
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
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
of size 778 only to be sure that the second smallest solution is
actually the smallest ever.
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
that I didn't search for n >= 10^20. This prunes the tree quite a
so I got much further.
Using his format, here are the solutions I found < 10^20:
This list is complete (for n < 10^20) for sum-of-prime-factors up to
It's always possible that we'll find an outlier somewhere, but I
suspect we've found the four smallest. At this point, to prove it,
probably more efficient to find all of the gaps > 460 which are less
the 74584470673440 value, and check them individually. The algorithm
which Bernardo and I used gets bogged down checking thousands
of possibilities where n+sopfr(n) and n-sopfr(n) are both prime but
they are not consecutive primes.