MC: Ping-Pong Cubes

[Joe Horn]

You always thought that Ping-Pong™ only involved planes and spheres, right? Here's a programming mini-challenge that involves Ping-Pong Cubes!

Definition 1: A Ping-Pong Number is any multi-digit integer whose consecutive digits always alternate between even and odd. For example, 18505 is a Ping-Pong Number because its consecutive digits are odd, even, odd, even, odd. 16850 is not (because 6 and 8 are both even). Any pair of even digits, or pair of odd digits, anywhere in the number, disqualifies it from being a Ping-Pong Number.

The name of course comes from the concept of a rally on a Ping-Pong table marked like this:


Note: Dotted lines are not necessarily to scale; on a perfect table, the probability of hitting any digit is the same.

Definition 2: A Ping-Pong Cube is a Ping-Pong Number which is the cube of another Ping-Pong Number. The smallest Ping-Pong Cube is 5832, because it is a Ping-Pong Number and it is the cube of 18 which is also a Ping-Pong Number.

The first 5 Ping-Pong Cubes are:

5832 = 18^3
12167 = 23^3
614125 = 85^3
658503 = 87^3
1030301 = 101^3

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.

[Didier Lachieze]

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

On the Prime the following program will solve the mini-challenge:

Code:

EXPORT PPCube()
BEGIN
 PRINT();
 FOR N FROM 10 TO 10000 DO
  IF ΠLIST(CONCAT(ΔLIST(ASC(STRING(N,1))),ΔLIST(ASC(STRING(N^3,1)))) MOD 2) THEN PRINT(N); END;
 END;
END;

[Joe Horn]

(05-22-2018 03:52 PM)Didier Lachieze Wrote:  On the Prime the following program will solve the mini-challenge...

Wow! It finds all 10 instantaneously. Very cool!

[Valentin Albillo]

.
Hi, Joe:

(05-22-2018 03:16 PM)Joe Horn Wrote:  The first 5 Ping-Pong Cubes are:
[...]
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.

Easy as pie. The following 4-liner (159 bytes) I've written for the HP-71B plus HP's String LEX does the job and finds all 10 such numbers less than 1,000 in 0.43 sec. under J-F's Emu71:

      1  A$="10101010101" @ FOR I=10 TO 999 @ IF NOT FNP(I) THEN 2 ELSE IF FNP(I^3) THEN DISP I;I^3
      2  NEXT I
      3  DEF FNP(N) @ N$=STR$(VAL(REPLACE$(STR$(N),"9","1"))+VAL(A$[1,LEN(STR$(N))]))
      4  IF SPAN(N$,"13579") THEN FNP=NOT SPAN(N$,"02468") ELSE FNP=1

      >SETTIME 0 @ CALL @ TIME

        18  5832
        23  12167
        85  614125
        87  658503
       101  1030301
       103  1092727
       301  27270901
       303  27818127
       363  47832147
       725  381078125

            0.43 sec.

FNP is a 2-line user-defined function that returns 1 (True) if its argument is a PPN and 0 (False) if it isn't. Notice that it doesn't use any kind of looping at all, it gets the answer straight away, in linear time.

Looking for all such numbers less than 10,000 takes less than 5 seconds but finds no additional ones.

Quote: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.

My program would find it in principle but it's limited to the 12-digit native floating point results so searching for N>=10,000 would take multiprecision computations. I'll give it a try if I find the time.

Regards.
V.
.
P.S.: Edited to feature an improved version (4 lines instead of 5 and also somewhat faster).

[Didier Lachieze]

A version of the mini-challenge for the 42S in 39 steps / 79 bytes:

Code:

00 { 79-Byte Prgm }
01▸LBL "PPC"
02 ALL
03 CF 29
04 SF 21
05 9
06 STO "N"
07▸LBL 00
08 1
09 STO+ "N"
10 1ᴇ4
11 RCL "N"
12 X=Y?
13 RTN
14 XEQ 01
15 X≠0?
16 GTO 00
17 RCL "N"
18 RCL× "N"
19 RCL× "N"
20 XEQ 01
21 X=0?
22 VIEW "N"
23 GTO 00
24▸LBL 01
25 CLA
26 ARCL ST X
27 ATOX
28 2
29 MOD
30▸LBL 02
31 ATOX
32 X=0?
33 RTN
34 2
35 MOD
36 X≠Y?
37 GTO 02
38 1
39 END

