OK, this is similar to a challenge I offered in January, but it's a bit different.

Write a program on whatever HP calculator you want to answer this question: is there a 4-digit number abcd such that a^a+b^b+c^c+d^d = abcd?

Brute force is easy. How about a non-brute force?

Don

An (easy) solution for the HP-48:

\<<

    {1 4 27 256 3125} \-> P

    \<<

        { }

        1 5 FOR a

        1 5 FOR b

        1 5 FOR c

        1 5 FOR d

          a 10 *

        b + 10 *

        c + 10 *

        d +

        P a GET

        P b GET +

        P c GET +

        P d GET +

        OVER

        IF == THEN + ELSE DROP END

        NEXT

        NEXT

        NEXT

        NEXT

    \>>

\>>

Gives the solution: { 3435 }

With 625 trials probably still using too much force.

At least a little better than testing 10,000.

Thanks for the challenge

Thomas

Nice puzzle! Let's see...

None of the digits can be larger than 5, because 6^6=46656, which is not a 4-digit number.


The digits can't all be 5, because 4*5^5 is too large. There also can't be 3 fives, because then the sum would be >= 9375, and there can be no digits larger than 5 in the right-hand side. There also can't be 2 fives, because then the sum would be >= 6250.


There can't be no fives, because four fours would give a sum of 1024, which is not a solution, and anything with no fives and less than four fours gives a sum of less than 1000, which is not a four-digit number. Ergo, there must be exactly one five.


The remaining three digits must all be less than five, so the sum of the powers can be no more than 5^5+3*4^4=3893. One five and three fours isn't a solution. One five and two fours gives a sum of >= 3637, which fails because the second digit of the sum is always too large. So there can be at most one four in the solution.


Given that there must be exactly one five and no more than one four, the sum of the powers can be no more than 5^5+4^4+2*3^3=3435, which happens to be a solution. The lower bound on the sum of the powers is 5^5=3125, so the first digit of the solution must be 3.


Given that the solution must have one five, at least one three, and at most one four, there are two groups of potential solutions: five, three, and two digits <= 3, and five, four, three, and one digit <= 3.


In the first group, with a five, at least one three, and no fours, the sum of the powers is between 3152 and 3206, so the second digit can't be a 3, so there are at most two threes, which lowers the upper bound of the sum to 3183, which means there must be at least one one, which lowers the upper bound of the sum to 3180.


So, the solution must have 5, 4, 3, and one digit between 0 and 3, or it must have 5, 3, 1, and one digit between 0 and 3. Out of those 8 potential solutions, only 5, 4, 3, 3 works. That's technically still a brute-force answer, but brute-forcing among 8 solutions is better than doing it among 9000, I guess. :-)

Edited: 29 May 2011, 3:30 a.m.

What a profound analysis! Great work!

But we'd still have to check (at most) 4! = 24
permutations for each of these 8 possible solutions.
Instead we can calculate MOD 9 on the sum.

We start with a table:

n       :     0     1     2     3     4     5

n^n     :     0     1     4    27   256  3125

n^n % 9 :     0     1     4     0     4     2

First we check: 5, 3, 1, 0..3:

    5 + 3 + 1 = 0      2 + 0 + 1 = 3

0   0 + 0 = 0            3 + 0 = 3

1   0 + 1 = 1            3 + 1 = 4

2   0 + 2 = 2            3 + 4 = 7

3   0 + 3 = 3            3 + 0 = 3

But 5,3,1,3 yields 3125+27+1+27=3,180.

No solution so far. Let's try: 5, 4, 3, 0..3:

    5 + 4 + 3 = 3      2 + 4 + 0 = 6

0   3 + 0 = 3            6 + 0 = 6

1   3 + 1 = 4            6 + 1 = 7

2   3 + 2 = 5            6 + 4 = 1

3   3 + 3 = 6            6 + 0 = 6

This leaves the only solution: 5, 4, 3, 3

But we still don't know the correct order. So here's the program for the HP-42S:

LBL "CUTE"

5

ENTER

yx

4

ENTER

yx

+

3

ENTER

yx

+

LASTx

+

END

This gives the correct answer: 3,435

Cheers

Thomas

Edited: 29 May 2011, 6:34 a.m.

There's no need to check permutations; you just brute-force check the 8 possible digit combinations (5310 5311 5312 5313 5430 5431 5432 5433), by calculating the sum of powers for each, and check if the result contains the same digits as the digit combination. 5433 yields the sum of powers 3435, which has the same digits as 5433, so 3435 is your answer.

