Problems & Puzzles: Puzzles

Puzzle 163. P+SOD(P)

Enoch Haga sent the following puzzle:

Let's start with a prime P, then let's add to P the sum of the digits of P. The new number may be, or not, another prime number. If not, then repeat the procedure until you get a prime number.

Example:

Starting with P=2, the sequence generated is:

2, 4, 8, 16, 23 (prime & bingo!), Large of the sequence, L = 5

Questions:

a) Can L take any value?
b) Find the earliest primes corresponding to L=100, 200, 300, .. 1000

The Enoch's puzzle let me think in some other similar questions: what about if we use the same procedure to generate the members of the same sequences but now we add the condition that all the members must be prime numbers ending when a composite number follows?

Example: P=277, L=4: 277, 293, 307, 317 (all are prime numbers)

Here are the earlier sequences of L members of this type, that I have obtained:

c) Can L take any value?
d) Find the earliest prime for L=9, 10, 11, 12 & 13

Last, what if we ask additionally that all the primes in the sequence need to be consecutive primes.

Example: P=11, L=3: 11, 13, 17

For this case, the largest sequence that I have found is: P=1427411, L=4

e) Find the earliest prime for L=5, 6 &7

Solution:

Sudipta Das found, for the question b) that "the earliest prime P for L = 100 is 954977". This same value was also found independently by Jean-Christophe Colin.

***

Sudipta Das found, for the question b) that "the earliest prime P for L = 200 is 1306002569"

***

Felice Russo made a statistical analysis for the question c) Can L take any value? and found an interesting result: "The experimental data seem to support that L cannot take any value and that most likely the maximum value should be L=14"

If you want to read the Russo's complete analysis you may download it clicking here.

***

On 16/9/6 C. Rivera wrote:

Smallest solution to question e) for K=5:

317130731, 317130757, 317130791, 317130823, 317130851

***

Giovanni Resta wrote on March 2011:

for question (d) of Puzzle 163 I found that
the first sequence with L=9 is
56676324799, 56676324863, 56676324919, 56676324977, 56676325039,
56676325091, 56676325141, 56676325187, 56676325243.

Other sequences with L=9 start at
373169411809, 2121959132809, 10180781225809, 14328311692789,
17429111275789, 32594135422789, 34327062247789, 39262151325799.
But I did not find (yet!) a sequence with L=10.

For question (e) of Puzzle 163 I found that
the earliest sequences with L=6,7 are:

(L=6) 102342031273, 102342031301, 102342031321, 102342031343,
102342031369, 102342031403

and

(L=7) 63604045061911, 63604045061957, 63604045062013, 63604045062053,
63604045062097, 63604045062149, 63604045062199

There are several sequences with L=6. The first 10 start at
102342031273, 1012835563819, 1070302300183, 2350811300953,
3063433129909, 3104103122173, 3551303300933, 5262316326901,
5426670290957, 6104611400971

***

On Oct 6, 2025, Jaroslaw Wroblewski wrote:

My attention was turned to your Puzzle 163 by Marek Penszko's puzzle
blog which is part of Polish weekly "Polityka" website:
https://blog.polityka.pl/penszko/2025/10/05/p-sp/

After a very selective search I came with the solution

1367618706414097919365699429 (28 digits)
1367618706414097919365699571
1367618706414097919365699711
1367618706414097919365699847
1367618706414097919365699993
1367618706414097919365700141
1367618706414097919365700257
1367618706414097919365700381
1367618706414097919365700503
1367618706414097919365700621

where all 10 numbers are prime and we iterate adding to a number sum
of its decimal dogits. This proves that in your question c) we can
have L=10.

I have no idea how to search efficiently for the smallest solution of
this kind, so I will even not try L=10 in question d).

By "a very selective search" I mean that the search was very far from being exhaustive. Firstly I assumed special form of solutions, namely starting from N99429, where
N has sum of digits 109 and is not ended by 9. Secondly, I checked
only a tiny part of numbers of that form in a given range. Therefore I
expect that the solution I found is nowhere near the smallest one.

***