After XEQ "PPC" the program will stop at each Ping-Pong Cube found, press R/S so see the next one. If a printer is enabled (PON) the program will print the Ping-Pong Cubes without stopping.

A .raw file is also attached so you can load it in Free42 or your DM42.

  ppc.zip (Size: 230 bytes / Downloads: 7)

[Werner]

I exhausted the 34 digits of Free42, I'm afraid.
No 11th Ping Pong Cube for x^3 <= 10^34
I used the following program, that generates all Ping Pong numbers with I digits and verifies if the third power is also a Ping Pong number.

Code:

00 { 128-Byte Prgm }
01▸LBL "PPC"
02 STO "I"
03 1.009
04 XEQ 99
05 RTN
06▸LBL 97
07 RCL IND ST X
08▸LBL 99
09 STO IND ST Y
10 IP
11 1.00902
12 +
13 2
14 MOD
15 DSE ST Y
16 GTO 99
17▸LBL 01
18 RCL "I"
19 1ᴇ3
20 0
21▸LBL 14
22 %
23 RCL IND ST Z
24 IP
25 +
26 DSE ST Z
27 GTO 14
28 STO 00
29 ENTER
30 X↑2
31 ×
32 XEQ 88
33 X=0?
34 VIEW 00
35 ISG 01
36 GTO 01
37 RCL "I"
38 1
39▸LBL 95
40 X<Y?
41 ISG ST X
42 RTN
43 ISG IND ST X
44 GTO 97
45 GTO 95
46▸LBL 88
47 1
48 X<>Y
49 R↓
50▸LBL 87
51 R↑
52 X=0?
53 RTN
54 10
55 ÷
56 IP
57 X<>Y
58 LASTX
59 0.2
60 MOD
61 X≠Y?
62 GTO 87
63 1
64 END

