HP Forum Archive 20

[ Return to Index | Top of Index ]

a cute little challenge Message #1 Posted by Don Shepherd on 28 May 2011, 9:30 p.m. 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

Re: a cute little challenge Message #2 Posted by Thomas Klemm on 28 May 2011, 11:14 p.m., in response to message #1 by Don Shepherd 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

Re: a cute little challenge Message #3 Posted by Thomas Okken on 29 May 2011, 3:07 a.m., in response to message #1 by Don Shepherd 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.

Re: a cute little challenge Message #4 Posted by Thomas Klemm on 29 May 2011, 5:51 a.m., in response to message #3 by Thomas Okken 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.

Re: a cute little challenge Message #5 Posted by Thomas Okken on 29 May 2011, 3:02 p.m., in response to message #4 by Thomas Klemm 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.

Re: a cute little challenge Message #6 Posted by Thomas Klemm on 29 May 2011, 10:20 p.m., in response to message #5 by Thomas Okken 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.

Re: a cute little challenge Message #7 Posted by Thomas Okken on 29 May 2011, 11:13 p.m., in response to message #6 by Thomas Klemm 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); } } } }

Re: a cute little challenge Message #8 Posted by Thomas Klemm on 30 May 2011, 3:56 p.m., in response to message #7 by Thomas Okken 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.

Re: a cute little challenge Message #9 Posted by Gerson W. Barbosa on 30 May 2011, 6:59 p.m., in response to message #8 by Thomas Klemm 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.

Re: a cute little challenge Message #10 Posted by Gerson W. Barbosa on 31 May 2011, 7:23 p.m., in response to message #9 by Gerson W. Barbosa 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

Re: a cute little challenge Message #11 Posted by Thomas Klemm on 2 June 2011, 6:18 a.m., in response to message #10 by Gerson W. Barbosa 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.

Re: a cute little challenge Message #12 Posted by Gerson W. Barbosa on 2 June 2011, 8:35 a.m., in response to message #11 by Thomas Klemm 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.

Re: a cute little challenge Message #13 Posted by Thomas Klemm on 2 June 2011, 9:22 a.m., in response to message #12 by Gerson W. Barbosa Quote: a b c 3, \->LIST 5, + Or rather? a b c 5, 4, \->LIST

Re: a cute little challenge Message #14 Posted by Gerson W. Barbosa on 2 June 2011, 10:28 a.m., in response to message #13 by Thomas Klemm Oops! :-) 2.37 seconds without the unnecessesary + in the innermost loop.

Re: a cute little challenge Message #15 Posted by Paul Dale on 2 June 2011, 8:58 a.m., in response to message #8 by Thomas Klemm 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

Re: a cute little challenge Message #16 Posted by Thomas Klemm on 2 June 2011, 9:44 a.m., in response to message #15 by Paul Dale 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

Re: a cute little challenge Message #17 Posted by Paul Dale on 2 June 2011, 6:18 p.m., in response to message #16 by Thomas Klemm 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

Re: a cute little challenge Message #18 Posted by C.Ret on 31 May 2011, 4:39 a.m., in response to message #4 by Thomas Klemm 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.

Re: a cute little challenge Message #19 Posted by Thomas Klemm on 31 May 2011, 8:01 a.m., in response to message #18 by C.Ret 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

Re: a cute little challenge Message #20 Posted by Andrés C. Rodríguez (Argentina) on 2 June 2011, 12:52 p.m., in response to message #18 by C.Ret About 0031... how could it be a solution? Edited: 2 June 2011, 12:53 p.m.

Re: a cute little challenge Message #21 Posted by C.Ret on 3 June 2011, 8:55 a.m., in response to message #20 by Andrés C. Rodríguez (Argentina) 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

[ Return to Index | Top of Index ]

Go back to the main exhibit hall