MC: Ping-Pong Cubes

[Valentin Albillo]

.
Hi, all:

As promised, I'm posting here my last say on the technical aspects of this interesting MC, structured in sections. Let's begin:

1. Definitions:

      PPN = Ping-Pong Number: any multi-digit integer whose consecutive digits always alternate between even and odd (J. Horn dixit).

      PPC = Ping-Pong Cube: a PPN which is the cube of another PPN (J. Horn dixit)

      APC = Alternating-Parity Cube: a PPN which is a cube but not necessarily of another PPN (V. Albillo dixit). Notice that all PPC are APC but not vice versa.

For example:

      1234567890   is a PPN, 6343169876 is not
      381078125    is a PPC because it's a cube and a PPN and its cube root (725) is a PPN too
      4767078987   is an APC because it's a cube and a PPN, but its cube root (1683) is not a PPN

Note: while large PPCs are extremely rare or even nonexistent, there seems to be no shortage of large APCs of every size. For instance here's a 40-digit APC which I generated during my original research:

      9872381896525256705012705418127254343816 = 21452305956706 ^3

2. The challenge:

      To find the 11th PPC (the first 10 are small integers which will be mostly ignored in what follows), if it exists.

3. My Original Research:

      As I posted earlier in this thread, I first created a small proof-of-concept HP-71B program to perform an exhaustive search but greatly enhanced with important conceptual improvements in order to enormously reduce the exponential running times. This 71B program ran correctly but due to the 71B's 12-digit native accuracy it couldn't go beyond 4-digit base PPNs (thus 12-digit cubes) so I did a straight, unoptimized port to a multiprecision programming environment.

      The resulting port, running on my POPS (Pretty Old Pretty Slow) system produced the second table I included in my earlier post, which reached up to 20-digit PPN (and their up to 60-digit cubes) in some 5 hours and provided evidence for the main conclusion then (always excluding the 10 small PPC):

      There are no PPNs up to 20-digit long which produce a PPC when cubed. So any further research must start with PPNs 21-digit long and up.

4. Improvements and further research:

      This straight, unoptimized port admitted substantial improvements which I then implemented. The result was an 11-line subprogram which ran 400%-500% faster than the unoptimized one, not another exponential reduction but enough to reach deeper. I then ran it (again in my POPS system, some 12 hours this time) for base PPNs up to 23-digit long and here are the new results to add to Table 2:

   # digits  #roots generated and checked
  -----------------------------------------
      21       1,879,816,080
      22       4,699,514,130
      23      11,748,682,690

without finding any new, 11th PPC up to 23-digit long despite checking almost 12 billion roots. The final conclusion can now be updated to:

            There are no PPNs up to 23-digit long which produce a PPC when cubed. Any further research must start with PPNs 24-digit long and up.
            This also means that no APC less than 70-digit long can be a PPC.

What does this negative result imply re the existence or not of an 11th PPC ? I've explored a couple of heuristics, as described in the following section.

5. Heuristics:

      The first heuristic I've considered is simply a very informal, probabilistic one. What's the probability of finding an additional PPC by exhaustive search ? (i.e., disregarding theoretical proofs or additional considerations). Well, let's consider for example integers up to 10-digit long. According to Table 2 the probability that a base number is a PPN is:

      21,972,645 / 9,999,999,990 = 0.0021972645

      Also, we'll see in a next post or MC that the number of APCs up to 10*3 = 30 digits long is 141 (i.e., there are 141 alternating cubes from 2 to 30 digits long), while there are 9,999,999,998 cubes (alternating or not) in that range so the probability of a cube being an APC is thus:

      141 / 9,999,999,998 = 0.0000000141

      Finally, assuming tentatively, on first approximation, that both facts are substantially independent of one another (i.e: that a number being a PPN and its cube being a PPC are independent events) as the empirical evidence seems to suggest, the probability of an up to 10-digit number being a PPN and its up to 30-digit cube simultaneously being an APC (and thus also a PPC) would be:

      0.0021972645 * 0.0000000141 = 3.09814E-11

