Problems & Puzzles: Puzzles

Puzzle 604. Primes in 2&3&4&...&n Make a string S composed by the concatenation for natural integers from 2 to n (*)   Then make a full subdivision of S in k substrings S1, S2, ... Sk such that:   a) Every Si is prime (**) b) S=S1&S2&...Sk c) k=maximal Obviously the rightmost digit of n must be 1 or 3 or 7 or 9. Example: for n= 13 S=2345678910111213 S=2&3&4567&89&10111&2&13 k=7=maximal? Q. Find the maximal k for n=101, 299 & 413 (and show the k primes obtained) ____ * We do not start this concatenation in the integer "1" because of the Yves Gallot's result in Puzzle 8 about no prime has been found listing the natural numbers. ¿has this changed since 1998? ** Please notice that substrings need not to be composed of complete integers.

---

Contributions came from Claudio Meller, Jan van Delden, Emmanuel Vantieghem and W. Edwin Clark

***

Claudio Meller found "at hand" k=27 for n=101.

***

The best results came from JVD & EVare summarized in this table.

According to the original puzzle statement, zeros are allowed at the left of the primes. Results inside parentheses are for k values if no zero is allowed at the left of the prime numbers.

Puzzler	Max k for n=101	Max k for n=299	Max k for n=413
JVD	43 (41)	211(176)	353(303)
EV	43	207	327

***

EWC, JVD & EV All pointed out that:

The maximum for n=13  is not 7 but 8.  The substrings in this case are: 2, 3, 4567, 89, 101, 11, 2, 13.

***

I will  show the results from JVD where is zero is allowed before prime numbers:

101 194 Digits computed Length 43
[2,3,4567,89,101,11,2,131,41,51617181920212223242526272829303,13,2,3,3,3
,43,5,3637,3839404142434445464748495051525354555657,58596061,6263,
64656667,6869,7,07,17,2,7,3,7,47,5,7,67,7,7,8798081,828384858687888990919,
2,93949,5,96979,899100101]

299 788 Digits computed Length 211
[2,3,4567,89,101,11,2,131,41,51617181920212223242526272829303,13,2,3,3,3
,43,5,3637,3839404142434445464748495051525354555657,58596061,6263,
64656667,6869,7,07,17,2,7,3,7,47,5,7,67,7,7,8798081,828384858687888990919,
2,93949,5,96979,8991001,011,02,1031,041,05,1061,07,1081091101,11,11,2,11,3,
11,41,1511,61,17,1181,19,1201,2,11,2,2,1231,2,41,251,2,61,2,71,281,29,13,013,
11,3,2,13,3,13,41,3,5,13,61,3,7,13,81391401411421,431,44145146147,1481,491,
5,01511,5,2,1531,5,41,5,5,156157,15815916016116216316416516616716816917017,
11,7,2,17,3,17,41,7,5,17,61,7,7,17,8179,1801,811,821,83,1841851861,87188189190191,
19,2,19,3,19,419,5,19,619,7198199,2,002,0120220320420520620720820921021121,2,
2,1321,421,5,2,1621,7,218219220221,2,2,2,2,2,3,2,2,4225226227228229,2,3,02,31,
2,3,2,2,3,3,2,3423523,623723,8239240241242243244245246247248249,2,5,0251,2,
5,2253254255256257258259260261262263264265266267,2,68269270271,2,7,2,2,7,
3,27427,5,2,7,6277,2,7,8279280281,2,8228328428528628728828929,029129,2,29,
3,29429,5,2,9629,7,2,98299]

413 1130 Digits computed Length 353
[2,3,4567,89,101,11,2,131,41,51617181920212223242526272829303,13,2,3,
3,3,43,5,3637,3839404142434445464748495051525354555657,58596061,
6263,64656667,6869,7,07,17,2,7,3,7,47,5,7,67,7,7,8798081,828384858687888990919,
2,93949,5,96979,8991001,011,02,1031,041,05,1061,07,1081091101,11,11,2,11,3,
11,41,1511,61,17,1181,19,1201,2,11,2,2,1231,2,41,251,2,61,2,71,281,29,13,013,
11,3,2,13,3,13,41,3,5,13,61,3,7,13,81391401411421,431,44145146147,1481,491,5,
01511,5,2,1531,5,41,5,5,156157,15815916016116216316416516616716816917017,
11,7,2,17,3,17,41,7,5,17,61,7,7,17,8179,1801,811,821,83,1841851861,87188189190191,
19,2,19,3,19,419,5,19,619,7198199,2,002,0120220320420520620720820921021121,2,2,
1321,421,5,2,1621,7,218219220221,2,2,2,2,2,3,2,2,4225226227228229,2,3,02,31,2,
3,2,2,3,3,2,3423523,623723,8239240241242243244245246247248249,2,5,0251,2,5,
2253254255256257258259260261262263264265266267,2,68269270271,2,7,2,2,7,
3,27427,5,2,7,6277,2,7,8279280281,2,8228328428528628728828929,029129,2,29,
3,29429,5,2,9629,7,2,98299,3,003,013,02,3,03,3,043,05,3,063073,083,093103,11,
31,2,3,13,31,431,5,3,163,17,31,83,19,3,2,03,2,13,2,2,3,2,3,3,2,43,2,5,3,263,2,7,
3,2,83,29,3,3,03,3,13,3,2,3,3,3,3,3,43,3,5,3,3,6337,3,3,83,393403,41,342343,3,
443,45346347348349,3,5,03,5,13,5,2,3,5,3,3,5,43,5,5,3,563,5,7,3,5,83,5,9360361,
3,623633,643,653,663673683693703,7,13,7,2,3,7,3,3,7,43,7,5,3,7,63773,7,83,79,
3,803813,823,83384385386387388389,3,903913,9239,3,3,9439,5,3,963973,
98399400401402403404405406407408409410411,41,2,41,3]

***

EV added:

Also, I think that it is not necessary to start with  2.  Here are some examples where the main string starts with  1 :

1&2&...&17 -> 1234567891, 011, 1213, 14151617

1&2&...&101 ->  1234567891, 11, 1213, 141516171819202122232425262728293031323, 3, 3, 43, 5, 3, 6373, 8394041, 4243444546474849505152535455565758596061626364656667686970717273, 7, 47, 5, 7, 67, 7, 7, 8798081, 828384858687888990919, 2, 93949, 5, 96979, 899100101.

This is not a contradiction to Gallot's result of 1998 (which I extended to 10000).

***

WEC wrote:

I was able to convert the problem into the graph theory problem of finding a path between two vertices. Maple easily finds the shortest path, but unfortunately doesn't have a procedure to find a longest path.

So I get solutions with the MINIMUM value of k. The problem of finding the maximum length path is harder and I don't have time to write such a program just now.

For n=101, kmin=8
For n=299, kmin=9
For n=413, kmin=9

Anyhow, I hope you will find these results of interest, even though they are the worst possible solutions if you are seeking maximum k.

***