challenge for programmable calculators

challenge for programmable calculators - Printable Version

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

Pages: 1 2 3

RE: challenge for programmable calculators - Katie Wasserman - 12-22-2013 04:40 PM

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?

RE: challenge for programmable calculators - Thomas Klemm - 12-22-2013 05:53 PM

(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

RE: challenge for programmable calculators - Thomas Klemm - 12-22-2013 06:59 PM

(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

RE: challenge for programmable calculators - Gerson W. Barbosa - 12-22-2013 07:03 PM

Just for the record, here is my wp34s program:

Code:

      LBL A

      9

      STO 01

      9

      STO 02

      RCL 01

      RCL[times] 02

      RCL 01

      x[^2]

      RCL[times] 02

      RCL 02

      x[^2]

      RCL[times] 01

      +

      DEC X

      RCL 01

      SDL 001

      RCL+ 02

      SDL 001

      +/-

      SLVQ

      x[<->] Y

      FP?

      SKIP 011

      9

      x<? Y

      SKIP 008

      x[<->] Y

      RCL 02

      SDL 001

      +

      RCL 01

      SDL 002

      +

      STOP

      DSE 02

      BACK 031

      DSE 01

      BACK 035

      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.

RE: challenge for programmable calculators - Thomas Klemm - 12-22-2013 07:12 PM

(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

RE: challenge for programmable calculators - Gerson W. Barbosa - 12-22-2013 09:15 PM

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

RE: challenge for programmable calculators - Katie Wasserman - 12-22-2013 09:48 PM

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?

RE: challenge for programmable calculators - Thomas Klemm - 12-22-2013 10:52 PM

(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

RE: challenge for programmable calculators - David Hayden - 12-24-2013 04:54 AM

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.

RE: challenge for programmable calculators - kakima - 12-24-2013 06:38 AM

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.

RE: challenge for programmable calculators - Gerson W. Barbosa - 12-24-2013 04:52 PM

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

Proof using number theory - cruff - 12-24-2013 05:43 PM

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

RE: challenge for programmable calculators - radwilliams - 12-24-2013 05:57 PM

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

RE: challenge for programmable calculators - Gerson W. Barbosa - 12-24-2013 06:02 PM

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

RE: challenge for programmable calculators - Gerson W. Barbosa - 12-24-2013 07:31 PM

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

RE: challenge for programmable calculators - Thomas Klemm - 12-24-2013 07:45 PM

(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

RE: challenge for programmable calculators - cruff - 12-24-2013 08:20 PM

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

RE: challenge for programmable calculators - David Hayden - 12-24-2013 09:38 PM

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

RE: challenge for programmable calculators - Han - 12-25-2013 01:27 AM

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

RE: challenge for programmable calculators - Gerson W. Barbosa - 12-25-2013 04:31 AM

(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