An efficient method for parallelizing massive searches, and a look at the world of lucky palindromes

Lucky Palindromes

The original community post by Vitaliy Kaurov, Lucky Palindromes: when do prime factors of palindromes make palindromes?, asks to find palindromes with the property that their prime factors, when concatenated (as decimal digit strings) also form palindromes, restricted to listing the factors in either ascending or descending order. Such palindromes are called lucky palindromes.
Here is an example with the factors in ascending order:
111010642191246010111==787*233406919*604332787
if you omit the multiplication signs on the right, and read it as a digit string, it forms another palindrome.

Incremental Searches

There is an obvious search procedure:
◼
  • Generate all palindromes in a certain range
    • ◼
  • test each one for luckiness, using Select[]
    • Select[palindromes,luckyQ]
    And the obvious parallelization
    Parallelize[Select[palindromes,luckyQ]]
    This approach suffers from these inefficiencies:
    ◼
  • The data set is pre-generated, using up storage space
    • ◼
  • The computation is committed to a specific initial portion of a possibly infinite search space
    • ◼
  • No partial results are made available as they are found

    • An incremental approach

    We want to make two changes
    ◼
  • generate data in batches as they are needed
    • ◼
  • let the kernels run in a worker loop: ask for a piece of work, generate the data, find results, and communicate these immediately
    • In this way, the results are still available if we stop the computation at some point, and we can let the computation for as long as we want.

    Batches of Palindromes

    To easily control the batch size, we can look at sets of palindromes {n,init} with a given number of digits, and a given initial list of digits.
    In[]:=
    palindromes[{1,init_/;1<=init<=9}]:={init}​​palindromes[{n_Integer/;n>1,init_Integer?Positive}]/;IntegerLength[init]<=n/2:=​​With[{digs=IntegerDigits[init]},​​With[{sgid=Reverse[digs],mirrored=Tuples[Range[0,9],Floor[n/2]-Length[digs]]},​​If[EvenQ[n],​​FromDigits[Join[digs,#,Reverse[#],sgid]]&/@mirrored​​,​​Flatten@Table[FromDigits[Join[digs,#,{k},Reverse[#],sgid]]&/@mirrored,{k,0,9}]​​]​​]]
    In[]:=
    palindromes[{1,1}]
    Out[]=
    {1}
    In[]:=
    palindromes[{2,1}]
    Out[]=
    {11}
    In[]:=
    palindromes[{5,99}]
    Out[]=
    {99099,99199,99299,99399,99499,99599,99699,99799,99899,99999}
    In[]:=
    Length[palindromes[{12,11}]]
    Out[]=
    10000
    Now, we need to generate successive batch descriptions such that the corresponding batches comprise all palindromes
    If the second element in {n,init} is all nines, we increase n, and set init to 10000 (with the correct number of digits), otherwise we increment the second element. We use a mutable iterator to do this job. This constructors returns such an iterator as a symbol, that contains all the logic for advancing it step by step:
    In[]:=
    setup[mink_?Positive,maxl_]:=​​Module{currentk,currentl,maxinit,init,next},​​(*forceinitbelow*)​​currentk=mink-1;​​maxinit=-1;​​init=0;​​next[]:=Which​​init<maxinit,​​ {currentk,++init},​​True,​​ currentk++;​​ currentl=Max[1,Ceiling[currentk/2-maxl]];​​ maxinit=10^currentl-1;​​ init=10^(currentl-1);​​ {currentk,init}​​;​​next​​
    Every time we call the iterator as parameter-less function, we get the next batch:
    next=setup[1,2];
    In[]:=
    Table[next[],20]
    Out[]=
    {{1,4},{1,5},{1,6},{1,7},{1,8},{1,9},{2,1},{2,2},{2,3},{2,4},{2,5},{2,6},{2,7},{2,8},{2,9},{3,1},{3,2},{3,3},{3,4},{3,5}}
    In[]:=
    Do[next[],1000]
    In[]:=
    next[]
    Out[]=
    {9,990}
    And we can use the iterator values as arguments of palindromes:
    In[]:=
    next=setup[1,2];
    In[]:=
    palindromes[next[]]
    Out[]=
    {1}
    In[]:=
    Flatten[Table[palindromes[next[]],20]]
    Out[]=
    {2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,303,313,323,333,343,353,363,373,383,393}

    Testing for Luckiness

    Given a palindrome, we need to factor it and then check whether the ascending or descending list of factors gives another palindrome, when concatenated (as base-10 digit strings). We return a list of the palindrome, and the ascending and descending factor lists, if they form a palindrome, {} otherwise.
    In[]:=
    palindromeListQ[factors_List]:=PalindromeQ[StringJoin[IntegerString/@factors]]
    In[]:=
    luckyTest[p_Integer]:=Module[{factors},​​factors=Sort@Flatten[Table[#1,#2]&@@@FactorInteger[p]];​​If[Length[factors]===1,​​{p,{},{}},​​{p,​​If[palindromeListQ[factors],factors,{}]​​,​​If[palindromeListQ[Reverse@factors],Reverse@factors,{}]​​}​​]]
    A descending lucky palindrome:
    In[]:=
    luckyTest[414]
    Out[]=
    {414,{},{23,3,3,2}}
    An ascending one:
    In[]:=
    luckyTest[10001]
    Out[]=
    {10001,{73,137},{}}
    And a doubly lucky palindrome:
    And one with five factors:

    Finding lucky palindromes in a batch

    This loop obtains the next batch, generates the palindromes, tests each one, and appends all nontrivial results (and only those!) to a global association.
    The loop uses getWork[] to obtain the next batch of work, and sendResults[res] to record results as they are found.
    Setup the iterator, the callback functions getWork and sendResult, and initialize the result.
    Setup for monitoring progress, so we have something took look at while it is running. Abort the computation when desired.
    The variable results now contains the results found so far.

    Parallelizing the Search

    The idea is to run one worker loop in each kernel. To allow these loops the get new work and communicate results, we need to set up the getWork[] and sendResult[] functions as shared functions, so each call on one of the kernels is sent back to the master kernel, where the data resides. We also implement a stop button to gracefully stop the computation.
    Note that we implement a checkpoint feature by remembering the results found so far in persistent storage, as a local symbol, just in case the computer (or Mathematica) crashes.

    A sample run

    Initialize a new search with batches of size 10^4
    Launch kernels
    Setup the monitoring function.
    And start it.
    After stopping the computation, we can analyze the results.

    Analysis of Results

    We ran a search on a 64 core computer partly into length 21, running for about 2 days.
    The results are embedded in this notebook. This version excludes the one-digit palindromes 4,8, and 9.

    Noteworthy Features

    Prime Powers

    The original definition of the problem excluded palindromes that are powers of a single prime, but this is now considered a bit arbitrary, so we include them here. There are a number of squares (more on these later), and some higher powers, such as 7^3, 11^3, 101^3, 11^4, 101^4

    Repunit Primes

    For any repunit prime p, the following are doubly lucky palindromes:
    The first of these is the only lucky palindrome with 20 digits.
    It is not yet known wether there are infinitely many such repunit primes; they are currently the best source for long lucky palindromes.

    Carry-free Prime Pairs

    The majority of lucky primes derive from pairs of primes where one is the reverse of the other. Looking at the long multiplication layout, we can see that in this case the central column is equal to the sum of the squares of the digits. If this sum is less than 10, there will be no carries, and the result is a palindrome.
    The central digit, 6, is equal to the sum of the squares of the prime.
    This condition can be satisfied in one of three ways:
    ◼
  • There are at most 9 ones, and the rest of the digits are zeroes
    • ◼
  • There is 1 two, and up to 5 ones, and the rest of the digits are zeroes
    • ◼
  • the prime 3
    • Searching for such carry-free prime pairs is an interesting exercise in itself. Here are two examples I found:

    The Best of the Rest

    Everything else seems to be lucky just by sheer luck.
    ◼
  • Five factors
    • ◼
  • Doubly Lucky, with three palindromic factors
    • ◼
  • Holes
    • There are no lucky palindromes with 2, 6, 8, 10, 16 digits.
    The carry-free prime pairs construction always gives palindromes with an odd number of digits. The even ones are rather scarce.

    Conclusion

    This problem turned out to be interesting and a good example for applying techniques for efficient parallel searches. It has the right amount of complexity to find nontrivial results within a few days of searching.

    CITE THIS NOTEBOOK

    Lucky palindromes: efficient search and results​
    by Roman Maeder​
    Wolfram Community, STAFF PICKS, July 22, 2023
    ​https://community.wolfram.com/groups/-/m/t/2974426