Edited: 29 May 2011, 3:08 p.m.

My assumption was that we have the four digits a, b, c, d and the sum s = a^a+b^b+c^c+d^d.

We could calculate 10(10(10x+y)+z)+t for each permutation of a, b, c, d and compare that to s.

Or we could split s into four digits A, B, C, D and check that each is contained in the set {a, b, c, d} as you suggested. For this we could use flags with the HP-42s or POS with the HP-48.

My suggestion was to compare (a+b+c+d) % 9 with (A+B+C+D) % 9 = s % 9 as we wouldn't have to split s into four digits.

Unfortunately we'd still have a false positive with 5 3 1 3; we could leave its falsification as an exercise to the user.

Best regards

Thomas

Edited: 29 May 2011, 10:34 p.m.

That's a lot less efficient than doing it the other way around, though: if you enumerate all combinations of 4 digits, you have only 715 combinations to check, and if you restrict it to the digits 0...5, there are only 126. The logic for the efficient brute-force approach would be like this:

for (a = 0; a <= 9; a++) {

    for (b = a; b <= 9; b++) {

        for (c = b; c <= 9; c++) {

            for (d = c; d <= 9; d++) {

                s = a^a + b^b + c^c + d^d;

                t = sort_digits_ascending(s);

                if (abcd == t) print("Solution found: " + s);

            }

        }

    }

}

My first attempt was the following python script:

N = range(5+1)

for a in N:

    for b in N:

        for c in N:

            for d in N:

                if ((10*a + b)*10 + c)*10 + d == a**a + b**b + c**c + d**d:

                    print a, b, c, d

It took me a few minutes to type that and I got the result in 0m0.018s.

IMHO there's no reason to optimize that.

It took me probably an hour or so to translate that to the RPL program I already posted.

That's because I'm not too familiar with it and furthermore I fumbled a while until I succeeded

to transfer the program to the calculator using kermit.

Nothing to be proud of. Maybe a little improved since the powers are cached.

But I'm not even sure since accessing an element of a list seems to be quite slow.

It takes about 36s to complete.

Here's my last attempt for the HP-41:

 01 LBL "CUTE"      18 RCL 11           35 RCL 15           52 RCL 14                                        

 02 1               19 RCL 00           36 STO 13           53 +               

 03 STO 01          20 *                37 LBL 13           54 VIEW X          

 04 4               21 STO 06           38 RCL 07           55 RCL 10          

 05 STO 02          22 RCL 15           39 RCL 13           56 RCL IND 14      

 06 27              23 STO 12           40 +                57 +               

 07 STO 03          24 LBL 12           41 RCL 00           58 X=Y?            

 08 256             25 RCL 06           42 *                59 STOP            

 09 STO 04          26 RCL 12           43 STO 09           60 DSE 14          

 10 3125            27 +                44 RCL 08           61 GTO 14          

 11 STO 05          28 RCL 00           45 RCL IND 13       62 DSE 13          

 12 10              29 *                46 +                63 GTO 13          

 13 STO 00          30 STO 07           47 STO 10           64 DSE 12          

 14 5               31 RCL IND 11       48 RCL 15           65 GTO 12          

 15 STO 15          32 RCL IND 12       49 STO 14           66 DSE 11          

 16 STO 11          33 +                50 LBL 14           67 GTO 11          

 17 LBL 11          34 STO 08           51 RCL 09           68 END             

Now also intermediate results are cached in registers 06-10 which makes the

innermost loop shorter.

You're using a magic function "sort_digits_ascending(s)" which I couldn't find neither

within the HP-48 nor the HP-41. Both calculators lack a split-function. The HP-41 doesn't

have a built-in sort-function. So you'd have to implement that which might be a little

more than just two additions and a comparison.

While you're correct that 126 is smaller than 625 the elapsed time depends also on what you're

doing within the innermost loop. So my solution for the HP-41 could still be faster.

And then it might also take a little more to implement your solution than my rather dumb

straightforward programs.

Kind regards

Thomas

PS: Just adapted the program above for the HP-42S using RCL-arithmetic, removing line 54

and using VIEW ST X instead of line 59. I got the result within 0.06s in Free42 on my iPhone.

That's fast enough for me. Thanks a lot for making that possible.

Edited: 30 May 2011, 4:44 p.m.

