Problems & Puzzles: Puzzles

Puzzle 322. Primeval primes as sum of primeval primes Patrick Capelle asks :"Is there a primeval prime which is sum of primeval primes ? Or prove there is no such prime" '...my question was inspired by the lecture of the web page of Mike Keith on the primeval numbers. Its address is : http://users.aol.com/s6sj7gt/primeval.htm ' The list of the integers that set a new record for the number of primes contained begins by : 2,13,37,107,113,137,1013,1037,1079,1237,1367,1379,10079,10123,10136,10139,10 237,10279,10367,10379,12379,13679,... Note that the smallest primeval number which is sum of primeval numbers is 10136, because 10136 = 10123 + 13. Among the primeval numbers, there are some which are primes. The list of the primeval primes begins by : 2,13,37,107,113,137,1013,1237,1367,10079,10139,12379,13679, ... The smallest prime number which is sum of primeval primes is 109, because 109 = 2 + 107, but 109 is not a primeval prime. Is there a primeval prime which is sum of primeval primes?

 

---

Giovanni Resta solved, the only, the question.

Giovanni wrote:

I assumed that you wanted solutions in which the primeval numbers are distinct, otherwise the problem is trivial.

For the moment I've generated the prime primevals smaller than 10^8.
In that range the solutions are the following:

12379 = 10079 + 1237 + 1013 + 37 + 13
13679 = 12379 + 1013 + 137 + 113 + 37
1012379 = 1001237 + 10079 + 1013 + 37 + 13
10123579 = 10123457 + 107 + 13 + 2

Regarding the much simpler case of a primeval equal to the sum of primevals, for which you reported the solution
10136 = 10123 + 13,
I want only to add that the 3 smallest solutions in this case are

1379 = 1079 + 137 + 113 + 37 + 13
10136 = 10123 + 13
10367 = 10123 + 137 + 107

I have extimated that my very simple little program will find all the primevals up to 10^9 in about 12 hours on my slow Athlon 1400.
So by tomorrow I think I'll be able to tell you if there are other solutions.
I can also provide a table with all the primevals (prime or not) up to 10^9.
...

I completed my search and up to 10^9 I did not find other solutions.
Indeed there is only one prime primeval in the range 10^8 - 10^9, i.e.
100234679

Below I report all the primeval up to 10^9 together with their prime count and the method I used to solve this problem.

N #P N #P
--------------------------------------
2 [1] 1012379 [1098]
13 [3] 1023457 [1162]
37 [4] 1023467 [1268]
107 [5] 1023479 [1662]
113 [7] 1234579 [1738]
137 [11] 1234679 [1953]
1013 [14] 10012349 [2418]
1037 [19] 10012379 [2920]
1079 [21] 10023457 [3133]
1237 [26] 10023467 [3457]
1367 [29] 10023479 [4483]
1379 [31] 10034579 [4517]
10079 [33] 10123457 [4917]
10123 [35] 10123469 [5174]
10136 [41] 10123579 [5953]
10139 [53] 10123679 [6552]
10237 [55] 10234567 [6799]
10279 [60] 10234579 [8938]
10367 [64] 10234679 [10219]
10379 [89] 12345679 [10542]
12379 [96] 100123379 [12515]
13679 [106] 100123457 [15346]
100279 [122] 100123469 [16632]
100379 [153] 100123579 [18686]
101237 [188] 100123679 [20661]
102347 [248] 100233479 [20734]
102379 [311] 100234567 [22157]
103679 [349] 100234579 [28837]
123479 [402] 100234679 [32608]
1001237 [421] 101234567 [34674]
1002347 [547] 101234579 [42797]
1002379 [705] 102334679 [46139]
1003679 [812] 102345679 [64905]
1012349 [906]

Primevals Primes (up to 10^9).
2 13, 37, 107, 113, 137, 1013, 1237, 1367, 10079, 10139, 12379, 13679, 100279, 100379, 123479, 1001237, 1002347, 1003679, 1012379, 1023467, 10034579, 10123457, 10123579, 100234679.

One possible way to compute primevals is to compute, for each number x, all the possible numbers which can be obtained with the digits of x and then checking which are prime. The "record setting" values of x are then primevals.

Of course, if our goal is to find all the primevals up to 10^9, there is no need to check all the numbers up to 10^9.

Indeed, a number like 713 cannot be a primeval, because there exist the number 137 which contains the same digits and it is smaller.

Thus we can concentrate ourself on the numbers whose digits are in non decreasing order, with the exceptions of those containing zeros:
in that case the zeros will start from 2nd position as in 3000357, to avoid leading zeroes.

In this way we can see that there are only 92368 primeval candidates up to 10^9.

I had no time to think to a clever approach, nor the time to implement the basic strategy reported above (since it require to be able to compute distint permutations/combinations of sets with repeated elements and so on).

So I implemented the folloging very stupid and simple algorithm with took about 12 hours of CPU time on an old Athlon 1400.

For each of the 92368 primeval candidates I prepared a record containing the candidate itself, a hit counter (to be explained later), and an array of 10 small integers (0..9) telling how many digits the candidate contains for each digit kind, that is, if the candidate is 10001668 then its "signature"
is {3,2,0,0,0,0,2,0,1,0} since it contains three 0, two 1, no 2,3,4,5, two 6, no 7, one 8, no 9.

Then I performed the following easy task for each of the
50,847,534 prime numbers below 10^9:
given the prime P I compute its signature, as above, so, if P=73, the signature is {0,0,0,1,0,0,0,1,0,0}.
Then I compare the signature of P with that of each of the
92368 primevals candidates. If term by term the signature of P is not greater than that of the candidate, then this means that P can be constructed with the digits of the candidate.
Thus I increase the hit count for that candidate.

At the end of this process, the hit count of each candidate tells me how many primes can be built with its digits.

Once obtained the prime primevals (with are quite scarce) it was very simple to device a trivial recursive program to test which numbers could be decomposed as a sum of other prime primevals.
 

***

---