Input the number of digits eg. 3 PPC will result in the 6 solutions being shown in the printout if you have PON selected (I'm running Free42 on a PC).
For input 12 change line 3 to 1.002 since 1e34^(1/3) = 215 443 469 003

Cheers, Werner

[DavidM]

An interesting challenge, Joe. This has a similar feel to some of your past challenges (Pan-prime Cube and All-odd digits come to mind). I suspect that some of the optimizations from the Pan-prime cube challenge could be helpful for this one; in particular, knowing in advance that certain root digit suffixes will create invalid results might speed things up. I didn't take it that far, though.

Here's my "plain UserRPL" approach:

Code:

\<<
  {
    DUP 2. MOD SWAP 10. / IP 1.
    WHILE
      OVER
    REPEAT
      ROT PICK3 2. MOD
      SWAP OVER XOR
      ROT AND
      ROT 10. / IP SWAP
    END
    NIP NIP
  }
  0.
  10.
  WHILE
    OVER 10. <
  REPEAT
    IF
      PICK3 OVER
      SWAP EVAL
    THEN
      IF
        PICK3 OVER
        DUPDUP * *
        SWAP EVAL
      THEN
        SWAP 1. + SWAP
        DUP 4. ROLLD
      END
    END
     1. +
  END
  DROP2 DROP
\>>

The code within the list brackets above is a subroutine that takes a real number as input and returns a 1 if the input was valid, otherwise a 0. It simply checks the parity of each digit after the first to make sure it isn't the same as the previous one.

The basic approach was to execute a loop on sequential integers starting with 10, stopping only after the 10th solution is found. In each loop iteration, the root is checked for validity before proceeding to check the cube. I opted to skip some obvious code shortcuts due to their performance impact. That said, I'm sure there are much faster UserRPL implementations possible -- I hope others will post their own. The above program completes in 24.6 seconds on my 50g.

For those who might like to compare a SysRPL approach, I submit the following translation of the above program. It uses the exact same approach as the UserRPL one above, and completes in less than half the time of the above at 9.6 seconds. Note: I use Debug4x, which doesn't require the code within a WHILE clause to be encapsulated in a ":: ... ;" block. You would have to add the :: and ; symbols to the WHILE clauses if you don't use Debug4x as your compiler:

Code:

::
   CK0NOLASTWD

   ( Valid Ping Pong Check )
   ' ::
      DUP %2 %MOD %0<> SWAP %10 %/ %IP TRUE
      BEGIN
         OVER %0<>
      WHILE
         ROT 3PICK %2 %MOD %0<>
         SWAPOVER XOR
         ROTAND
         ROT %10 %/ %IP SWAP
      REPEAT
      ROTROT2DROP
   ;

   ( count of solutions )
   BINT0

   ( bind local vars )
   FLASHPTR 2LAMBIND

   ( seed initial test )
   %10

   ( do until 10 solutions found )
   BEGIN
      1GETLAM BINT10 #<
   WHILE
      DUP 2GETEVAL IT ::
         DUPDUP DUP %* %* 2GETEVAL IT ::
            1GETLAM #1+ 1PUTLAM
            DUP
         ;
      ;
      %1+
   REPEAT

   ( drop the count )
   DROP

   ( abandon local vars )
   ABND
;

...and finally, to show how much time is spent in that laborious ping-pong validation, I replaced the validation subroutine from the previous SysRPL example with this Saturn code object to see how much improvement I could get. Using this brought the total time down to 1.26 seconds:

Code:

   CODEM
      SAVE
      A=DAT1 A
      AD1EX
      D1+5
      A=DAT1 W
      ST=1 0
      B=0 S
      B+1 S
      C=A M
      CSL W
      A-1 X
      C&B S
      D=C S
      {
         CSL W
         C&B S
         ?C=D S ->{ ST=0 0 }
         D=C S
         A-1 X
         UPNC
      }
      LOAD
      LA 03AC0
      ?ST=1 0 ->{ LA 03A81 }
      DAT1=A A
      RPL
   ENDCODE

[ijabbott]

I don't know if there is a clever trick to this problem (I can't think of one, but I'm not that clever!) or if it's just a brute force search. If the latter, it's not very interesting to me,

[Valentin Albillo]

(05-25-2018 10:55 PM)ijabbott Wrote:  I don't know if there is a clever trick to this problem (I can't think of one, but I'm not that clever!) or if it's just a brute force search. If the latter, it's not very interesting to me,

There are many solutions (different approaches) for this problem and further there are two kinds of clever tricks which can be used to greatly decrease the search and/or the searching time:

- on the one hand, you can avoid looping through every digit of a number to ascertain whether it's a PP or not. My solution above uses one such trick, as noted in the description, and not using loops greatly increases the speed there, almost linear time to check every number large or small.

- on the other hand, you can avoid testing essentially 10\(^N\) N-digit numbers by using a clever but simple trick, reducing the search time by orders of magnitude.

I've devised four or five different solutions using none, some or all of these techniques (the one above uses just the first kind) but they will be left an an exercise for the reader as I don't see much interest, if any, in HP-71B-coded solutions.

Have a nice weekend.
V.
.

[pier4r]

(05-25-2018 10:55 PM)ijabbott Wrote:  I don't know if there is a clever trick to this problem (I can't think of one, but I'm not that clever!) or if it's just a brute force search. If the latter, it's not very interesting to me,

The very fact that you don't know should tell you that it is interesting, as figuring out yourself which case applies is already a challenge.

There is also an hint. Werner went throughthe numbers up to magnitude 10^34 in likely some hours or days , do you estimate it can be brute force?


Also little note, if it is not interesting, ignore it. There are billions of uninteresting discussions online, we don't go writing around that we are not interested. Writing that we are not interested is first and foremost uninteresting (nobody asked us) and secondly it sounds a tad confrontational.

[DavidM]

(05-25-2018 10:55 PM)ijabbott Wrote:  I don't know if there is a clever trick to this problem (I can't think of one, but I'm not that clever!) or if it's just a brute force search. If the latter, it's not very interesting to me,

Most challenges/contests posted here are crafted by people who have already found some amount of optimization to the problem at hand prior to initiating the challenge. Sometimes there's no known shortcuts, though, and the challenge is presented in the hopes that someone may discover a useful approach to a solution that hasn't yet been thought up.

In this particular case, the similarities with some other challenges provide some clues as to some possible optimizations. In my case, I didn't use any of them and instead simply wanted to use a "generic" solution as a basis, then refining the process with increasingly specialized translations of the code. Some here have expressed interest in SysRPL, so I thought a RPL->SysRPL->Saturn progression might show some interesting performance differences.

That said, I did try several methods before settling on the "brute force" test that my RPL/SysRPL code used, including Didier's ΔLIST/ΠLIST approach. I was actually surprised to find that even some optimized list processing approaches were slower than what I ended up using. I realized that ANDing the numbers with"111.." would result in "10101..." results for ping-pong numbers, which could then be divided by 11 for interesting intermediate results, etc. But all those transformations in RPL ended up being slower than simply testing for alternating parity of each digit. That's part of the fun of challenges like this -- you learn a lot through the experimentation.

"The journey is the reward."

[Juan14]

The first program is a subroutine that checks if the number is a ping-pong number, I called it ISPP?
«
DUP 2. MOD 1
WHILE PICK3 10 > OVER AND
REPEAT
DROP SWAP 10. / IP DUP 2. MOD ROT OVER XOR
END NIP NIP
»

The next program uses ISPP? To check for ping-pong numbers starting with 10, if a ping-pong number is found checks if the square of that number is a ping-pong number, if so stores it in a list and the process repeat ten times in a START-NEXT loop.
«
{ } 10 1 10
START
DO 1 +
UNTIL
IF DUP ISPP?
THEN
DUP SQ ISPP?
ELSE 0
END
END SWAP OVER + SWAP
NEXT DROP
»

[Valentin Albillo]

(05-26-2018 06:47 AM)pier4r Wrote:  

(05-25-2018 10:55 PM)ijabbott Wrote:  I don't know if there is a clever trick to this problem (I can't think of one, but I'm not that clever!) or if it's just a brute force search. If the latter, it's not very interesting to me,

The very fact that you don't know should tell you that it is interesting, as figuring out yourself which case applies is already a challenge.

Chill out, Pier.

As you can see, ijabbott is very new to this forum, just 69 posts right now, so he probably can't know for sure whether Joe has a reputation for posting brute-force search problems or not. Not having direct experience about Joe's challenges, he does the rational thing which is to directly ask for information to older members in this forum who surely should know, instead of entering a challenge which, for all he knows, might be uninteresting.

Quote:There is also an hint. Werner went throughthe numbers up to magnitude 10^34 in likely some hours or days , do you estimate it can be brute force?

Of course it can. If you meant that Werner explored all numbers from, say, 10 up to 10^34, he didn't say that. He said that he explored numbers up to 215 443 469 003, which is the cube root of 10^34, and that number is only 2e11, not 1e34, and requires on the order of 1e8 tests, which is entirely doable in at most a few hours by simple brute force.

Quote:Writing that we are not interested is first and foremost uninteresting (nobody asked us) and secondly it sounds a tad confrontational.

Consider what I said above, think about it, and then decide who's the one being confrontational. This is no helpful or friendly way to address a fairly new member.

Have a nice weekend.
V.
.

[Joe Horn]

(05-26-2018 05:01 PM)DavidM Wrote:  ... That's part of the fun of challenges like this -- you learn a lot through the experimentation.

I totally agree. Over the years, I've had the most fun writing programs which presented many possible approaches. And the very best ones were the ones which, while writing them, suggested FAR BETTER approaches than the current approach which was then promptly discarded and replaced by the better approach. At first it seems that all the hours spent writing code for the now-abandoned approach were wasted, but they weren't really wasted, because the newer, better approach only came to light because of the development of the original approach. A few times that development / discovery / replacement process happened more than once during the same project, resulting in many routines on the cutting room floor and much learning along the way. Although discarding already-written code (and replacing it with better code) might be frustrating and expensive when developing commercial software, it tickles me pink when it happens while programming just for the fun of it. One of the goals of the "mini-challenges" is to share opportunities for that delightful experience.

[pier4r]

(05-26-2018 11:31 PM)Valentin Albillo Wrote:  Consider what I said above, think about it, and then decide who's the one being confrontational. This is no helpful or friendly way to address a fairly new member.

I see it differently.

Yes if the post count would equal the sum of all life experiences of a person, then I would be with you.
Instead I presume that here on the forum 99.9% of the userbase is 16 years old or older (I am much older than 16, I am near to EOL).

So independently from whom create the discussion (Joe or another member) and what the discussion states (n1), I don't find it nice entering the discussion saying something on the line "hmm, I don't know, it doesn't seem interesting to me" (at least this is how I perceived it).

To explain myself I propose this analogy. There is a person, as presumed above 16 year old or older, that goes to a park. In this park there are plenty of open activities and groups form around them.

This person decides to go to a random group and say "hello, may I participate?"
"Sure!"
"Ok what are you doing here?"
"Oh, we try to build the highest lego tower"
"Meh, boring"

Then he does the same with other groups. I don't find it nice because one of my ears (n2) hear it as "meh, why are you wasting your time on it?".

Now it is completely legit that someone finds this or that activity uninteresting or boring. What I find not ok is that between the option to do the following: "look, ask, decide and in the case leave or ignore", one does instead "look, ask, decide, voice that the activity is uninteresting".

The last part, the one about voicing that an activity is not interesting, is the one that is not nice to me.

And now another example. If I would enter each of your Short and sweet challenges, and I would say "oh, they are mostly built around the 71B, how uninteresting for me" (n3), would you consider it nice?
I can surely think the sentence, but voicing it is either a lack of tact or is belittling or is confrontational. At least, according to my perception.

Now it is also true that I could have decided to ignore the message. In my case I decided to answer to it (and from there this discussion).

n1: I am the first that create a lot of math challenges that are trivial for many here.
n2: https://en.wikipedia.org/wiki/Four-sides_model
n3: of course they are not. I am amazed at the 71B capabilities that you expose nicely.

[brickviking]

The original reply to the question being this:

Quote:I don't know if there is a clever trick to this problem (I can't think of one, but I'm not that clever!) or if it's just a brute force search. If the latter, it's not very interesting to me,

I let that one slide, as nobody's going to look pretty if they try to prosecute the guy for expressing his opinions. Jumping up and down about it won't look pretty either. So I let it slide. Yes, that's his opinion. Yes, he's expressing it in a scenario where it could be perceived to be rude. But no, nobody wins.

(1) Brute force searches can be boring because there's no finesse in finding it, just overwhelming the problem space by hitting everywhere on the dartboard, which will of course find the response. Eventually. Sometimes this is the only feasible way of solving the problem when there's no obvious mathematical formula behind a response.
(2) Searching for far faster routines can be (a) considerably challenging, and (b) extremely rewarding, especially when you can prove they exist.
(3) Let's get back to peoples' replies about the original topic, that of routines for finding ping-pong cubes.

'nuff said from me.

(Post 232)

[ijabbott]

To clarify my previous point, I really meant it is not mathematically interesting to me, or just searching for numbers that have some arbitrary property is not interesting to me. I understand some people are interested in finding out the fastest or most efficient ways to search for those numbers on their particular devices. I didn't mean to come across as confrontational.

I suppose the only interesting part to me is whether there are any ping-pong cubes beyond 725^3. Intuitively, they should be less common for larger numbers because there are more digits in the cube that need to alternate their decimal digit even parity. Anyway, I wrote a small C++ program with the GNU MP library for bignum support, and left it running overnight. The first 10 results popped up in a fraction of a second, but it didn't find an 11th result.

Code:

#include <iostream>
#include <gmpxx.h>

using namespace std;

static mpz_class nextpp(mpz_class n)
{
    mpz_class a;
    mpz_class pow = 1;
    mpz_class d;

    n += 2;
    a = n;
    while ((d = (a % 10)) < 2)
    {
        pow *= 10;
        a /= 10;
        if (a >= 10)
        {
            n += pow;
            a += 1;
        }
        else
        {
            break;
        }
    }
    if (a < 10)
    {
        n = a * pow;
        if ((a % 2) == 0)
        {
            pow /= 10;
        }
        else
        {
            pow /= 100;
        }
        while (pow)
        {
            n += pow;
            pow /= 100;
        }
    }
    return n;
}

static bool ispp(mpz_class a)
{
    mpz_class parity = (a % 2);
    
    while (a /= 10)
    {
        if ((a % 2) == parity)
            return false;
        parity = 1 - parity;
    }
    return true;
}

int main()
{
    mpz_class i, cube;
    
    for (i = 10; ; i = nextpp(i))
    {
        cube = i * i * i;
        if (ispp(cube))
            cout << i << " " << cube << "\n";    
    }
    return 0;
}

[DavidM]

(05-27-2018 12:30 PM)ijabbott Wrote:  I suppose the only interesting part to me is whether there are any ping-pong cubes beyond 725^3...

As I recall some of Joe's previous challenges (and/or posted observations), I suspect a big motivator for him is answering that same question. Certainly it is a curiosity that there would exist a nicely-rounded quantity of 10 solutions, in relative close proximity, but then nothing else even close.

So if we simply look at answering that specific question, we very quickly find that a simple brute-force search will run for quite some time with no success. It is inevitable that optimizations need to be applied which will both speed up the test and limit the input to have any hope of being useful. Discovering the "arbitrary properties" of the numbers that can be ruled out (or in) becomes an imperative for any hope of speeding up the search (regardless of platform), and the more advanced mathematical minds here may even discover a proof of existence/nonexistence in the process (one can dream!).

I'm certainly not trying to tell you what you should find interesting, but rather trying to explain how some of us connect what you did find interesting to other aspects of the problem that you didn't. As time permits, I will continue to experiment with this challenge. It's my expectation that others will find a variety of optimizations long before I do, and I will celebrate with them when they do. That's the better part of this unique community that keeps me coming back -- the collective learning/sharing process (and the confirmation that I'm not the only person in the world who still appreciates these well-designed, geeky devices ).

Thanks for sharing your code and contributing to this puzzle!

[DavidM]

(05-26-2018 08:19 PM)Juan14 Wrote:  The first program is a subroutine that checks if the number is a ping-pong number, I called it ISPP?
«
DUP 2. MOD 1
WHILE PICK3 10 > OVER AND
REPEAT
DROP SWAP 10. / IP DUP 2. MOD ROT OVER XOR
END NIP NIP
»

That's a nicer (and faster) RPL approach to testing ping-pong validity than I came up with, Juan! Using your better routine lowered the run time in my original RPL attempt by 22%. Executing it as a separate global variable also saved a bit of time as well.

(05-26-2018 08:19 PM)Juan14 Wrote:  

Code:


...
   THEN
    DUP SQ ISPP?
...

I did have to change the "SQ" above to "3. ^" in order to match the original problem, though. Just curious... did you find any interesting results from testing the squares?

[David Hayden]

(05-27-2018 05:06 AM)Joe Horn Wrote:  Although discarding already-written code (and replacing it with better code) might be frustrating and expensive when developing commercial software, it tickles me pink when it happens while programming just for the fun of it.

I'm going a bit off topic here but I hope some readers might find this interesting.

Sometimes discarding code frustrating and expensive, but sometimes it's the best thing you can do. In the late 90's we totally rewrote a core piece of our software. It had grown into a mass of spaghetti code that was very hard to maintain and enhance. I think the real interesting thing about that project was that we needed that first implementation to truly understand the requirements of the program.

That rewrite is still going strong nearly 20 years after going online and through almost constant enhancement.

In another case, we deliberately wrote a piece of thow-away code. The throw-away couldn't handle the rapidly growing load that we anticipated, but it could be written and deployed quickly. It gave us time to write a more robust implementation that could handle the load which increased four orders of magnitude.

Dave