Threaded Mode | Linear Mode

Valentin Albillo · 06-01-2018, 01:16 AM

Hi, all:

This is my original research for this interesting challenge (you won't find any of this on the internet prior to this very post, AFAIK). First of all, a couple of

Definitions:

      - In what follows I'll call APN (Alternate-Parity Number) to any positive integer N (not necessarily a cube) which has all its digits alternating in parity.

      - In what follows I'll call PPN (Ping-Pong Number, as per Mr. Horn's definition) to any positive integer N such than both N and N\(^3\) are APNs. Notice that there are no single-digit PPNs (they would be just "Ping" or "Pong" but not "Ping-Pong").

So far I've worked out the following:

For D ranging from 2 to 20 digits, the following table lists: the number of APNs having D digits, having up to D digits, and the probability that an arbitrary positive integer having up to D digits is an APN:

Digits  #Numbers up to D digits    # of D-Digit APNs  # APNs up to D dig.   Prob. N is APN
-------------------------------------------------------------------------------------------
  2                          90                   45                   45   0.500000000000
  3                         990                  225                  270   0.272727272727
  4                       9,990                1,125                1,395   0.139639639640
  5                      99,990                5,625                7,020   0.070207020702
  6                     999,990               28,125               35,145   0.035145351454
  7                   9,999,990              140,625              175,770   0.017577017577
  8                  99,999,990              703,125              878,895   0.008788950879
  9                 999,999,990            3,515,625            4,394,520   0.004394520044
10               9,999,999,990           17,578,125           21,972,645   0.002197264502
11              99,999,999,990           87,890,625          109,863,270   0.001098632700
12             999,999,999,990          439,453,125          549,316,395   0.000549316395

13           9,999,999,999,990        2,197,265,625        2,746,582,020   0.000274658202
14          99,999,999,999,990       10,986,328,125       13,732,910,145   0.000137329101
15         999,999,999,999,990       54,931,640,625       68,664,550,770   0.000068664551
16       9,999,999,999,999,990      274,658,203,125      343,322,753,895   0.000034332275
17      99,999,999,999,999,990    1,373,291,015,625    1,716,613,769,520   0.000017166138
18     999,999,999,999,999,990    6,866,455,078,125    8,583,068,847,645   0.000008583069
19   9,999,999,999,999,999,990   34,332,275,390,625   42,915,344,238,270   0.000004291534
20  99,999,999,999,999,999,990  171,661,376,953,125  214,576,721,191,395   0.000002145767

The following code for the 12-digit HP-71B will produce the above table for D ranging from 2 up to 12 digits.

      1  DEF FNC1(D)=D
      2  DEF FNC2(D)=10^D-10
      3  DEF FNC3(D)=9*5^(D-1)
      4  DEF FNC4(D)=45/4*(5^(D-1)-1)
      5  DEF FNC5(D)=45/4*(5^(D-1)-1)/(10^D-10)
      6  !
      7  DESTROY ALL
      8  FOR D=2 TO 12 @ DISP FNC1(D);FNC2(D);FNC3(D);FNC4(D);FNC5(D) @ NEXT D

(I computed the results for D from 13 up to 20 digits using multiprecision software.)

Inspecting the table reveals that by the time we're considering 20-digit numbers (and so 60-digit cubes) we're dealing with 99,999,999,999,999,999,990 (almost 100 quintillion, 10\(^{20}\)) candidates if we're conducting a pure brute-force search where we check both N and N\(^3\) for APN-ness.

A much faster strategy consists in directly generating each APN in turn and then checking only its cube for APN-ness. This reduces the search order from O(10\(^N\)) to O(5\(^N\)), i.e., a mere 214,576,721,191,395 (214 trillion) candidates instead of 100 quintillion. This reduces the number of candidates by a factor of 466,033x.

Obviously, checking the cubes of 214 trillion APNs to try and find any that also happen to be PPN is beyond the computation capabilites of a typical PC, at least in a reasonable amount of time. For instance, even using hardware capable or generating one million/sec. APNs up to 20-digits long while also computing and checking their up to 60-digit cubes, it would take almost 2,500 days to complete the search so it's clear that a more refined idea is sorely needed.

After thinking about it for a while I came up with a workable idea to speed the search greatly by trading extending checking time (increasing it 5x) for reducing the number of candidates to check (decreasing it to O(2.5\(^N\))). This provides a tremendous, exponential reduction in search time, to the point that for 20-digit candidates we only need to check the cubes of 751,937,115 candidates. Compared to the previous 214 trillion candidates, this further reduces the number of candidates by a factor of 285,365x, for a total reduction over pure brute-force of almost 133 billion times. I'm still using brute force but less and less brute and more and more refined.

The technique involves generating and checking what I call "root" candidates, which are not so easy to describe (and doing so here would make this already very long post about twice or thrice longer) but which, as stated above, take 5x more time to check but their number is reduced to O(2.5\(^N\)).

I wrote code for and tested it first in the 12-digit HP-71B, which reproduces just the first 3 rows of the following table, as 4-digit candidates already generate 12-digit cubes. The remaining rows up to 20 digits were generated by converting the 71B code and then running it using multiprecision software:

Digits  #Numbers up to D digits   # APNs up to D dig. #Roots up to D dig.
-------------------------------------------------------------------------
  2                          90                   45             35
  3                         990                  270            110
  4                       9,990                1,395            315

  5                      99,990                7,020            810
  6                     999,990               35,145          2,035
  7                   9,999,990              175,770          5,055
  8                  99,999,990              878,895         12,630
  9                 999,999,990            4,394,520         31,605
10               9,999,999,990           21,972,645         79,190
11              99,999,999,990          109,863,270        197,650
12             999,999,999,990          549,316,395        493,380
13           9,999,999,999,990        2,746,582,020      1,232,630
14          99,999,999,999,990       13,732,910,145      3,080,445
15         999,999,999,999,990       68,664,550,770      7,701,600
16       9,999,999,999,999,990      343,322,753,895     19,253,260
17      99,999,999,999,999,990    1,716,613,769,520     48,128,440
18     999,999,999,999,999,990    8,583,068,847,645    120,313,780
19   9,999,999,999,999,999,990   42,915,344,238,270    300,777,310
20  99,999,999,999,999,999,990  214,576,721,191,395    751,937,115

I've found no simple formula or recurrence relation for the 4th column (# of roots up to D digits long) but the simple formula   #roots(D) = 8.2675*2.5\(^D\)   gives a good approximation from D=3 onwards. Notice that the ratio between the number of roots up to 20 and 19 digits respectively is already 751937115/300777310 = 2.49998 so the limit ratio seems clearly to be 2.5 and thus there are O(2.5\(^N\)) root candidates to check.

The reduction in the number of candidates to generate and check is most dramatic when going from checking all the number to generating and checking only APNs to generating and checking only roots. Matter of fact, the search and check procedure for the 751,937,115 up-to-20-digit candidates takes just 5 hours to complete in pretty old hardware & software.

Conclusions:

Regrettably, after all this work, except for the 10 small ones already known, no further solutions were found for numbers from 10 up to 10\(^{20}\) so if an 11th PPN does exist it has more than 20 digits (and its cube more than 60 digits). Thus, any further search should begin with numbers 21-digit long and up, i.e.: N >= 10\(^{20}\), and a fast modern PC coupled with suitably fast, compiled software will probably be capable to extend the search up to 27 or 28 digits in the same timet took me to reach 20 digits.

Regards.
V.
.