▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
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
▼
Posts: 735
Threads: 34
Joined: May 2007
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
Posts: 727
Threads: 43
Joined: Jul 2005
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.
▼
Posts: 735
Threads: 34
Joined: May 2007
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.
▼
Posts: 727
Threads: 43
Joined: Jul 2005
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.
▼
Posts: 735
Threads: 34
Joined: May 2007
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.
▼
Posts: 727
Threads: 43
Joined: Jul 2005
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);
}
}
}
}
▼
Posts: 735
Threads: 34
Joined: May 2007
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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,
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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
▼
Posts: 735
Threads: 34
Joined: May 2007
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
▼
Posts: 735
Threads: 34
Joined: May 2007
Quote:
a b c 3, \->LIST 5, +
Or rather?
a b c 5, 4, \->LIST
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Oops! :-)
2.37 seconds without the unnecessesary + in the innermost loop.
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
▼
Posts: 735
Threads: 34
Joined: May 2007
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
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
Posts: 260
Threads: 0
Joined: Oct 2008
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 nn=0 when n = 0.
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 !
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 aa+bb+cc+dd when considering 00 to be equal to 1.
▼
Posts: 735
Threads: 34
Joined: May 2007
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
Posts: 1,193
Threads: 43
Joined: Jul 2005
About 0031... how could it be a solution?
Edited: 2 June 2011, 12:53 p.m.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
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
|