+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: challenge for programmable calculators (/thread-194.html)
challenge for programmable calculators - Don Shepherd - 12-21-2013 06:15 PM
Well, it's a rainy day outside, how about a new challenge for a new forum.
Find a 3-digit number (or numbers) abc such that the sum of the digits times the product of the digits equals the original number. Or, mathematically, a 3-digit number abc such that (a+b+c) X (a X b X c) = abc. The number 000 doesn't count.
All programmable calculator solutions are welcomed, including RPN, RPL, BASIC, Prime, 34s, and even non-HP programmable calculators.
The brute-force solution is relatively easy. A non-brute-force solution would greatly enlighten this rainy day.
RE: challenge for programmable calculators - kakima - 12-21-2013 06:51 PM
Do you have a non-brute-force solution?
My brute force 50g program runs in about 20 seconds and gives two nontrivial solutions (in addition to the 000 solution).
RE: challenge for programmable calculators - Don Shepherd - 12-21-2013 07:29 PM
(12-21-2013 06:51 PM)kakima Wrote: Do you have a non-brute-force solution?
My brute force 50g program runs in about 20 seconds and gives two nontrivial solutions (in addition to the 000 solution).
No, I don't yet have a non-brute-force solution, I'm hoping some clever individual might come up with one. Please post your 50g code here. Thanks.
RE: challenge for programmable calculators - kakima - 12-21-2013 08:08 PM
Let me wait a few hours. I don't want my brute force solution to deter some clever individual from coming up with a better one.
Having said that, I did come up with a simple optimization that cuts the time to about 15 seconds and eliminates the false solution as well. I suppose I should also mention that this is in UserRPL. I may try SysRPL just for the fun of it.
I've also got a RPN version that runs in under three seconds on an emulator. I'd like to get home and run it on real hardware before posting that one (the 50g is the only physical calculator I've got on me right now).
Am I right in claiming two solutions? My programs are so simple and brute force that it's hard to imagine they're wrong, but I've been wrong before...
RE: challenge for programmable calculators - Gerson W. Barbosa - 12-21-2013 08:18 PM
[quote= A non-brute-force solution would greatly enlighten this rainy day.
[/quote]
I hope the rain has gone :-)
%%HP: T(3)A(D)F(.);
\<< 1. 9.
FOR a 1. 9.
FOR b a SQ b * a b SQ * + 1. - NEG DUP SQ a b * 4. * a 100. * b 10. * + * + \v/ + a b * 2. * / DUP FP NOT NOT { DROP } { DUP 10. < { a 100. * b 10. * + + } { DROP } IFTE } IFTE
NEXT
NEXT
\>>
EVAL -->
135.
144.
after 2.9 seconds (hp 50g)
RE: challenge for programmable calculators - Don Shepherd - 12-21-2013 08:23 PM
(12-21-2013 08:08 PM)kakima Wrote: Let me wait a few hours. I don't want my brute force solution to deter some clever individual from coming up with a better one.
Having said that, I did come up with a simple optimization that cuts the time to about 15 seconds and eliminates the false solution as well. I suppose I should also mention that this is in UserRPL. I may try SysRPL just for the fun of it.
I've also got a RPN version that runs in under three seconds on an emulator. I'd like to get home and run it on real hardware before posting that one (the 50g is the only physical calculator I've got on me right now).
Am I right in claiming two solutions? My programs are so simple and brute force that it's hard to imagine they're wrong, but I've been wrong before...
Yes, 2 solutions is correct.
RE: challenge for programmable calculators - Katie Wasserman - 12-21-2013 10:26 PM
Code:
%%HP: T(3)A(D)F(.);
\<< 1. 9.
FOR a 1. 9.
FOR b a SQ b * a b SQ * + 1. - NEG DUP SQ a b * 4. * a 100. * b 10. * + * + \v/ + a b * 2. * / DUP FP NOT NOT { DROP } { DUP 10. < { a 100. * b 10. * + + } { DROP } IFTE } IFTE
NEXT
NEXT
\>>Nice use of the quadratic formula to save the inner-most loop -- compared to the brute force solution. I wonder if there's an even better way.
RE: challenge for programmable calculators - Gerson W. Barbosa - 12-21-2013 11:26 PM
(12-21-2013 10:26 PM)Katie Wasserman Wrote:Code:
%%HP: T(3)A(D)F(.);
\<< 1. 9.
FOR a 1. 9.
FOR b a SQ b * a b SQ * + 1. - NEG DUP SQ a b * 4. * a 100. * b 10. * + * + \v/ + a b * 2. * / DUP FP NOT NOT { DROP } { DUP 10. < { a 100. * b 10. * + + } { DROP } IFTE } IFTE
NEXT
NEXT
\>>
Nice use of the quadratic formula to save the inner-most loop -- compared to the brute force solution. I wonder if there's an even better way.
Perhaps one should analyze the formula and limit the outer loop (I haven't done that). BTW, I have to say "my" method is kind of cheating, since the hard work was done by W|A:
solve a*b*c*(a+b+c)==100*a+10*b+c for a, b and c
RE: challenge for programmable calculators - Don Shepherd - 12-22-2013 12:14 AM
(12-21-2013 11:26 PM)Gerson W. Barbosa Wrote:(12-21-2013 10:26 PM)Katie Wasserman Wrote:Code:
%%HP: T(3)A(D)F(.);
\<< 1. 9.
FOR a 1. 9.
FOR b a SQ b * a b SQ * + 1. - NEG DUP SQ a b * 4. * a 100. * b 10. * + * + \v/ + a b * 2. * / DUP FP NOT NOT { DROP } { DUP 10. < { a 100. * b 10. * + + } { DROP } IFTE } IFTE
NEXT
NEXT
\>>
Nice use of the quadratic formula to save the inner-most loop -- compared to the brute force solution. I wonder if there's an even better way.
Perhaps one should analyze the formula and limit the outer loop (I haven't done that). BTW, I have to say "my" method is kind of cheating, since the hard work was done by W|A:
solve a*b*c*(a+b+c)==100*a+10*b+c for a, b and c
Gerson, I've never used Wolfram Alpha, but from your link, it does not appear to give the actual answer, ie, the two numbers.
RE: challenge for programmable calculators - Gerson W. Barbosa - 12-22-2013 12:39 AM
(12-22-2013 12:14 AM)Don Shepherd Wrote: Gerson, I've never used Wolfram Alpha, but from your link, it does not appear to give the actual answer, ie, the two numbers.
Don, it gives 'c' as a function of 'a' and 'b' (third formula). This saves the outer loop, so the inner loop, albeit now a bit more complicated, is executed 81 times instead of 729 times. But I think there is still room for optimization. The BASIC program might be more clear to those not familiar with RPL:
Code:
FOR A = 1 TO 9
FOR B = 1 TO 9
T = A * A * B + A * B * B - 1
C = (SQR(T * T + 4 * A * B * (100 * A + 10 * B)) - T) / (2 * A * B)
IF INT(C) < 10 THEN IF C - INT(C) = 0 THEN PRINT 100 * A + 10 * B + C
NEXT B
NEXT ARE: challenge for programmable calculators - Don Shepherd - 12-22-2013 12:46 AM
I realize that the 17bii is not in the same league as the 50g and RPL, and is not even considered a "programmable" calculator by most (including HP), but it can solve this problem. The following solver equation stops and displays "Solution Not Found" when, ironically, it finds a solution, so you RCL ANS to see the solution. When you run it the first time, start at 111 and solve for ANS, and it finds the first solution pretty quickly. Then start at 136 and it finds the second solution quickly.
By this problem, I also wanted to discover how easy it is to use the special characters for sigma, multiply, and divide.
Code:
ANS = ∑(J:START:999:1:
IF(
0×L(A:1)+
∑(I:0:LOG(J):1:
L(B:MOD(IDIV(J:10^I):10))
+0×L(A:G(A)×G(B))
)
×G(A)=J:
L(ANS:J)÷0
:0
)
)RE: challenge for programmable calculators - Katie Wasserman - 12-22-2013 12:49 AM
Quote:I have to say "my" method is kind of cheating, since the hard work was done by W|A:
I'm pretty sure that you didn't really need WA to solve that for you
RE: challenge for programmable calculators - Don Shepherd - 12-22-2013 12:49 AM
(12-22-2013 12:39 AM)Gerson W. Barbosa Wrote:(12-22-2013 12:14 AM)Don Shepherd Wrote: Gerson, I've never used Wolfram Alpha, but from your link, it does not appear to give the actual answer, ie, the two numbers.
Don, it gives 'c' as a function of 'a' and 'b' (third formula). This saves the outer loop, so the inner loop, albeit now a bit more complicated, is executed 81 times instead of 729 times. But I think there is still room for optimization. The BASIC program might be more clear to those not familiar with RPL:
Code:
FOR A = 1 TO 9
FOR B = 1 TO 9
T = A * A * B + A * B * B - 1
C = (SQR(T * T + 4 * A * B * (100 * A + 10 * B)) - T) / (2 * A * B)
IF INT(C) < 10 THEN IF C - INT(C) = 0 THEN PRINT 100 * A + 10 * B + C
NEXT B
NEXT A
Very interesting, Gerson, thanks. BASIC I understand! I'll have to study this awhile.
RE: challenge for programmable calculators - Gerson W. Barbosa - 12-22-2013 01:17 AM
(12-22-2013 12:49 AM)Katie Wasserman Wrote: I'm pretty sure that you didn't really need WA to solve that for you
Thanks! It would really have been more fun if done by hand:
abc(a + b + c) = 100a + 10b + c
bca^2 + acb^2 + abc^2 - 100a - 10b - c = 0
abc^2 + (ab^2 + ab^2 - 1)c - (100a + 10b) = 0
...
P.S.: Why should I be accepting programming challenges when Google reminds me it's the first day of Summer down here? So far no one from Down Under, BTW :-)
![[Image: first-day-of-summer-2013-5870728519876608-hp.gif]](https://www.google.com.br/logos/doodles/2013/first-day-of-summer-2013-5870728519876608-hp.gif)
RE: challenge for programmable calculators - RMollov - 12-22-2013 01:48 AM
(12-22-2013 01:17 AM)Gerson W. Barbosa Wrote: P.S.: Why should I be accepting programming challenges when Google reminds me it's the first day of Summer down here? So far no one from Down Under, BTW :-)
Down Under we are soooo different... Haven't you noticed?
Our first days of seasons are not the same as the rest of the world.
RE: challenge for programmable calculators - Gerson W. Barbosa - 12-22-2013 01:50 AM
(12-22-2013 12:46 AM)Don Shepherd Wrote:Very short code!Code:
ANS = ∑(J:START:999:1:
IF(
0×L(A:1)+
∑(I:0:LOG(J):1:
L(B:MOD(IDIV(J:10^I):10))
+0×L(A:G(A)×G(B))
)
×G(A)=J:
L(ANS:J)÷0
:0
)
)
(12-22-2013 12:46 AM)Don Shepherd Wrote: By this problem, I also wanted to discover how easy it is to use the special characters for sigma, multiply, and divide.Unfortunately one cannot start editing other people's posts anymore to see how this is done.
RE: challenge for programmable calculators - kakima - 12-22-2013 04:41 AM
Great to see the better-than-brute-force solutions.
I offer these brute force solutions as baselines for anyone else wishing to try the problem. First, UserRPL for the 50g runs in about 15 seconds:
Code:
<<
1. 9. FOR a
1. 9. FOR b
1. 9. FOR c
a 10. * b + 10. * c +
IF DUP a b c + + a b c * * * # THEN DROP END
NEXT
NEXT
NEXT
>>SysRPL for the 50g runs in just under two seconds:
Code:
!RPL !NO CODE
::
9 1LAMBIND
BEGIN
10 ONE_DO
10 ONE_DO
1GETLAM #10* JINDEX@ #+ #10* INDEX@ #+
1GETLAM JINDEX@ INDEX@ #+ #+
1GETLAM JINDEX@ INDEX@ #* #* #*
OVER #= ITE
UNCOERCE
DROP
LOOP
LOOP
1GETLAM #1- DUP 1PUTLAM #0= UNTIL
ABND
;
@RPN for the 15C. Runs in ten seconds on the 15C+. For the 15C LE you'll have to replace the PSE with R/S then press R/S to see the other solutions.
Code:
LBL A
9
STO 0
STO 1
STO 2
LBL 1
EEX
1
RCL* 0
RCL+ 1
EEX
1
*
RCL+ 2
RCL 0
RCL+ 1
RCL+ 2
RCL* 0
RCL* 1
RCL* 2
x=y?
PSE
DSE 2
GTO 1
9
STO 2
DSE 1
GTO 1
STO 1
DSE 0
GTO 1
CLxRPN for the WP 34S gives the first solution in about three seconds. R/S for the second solution almost instantaneously. Another R/S gives 0 almost instantaneously.
Code:
LBL D
#009
STO 00
STO 01
STO 02
RCL 00
SDL 001
RCL+ 01
SDL 001
RCL+ 02
RCL 00
RCL+ 01
RCL+ 02
RCL* 00
RCL* 01
RCL* 02
x=? Y
STOP
DSZ 02
BACK 014
#009
STO 02
DSZ 01
BACK 018
STO 01
DSZ 00
BACK 021
CLx
ENDRE: challenge for programmable calculators - Gerson W. Barbosa - 12-22-2013 05:30 AM
(12-22-2013 04:41 AM)kakima Wrote: RPN for the WP 34S gives the first solution in about three seconds. R/S for the second solution almost instantaneously. Another R/S gives 0 almost instantaneously.
Code:
LBL D
#009
STO 00
STO 01
STO 02
RCL 00
SDL 001
RCL+ 01
SDL 001
RCL+ 02
RCL 00
RCL+ 01
RCL+ 02
RCL* 00
RCL* 01
RCL* 02
x=? Y
STOP
DSZ 02
BACK 014
#009
STO 02
DSZ 01
BACK 018
STO 01
DSZ 00
BACK 021
CLx
END
Hi,
My first wp34s attempt using the built-in quadratic solver is 43 steps long (but can be reduced to 40 by eliminating three labels and using BACK and SKIP instructions instead). About 3.3 seconds to show 144, then 135 is shown instantly after R/S. Apparently no gain...
RE: challenge for programmable calculators - Thomas Klemm - 12-22-2013 03:01 PM
(12-21-2013 06:15 PM)Don Shepherd Wrote: A non-brute-force solution would greatly enlighten this rainy day.
This solution for the HP-42S reduces the amount of trials from 729 to 86 by using the symmetry of the expression.
Registers:
00: a.009
01: b.009
02: c.009
03: a
04: d = 10*a
05: e = a+b
06: f = a*b
07: g = 10*(d+b) = 10*(10*a+b)
Code:
00 { 85-Byte Prgm}
01 1.009
02 STO 00 ; a.009 = 1.009
03 LBL 00
04 RCL 00 ; a.009
05 STO 01 ; b.009 = a.009
06 IP ; a
07 STO 03 ; a
08 10
09 ×
10 STO 04 ; d = 10*a
11 LBL 01
12 RCL 03 ; a
13 STO 05 ; e = a
14 STO 06 ; f = a
15 RCL 01 ; b.009
16 STO 02 ; c.009 = b.009
17 IP ; b
18 STO+ 05 ; e = a+b
19 STO× 06 ; f = a*b
20 RCL+ 04 ; d+b = 10*a+b
21 10
22 ×
23 STO 07 ; g = 10*(d+b) = 10*(10*a+b) = ab0
24 LBL 02
25 RCL 07 ; ab0
26 RCL 02 ; ab0 c.009
27 IP ; ab0 c
28 + ; abc
29 LASTX ; abc c
30 ENTER ; abc c c
31 RCL+ 05 ; abc c a+b+c
32 × ; abc (a+b+c)*c
33 RCL× 06 ; abc (a+b+c)*a*b*c
34 1E3 ; abc (a+b+c)*a*b*c 1000
35 X≤Y? ; (a+b+c)*a*b*c ≥ 1000 ?
36 GTO 03
37 R↓ ; abc (a+b+c)*a*b*c
38 X=Y? ; abc = (a+b+c)*a*b*c ?
39 STOP ; found a solution
40 ISG 02 ; c++
41 GTO 02
42 LBL 03
43 RCL 01 ; b.009
44 RCL 02 ; b.009 c.009
45 X=Y? ; b.009 = c.009 ?
46 GTO 04
47 ISG 01 ; b++
48 GTO 01
49 LBL 04
50 RCL 00 ; a.009
51 RCL 01 ; a.009 b.009
52 X=Y? ; a.009 = b.009 ?
53 GTO 05
54 ISG 00 ; a++
55 GTO 00
56 LBL 05
57 ENDSince we're lucky and the digits of the solutions are in the correct order I'm cheating a little as well and leave that part as an exercise.
Cheers and thanks for the challenge
Thomas
PS: This Python program does the same.
Code:
for a in range(1,10):
d = 10*a
for b in range(a,10):
e = a+b
f = a*b
g = 10*(d+b)
for c in range(b,10):
h = (e+c)*f*c
if h < 1000:
if h == g+c:
print h
else:
break
else:
continue
if b == c:
break
else:
continue
if a == b:
breakRE: challenge for programmable calculators - Don Shepherd - 12-22-2013 03:20 PM
Thanks Kakima, Gerson, Katie, and Thomas. Those are some very thought-provoking solutions to this challenge.