Problems & Puzzles: Puzzles

Puzzle 190. A follow up for the puzzle 188

Maybe is worthwhile to read first the Puzzle 188.

Here you are asked to seek for these n values such that:

  • n is prime
  • n divides S where S is the concatenation of the first n natural numbers

Jeff Heleen, who proposed this follow up, has gotten the first 5 solutions: n = 2, 3, 5, 8167 & 371321.

BTW, S(371321) is a number having 2,116,821 decimal digits

Question: Find 3 more solutions.

Note: if n is not asked to be prime,  then the corresponding sequence is the EIS A029455, by Olivier Gerard.



Jens Kruse Andersen wrote (24/9/2002): " I have tested all primes below 20 million with an efficient C program using inline assembler. The program reached the biggest known solution 371321 in 3.5 minutes and then ran for several days. I only found the known solutions. This looks hard unless someone can find a clever shortcut".


Jeff Heleen wrote on Set 2014:

Using my original code to even reach what Mr. Andersen achieved would have taken 
forever. Therefore, I found a way to modify the approach to make it much faster. Using 
this approach over the last 2 months I was able to test all primes less than 100,000,000. 
No further solutions were found to that point. 

For the largest prime less than 100 million (99,999,989), S(99999989) has 788,888,809 decimal digits.


After much thought and playing with different ideas I found that trying
multiple primes 'at once' seemed to be the way forward. The major part 
of the process that consumes the most time is building each individual
number to use in the mod function. If fewer numbers needed to be built
progress would be faster.

Let me give you an example with small numbers.

Let's say we're testing these three numbers:

1234567891011121314151617 mod 17

12345678910111213141516171819 mod 19

1234567891011121314151617181920212223 mod 23

for divisibility by 17, 19 and 23. Doing each one separately is time
consuming. I noticed that if, beforehand, 17, 19 and 23 are multiplied
together to get 7429, then 1234...1617 mod 7429 is 1001.

1001 mod 17 == 15, so 17 is not a solution.

1001 mod 19 == 13, 131819 mod 19 == 16, so 19 is not a solution.

1001 mod 23 == 12, 12181920212223 mod 23 == 6, so 23 is not a solution.

And when 1234...1617 is mod by 17, 19, and 23 the standard way the
residues are indeed 15, 13 and 12. 

So in this way I was able to speed things up. My program used primes in
groups of 10, thus I only had to build one multi-million digit number
for every 10 primes, mod by the primes multiplied, then build the small
remainder of each of the numbers to test.








Records   |  Conjectures  |  Problems  |  Puzzles