It's a bit late, but I've decided to implement my idea as of yesterday night, when Thomas & Thomas came and solved the challenge nicely. (I'd gone as far as seeing there was no digit greater than five and there was only one five, and I was also thinking of sorting the digits - that's all I'll be using).

The "cuteness" of Don's problem resides in the fact that it can be solved without brute force (or at least with moderate force as in the program below) unlike, I think, "finding a 4-digit number abcd such as a^b+c^d = abcd".

%%HP: T(3)A(D)F(,);

DIR

  CLC

  \<< 1, 4,

    FOR a 1, 4,

      FOR b 1, 4,

        FOR c { a b c } DUP DUP ^ \GSLIST 3125, + N2L SORT SWAP 1, * { 5, } + SORT DUP2 == { ^ \GSLIST KILL } { DROP2 } IFTE

        NEXT

      NEXT

    NEXT

  \>>

  N2L

  \<< \->STR DUP HEAD SWAP 1, 3,

    START TAIL HEAD LASTARG

    NEXT DROP 4, \->LIST STR\->

  \>>

END

The solution is found in 17 seconds on the hp-50g, which is too much time when compared to the 36 seconds you have obtained on your HP-41 program.

Best regards,

Gerson.

Edited: 30 May 2011, 7:02 p.m.

Quote:

---

[...]
We start with a table:

n       :     0     1     2     3     4     5

n^n     :     0     1     4    27   256  3125

n^n % 9 :     0     1     4     0     4     2

---

Dear Tomas,

In your table we read that nⁿ=0 when n = 0.
This is an interesting assumption. We generaly assume that 0⁰ is either 1 or undefined.

I am always surprise how a so little detail can reveal so great philosophical aspect of day to day and primary mathematic !

These thinkings lead me to ask one stupid question.

Is twelve (when written as 0012) a four digits number ?

If the answer to this question is true, then when have to consider that 30 and 31 are also solutions of the general formulea a^a+b^b+c^c+d^d when considering 0⁰ to be equal to 1.

Quote:

---

This is an interesting assumption. We generaly assume that 0⁰ is either 1 or undefined.

---

There are several ways to define 0⁰ as a limit:

Given that we look at numbers of the form nⁿ you may consider 0 a poor choice.

Some may have noted that I cheated a little in my programs since I omitted 0. The main reason was not gain in speed

but that lists in the HP-48 start with index 1. And then again DSE skips 0.

I wouldn't consider twelve a four digits number. Otherwise what's gained with this expression compared to "smaller than 10⁴"?

Thomas

Seven seconds on the hp50g and there's still a lot of room for improvement as the inner loop is not so efficient as is could be. I have disregarded digits 0 because 0^0 is defined as 1 on the hp50g. BTW, it is defined differently in these two related OEIS sequences.

%%HP: T(3)A(D)F(,);

DIR

  CLC

  \<< 1, 4,

    FOR a a 4,

      FOR b b 4,

        FOR c { a b c } DUPDUP ^ \GSLIST 3125, + N2L SORT SWAP 1, * { 5, } + SORT DUP2 == { ^ \GSLIST KILL } { DROP2 } IFTE

        NEXT

      NEXT

    NEXT

  \>>

  N2L

  \<< \->STR 1, 4,

    FOR i DUP i i SUB SWAP

    NEXT DROP 4, \->LIST STR\->

  \>>

END

Quote:

---

{ a b c } DUPDUP ^ \GSLIST

---

Quote:

---

there's still a lot of room for improvement as the inner loop is not so efficient as it could be

---

Using the '9 MOD' trick the expensive check is avoided in most of the cases:

\<< { } 1 4

  FOR a a 4

    FOR b b 4

      FOR c { 5 } a + b + c +

        DUP DUP ^

        \GSLIST OVER

        \GSLIST OVER

        - 9 MOD

        IF 0 ==

        THEN N2L

          SORT SWAP SORT

          IF DUP2 ==

          THEN ^ \GSLIST +

          ELSE DROP2

          END

        ELSE DROP2

        END

      NEXT

    NEXT

  NEXT

\>>

I had problems using { a b c } with the HP-48. The local variables are not evaluated resulting in an algebraic expression. However adding them to the list is fine. Maybe using \->LIST is faster. Other suggestions?

The execution time dropped from about 1.5s to 0.6s using m48 on the iPhone.

Cheers

Thomas Klemm

Edited: 2 June 2011, 6:34 a.m.

Great improvement! 2.67 seconds on the hp50g.

You're right, \->LIST is faster, 2.46 seconds:

%%HP: T(3)A(D)F(,);

DIR

  CLC

  \<< { } 1, 4,

    FOR a a 4,

      FOR b b 4,

        FOR c a b c 3, \->LIST 5, + DUP DUP ^ \GSLIST OVER \GSLIST OVER - 9, MOD

          IF NOT

          THEN N2L SORT SWAP SORT

            IF DUP2 ==

            THEN ^ \GSLIST +

            ELSE DROP2

            END

          ELSE DROP2

          END

        NEXT

      NEXT

    NEXT

  \>>

  N2L

  \<< \->STR 1, 4,

    FOR i DUP i DUP SUB SWAP

    NEXT DROP 4, \->LIST STR\->

  \>>

END

Regards,

Gerson.

A naive translation to the 34s of this hp-41 program takes about 0.4 seconds to find the solution in real mode and 0.3 seconds in integer mode.

- Pauli

	001  LBL A

	002  TICKS

	003  STO I

	004  1

	005  STO 01

	006  4

	007  STO 02

	008  2

	009  7

	010  STO 03

	011  2

	012  5

	013  6

	014  STO 04

	015  3

	016  1

	017  2

	018  5

	019  STO 05

	020  1

	021  0

	022  STO 00

	023  5

	024  STO 15

	025  STO 11

	026  LBL 11

	027  RCL 11

	028  RCL* 00

	029  STO 06

	030  RCL 15

	031  STO 12

	032  LBL 12

	033  RCL 06

	034  RCL+ 12

	035  RCL* 00

	036  STO 07

	037  RCL->11

	038  RCL+->12

	039  STO 08

	040  RCL 15

	041  STO 13

	042  LBL 13

	043  RCL 07

	044  RCL+ 13

	045  RCL* 00

	046  STO 09

	047  RCL 08

	048  RCL+->13

	049  STO 10

	050  RCL 15

	051  STO 14

	052  LBL 14

	053  RCL 09

	054  RCL+ 14

	055  RCL 10

	056  RCL+->14

	057  x=? Y

	058  GTO 99

	059  DSZ 14

	060  GTO 14

	061  DSZ 13

	062  GTO 13

	063  DSZ 12

	064  GTO 12

	065  DSZ 11

	066  GTO 11

	067  RTN

	068  LBL 99

	069  TICKS

	070  RCL- I

	071  RTN

Checksum 4FEd

Quote:

---

a b c 3, \->LIST 5, +

---

Or rather?

a b c 5, 4, \->LIST

Wow, that's fast. Thanks for taking the time to measure it. Just keep in mind that here we count down from 5555 to 3435. Thus bailing out at the first occurence of a solution might not be fair. Or just be careful when comparing the figures.

Kind regards

Thomas

Oops! :-)

