challenge for programmable calculators

[Katie Wasserman]

Quote:symmetry of the expression

Can you explain why you can break out of the loops early? While you'll get the right answer what's the mathematical reasoning behind it? If \( abc(a + b + c) = 100a + 10b + c \) were symmetric wouldn't you be able to swap positions of the variables without changing the results?

[Thomas Klemm]

(12-22-2013 04:40 PM)Katie Wasserman Wrote:  

Quote:symmetry of the expression

Can you explain why you can break out of the loops early? While you'll get the right answer what's the mathematical reasoning behind it? If \( abc(a + b + c) = 100a + 10b + c \) were symmetric wouldn't you be able to swap positions of the variables without changing the results?

I was using the symmetry of \(abc(a + b + c)\) to bail out early for values ≥ 1000. We can do that since a ≤ b ≤ c. After noticing that (1 7 9) is too high it's still necessary to check (1 8 8) but we can skip the next value (1 9 9) since that is surely higher. For the same reason we don't need to check values after we noticed that (5 5 5) is too high.

I'm giving you here a list of all the checks that are performed (numbers in red are ≥ 1000):
a b c : \(abc(a + b + c)\)
1 1 1 : 3
1 1 2 : 8
1 1 3 : 15
1 1 4 : 24
1 1 5 : 35
1 1 6 : 48
1 1 7 : 63
1 1 8 : 80
1 1 9 : 99
1 2 2 : 20
1 2 3 : 36
1 2 4 : 56
1 2 5 : 80
1 2 6 : 108
1 2 7 : 140
1 2 8 : 176
1 2 9 : 216
1 3 3 : 63
1 3 4 : 96
1 3 5 : 135
1 3 6 : 180
1 3 7 : 231
1 3 8 : 288
1 3 9 : 351
1 4 4 : 144
1 4 5 : 200
1 4 6 : 264
1 4 7 : 336
1 4 8 : 416
1 4 9 : 504
1 5 5 : 275
1 5 6 : 360
1 5 7 : 455
1 5 8 : 560
1 5 9 : 675
1 6 6 : 468
1 6 7 : 588
1 6 8 : 720
1 6 9 : 864
1 7 7 : 735
1 7 8 : 896
1 7 9 : 1071
1 8 8 : 1088
2 2 2 : 48
2 2 3 : 84
2 2 4 : 128
2 2 5 : 180
2 2 6 : 240
2 2 7 : 308
2 2 8 : 384
2 2 9 : 468
2 3 3 : 144
2 3 4 : 216
2 3 5 : 300
2 3 6 : 396
2 3 7 : 504
2 3 8 : 624
2 3 9 : 756
2 4 4 : 320
2 4 5 : 440
2 4 6 : 576
2 4 7 : 728
2 4 8 : 896
2 4 9 : 1080
2 5 5 : 600
2 5 6 : 780
2 5 7 : 980
2 5 8 : 1200
2 6 6 : 1008
3 3 3 : 243
3 3 4 : 360
3 3 5 : 495
3 3 6 : 648
3 3 7 : 819
3 3 8 : 1008
3 4 4 : 528
3 4 5 : 720
3 4 6 : 936
3 4 7 : 1176
3 5 5 : 975
3 5 6 : 1260
3 6 6 : 1620
4 4 4 : 768
4 4 5 : 1040
4 5 5 : 1400
5 5 5 : 1875

But of course the digits of these values should be sorted as well when comparing them to \(100a + 10b + c\). I just noticed that with these two solutions (135 and 144) it's not necessary to do that as they are already in the correct order. So I was lazy and left that as an exercise.

Kind regards
Thomas

[Thomas Klemm]

(12-22-2013 05:30 AM)Gerson W. Barbosa Wrote:  About 3.3 seconds to show 144, then 135 is shown instantly after R/S. Apparently no gain...

Using an HP-41: About 13 seconds to show 135, then after 5 seconds 144 was shown. The whole program needed about 1 minute to finish.

Cheers
Thomas

Code:


