challenge for programmable calculators

12222013, 04:40 PM
Post: #21




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 

12222013, 05:53 PM
(This post was last modified: 12222013 06:01 PM by Thomas Klemm.)
Post: #22




RE: challenge for programmable calculators
(12222013 04:40 PM)Katie Wasserman Wrote:Quote:symmetry of the expression 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 

12222013, 06:59 PM
Post: #23




RE: challenge for programmable calculators
(12222013 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 HP41: 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:


12222013, 07:03 PM
Post: #24




RE: challenge for programmable calculators
Just for the record, here is my wp34s program:
Code: 001: LBL A 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. 

12222013, 07:12 PM
Post: #25




RE: challenge for programmable calculators  
12222013, 09:15 PM
Post: #26




RE: challenge for programmable calculators
(12222013 07:12 PM)Thomas Klemm Wrote:(12222013 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. I thought love for money was that :) 

12222013, 09:48 PM
(This post was last modified: 12222013 09:49 PM by Katie Wasserman.)
Post: #27




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 

12222013, 10:52 PM
(This post was last modified: 12222013 11:12 PM by Thomas Klemm.)
Post: #28




RE: challenge for programmable calculators
(12222013 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. 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 

12242013, 04:54 AM
Post: #29




RE: challenge for programmable calculators
SySRPL with a twist:
Code:


12242013, 06:38 AM
Post: #30




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.


12242013, 04:52 PM
Post: #31




RE: challenge for programmable calculators
(12242013 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(.); 3: 135. 2: 144. 1: s:2.2434 (Real hp 50g) Comparing with a plain bruteforce solution: Code:
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... 

12242013, 05:43 PM
Post: #32




Proof using number theory
(12212013 06:15 PM)Don Shepherd Wrote: A nonbruteforce 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: \[abc1 = \frac{9(11a+b)}{a+b+c}\] Since we are dealing exclusively with positive nonzero integers, both \(abc1\) 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} abc1 &= \frac{9(11a+b)}{(a+b+c)}\\ abc1 &= \frac{9(11a+b)}{9}\\ abc1 &= 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 nonzero 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 &= (an1)b\\ \frac{11a+1}{an1} &= 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}{an1} \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. 

12242013, 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 

12242013, 06:02 PM
Post: #34




RE: challenge for programmable calculators
(12242013 04:52 PM)Gerson W. Barbosa Wrote: We can safely reduce the number of trials from 63 to 42: Code: %%HP: T(3)A(D)F(.); 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 bruteforce solution, even considering the greater complexity of the innermost loop, at least for the real hp 50g. 

12242013, 07:31 PM
(This post was last modified: 12242013 07:46 PM by Gerson W. Barbosa.)
Post: #35




RE: challenge for programmable calculators
(12242013 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(.); which finds both solutions in 0.6675 seconds on the real hp 50g. That's about a 22time improvement over the plain bruteforce 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! 

12242013, 07:45 PM
(This post was last modified: 12242013 10:07 PM by Thomas Klemm.)
Post: #36




RE: challenge for programmable calculators
(12242013 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^29a)b+11a+1=0\] The determinant \((1+a^29a)^24a(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 HP42S: Code:
Cheers Thomas 

12242013, 08:20 PM
Post: #37




RE: challenge for programmable calculators  
12242013, 09:38 PM
Post: #38




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.


12252013, 01:27 AM
Post: #39




RE: challenge for programmable calculators
(12242013 07:45 PM)Thomas Klemm Wrote:(12242013 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: 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 

12252013, 04:31 AM
Post: #40




RE: challenge for programmable calculators
(12252013 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 

« Next Oldest  Next Newest »

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