challenge for programmable calculators

[Don Shepherd]

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.

[kakima]

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).

[Don Shepherd]

(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.

[kakima]

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

[Gerson W. Barbosa]

[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)

[Don Shepherd]

(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.

[Katie Wasserman]

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.

[Gerson W. Barbosa]

(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

[Don Shepherd]

(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.

[Gerson W. Barbosa]

(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

[Don Shepherd]

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

[Katie Wasserman]

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

[Don Shepherd]

(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.

[Gerson W. Barbosa]

(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 :-)

[RMollov]

(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.

[Gerson W. Barbosa]

(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.

[kakima]

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

[Gerson W. Barbosa]

(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...

[Thomas Klemm]

(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

[Don Shepherd]

Thanks Kakima, Gerson, Katie, and Thomas. Those are some very thought-provoking solutions to this challenge.