challenge for programmable calculators
12-22-2013, 04:40 PM
Post: #21 Katie Wasserman Super Moderator Posts: 629 Joined: Dec 2013
RE: challenge for programmable calculators
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?

-katie

12-22-2013, 05:53 PM (This post was last modified: 12-22-2013 06:01 PM by Thomas Klemm.)
Post: #22
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: challenge for programmable calculators
(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
12-22-2013, 06:59 PM
Post: #23
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: challenge for programmable calculators
(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
12-22-2013, 07:03 PM
Post: #24 Gerson W. Barbosa Senior Member Posts: 1,243 Joined: Dec 2013
RE: challenge for programmable calculators
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.
12-22-2013, 07:12 PM
Post: #25
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: challenge for programmable calculators
(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
12-22-2013, 09:15 PM
Post: #26 Gerson W. Barbosa Senior Member Posts: 1,243 Joined: Dec 2013
RE: challenge for programmable calculators
(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 :-)
12-22-2013, 09:48 PM (This post was last modified: 12-22-2013 09:49 PM by Katie Wasserman.)
Post: #27 Katie Wasserman Super Moderator Posts: 629 Joined: Dec 2013
RE: challenge for programmable calculators
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?

-katie

12-22-2013, 10:52 PM (This post was last modified: 12-22-2013 11:12 PM by Thomas Klemm.)
Post: #28
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: challenge for programmable calculators
(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
12-24-2013, 04:54 AM
Post: #29 David Hayden Senior Member Posts: 302 Joined: Dec 2013
RE: challenge for programmable calculators
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.
12-24-2013, 06:38 AM
Post: #30
 kakima Junior Member Posts: 41 Joined: Dec 2013
RE: challenge for programmable calculators
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.
12-24-2013, 04:52 PM
Post: #31 Gerson W. Barbosa Senior Member Posts: 1,243 Joined: Dec 2013
RE: challenge for programmable calculators
(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...
12-24-2013, 05:43 PM
Post: #32
 cruff Member Posts: 162 Joined: Dec 2013
Proof using number theory
(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.
12-24-2013, 05:57 PM
Post: #33
RE: challenge for programmable calculators
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
12-24-2013, 06:02 PM
Post: #34 Gerson W. Barbosa Senior Member Posts: 1,243 Joined: Dec 2013
RE: challenge for programmable calculators
(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.
12-24-2013, 07:31 PM (This post was last modified: 12-24-2013 07:46 PM by Gerson W. Barbosa.)
Post: #35 Gerson W. Barbosa Senior Member Posts: 1,243 Joined: Dec 2013
RE: challenge for programmable calculators
(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.
\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!
12-24-2013, 07:45 PM (This post was last modified: 12-24-2013 10:07 PM by Thomas Klemm.)
Post: #36
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: challenge for programmable calculators
(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
12-24-2013, 08:20 PM
Post: #37
 cruff Member Posts: 162 Joined: Dec 2013
RE: challenge for programmable calculators
(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!
12-24-2013, 09:38 PM
Post: #38 David Hayden Senior Member Posts: 302 Joined: Dec 2013
RE: challenge for programmable calculators
I'm not sure if this helps in any way, but if C is odd then A and B must also be odd.
12-25-2013, 01:27 AM
Post: #39 Han Senior Member Posts: 1,810 Joined: Dec 2013
RE: challenge for programmable calculators
(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.

Graph 3D | QPI | SolveSys
12-25-2013, 04:31 AM
Post: #40 Gerson W. Barbosa Senior Member Posts: 1,243 Joined: Dec 2013
RE: challenge for programmable calculators
(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
 « Next Oldest | Next Newest »

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