1.009
STO 00
LBL 00
RCL 00
STO 01
INT
STO 03
10
*
STO 04
LBL 01
RCL 03
STO 05
STO 06
RCL 01
STO 02
INT
ST+ 05
ST* 06
RCL 04
+
10
*
STO 07
LBL 02
RCL 07
RCL 02
INT
+
LASTX
LASTX
RCL 05
+
*
RCL 06
*
1E3
X<=Y?
GTO 03
RDN
X=Y?
STOP
ISG 02
GTO 02
LBL 03
RCL 01
RCL 02
X=Y?
GTO 04
ISG 01
GTO 01
LBL 04
RCL 00
RCL 01
X=Y?
GTO 05
ISG 00
GTO 00
LBL 05
END

[Gerson W. Barbosa]

Just for the record, here is my wp34s program:

Code:

001:      LBL A
002:      9
003:      STO 01
004:      9
005:      STO 02
006:      RCL 01
007:      RCL[times] 02
008:      RCL 01
009:      x[^2]
010:      RCL[times] 02
011:      RCL 02
012:      x[^2]
013:      RCL[times] 01
014:      +
015:      DEC X
016:      RCL 01
017:      SDL 001
018:      RCL+ 02
019:      SDL 001
020:      +/-
021:      SLVQ
022:      x[<->] Y
023:      FP?
024:      SKIP 011
025:      9
025:      x<? Y
027:      SKIP 008
028:      x[<->] Y
029:      RCL 02
030:      SDL 001
031:      +
032:      RCL 01
033:      SDL 002
034:      +
035:      STOP
036:      DSE 02
037:      BACK 031
038:      DSE 01
039:      BACK 035
040:      END

A --> 144 ; first solution ( ~ 3 sec )
R/S --> 135 ; second solution
R/S --> 9 ; no more solutions

It seems the complexity of the inner loop outweighs the gain obtained by the elimination of the third loop.

[Thomas Klemm]

(12-22-2013 07:03 PM)Gerson W. Barbosa Wrote:  It seems the complexity of the inner loop outweighs the gain obtained by the elimination of the third loop.

Quote:premature optimization is the root of all evil

-- Donald Knuth

[Gerson W. Barbosa]

(12-22-2013 07:12 PM)Thomas Klemm Wrote:  

(12-22-2013 07:03 PM)Gerson W. Barbosa Wrote:  It seems the complexity of the inner loop outweighs the gain obtained by the elimination of the third loop.

Quote:premature optimization is the root of all evil

-- Donald Knuth

I thought love for money was that :-)

[Katie Wasserman]

Quote:I was using the symmetry of abc(a+b+c) to bail out early for values ≥ 1000. We can do that since a ≤ b ≤ c.

Okay, I see the symmetry that you're using and the partial ordering. But I don't see why you don't need to test for the reverse digit ordering. For example, in 2 4 7 you test if 728 matches 247, but you don't test if 728 matches 742. In looking at the Python code, I don't see that test in there.

Am I still not understanding your speedup method or is there a bug in the code?

[Thomas Klemm]

(12-22-2013 09:48 PM)Katie Wasserman Wrote:  

Quote:I was using the symmetry of abc(a+b+c) to bail out early for values ≥ 1000. We can do that since a ≤ b ≤ c.

Okay, I see the symmetry that you're using and the partial ordering. But I don't see why you don't need to test for the reverse digit ordering. For example, in 2 4 7 you test if 728 matches 247, but you don't test if 728 matches 742. In looking at the Python code, I don't see that test in there.

Am I still not understanding your speedup method or is there a bug in the code?

A lot of the possibilities can be excluded not because they don't match the criteria but simply because the value is too big. We use the fact that the function \(f(a, b, c) = abc(a+b+c)\) is both symmetric and monotonous. Thus instead of 729 cases we only have to check the 86 cases I've listed.

What's missing (and you may call that cheating or a bug) is that in case of 2 4 7 the value 728 should be ordered to 278 before comparing it to 247. If these two match then 728 would be a solution.
Another possibility is to split 728 into 7 2 8 and check whether (7+2+8)*7*2*8 = 1904 is the same as 728.

Since that operation is expensive we could perform it only when the difference 728 - 247 = 481 is 0 modulo 9. This reduces the set to only 15 cases:
1 1 1 : 3
1 1 4 : 24
1 1 7 : 63
1 2 5 : 80
1 2 6 : 108
1 3 5 : 135
1 4 4 : 144
1 4 7 : 336
1 7 7 : 735
2 2 5 : 180
2 2 7 : 308
2 3 4 : 216
2 4 8 : 896
3 3 3 : 243
4 4 4 : 768

