Post Reply 
MC: Ping-Pong Cubes
06-01-2018, 01:16 AM
Post: #28
RE: MC: Ping-Pong Cubes
 
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.
.

  
All My Articles & other Materials here:  Valentin Albillo's HP Collection
 
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
MC: Ping-Pong Cubes - Joe Horn - 05-22-2018, 03:16 PM
RE: MC: Ping-Pong Cubes - Didier Lachieze - 05-22-2018, 03:52 PM
RE: MC: Ping-Pong Cubes - Joe Horn - 05-22-2018, 04:05 PM
RE: MC: Ping-Pong Cubes - Valentin Albillo - 05-22-2018, 08:46 PM
RE: MC: Ping-Pong Cubes - Didier Lachieze - 05-23-2018, 12:14 PM
RE: MC: Ping-Pong Cubes - Werner - 05-24-2018, 01:19 PM
RE: MC: Ping-Pong Cubes - DavidM - 05-25-2018, 08:20 PM
RE: MC: Ping-Pong Cubes - ijabbott - 05-25-2018, 10:55 PM
RE: MC: Ping-Pong Cubes - Valentin Albillo - 05-25-2018, 11:45 PM
RE: MC: Ping-Pong Cubes - pier4r - 05-26-2018, 06:47 AM
RE: MC: Ping-Pong Cubes - Valentin Albillo - 05-26-2018, 11:31 PM
RE: MC: Ping-Pong Cubes - pier4r - 05-27-2018, 08:13 AM
RE: MC: Ping-Pong Cubes - DavidM - 05-26-2018, 05:01 PM
RE: MC: Ping-Pong Cubes - Joe Horn - 05-27-2018, 05:06 AM
RE: MC: Ping-Pong Cubes - David Hayden - 05-27-2018, 04:48 PM
RE: MC: Ping-Pong Cubes - ijabbott - 05-27-2018, 06:50 PM
RE: MC: Ping-Pong Cubes - pier4r - 05-27-2018, 09:19 PM
RE: MC: Ping-Pong Cubes - brickviking - 05-27-2018, 10:33 PM
RE: MC: Ping-Pong Cubes - Juan14 - 05-26-2018, 08:19 PM
RE: MC: Ping-Pong Cubes - DavidM - 05-27-2018, 03:02 PM
RE: MC: Ping-Pong Cubes - brickviking - 05-27-2018, 10:05 AM
RE: MC: Ping-Pong Cubes - ijabbott - 05-27-2018, 12:30 PM
RE: MC: Ping-Pong Cubes - DavidM - 05-27-2018, 02:50 PM
RE: MC: Ping-Pong Cubes - pier4r - 05-27-2018, 11:15 PM
RE: MC: Ping-Pong Cubes - ijabbott - 05-29-2018, 08:07 PM
RE: MC: Ping-Pong Cubes - Valentin Albillo - 06-01-2018 01:16 AM
RE: MC: Ping-Pong Cubes - Warbucks - 06-03-2018, 04:26 AM
RE: MC: Ping-Pong Cubes - Joe Horn - 06-03-2018, 03:24 PM
RE: MC: Ping-Pong Cubes - Valentin Albillo - 06-14-2018, 03:07 PM
RE: MC: Ping-Pong Cubes - Joe Horn - 06-15-2018, 02:12 AM
RE: MC: Ping-Pong Cubes - Valentin Albillo - 06-20-2018, 09:30 PM
RE: MC: Ping-Pong Cubes - Joe Horn - 06-21-2018, 02:50 AM
RE: MC: Ping-Pong Cubes - Valentin Albillo - 06-21-2018, 09:29 PM
RE: MC: Ping-Pong Cubes - ijabbott - 06-03-2018, 05:42 AM
RE: MC: Ping-Pong Cubes - pier4r - 06-03-2018, 12:29 PM
RE: MC: Ping-Pong Cubes - Werner - 06-15-2018, 04:52 AM
RE: MC: Ping-Pong Cubes - Joe Horn - 06-15-2018, 03:37 PM
RE: MC: Ping-Pong Cubes - ijabbott - 06-17-2018, 10:33 AM
RE: MC: Ping-Pong Cubes - brickviking - 06-21-2018, 03:22 AM
RE: MC: Ping-Pong Cubes - pier4r - 06-21-2018, 06:24 AM
RE: MC: Ping-Pong Cubes - Joe Horn - 06-22-2018, 04:40 AM
RE: MC: Ping-Pong Cubes - Valentin Albillo - 06-25-2018, 08:45 PM
RE: MC: Ping-Pong Cubes - ijabbott - 06-25-2018, 09:48 PM
RE: MC: Ping-Pong Cubes - Valentin Albillo - 06-26-2018, 09:43 PM
RE: MC: Ping-Pong Cubes - rprosperi - 06-27-2018, 12:38 AM
RE: MC: Ping-Pong Cubes - Massimo Gnerucci - 06-27-2018, 06:58 AM
RE: MC: Ping-Pong Cubes - Jim Horn - 06-26-2018, 10:10 PM
RE: MC: Ping-Pong Cubes - Joe Horn - 06-26-2018, 10:23 PM
RE: MC: Ping-Pong Cubes - brickviking - 06-27-2018, 04:41 AM
RE: MC: Ping-Pong Cubes - Joe Horn - 06-27-2018, 05:23 AM
RE: MC: Ping-Pong Cubes - Valentin Albillo - 06-27-2018, 09:29 PM



User(s) browsing this thread: 2 Guest(s)