MC: Ping-Pong Cubes

[pier4r]

Valentin Just as info. While I would click on a like button or a "+1" if there was one already for the effort that you put in your posts, often I don't comment because reasons.

I believe several people do the same as me. (appreciating but not commenting)

On the other side I appreciate those that contribute because they want to share their ideas, if one contributes to get attention, while it is still great it feels a bit different.

[Valentin Albillo]

.
Hi, Joe:

(06-21-2018 02:50 AM)Joe Horn Wrote:  YIKES! Sorry! YES, I didn't reply, but NO, I was NOT ignoring your posts! [...] I'm very sorry if saying this NOW is too little too late to prevent you from feeling offended by my silence.

Don't worry, Joe, no offence taken. I've just sent you a PM re this private matter so this thread can deal exclusively with just the technical aspects.

Joe Horn Wrote:

(06-20-2018 09:30 PM)Valentin Albillo Wrote:  [...] contingent on there being some interest, in a few days I'll post updated details [...]

Yes, I'm interested. Thanks in advance.

It'll be ready to be posted by tomorrow evening (GMT+1). I hope you'll like it.

Best regards.
V.
.

[Joe Horn]

Cool! Thanks, Valentin! I'm looking forward to it.

[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.
.

[ijabbott]

Thanks for all that, Valentin. That's a lot of effort you put in to this problem.

Would it be possible to post the filtering algorithm you used for deciding which PPNs to cube and check, since I understand you do not cube and check every PPN? Perhaps you could add it as an appendix after your conclusions.

My gut feeling is still that there are probably an infinite number of PPCs, mostly because infinity gives you an awful lot of wiggle room, and as you mentioned, the occurrences of PPNs and APCs seem fairly independent from each other.

[Valentin Albillo]

.
Hi, ijabbott:

(06-25-2018 09:48 PM)ijabbott Wrote:  Thanks for all that, Valentin. That's a lot of effort you put in to this problem.

You're welcome, thanks to you for your appreciation. It wasn't that much effort, really: getting the idea for an efficient algorithm was easy, then concocting an 11-line subprogram to implement it was no big deal either, and letting my POPS system run for 12 hours straight was painless to me. The real effort was to write and properly format the post I then made to this thread, that was a very big chore. And, sadly, an almost fully wasted effort at that ... 8D

Quote:Would it be possible to post the filtering algorithm you used for deciding which PPNs to cube and check, since I understand you do not cube and check every PPN? Perhaps you could add it as an appendix after your conclusions.

Yes, sure, but not here. Apart from you it seems there's not much interest in my contributions here so I'll reserve the algorithm, code and further results for a new article to be written down in the near future, as soon as I can get some place where to upload it and further make all of my previous articles and challenges freely available on line. Sylvain kindly offered to host my HP-related materials but I've been unable to successfully ftp them up to his server so far.

Quote:My gut feeling is still that there are probably an infinite number of PPCs, mostly because infinity gives you an awful lot of wiggle room, and as you mentioned, the occurrences of PPNs and APCs seem fairly independent from each other.

Yes but my second heuristic makes it likely that the number of consecutive alternating digits lags behind the total number of digits more and more or, conversely, that the number of non-alternating digits grows and grows, in which case there will never be another PPC, infinity notwithstanding. I know of many examples where infinity would seem to give room for further results but it actually doesn't.

Thanks again for your interest and best regards.

V.
.

[Jim Horn]

Hello, Valentin,

I just want to thank you not only for the fine work and documentation you supplied for this problem but for the many you have graced this forum with through the years. Your insight and explanations have been understandable, enlightening and enjoyable. As someone who reads them all, I seldom respond and never considered that you may feel you are casting your efforts into the void. Please be sure that you are not. I am certain that like me, many of the forum members read and appreciate your hard work without commenting.

Best to you always!

Jim Horn (Older than Joe)

[Joe Horn]

(06-25-2018 08:45 PM)Valentin Albillo Wrote:  As promised, I'm posting here my last say on the technical aspects of this interesting MC...

Holy smokes, thank you, Valentin, for both doing and sharing all that good work! Your patience and tenacity with tough problems is inspiring. Thank you!

And ditto to what my brother Jim said above.

[rprosperi]

(06-26-2018 09:43 PM)Valentin Albillo Wrote:  ...The real effort was to write and properly format the post I then made to this thread, that was a very big chore. And, sadly, an almost fully wasted effort at that ... 8D

and

...Apart from you it seems there's not much interest in my contributions here so I'll reserve the algorithm, code and further results for a new article to be written down in the near future...

As both Jim and Joe have mentioned, many, many thanks for your impressive research and post for this MC.

Often, after reading a tour-de-force post like this one, it can feel very disingenuous to simply reply with a 'thanks very much for that', especially when one may not fully understand the content or fully appreciate the insights used in the research and solution.

However one thing I can fully appreciate is how much painstaking time and effort it took to create the clear and well-formatted post which indeed helps a great deal when trying to understand some of these non-casual topics. Carefully formatting the explanation and especially results goes a long way to explain some of the subtle aspects of the resulting numbers; I know you understand this well, as your posts always are a model of clarity in this regard.

So, don't take a lack of eager comments to mean your work is not appreciated; it often simply means we are too humbled to reply with meaningful comments.

I promise that in the future, should I see a post of yours that I feel is pointless and not contributing, I'll say so. But don't expect that soon.

[brickviking]

Considering I had alternatively considered solutions using logs and discarded same, ditto square roots, that was about as far as I had got into the MC at hand. The fact that not only has Valentin looked at the problem, but has possibly done pretty decent amounts of time into the problem means that finding the 11th APC is probably not as simple as a MC would ordinarily suggest. I might not understand the mathematics behind the research, but I can still appreciate the effort that went into it. About as close as I can get is to take the work thus presented, and hopefully massage it into something that R or at least Maxima accepts. Maybe throwing big iron at it might eventually cough up a result.

(Post 252)

[Joe Horn]

(06-27-2018 04:41 AM)brickviking Wrote:  ... finding the 11th APC is probably not as simple as a MC would ordinarily suggest.

The OP agrees with you:

(05-22-2018 03:16 PM)Joe Horn Wrote:  ... Your mini-challenge, should you choose to accept it, is to write an HP calculator program that finds the first ten Ping-Pong Cubes. Don't worry; the 10th one is not very large.

A much bigger challenge, which has eluded me thus far, is to find the 11th Ping-Pong Cube. It must be very large, if it even exists.

[Massimo Gnerucci]

(06-27-2018 12:38 AM)rprosperi Wrote:  Often, after reading a tour-de-force post like this one, it can feel very disingenuous to simply reply with a 'thanks very much for that', especially when one may not fully understand the content or fully appreciate the insights used in the research and solution.

However one thing I can fully appreciate is how much painstaking time and effort it took to create the clear and well-formatted post which indeed helps a great deal when trying to understand some of these non-casual topics. Carefully formatting the explanation and especially results goes a long way to explain some of the subtle aspects of the resulting numbers; I know you understand this well, as your posts always are a model of clarity in this regard.

So, don't take a lack of eager comments to mean your work is not appreciated; it often simply means we are too humbled to reply with meaningful comments.

Ditto.
So, thank you very much, Valentin: I am always astounded and astonished at your deep maths abilities.
Nothing to add by me, unfortunately.

[Valentin Albillo]

.
Hi, Jim Horn, Joe Horn, rprosperi, brickviking and Massimo Gnerucci:

Thank you very much for your kind words, really much appreciated.

I must confess I was feeling somewhat disappointed by the lack of responses but it's all cleared now and, on hindsight, I should have known better. Pinky promise not to jump to such negative conclusions again whether people comment or not, I'll know you are there for me ... :-)

By the way, brickviking (who in his post #247 said he generally stayed out of the way of people like me ... ;-) ) raises an interesting point:

Quote:About as close as I can get is to take the work thus presented, and hopefully massage it into something that R or at least Maxima accepts. Maybe throwing big iron at it might eventually cough up a result.

I'd love for big irons to work, please do try, but I'm still quite convinced that there's no 11th PPC, not even taking infinity into account (as per ijabbott). However, as part of my original research I also generated and examined many alternating-parity cubes (APCs) up to 40-digit long and more, and these numbers let me quite perplexed, they seem to have some very intriguing , unexpected features which seem too contrived to be due to pure chance.

There ¡s also the fact that they seem to exist for any number of digits and this raises the question of whether they are infinite in number or finally you can get to the very last one of them. If I can sort some publication issues I intend to dedicate a full article to them in the near future, including how to efficiently search for really big ones.

Thanks again to all of you, I hope to be deserving of your kind words in the future.

Best regards.
V.
.