|
Problems & Puzzles: Puzzles
From May 23 to May 29, 2026, contriburions came from Michael Branicky, Paul Cleary, Oscar Volpatti *** Michael wrote: I found a numbers with the same qualification: 13/18 (Qualification 72.22%)
Here are two of them.
1526281538351826251 1608474946494748061 1447691427241967441
1448892526252988441 1527482637362847251 1606072748472706061 1607273847483727061 1446490328230946441 1528683736373868251* 3052563076703652503 3216949892989496123 2895382854483934883** 2897785052505976883** 3054965274725694503 3212145496945412123 3214547694967454123 2892980656461892883** 3057367472747736503** ==
15150545392929354505151 15180649091719094608151 15150447393839374405151*
15160449293739294406151* 15160547292829274506151 15160645291919254606151
15170647191819174607151 15140445493939454404151 15170549192729194507151 30301090785858709010303 30361298183438189216303 30300894787678748810303** 30320898587478588812303** 30321094585658549012303 30321290583838509212303 30341294383638349214303 30280890987878908808303** 30341098385458389014303
* Integers that are Palindromes but not
Primes
** Integers are neither Primes nor Palindromes *** Paul wrote:
During the week I found a few 13 out of 18 pp's and sometimes 1 and 2
others that were just palindromes, the number of digits ranged from 19
to 21. My last attempt with digit length 23 produced a 14 out
of 18 solution (Qualification
77.77%), my program has another 24 hours or so to run so
I doubt I will meet your deadline if any better solutions appear. Here
is my 14 solution.
Magic sum = 111818481812121818481819
37789722330808322248778 38160917070507071906183 35867842410806424326858
35350947350705374905353 37272827270707272827273 39194707190709170749193 38677812130608121327688 36384737470907473748363 36755932210606223405768
and
Magic sum = 223636963624243636963641
75579444661616644497557 76321834141014143812367 71735684821612848653717
70701894701410749810707 74545654541414545654547 78389414381418341498387 77355624261216242655377 72769474941814947496727 73511864421212446811537
as a picture with colour.
(I responded to Paul that whenever his code finish I will add his last results.) *** Oscar wrote:
Problem 93 was very challenging!
I wasn't able to find a complete solution. My best solutions so far have qualification 15/18 = 83.33%. The smallest such solution was somehow unexpected: I assumed that my search algorithm would generate candidate squares with odd entries only, but I didn't explicitly forbid even entries. So, "base" magic square of this solution happens to contain three even non-palindrome composites, placed on main diagonal; the remaining 15 entries are palprimes. 36656777836768827765668 39354717172927171745393 37261838473637483816273 38362838464646483826383 37757 38253717181918171735283 36160838482628483806163 3885 73313555673537655531337 78709434345854343490787 74523676947274967632547 76725676929292967652767 75515555655555655551557 74305434381818343450347 76507434363836343470567 72321676965256967612327 77717555637573655571777 I found 154 more solutions with qualification 15/18, involving numbers with up to 35 digits. Two of them are remarkable because they are the most similar to Jaime Ayala's construction: in both cases, the 18 integers are odd palindromes, and 15 of them are also prime. Solution involving six Sophie Germain palprime pairs: 15163525171839293817152536151 17192545172705450727154529171 16164535170937073907153546161 17174545170925052907154547171 16173535171827272817153537161 15172525172729492727152527151 16182535172717471727153528161 30327050343678587634305072303 34385090345410901454309058343 32329070341874147814307092323 34349090341850105814309094343 32347070343654545634307074323 30345050345458985454305054303 32365070345434943454307056323 30309050341898189814305090303 34367090343630503634309076343 Solution involving seven Sophie Germain palprime pairs: 350529381637174636471736183925 350717373727390747093727373717 350638392547252525252745293836 701058763274349272943472367850 701434747454781494187454747434 701276785094505050505490587672
I implemented the clever search strategy described by Arina Bator.
The entries of every magic square can be arranged into three
arithmetic progressions with common difference r.
Corresponding elements from each sequence also form three more
arithmetic progressions with common difference d.
A "greedy" strategy allows to generate candidate solutions with
qualification at least 12/18.
Detect six Sophie Germain palprime pairs (x1a,y1a), (x2a,y2a),
(x3a,y3a), (x1b,y1b), (x2b,y2b), (x3b,y3b)
such that triplets (x1a,x2a,x3a) and (x1b,x2b,x3b) are both
arithmetic progressions with common difference r.
Choose integer x1c in order to form a three-term arithmetic progression
with x1a and x1b.
Generate arithmetic progression (x1c,x2c,x3c) with common difference r.
Fill "base" magic square Mx, generate "transformed" magic square My,
compute qualification.
But I added an explicit constraint: the 18 integers of a candidate solution must have the same (odd) number of digits. I'm not sure if such constraint is necessary or not, but it produces nicer solutions.
Implementation details.
Step 0: choose the desired number of digits 2*k+1 (odd, otherwise all palindromes are divisible by 11). Step 1: search for all Sophie Germain palprime pairs (x,y).
There are 4*10^k palindromes x ending with digit 1,3,7, or 9; but if x
starts with 7 or 9, then number y = 2*x+1 has one more digit than x, so
discard them.
In general, if y is also a palindrome with 2*k+1 digits, then the digits
of x and y must follow specific patterns:
digits of x: low, high, low, ... , high, low; digits of y: odd, even, odd, ... , even, odd; where "low" means "from 0 to 4" and "high" means "from 5 to 9". So there are only 2*5^k candidate pairs of palindromes (x,y); check them all and save the pairs whose members are both prime. This is the most time-consuming step. Step 2: among saved palprimes x, search for all triplets (x1,x2,x3) forming an arithmetic progression. The idea is to consider every possible pair (x1,x3) and check if the mean value x2=(x1+x3)/2 is also a saved palprime. But x2 will be a palindrome with the correct digit pattern only if every digit in x3 has the same parity of the corresponding digit in x1. Divide saved palprimes x in 2^k distinct buckets according to digit parity pattern, then consider only pairs (x1,x3) of palprimes from the same bucket. For every arithmetic progression (x1,x2,x3) found, save the common difference r=x2-x1=x3-x2, along with the starting term x1 of the progression. Step 3: compare saved pairs (r,x1) and search for repeated values of r. It suffices to sort saved pairs by increasing r and then by increasing x1. For each saved difference r, group together all corresponding starting terms x1 saved. If resulting group has only one element, discard r. Otherwise, consider every possible pair (x1a, x1b) of elements from the group.
Term x1c can be chosen in three ways, depending on which of x1a, x1b,
x1c will be the middle term of the resulting arithmetic progression.
x1c = (x1a+x1b)/2;
x1c = 2*x1a-x1b;
x1c = 2*x1b-x1a.
My laptop computed all Sophie Germain palprime pairs (x,y) with at most
39 digits in less than one day.
However, starting form 37 digits, it seems that available memory (2GB)
was not enough to store all necessary data for detecting arithmetic
progressions.
*** |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
