# HP Forums

Full Version: a cute little challenge
You're currently viewing a stripped down version of our content. View the full version with proper formatting.

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 aa+bb+cc+dd = 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.

```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 = aa+bb+cc+dd.

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 ab+cd = 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,
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:
[...]
```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,

This is an interesting assumption. We generaly assume that 00 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 !

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 aa+bb+cc+dd when considering 00 to be equal to 1.

Quote:
This is an interesting assumption. We generaly assume that 00 is either 1 or undefined.

There are several ways to define 00 as a limit:

Given that we look at numbers of the form nn 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 104"?

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
```

Very nice! That's one of the reasons I like RPL.

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 = 00 + 00+00+33+11 = 1+1+1+27+1 = 31