Problems & Puzzles: Puzzles

Puzzle 605. Follow up to Puzzle 604 Emmanuel Vantieghem explicitly, and W. Edwin Clark by his results on Puzzle 604, suggested this follow up: Determine for every n the least k for which the concatenation of  1, 2, ..., n  could be split into k subsets S1, S2, ..., Sk, such that every Si is prime (zeros allowed at the left of the primes)

---

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

***

W. Edwin wrote:

below are my solutions for Puzzle 605: I only give the
partitions for n up to 47, thereafter (for odd n up to 101 plus n = 299 and n = 413) I give only minimum k.

I hope no one proves me wrong on the cases where there are no such partitions--indicated by "none".

n =   3: none
n =   5: none
n =   7: none
n =   9: none
n =  11 minimum k = 2: [1234567891, 11]
n =  13 minimum k = 3: [1234567891, 11, 1213]
n =  15 minimum k = 4: [1234567891, 11, 1213141, 5]
n =  17 minimum k = 2: [123456789101112131415161, 7]
n =  19: none
n =  21 minimum k = 3: [1234567891, 1112131, 415161718192021]
n =  23 minimum k = 5: [1234567891, 1112131, 415161718192021, 2, 223]
n =  25: none
n =  27: none
n =  29: none
n =  31 minimum k = 2: [123456789101112131415161, 71819202122232425262728293031]
n =  33 minimum k = 4: [1234567891, 11, 1213141, 5161718192021222324252627282930313233]
n =  35 minimum k = 4: [123456789101112131415161, 7181920212223242526272829303132333, 43, 5]
n =  37 minimum k = 5: [1234567891, 11, 1213141, 5161718192021222324252627282930313233, 34353637]
n =  39 minimum k = 6: [1234567891, 11, 1213, 141516171819202122232425262728293031323, 3343536373, 839]
n =  41 minimum k = 4: [1234567891, 11, 1213141, 51617181920212223242526272829303132333435363738394041]
n =  43 minimum k = 3: [1234567891, 111213141516171819202122232425262728293031323334353637383, 940414243]
n =  45: none
n =  47 minimum k = 4: [1234567891, 11, 1213, 14151617181920212223242526272829303132333435363738394041424344454647]
n =  49: none
n = 51 minimum k = 4:
n = 53 minimum k = 4:
n =  55: none
n = 57 minimum k = 6:
n = 59 minimum k = 6:
n = 61 minimum k = 3:
n = 63 minimum k = 4:
n =  65: none
n = 67 minimum k = 5:
n = 69 minimum k = 6:
n = 71 minimum k = 8:
n = 73 minimum k = 5:
n = 75 minimum k = 5:
n = 77 minimum k = 4:
n = 79 minimum k = 5:
n = 81 minimum k = 3:
n = 83 minimum k = 4:
n =  85: none
n =  87: none
n =  89: none
n =  91: none
n = 93 minimum k = 5:
n = 95 minimum k = 7:
n = 97 minimum k = 4:
n = 99 minimum k = 7:
n =101 minimum k = 7:
n =299 minimum k = 8:
n =413 minimum k = 7:

***

Claudio wrote:

Here is what I found:

k=2 n=11, 17, 31, 119, 123

K=3 n=13, 21, 43, 61, 81

K=4 n=15, 17, 21, 33, 35, 41, 47, 51, 53, 61, 77, 81, 83, 97 

K=5 n=15, 23, 33, 35, 37, 43, 61, 63, 67, 73, 75 ,79, 81, 83, 93    

***

Emmanuel wrote:

Here is a resume of what I could find about puzzle 605.

________________________________ 

 

Let us denote by  k(n)  the smallest number of subsets  Si  such that   Si  is prime and S1&S2&...&Sk(n)  is the concatenation of  1, 2, 3, ..., n.

I computed  k(n)  for  1 <= n <= 601.

k(n) = 0  when  n == 0, 4, 6, 8 (mod 10)  and  n == 42, 62, 82, 45, 65, 85 (mod 100).

Also, k(n) = 0  for  n = 1, 2, 3, 5, 7, 9, 19, 25, 27, 29, 49, 55, 87, 89, 91, 205,

                            225, 255, 387, 402, 405, 422, 425, 447, 449, 452, 455,

                            467, 505, 525, 555, 567  (all together 308 values).

k(n)  is never  1  (this holds even for  n <= 10000).

k(n) = 2, for  n = 11, 12, 17, 31, 119, 123, 309  (7 values)