2.37 seconds without the unnecessesary + in the innermost loop.

About 0031... how could it be a solution?

Edited: 2 June 2011, 12:53 p.m.

Without the short cut finish it takes 0.8 seconds in real mode and 0.7 in integer mode.

- Pauli

	001  LBL A

	002  TICKS

	003  STO I

	004  1

	005  STO 01

	006  4

	007  STO 02

	008  2

	009  7

	010  STO 03

	011  2

	012  5

	013  6

	014  STO 04

	015  3

	016  1

	017  2

	018  5

	019  STO 05

	020  1

	021  0

	022  STO 00

	023  5

	024  STO 15

	025  STO 11

	026  LBL 11

	027  RCL 11

	028  RCL* 00

	029  STO 06

	030  RCL 15

	031  STO 12

	032  LBL 12

	033  RCL 06

	034  RCL+ 12

	035  RCL* 00

	036  STO 07

	037  RCL->11

	038  RCL+->12

	039  STO 08

	040  RCL 15

	041  STO 13

	042  LBL 13

	043  RCL 07

	044  RCL+ 13

	045  RCL* 00

	046  STO 09

	047  RCL 08

	048  RCL+->13

	049  STO 10

	050  RCL 15

	051  STO 14

	052  LBL 14

	053  RCL 09

	054  RCL+ 14

	055  RCL 10

	056  RCL+->14

	057  x=? Y

	058  VIEW X

	059  DSZ 14

	060  GTO 14

	061  DSZ 13

	062  GTO 13

	063  DSZ 12

	064  GTO 12

	065  DSZ 11

	066  GTO 11

	067  TICKS

	068  RCL- I

	069  RTN

Checksum F3d3

Yes, you are right, sorry for that. 31 have to be consider as a 5 digits number :

[pre] 00031 = 0⁰ + 0⁰+0⁰+3³+1¹ = 1+1+1+27+1 = 31