which means the expected number of up to 10-digit PPNs which when cubed result in a PPC would be less than 0.31, i.e., less than one, so it's no great surprise when we actually don't find even one.

      This is just for possible PPNs up to 10-digit long. As the number of digits grows the probability gets exponentially smaller and the expected number of PPN/PPC tends to zero, which indicates that very likely there's no 11th PPC. This of course doesn't bar the possibility of finding one but the low and ever decreasing probability makes it unwarranted and unappealing to try and find it by conducting an even longer search.

      The second heuristic has to do with the concept of near-solutions. I'll explain: as it happens, my 11-line subprogram will report every perfect solution it finds but can also report the closest non-solutions it finds during the search, where the closeness is defined according to some criterium of "distance" to a theoretical perfect solution.

      There are several plausible criteria which will give slightly different results but the main conclusion is the same for all of them, so I've chosen to report (for a given number of digits) the cube (and its cube root, the base PPN) that has the longest continuous string of alternating digits starting from the right (the units digit). Of course, if the length of this longest string equals the length of the cube proper, then the cube is actually a PPC and is reported as a true perfect solution.

      The heuristic thus consist in examining the difference between the length of the cube and the length of its longest string of alternating digits starting from the right. If the difference is 0, we've found a perfect solution. If it's not, we report the difference to afterwards analyze the trend (i.e., whether differences tend to grow or shrink). This said, running the code in my POPS system I obtain these results, with the column legends being as follows:

         A:   # of dígits of N (which is guaranteed to be a PPN)
         B:   # of dígits of N^3 (which might be a PPC but usually isn't)
         C:   # of consecutive alternating digits of N^3 starting from the right
         D:   difference between C and B (D = C-B), our heuristic (if it's 0 then N and N^3 are a perfect solution)
         E:   % of C with respect to B (if it's 100%, then N and N^3 are a perfect solution)
         F:   N (which is guaranteed to be a PPN)
         G:   N^3 (the longest alternating string from the right is underlined)

   -------------------------------------------------------------------------------------------------------------------
    A  B  C  D  E   F          G
   -------------------------------------------------------------------------------------------------------------------
    3  9  9  0 100% 725 ^3= 381078125       (a perfect solution, the 10th PPC)
    4 12 11  1 91 % 7416 ^3= 407858167296       (a quasi-solution: only the first digit has the wrong parity)
    5 14 13  1 92 % 38981 ^3= 59232345230141        (ditto)
    6 18 16  2 88 % 769256 ^3= 455210925456329216
    7 19 17  2 89 % 1054565 ^3= 1172789476189812125
    8 23 21  2 91 % 45658321 ^3= 95183092565230303010161
    9 27 25  2 92 % 747274701 ^3= 417292749018949010745094101
   10 30 26  4 86 % 6303650349 ^3= 250481898947474907030163458549
   11 31 29  2 93 % 12963030703 ^3= 2178309818321898907256727238927
   12 35 31  4 88 % 296989432165 ^3= 26195276565032385492529078743092125
   13 38 32  6 84 % 3216961616303 ^3= 33291827618329634743672385276541850127
   14 42 38  4 90 % 89478707272163 ^3= 716405816503476781632905294185458709634747
   15 44 36  8 81 % 436767210509416 ^3= 83320157303034329838381018963270147696503296
   16 48 37 11 77 % 6985470509212127 ^3= 340868595015072149278781654745018761676907092383
   17 50 41  9 82 % 34127452303658127 ^3= 39747663556583230387850743016183850509876385694383
   18 54 46  8 85 % 856981258905698521 ^3= 629381500769096307492303896507250109676707696705874761
   19 52 46  6 88 % 145898961034783836 ^3= 3105679230707014307418321034961070963670363894981056
   20 59 53  6 89 % 36949058181274901056 ^3= 50444069870945836721092903418545810505698905294181836783616
   21 59 53  6 89 % 36949058181274901056 ^3= 50444069870945836721092903418545810505698905294181836783616
   22 65 52 13 80 % 4161012927430329216965 ^3= 72043896756608501032709690161812725658301012963630965298527432125
   23 68 57 11 83 % 41010165072729212345438 ^3= 68972275172254303236765296325698767498707692941430961876983276567672

Examining the above results we find the following:

      - the closest solution for 3 digits is actually a perfect solution (D=0, E=100%): 725^3 = 381078125, the 10th PPC.

      - the cubes for 4 and 5 digits are quasi-solutions: only the first digit has the wrong parity, the rest alternate correctly

      - the cubes for 6, 9 and 11 digits aren't perfect solutions but can be divided in two parts where each part is indeed a PPN but their union (the whole cube) is not. Example:

            for 11 digits, 12963030703^3= 2178309818321898907256727238927 and both 21 and 78309818321898907256727238927 are PPNs on their own but their union (the cube itself) is not.

      - finally and most important, the difference column, our heuristic, goes like this for increasing number of digits:

            0,1,1,2,2,2,2,4,2,4,6,8,11,9,8,6,6,6,13,11,...

      and while it seems to grow in fits and starts, a simple linear model makes it seems plausible that it continues to grow indefinitely. Notice that only the first value scores a 0 (a perfect solution) and only the next two values score a 1 (a quasi-solution, only the first digit has the wrong parity). After that no more 1's appear and after a little while the 2's stop appearing as well, then the 4's ...

      By the end of the list we are dealing with differences of 13, 11, ... so it seems plausible that a 0 difference is never reached again and thus there would be no more PPCs than the 10 small ones known.

6. Conclusions:

      Definitive:

            There are no PPNs up to 23-digit long which produce a PPC when cubed. So any further research must start with PPNs 24-digit long and up. This also means that no APC less than 70-digit long can be a PPC.

      Tentative:

            Both heuristics, most especially the second one (the differences heuristic), make it seem very implausible that an 11th PPC could exist. The evidence is not conclusive, just heuristic, but quite compelling, actually enough for me to abandon the search, as it would quickly become exponentially unmanageable and without realistic chances of success.


Thanks, Mr. Horn, for a very interesting MC. I really liked it, kudos to you for it !

Best regards.
V.
.