In this list we can easily spot the solutions. Thus the last step may be omitted.

Cheers
Thomas

[David Hayden]

SySRPL with a twist:

Code:


::
  TEN ONE_DO (DO)
    INDEX@
    TEN ZERO_DO (DO)
        TEN ZERO_DO (DO)
            INDEX@ OVER #* JINDEX@ #* ( a*b*c )
            INDEX@ 3PICK #+ JINDEX@ #+ ( a+b+c )
            #*
            OVER ONEHUNDRED #* JINDEX@ TEN #* #+ INDEX@ #+ ( abc )
            OVER #= ITE ( a abc )
                 SWAP DROP
        LOOP
    LOOP
    DROP
  LOOP
;

0.02 seconds on my RPL32 interpreter running on my PC.

[kakima]

Ah, excellent use of the stack to get rid of the local variable. You can also replace the two ZERO_DO instructions with ONE_DO since if any of the digits are zero then (a+b+c)*a*b*c is zero. That cuts the time down to about 2.2 seconds on a real 50g.

[Gerson W. Barbosa]

(12-24-2013 06:38 AM)kakima Wrote:  Ah, excellent use of the stack to get rid of the local variable. You can also replace the two ZERO_DO instructions with ONE_DO since if any of the digits are zero then (a+b+c)*a*b*c is zero. That cuts the time down to about 2.2 seconds on a real 50g.

Assuming c = 1 (the lowest possible integer value for c) we can see by the table that b cannot be greater than 7 when a ranges from 1 to 9 (or, conversely, if b ranges from 1 to 9 a will not be able to be 8 or 9, otherwise the result will exceed 999).

a | b | a*b*c*(a + b + c)
--+--+------------------
9 | 9 | 1539
9 | 8 | 1296
9 | 7 | 1071
9 | 6 | 864
8 | 9 | 1296
8 | 8 | 1088
8 | 7 | 896
7 | 9 | 1071
7 | 8 | 896
...
Thus, we can limit either loop to 7. For instance:

Code:

%%HP: T(3)A(D)F(.);
\<< 1. 7.
  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
\>>

TEVAL

3: 135.
2: 144.
1: s:2.2434 (Real hp 50g)

Comparing with a plain brute-force solution:

Code:


%%HP: T(3)A(D)F(.);
\<< 1. 9.
  FOR a 1. 9.
    FOR b 1. 9.
      FOR c a b * c * a b + c + * a 10. * b + 10. * c + - NOT { 100. a * 10. b * + c + } IFT
      NEXT
    NEXT
  NEXT
\>>

TEVAL
3: 135.
2: 144.
1: s:14.3193

That is, the first program performs 63 trials in the same time the second program does about 114 tests, which means the more complicated inner loop involving root extraction requires about 81% more time to execute. All in all, not so bad at all...

[cruff]

(12-21-2013 06:15 PM)Don Shepherd Wrote:  A non-brute-force solution would greatly enlighten this rainy day.

I believe I have the proof using a bit of basic number theory. It has been 30 years or so since I took my number theory class, so if anyone spots an error, please provide a correction! By the way, does anyone know of a way to number the equations nicely near the margin as is done in texts?

Definition 1: Let \(a, b, c\) be integers such that: \(1 \le a,b,c \le 9\)
Equation 1:
\[abc(a+b+c) = 100a + 10b + c\]
Note that \(a+b+c\) is present on both sides and rewrite the equation a bit:
\begin{align}
abc(a+b+c) &= 99a+9b+(a+b+c)\\
abc &= \frac{9(11a+b)+(a+b+c)}{(a+b+c)}\\
abc &= \frac{9(11a+b)}{(a+b+c)} + 1\end{align}
Equation 2:
\[abc-1 = \frac{9(11a+b)}{a+b+c}\]
Since we are dealing exclusively with positive non-zero integers, both \(abc-1\) and \(\frac{9(11a+b)}{a+b+c}\) must both be integral. This means that the term \(a+b+c\) must be a factor of \(9(11a+b)\). Because \(9(11a+b)\) is > 1 by definition 1, the unique factorization theorem states that it is a product of primes and the factorization is unique. Thus the factors are \(3, 3^2\) and \(11a + b\).

