|
Problems & Puzzles: Puzzles
Important note: Paul Cleary sent his solutions to puzzle 1227 a little bit later (Saturday 5, 2025, 3:06 am). This is why I couldn't publish these result together with the rest; I usually post new results between 4-5 pm on each friday...The worst of this is that he already got two examples with seven distinct primes...!!! improving twice the example given above, gotten by Branicky & Cavegn... 1732317511 {17,3,2,31,7,5,11} 1732317510 -- 2 * 3 * 5 * 7 * 11 * 17 * 31 * 14232547377911 {2,5,47,3,7,79,11} 2547377910 -- 2 * 3^4 * 5 * 7 * 11^2 * 47 * 79 Later Paul wrote this:
"Thanks
for your patience. It’s been a hectic weekend, and I apologize for the slow
reply. According with this all the submissions from Mr. Cleary to this puzzle and he previous one, Puzzle 1227, must be forgotten. *** From 5-11 July, 2025. contributions came from Michael Branicky, Paul Rebert, Simon Cavegn, Oscar Volpatti, *** Michael wrote:
Here is a solution with 7 distinct primes:
233118097213 = (23)(3)(11)(809)(7)(2)(13)-> 233118097212 = 2^2 x 3 x 7^2
x 11 x 13 x 23 x 149 x 809
Solution for 9 distinct primes: 79713347223511 = 79.7.13.3.47.2.23.5.11 -> 79713347223510 = 2 x 3^2 x 5 x 7 x 11 x 13^2 x 23 x 47 x 79 x 797 *** Paul wrote: Q. Send your largest example with the most distinct primes you can find (more that 6)?
I found:
primes d d-1 =
factorization
[5, 3, 13, 19, 2, 31] 531319231 531319230 = 2 * 3^3 * 5 * 13 * 19 *
31 * 257;
[7, 3, 2, 13, 41, 31] 732134131 732134130 = 2 * 3 * 5 * 7 * 13 * 31
* 41 * 211;
[2, 3, 19, 103, 7, 11] 2319103711 2319103710 = 2 * 3^4 * 5 * 7 * 11
* 19^2 * 103;
[7, 73, 2, 13, 3, 137] 7732133137 7732133136 = 2^4 * 3^2 * 7 * 13 *
59 * 73 * 137;
[113, 29, 5, 7, 2, 11] 1132957211 1132957210 = 2 * 5 * 7 * 11 * 29
* 113 * 449;
[379, 17, 31, 2, 7, 3] 3791731273 3791731272 = 2^3 * 3 * 7 * 17 *
31 * 113 * 379;
[2, 3, 79, 43, 1367, 7], 23794313677, 23794313676 = 2^2 * 3 * 7 * 43
* 61 * 79 * 1367;
[3, 2, 13, 37, 83, 163], 32133783163, 32133783162 = 2 * 3 * 13 * 37
* 83 * 163 * 823;
[2, 7, 97, 431, 79, 11], 27974317911, 27974317910 = 2 * 5 * 7 * 11^2
* 79 * 97 * 431;
[5, 7, 11, 353, 2, 631], 57113532631, 57113532630 = 2 * 3^2 * 5 * 7
* 11 * 37 * 353 * 631;
[7, 3, 83, 1231, 5, 31], 73831231531, 73831231530 = 2 * 3^2 * 5 * 7
* 31 * 37 * 83 * 1231;
[5, 2, 139, 37, 3, 991], 52139373991, 52139373990 = 2 * 3 * 5 * 11 *
31 * 37 * 139 * 991;
[2, 3, 13, 5, 39619, 31], 231353961931, 231353961930 = 2 * 3^2 * 5 *
7 * 13 * 23 * 31 * 39619;
[2, 3, 79, 43, 1367, 61], 237943136761, 237943136760 = 2^3 * 3 * 5 *
7 * 43 * 61 * 79 * 1367;
[2, 3, 97, 1279, 17, 19], 239712791719, 239712791718 = 2 * 3 * 17 *
19 * 97 * 997 * 1279;
[2, 3, 97, 1279, 17, 19], 239712791719, 239712791718 = 2 * 3 * 17 *
19 * 97 * 997 * 1279;
[2, 5, 47, 3, 7, 79, 11] 2547377911 2547377910 = 2 * 3^4 * 5 * 7
* 11^2 * 47 * 79;
[17, 3, 2, 3, 18, 5, 11] 1732317511 1732317510 = 2 * 3 * 5 * 7 *
11 * 17 * 31 * 1423;
[2, 5, 3, 7, 37, 353, 11] 25373735311 25373735310 = 2 * 3 * 5 * 7 *
11 * 29^2 * 37 * 353;
[2, 5, 37, 3, 7, 353, 11] 25373735311 25373735310 = 2 * 3 * 5 * 7 *
11 * 29^2 * 37 * 353;
[5, 2, 89, 193, 3, 7, 11] 52891933711 52891933710 = 2 * 3 * 5 * 7 *
11 * 31 * 43 * 89 * 193;
[7, 23, 5, 3, 337, 2, 11] 72353337211 72353337210 = 2 * 3^3 * 5 * 7
* 11 * 23 * 337 * 449;
[47, 3, 31, 41, 7, 2, 11] 47331417211 47331417210 = 2 * 3 * 5 * 7^4
* 11 * 31 * 41 * 47;
[61, 89, 5, 3, 23, 2, 31] 61895323231 61895323230 = 2 * 3 * 5 * 13
* 23 * 31 * 41 * 61 * 89;
[211, 5, 3, 7, 71, 2, 41] 21153771241 21153771240 = 2^3 * 3 * 5 * 7
* 41^2 * 71 * 211;
[3, 7, 5701, 2, 5, 89, 41], 375701258941, 375701258940 = 2^2 * 3 * 5
* 7 * 41 * 43 * 89 * 5701;
[2, 29, 3, 31, 67, 83, 43, 7],
2293316783437, 2293316783436 = 2^2 * 3 * 7 * 29 * 31 * 43 * 67 * 83
* 127;
*** Simon wrote: 11, 5, 2, 17, 7, 61, 31, 3, 19, 53, 11, 115217761313195311, 115217761313195310 = 2 * 3 * 5 * 7 * 11 * 17 * 19 * 31 * 53 * 61 * 947 * 1627
Yes
11 is repeated.
Reading the question as "the most primes, all distinct", then it will be
basically exactly the same as Puzzle 1227 Q2.
Therefore I did interpret it as "the most distinct primes", allowing
some non-distinct.
*** A little bit later, Oscar Volpatti sent the folllowing contributions:
As a first step, I performed an exaustive search up to p < 10^13:
generate every prime p in ascending order, try to cut p in every
permitted way.
Numbers with d digits can be cut in 2^(d-1) ways, but most cuts can be
discarded:
every new piece must have non-zero leading digit and represent an unused
prime which divides p-1.
The search provided four solutions with seven primes each:
23.3.11.809.7.2.13
293.439.73.3.5.2.11
31.2.5.16217.7.3.41
3.701.43.89.2.37.11
In order to find larger solutions, I used the following trick.
Let solution p be the concatenation of np distinct primes, with product
qp, using dp digits.
Split p into two blocks x and y, with x > y.
Let x be the concatenation of last nx primes, with product qx, using
last dx digits of p.
Let y be the concatenation of remaining ny primes, with product qy,
using first dy digits of p.
Such decomposition is possible for every solution p; in the worst case,
choose nx = np-1 and ny = 1.
Then:
dp = dx+dy;
np = nx+ny;
qp = qx*qy;
p = y*10^dx + x;
p-1 = qp*t;
y*10^dx + (x-1) = qx*qy*t.
But qx and qy are coprime (no repeated prime), so last equation is
equivalent to the following system of congruence relations:
y*10^dx + (x-1) == 0 mod qx,
y*10^dx + (x-1) == 0 mod qy.
Given x, the congruence relation modulo qx allows to recover y among few
candidates (often uniquely).
As an example, consider the following solution:
p = 19.2.7.3.43.5.191.151
Pick x = 5.191.151, so dx = 7 and qx = 144205.
Solve congruence equation mod qx:
y = 23837 + 28841*k, with 0 <= k <= 179.
We obtain desired value y = 1927343 for k=66.
Search algorithm.
Consider every integer x in ascending order, try to cut x in every
permitted way
(every new piece must have non-zero leading digit and represent an
unused prime).
Solve congruence equation modulo qx.
For each candidate y, try to cut y in every permitted way and check if
congruence modulo qy holds too.
Best solutions found so far.
5.13.11.3.2.29.7.8863.367.421 (np=10, dp=20)
3.7.3023.13.2.149.97.43.5.151 (np=10, dp=20)
2.433.36947.3.19.7.937.11903 (np=8, dp=21)
3.337.19.283.2.14559403.487 (np=7, dp=21)
35809.2.19.71.1801.65063.47 (np=7, dp=21)
3.19.83.2.11.7.13.15151423543 (np=8, dp=22)
Some primes have more than one permitted decomposition.
797.13.3.47.2.23.5.11
79.7.13.3.47.2.23.5.11
7.17.83.211.743.41.281.59
7.17.83.2.11.743.41.281.59
***
|
|||
|
|||
|
