challenge for programmable calculators
12-21-2013, 06:15 PM
Post: #1
 Don Shepherd Senior Member Posts: 532 Joined: Dec 2013
challenge for programmable calculators
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.
12-21-2013, 06:51 PM
Post: #2
 kakima Junior Member Posts: 41 Joined: Dec 2013
RE: challenge for programmable calculators
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).
12-21-2013, 07:29 PM
Post: #3
 Don Shepherd Senior Member Posts: 532 Joined: Dec 2013
RE: challenge for programmable calculators
(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.
12-21-2013, 08:08 PM
Post: #4
 kakima Junior Member Posts: 41 Joined: Dec 2013
RE: challenge for programmable calculators
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...
12-21-2013, 08:18 PM
Post: #5
 Gerson W. Barbosa Senior Member Posts: 1,056 Joined: Dec 2013
RE: challenge for programmable calculators
[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)
12-21-2013, 08:23 PM
Post: #6
 Don Shepherd Senior Member Posts: 532 Joined: Dec 2013
RE: challenge for programmable calculators
(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.
12-21-2013, 10:26 PM
Post: #7
 Katie Wasserman Super Moderator Posts: 626 Joined: Dec 2013
RE: challenge for programmable calculators
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.

-katie

12-21-2013, 11:26 PM (This post was last modified: 12-21-2013 11:31 PM by Gerson W. Barbosa.)
Post: #8
 Gerson W. Barbosa Senior Member Posts: 1,056 Joined: Dec 2013
RE: challenge for programmable calculators
(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
12-22-2013, 12:14 AM
Post: #9
 Don Shepherd Senior Member Posts: 532 Joined: Dec 2013
RE: challenge for programmable calculators
(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.
12-22-2013, 12:39 AM (This post was last modified: 12-22-2013 12:40 AM by Gerson W. Barbosa.)
Post: #10
 Gerson W. Barbosa Senior Member Posts: 1,056 Joined: Dec 2013
RE: challenge for programmable calculators
(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
12-22-2013, 12:46 AM
Post: #11
 Don Shepherd Senior Member Posts: 532 Joined: Dec 2013
RE: challenge for programmable calculators
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                )             )
12-22-2013, 12:49 AM
Post: #12
 Katie Wasserman Super Moderator Posts: 626 Joined: Dec 2013
RE: challenge for programmable calculators
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

-katie

12-22-2013, 12:49 AM
Post: #13
 Don Shepherd Senior Member Posts: 532 Joined: Dec 2013
RE: challenge for programmable calculators
(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.
12-22-2013, 01:17 AM (This post was last modified: 12-22-2013 01:36 AM by Gerson W. Barbosa.)
Post: #14
 Gerson W. Barbosa Senior Member Posts: 1,056 Joined: Dec 2013
RE: challenge for programmable calculators
(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 :-)

12-22-2013, 01:48 AM (This post was last modified: 12-22-2013 01:53 AM by RMollov.)
Post: #15
 RMollov Member Posts: 201 Joined: Dec 2013
RE: challenge for programmable calculators
(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.
12-22-2013, 01:50 AM
Post: #16
 Gerson W. Barbosa Senior Member Posts: 1,056 Joined: Dec 2013
RE: challenge for programmable calculators
(12-22-2013 12:46 AM)Don Shepherd Wrote:
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                )             )
Very short code!

(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.
12-22-2013, 04:41 AM
Post: #17
 kakima Junior Member Posts: 41 Joined: Dec 2013
RE: challenge for programmable calculators
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 CLx

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
12-22-2013, 05:30 AM (This post was last modified: 12-22-2013 05:57 AM by Gerson W. Barbosa.)
Post: #18
 Gerson W. Barbosa Senior Member Posts: 1,056 Joined: Dec 2013
RE: challenge for programmable calculators
(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...
12-22-2013, 03:01 PM (This post was last modified: 12-22-2013 03:58 PM by Thomas Klemm.)
Post: #19
 Thomas Klemm Senior Member Posts: 1,148 Joined: Dec 2013
RE: challenge for programmable calculators
(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 END

Since 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:         break
12-22-2013, 03:20 PM
Post: #20
 Don Shepherd Senior Member Posts: 532 Joined: Dec 2013
RE: challenge for programmable calculators
Thanks Kakima, Gerson, Katie, and Thomas. Those are some very thought-provoking solutions to this challenge.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)