We won't tackle the determination of if \(11a + b\) is prime, but will instead show a contradiction results:
\begin{align}
a+b+c &= 11a+b\\
c &= 10a\end{align}Which contradicts definition 1.

Next we examine if \(a+b+c=3\). This implies that \(a=1\), \(b=1\) and \(c=1\), which leads to a contradiction of equation 1.

This leaves the \(a+b+c=9\) possibility. Substituting into equation 2 produces:
\begin{align}
abc-1 &= \frac{9(11a+b)}{(a+b+c)}\\
abc-1 &= \frac{9(11a+b)}{9}\\
abc-1 &= 11a+b\end{align}
Now we solve for \(c\):
\begin{align}
abc &= 11a+b+1\\
c &= \frac{11a+b+1}{ab}\\
c &= \frac{11a}{ab}+\frac{b}{ab}+\frac1{ab}\\
c &= \frac{11}b+\frac{b+1}{ab}\\
c &= \frac{11}b+\frac{\frac{b+1}a}b\\
c &= \frac{11+\frac{b+1}a}b\\\end{align}
Since we are dealing only with non-zero positive integers, this means b must evenly divide \(11+\frac{b+1}a\). Therefore, there exists some integer \(n\), \(n > 0\), such that:
\[11+\frac{b+1}a = nb\]
Solve for \(b\):
\begin{align}
11+\frac{b+1}a &= nb\\
11a+b+1 &= anb\\
11a+1 &= (an-1)b\\
\frac{11a+1}{an-1} &= b\end{align}
If \(a+b+c=9\), this implies that \(1 \le a,b,c \le 7\) and thus:
Equation 3:
\[1 \le \frac{11a+1}{an-1} \le 7\]
Substitution of the seven possible values of \(a\) into equation 3 and using the unique factorization theorem for the resulting values of the numerator \(11a+1\) limit the search space for possible values of \(n\) that result in integers for \(b\). Back substitution into equation 1 produces the two solutions and a number of contradictions without too much effort. I wish I could have proved that \(a\) must be \(1\), which would have further limited the search for n by a factor of 7, but that escapes my aging brain at the moment.

[radwilliams]

I think I've found an equivalent numerical solution but not an identical solution (the order of operations is critical otherwise it is 0=0 and that is not a valid solution).

If you first expand the left side of (a+b+c)*(a*b*c) = abc

a^2+b^2+c^2 + 2*(a*b + a*c + b*c) = abc, now let a=b=0 and c=1

0^2 + 0^2 + 1^2 + 2*( 0 + 0 + 0 ) = 001

1 = 001 could be a solution it all depends on if '1' alone is the same as 001? Food for thought.

Happy Holidays to all, Ronald Williams

[Gerson W. Barbosa]

(12-24-2013 04:52 PM)Gerson W. Barbosa Wrote:  

Code:

%%HP: T(3)A(D)F(.);
\<< 1. 7.
  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
\>>

TEVAL

3: 135.
2: 144.
1: s:2.2434 (Real hp 50g)

We can safely reduce the number of trials from 63 to 42:

Code:

%%HP: T(3)A(D)F(.);
\<< 1. 7.
  FOR a a 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
\>>

TEVAL

3: 135.
2: 144.
1: s:1.5228 (Real hp 50g)

This is now equivalent to reducing the number of trials from 729 down to 77 or 78 when compared to the plain brute-force solution, even considering the greater complexity of the innermost loop, at least for the real hp 50g.

[Gerson W. Barbosa]

(12-24-2013 05:43 PM)cruff Wrote:  Substitution of the seven possible values of \(a\) into equation 3 and using the unique factorization theorem for the resulting values of the numerator \(11a+1\) limit the search space for possible values of \(n\) that result in integers for \(b\). Back substitution into equation 1 produces the two solutions and a number of contradictions without too much effort. I wish I could have proved that \(a\) must be \(1\), which would have further limited the search for n by a factor of 7, but that escapes my aging brain at the moment.

Using two of your conclusions,
\begin{align}
c &= \frac{11+\frac{b+1}a}b\\\end{align}
and
\begin{align}
a+b+c=9\end{align}
one can write the following RPL program,