k(n) = 3, for  n = 13, 21, 43, 61, 81, 121, 153, 199, 221, 343, 421, 423  (12 values)

k(n) = 4, for  n = 15, 32, 33, 35, 41, 47, 51, 53, 63, 77, 83, 97, 113, 117,

                            131, 132, 137, 141, 147, 179, 193, 197, 201, 209, 219,

                            269, 273, 311, 313, 315, 317, 329, 333, 339, 392, 393,

                            411, 473, 483, 597, 601 (41 values)

k(n) = 5, for  n = 22, 23, 37, 67, 73, 75, 79, 92, 93, 103, 109, 111, 133,

                            139, 151, 155, 157, 169, 171, 181, 183, 189, 203, 207,

                            211, 215, 217, 223, 229, 235, 237, 247, 259, 267, 271,

                            277, 295, 301, 307, 319, 331, 337, 349, 351, 357, 367,

                            369, 373, 397, 403, 409, 437, 441, 451, 463, 499, 503,

                            513, 519, 529, 543, 569, 599 (63 values)

k(n) = 6, for  n = 39, 52, 57, 59, 69, 105, 107, 112, 115, 122, 125, 129,

                            135, 143, 149, 152, 161, 163, 167, 172, 173, 177, 187,

                            191, 195, 202, 213, 222, 227, 233, 239, 241, 249, 251,

                            261, 263, 275, 279, 281, 289, 293, 297, 312, 321, 322,

                            323, 325, 327, 341, 363, 371, 372, 377, 379, 381, 383,

                            389, 391, 395, 401, 407, 412, 415, 417, 419, 432, 433,

                            435, 439, 443, 453, 459, 461, 472, 479, 487, 489, 491,

                            492, 501, 507, 517, 531, 533, 537, 547, 563, 579, 583,

                            592, 593, 595 (92 values)

k(n) = 7, for  n = 95, 99, 101, 102, 127, 159, 192, 212, 231, 232, 243,

                            253, 292, 302, 303, 332, 335, 347, 353, 355, 359, 361,

                            375, 413, 427, 457, 469, 471, 477, 481, 511, 521, 523,

                            527, 532, 535, 541, 549, 551, 553, 559, 571, 573, 575,

                            577 (41 values)

k(n) = 8, for  n = 71, 72, 175, 257, 272, 283, 287, 291, 299, 305, 352,

                            399, 429, 431, 475, 493, 495, 497, 502, 509, 512, 515,

                            539, 561, 572 (25 values)

k(n) = 9, for  n = 252, 581

k(n) = 10 for  n = 522, 552, 589, 591

k(n) was never 11 or 12.

k(n) = 13 for  n = 557, 587

It is highly possible that  k(n)  takes on arbitrary large values.  This happens when  n  is a number of  j  digits, all 2 or 5 and ending with 2  and  k(n-1)  not zero. We then have :  k(n) = k(n-1)+j.

It should be remarked that the proof of the primality of the  Si  may be very time consuming. Actually, I did it rigorously for all  n < =205.  I need much more time for the other values.

***

Jan wrote:

Carlos,

 

I found a routine which computes all minima in a range 1..n. If properly programmed it takes (about) the same time as calculating the minimum for n itself.
However the order of the routine is about 1/2*cat(1,n)^2. With cat(i,j) equal to the concatenated number of the numbers i..j. Since the time needed to decide whether a concatenated number is prime is costly,
the routine computes each possible cat(i,j) once, so i<=j, and stores the found primes in a list and remembers cat(i,n) in a seperate list.
...

 

The next step tests whether found primes are connected, starting from n downwards, without destroying the original list. The final step computes the minimum value, by computing the minimum path length starting from n downwards. Both these steps take a very small amount of time compared to scanning for primes. All routines don’t use recursion, to make sure there is no heap overflow.

 

Values of n for which the minimum value for k is quite low 309, k=2 (809 digits) and 647, k=3 (1833 digits) or 753, k=4 (2151 digits). And what to think about 629 (1779 digits) which has minimum 0?

...

My routine allows zeroes in front. However if the solution for a certain n doesn’t use a 0 it is reported. [So it is also the minimal solution in that case]. Look for instance at 71, the first situation where not using a 0 in front would increase the minimum. The minima for the numbers n reported by W.Edwin Clark are the same (however the minimal solution is not always the same, the reason is that the multiple solutions might exist with the same minimum k).

 

I also checked against Emmanuel. [I did test for certain even values of n as well, but I lost that text file, so I can only check the odd n]. An small sample shows <I only checked large k> that the results are the same. Checking all would take more time, given the form of his table.

***