Code:

%%HP: T(3)A(D)F(.);
\<< 1. 7.
  FOR a 1. 7.
    FOR b b 1. + a / 11. + b / DUP FP NOT NOT { DROP } { DUP 9. a - b - == { a 100. * b 10. * + + } { DROP } IFTE } IFTE
    NEXT
  NEXT
\>>

which finds both solutions in 0.6675 seconds on the real hp 50g. That's about a 22-time improvement over the plain brute-force solution. This would have been even faster if all your conclusions were taken into account (if a program would be necessary at all).
Quite impressive!

[Thomas Klemm]

(12-24-2013 05:43 PM)cruff Wrote:  I wish I could have proved that \(a\) must be \(1\), which would have further limited the search for n by a factor of 7, but that escapes my aging brain at the moment.

That's brilliant! We can now use Gerson's idea and solve the quadratic equation for b:
\[ ab^2+(1+a^2-9a)b+11a+1=0\]
The determinant \((1+a^2-9a)^2-4a(11a+1)\) is only positive for a = 1 which leads to the well known solutions b = 3 and b = 4.

Here's a program for the HP-42S:

Code:


00 { 56 Byte Prgm }
01 1.007
02 STO 00
03 LBL 00
04 11
05 RCL 00
06 IP
07 STO 01
08 STO 02
09 1/X
10 +
11 STO* 02
12 9
13 LASTX
14 RCL+ 01
15 -
16 2
17 /
18 ENTER
19 ENTER
20 X^2
21 R^
22 -
23 X<0?
24 GTO 01
25 SQRT
26 STO- ST Z
27 +
28 RCL 02
29 STO+ ST Z
30 +
31 9
32 STO* ST Z
33 *
34 STOP
35 LBL 01
36 ISG 00
37 GTO 00
38 END

Cheers
Thomas

[cruff]

(12-24-2013 07:45 PM)Thomas Klemm Wrote:  That's brilliant! We can now use Gerson's idea and solve the quadratic equation for b: ...

Doh! Should have been obvious, but I was up too late last night working on it. Thanks!

[David Hayden]

I'm not sure if this helps in any way, but if C is odd then A and B must also be odd.

[Han]

(12-24-2013 07:45 PM)Thomas Klemm Wrote:  

(12-24-2013 05:43 PM)cruff Wrote:  I wish I could have proved that \(a\) must be \(1\), which would have further limited the search for n by a factor of 7, but that escapes my aging brain at the moment.

That's brilliant! We can now use Gerson's idea and solve the quadratic equation for b:
\[ ab^2+(1+a^2-9a)b+11a+1=0\]
The determinant \((1+a^2-9a)^2-4a(11a+1)\) is only positive for a = 1 which leads to the well known solutions b = 3 and b = 4.

Here's a program for the HP-42S:

Code:


00 { 56 Byte Prgm }
01 1.007
02 STO 00
03 LBL 00
04 11
05 RCL 00
06 IP
07 STO 01
08 STO 02
09 1/X
10 +
11 STO* 02
12 9
13 LASTX
14 RCL+ 01
15 -
16 2
17 /
18 ENTER
19 ENTER
20 X^2
21 R^
22 -
23 X<0?
24 GTO 01
25 SQRT
26 STO- ST Z
27 +
28 RCL 02
29 STO+ ST Z
30 +
31 9
32 STO* ST Z
33 *
34 STOP
35 LBL 01
36 ISG 00
37 GTO 00
38 END

Cheers
Thomas

Once you've solved a problem completely using mathematics, is there really any need for a program? I always held the opinion that programs were useful when we reached a mathematical stumbling block.

[Gerson W. Barbosa]

(12-25-2013 01:27 AM)Han Wrote:  Once you've solved a problem completely using mathematics, is there really any need for a program? I always held the opinion that programs were useful when we reached a mathematical stumbling block.

Also, no more fun writing a program anymore :-(

Code:

wp34s
001 LBL A
002 # 001
003 7
004 +/-
005 # 012
006 SLVQ
007 XEQ 01
008 x<> Y
009 XEQ 01
010 RTN
011 LBL 01
012 SDL 001
013 8
014 RCL-L
015 +
016 # 100
017 +
018 END

A     -->  135
x<>y  -->  144