A modest arithmetical challenge - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: A modest arithmetical challenge (/thread-112157.html) |
A modest arithmetical challenge - Karl Schneider - 04-14-2007 Hi, all -- Here is an interesting arithmetical problem that appeared in a student-engineer magazine in 1993 or 1994: Assume that each integer from 1 through 9 is used exactly once to form three quotients of single-digit integer numerators and two-digit integer denominators. How many ways could the digits be arranged such that the sum of these three terms equaled unity?
Example: 7 8 9 181 is almost a solution. I obtained the above result by trial-and-error, but was unable to analytically deduce the correct answer. In 1995, I wrote a recursive C-language program that found the solution by "brute force", evaluating all 9! = 362,880 possible combinations of digits. Of course, there are six ways to arrange the three terms, so there are "only" 60,480 unique combinations. Several years ago, I showed this problem to a colleague who offered the following:
"There is a subset that populates a more general relationship, He obtained the correct solution by trial and error within this subset of combinations. I can't offer a proof that the stated equation is generally true, or why it may have been a necessary (not merely sufficient) condition for the solution.
So, the challenge: Can anyone provide a direct analytical solution to this problem? If not, would anyone dare to attempt to write an efficient HP calculator program to solve the problem? I believe that the HP-15C offers sufficient programming features to tackle the problem using the brute-force method:
So, a workable HP-15C program could be written. However, I also believe that such a program might take literally weeks to run to completion on an actual HP-15C! Recursion and integer arithmetic could not be employed, as my C program does. The HP-71B would be more suitable, with 12 times the speed, BASIC language, and recursion. Of course, with computing speed being an important issue, a PC-based simulator would be a better choice than an actual calculator. I doubt that there is any trivially-simple derivation of the solution; I also believe that an efficient program would require time and effort. Still, the mathematical knowledge and programming skills offered in response to Valentin's challenges never ceases to impress me. I'll post my C-language program shortly, as a guide for those who might find it useful. Best regards,
-- KS
Re: A modest arithmetical challenge - Valentin Albillo - 04-14-2007 Hi, Karl:
1 DESTROY ALL @ FOR A=1 TO 9 @ FOR D=A+1 TO 9 @ FOR G=D+1 TO 9 and it finds the unique solution (and the fact that there are no others) in about one minute under Emu71, which translates to about 4 hours in a physical HP-71B. Improvements like the ones mentioned above would easily diminish these times enormously, but it would take me more than 10 minutes in all to concoct. :-) Thanks for your interesting and entertaining challenge and
Best regards from V.
Re: A modest arithmetical challenge - Gerson W. Barbosa - 04-14-2007 Hello Karl,
Quote:"There is a subset that populates a more general relationship, The relationships below might also be useful to reduce the use of brute force:
Regards,
Gerson.
Re: A modest arithmetical challenge - Allen - 04-15-2007 Karl,
Quote: interesting challenge!! I am looking into this approach. So far I have the following:
Edited: 15 Apr 2007, 4:22 p.m.
Re: A modest arithmetical challenge - Karl Schneider - 04-15-2007 Hi, Valentin -- Well, I can't verify your astounding claim of only 10 minutes for analysis, development and entry of code, and testing. Still, I'm quite impressed by your analytical and programming skills. Your program did indeed produce the only correct result. A solution based on Fortran 77 (which does not support dynamic memory allocation for recursion), would likely utilize eight or nine nested loops, as you did using BASIC. I developed my C program for learning experience after my collegiate course in C showed that recursion was supported. Recursion can make the code more compact and flexible, but likely slows the execution due to O/S overhead for assignment and release of RAM. I will likely post my C program on Monday evening (Tuesday morning for those of you in Europe), because an electronic copy of the source code is not readily available at home. Your BASIC program as it is structured -- which is not difficult to interpret -- may not port readily to a "clean" RPN-keystroke program absent excessive conditional tests and GTO's. However, despite your description of it as "quick-and-dirty", I see clear evidence of logical structure and thought. Furthermore, it already performs the optimization not to execute redundant permuatations of digits by setting in line 1 the condition A < D < G (which are the three numerators). Your program also wisely calculates the common-denominator products instead of the three quotients. I had done the same in my C program both to eliminate the possiblity of roundoff errors and to exploit the much-faster integer arithmetic. A program that I would write for an HP-15C/32S/32SII/33S/41*/42S would probably emulate the approach I used for my C program, which uses a variable in the fashion of a Fortran LOGICAL variable to identify which digits were already "in use". Flags would fill that role on an HP calculator. Use of an indirect register would reduce redundant code considerably. Thanks again for your informative contribution, -- KS
Edited: 15 Apr 2007, 5:00 p.m.
Re: A modest arithmetical challenge - Valentin Albillo - 04-15-2007 Hi again, Karl: Karl posted:
Still, I'm quite impressed by your analytical and programming skills. Your program did indeed produce the only correct result."
The 10-min claim is easily justified by simply looking at my program: it is nothing but a series of brute-force loops, with the only proviso being the storage of invariant intermediate values out of the loops which doesn't affect their value, the final digit being directly computed as 45 less the sum of the others (as all 9 digits add up to 45), and clumsily testing each digit against the previous ones to make sure no digits are repeated. This straightforward logic can be keyed in very quickly, as the HP-71B lets you enter a variant of a program line by simply editing its line number, kind of a copy-paste operation. You just enter first the most complicated FOR ... IF ... line, then edit its variable and line number (deleting the final test) to enter the next simplest one, which is then edited likewise to produce the next one, etc. (BTW, anyone who's got Emu71 can enter this code by simply doing a real copy-paste of the code from the posted message to Emu71, no need to actually key anything in). As for testing time it's actually zero because, matter of fact, everything is so simple that no debugging was needed, it produced the correct solution on its 'maiden' run. "I will likely post my C program on Monday evening (Tuesday morning for those of you in Europe)"
"However, despite your description of it as "quick-and-dirty", I see clear evidence of logical structure and thought."
which translates as 4:49 A.M. Spanish Time, i.e., 4:49 in the midst of the night, after a very hard daytime with some certification training, with a mild headache and practically asleep.
If I get the time, I'll try to post a decent solution but I doubt I will be able to do that before you (or someone else) post your own. Largest sum : 7/46 + 8/25 + 9/13 = 1.16448160535 (17409/14950) On the analytic front, it's easy to prove that in order for the three fractions to be able to add up to 1 or greater, the digit 1 must forcibly be the first digit of a denominator, and the corresponding numerator must then be > 5. Making use of this shortcut will help save lots of running time. Thanks for your delightful arithmetic challenge, seconds please ! :-) Best regards from V.
Edited: 16 Apr 2007, 9:07 a.m.
Re: A modest arithmetical challenge - Gerson W. Barbosa - 04-15-2007 Not an elegant and concise solution as Valentin's, but this Turbo Pascal 3 program does find the solution:
---------------------------------------------------------------------------------------------------------------------------- The output is:
5/34 + 7/68 + 9/12 = 1
The tests in the outer loop filter 232 candidates. Additional tests are performed in the innermost loop in order to obtain the final solution.
Karl's problem is a pandigital one, that is, a problem whose Incidentally, I was playing with these when Karl posted his interesting problem:
'71/(2*9+4.60)-8^(-sqrt(53))' (to be evaluated on a ten-digit calculator)or '710/CEIL(sqrt(26^4/9))-8^(-sqrt(53))' This looks like cheating, but it's hard to get 226 out of the digits 2, 4, 6 and 9 :-) Gerson.
Edited: 16 Apr 2007, 6:43 p.m.
Re: A modest arithmetical challenge - Gerson W. Barbosa - 04-16-2007
Quote: Dr. Math has provided an analytical solution here, however it doesn't look so direct: http://mathforum.org/library/drmath/view/56829.html
Gerson. Edited: 16 Apr 2007, 7:17 p.m.
Another approach - Gerson W. Barbosa - 04-16-2007 Let's give luck a chance:
------------------------------------Output: 5 / 34 + 7 / 68 + 9 / 12 = 1 This QBASIC program finds the solution in about 15 seconds (Pentium III @ 500 MHz). The random generator seed in line 17 was chosen arbitrarily. ------------ P.S.: Only 14 lines as I've just noticed, but this took at least 20 minutes between the first idea and the printing of the answer :-)
These two lines should be replaced in the QBASIC program above:
45 J = 0
By the way, it's easy to port the program to the HP-71B:
>RUN
The result was found in 57.75 seconds (Emu71 @500MHz), 1 h 40 min 53 sec on the real HP-71B, according to the built-in timer. Previoulsy I had run the program on the emulator once with the original seed but I quit after one hour with no result. This was the second seed I tried.
-----------
Some interesting seeds:
10 DESTROY ALL @ OPTION BASE 0 @ DIM N(8),M(8) @ RANDOMIZE 10.99
10 DESTROY ALL @ OPTION BASE 0 @ DIM N(8),M(8) @ RANDOMIZE 82.622
10 DESTROY ALL @ OPTION BASE 0 @ DIM N(8),M(8) @ RANDOMIZE 82.583
Respectively 71.9, 51.8, 12.56 and 1.43 seconds on the real HP-71B. This is plain cheating though :-)
-----------
The equivalent Turbo Pascal program finds the result in 3 minutes and 20 seconds on the HP-200LX, the first time it is run:
Edited: 28 Apr 2007, 10:57 p.m.
My C program ("A modest arithmetical challenge") - Karl Schneider - 04-17-2007 All -- Thanks to all who have read or taken interest in "A modest arithmetical challenge", and especially to Valentin and Gerson for developing solutions in computer language. As promised, I'm posting my recursive C-language solution from 12 years ago. I wrote it more as a training exercise than as a fully-optimized product. It performs much redundant processing by generating every possible permutation of digits (9! in all) instead of restricting the selections to those that are feasible and mathematically-unique. The source code would be more compact if it weren't for the comments and two subroutine definitions with required function prototypes and variable declarations. The code is ANSI-standard C (1989), so if you have a C compiler, the copied and pasted code should work just fine. -- KS
HP-15C program - Gerson W. Barbosa - 04-17-2007
Quote: The HP-15C program below might find the solution, given enough time (five days? one week? one fortnight?). Of course, this depends also on the quality of the random number generator. As a test, the line 57 could be replaced with .25 and the line 58 with g TEST 8. If the program has been keyed in correctly, the answer will be 439,265,871.0, that is, 4/39 + 2/65 + 8/71. This is equal to 0.2460093897, the first sum less then 1/4 found by the program. This takes less than 60 seconds on my 2.2x 15C. Line numbers followed by a lower case "u" have to be keyed in USER mode. This has been written just an exercise to remember the use of matrices on the HP-15C. It is far from optimized. Improvement suggestions are welcome. Besides pure brute force, the program relies on luck, which is not good, unless, of course, we are lucky enough :-) The program is just a translation of the previous QBASIC program to RPN. The second matrix is not initialized to zero because this is not necessary. Regards, Gerson.
----------------------------------------------------------------------------------------
Edited: 17 Apr 2007, 10:58 p.m.
Re: HP-15C program - Karl Schneider - 04-19-2007 Hi, Gerson -- Thank you for the imaginitive HP-15C solution. I'll have to give it a try on an accelerated calculator or emulator. I have to admit that an approach utilizing random numbers never would have occurred to me... Best regards,
-- KS
Discussion ("A modest arithmetical challenge") - Karl Schneider - 04-19-2007 Hi, Valentin --
Quote: Oh, I wouldn't denigrate your own work, even if it doesn't represent your finest efforts. Hardly anyone -- including myself -- could have immediately written a working program to solve the problem without a fair amount of forethought.
Quote: As far as I'm concerned, your effort surpassed the specification. I never stated "elegant", and "efficient" implied only that it would run in a reasonable amount of time without exhausting multiple sets of batteries. The techniques of computational reduction and the "special sums" you offered were an added bonus.
Quote: Sorry, but I don't have any others in store at the moment. I suspect, though, that any I had would cause me "Mom's lament": An hour to prepare, and ten minutes to demolish... :-) Best regards, -- KS
Edited: 19 Apr 2007, 12:44 a.m.
Re: HP-15C program - Gerson W. Barbosa - 04-19-2007 Hello Karl,
Quote: I fear this might not be a good idea. The average number of tries before the solution was found was 91,985.8 in 50 runs of a modified QBASIC program. In the first run the solution was found after 166,192 tries while in the second run the answer appeared after only 3,394 tries (this was the least number of tries; the maximum number of tries was 256,069, in the 23rd run). Assuming my sped-up 15C takes 20 seconds to process each try, this would take from 19 hours to 60 days to run (from 42 hours to 131 days on a normal 15C!). I wish there were a fast running mode in Nonpareil :-) Regards, Gerson. --------
P.S.: This modification saves one step and might cause the solution to be found weeks earlier or later :-) 001- f LBL B -------- The estimated runtime I provided earlier was wrong. The correct average runtime should be: (9!/3!)*40s/86400 = 28 days (Assuming it takes 40 seconds in average to generate each set of 9 different digits, which I haven't checked yet). A feasible way of solving the problem on the HP-15C would be running the program simultaneously on, say, 15 calculators (or Nonpareil instances), each beginning with a different seed. It is probable at least one of them would complete the task in less than 30 hours... A program using plain brute force would be longer, I guess, and would take about the same time to reach the solution. However, I think I wouldn't be able to write one...
Anyway, considering an HP-15C was recently given the task to compute pi using a Monte Carlo method, the idea of using random numbers to find those three fractions don't look so absurd :-)
Edited: 21 Apr 2007, 8:25 a.m.
Re: Discussion ("A modest arithmetical challenge") - Gerson W. Barbosa - 04-19-2007 Quote: Karl, Don't worry about it being solved that soon. Ten minutes really appears to be the standard time to write a program to solve your challenge: Quoted from http://users.skynet.be/worldofnumbers/ninedig3.htm:
Quote: Having it take me at least 100 minutes to write that ugly piece of Turbo Pascal code only shows I was right not having tried to pursue a career in computer programming :-) Best regards, Gerson.
Edited: 19 Apr 2007, 8:37 p.m.
Re: HP-15C program - David Jedelsky - 04-20-2007 Hi, it really works. I tried it in my testing simulator of 15c and got answer in about 68min of cpu time. If my estimate is correct it roughly corresponds to 850hours on real calculator. Here is the result:
Best Regards,
David
Re: HP-15C program - Gerson W. Barbosa - 04-20-2007 Hi David, Thanks for taking the time to test the program on your simulator. I have an instance of Nonpareil running since yestarday (seed=1); my sped-up 15C (2.2x) ran for at least 52 hours before the batteries went down (not fresh alkaline batteries). By the way, is your simulator freely available? Does it run under DOS or Linux? Is it based on Eric Smith's Nonpareil? 750x is quite good :-) The modification below, beginning from line 40 would save about two hours in a month, on a real HP-15C. Optimizing the first part of the program would give a better result though.
039- GTO 7 058-u RCL B One could use the simulator to try different seeds (twenty of them would suffice) until the solution was found under 20 hours on the real calculator. Of course, this would be cheating :-) Best regards,
Gerson.
Re: HP-15C program - David Jedelsky - 04-20-2007 Hi Gerson, I appreciate your interest in my simulator, but I'm afraid it is not much of general usability. I created it just as a reference platform for the testing of my PIC simulator core. It runs under linux and I even used one source file (digit_ops.c) from Nonpareil (thank you Eric), because the implementation of arithmetic operations was clear and it saved me some time. It is pure console application, as you can also see from the printed result in my previous post. Moreover, it accepts keys just by internal calculator codes. So, it is not mentioned as simulator for the general calculator use. It is just testing tool. Anyway, if anybody want to use it or take a look at it I'm prepared to publish it. Regarding the speed. I don't think 750x is really good, but definitely enough :). If I include optimization options to gcc and place my cpu at regular speed 2.2GHz it runs even somewhere around 1000x. But the code is far from optimal. I think it is possible to reach several times better speeds with optimizations. I didn't try your modification so far. But at least tried seed bases from 0.00 to 0.99 ;). The winner is 0.12 (12 STO RAN#). My estimation for your 2.2x calculator is around two hours to get the result (but maybe I'm wrong). Well, you are right, it is kind of cheating, but who don't want to see real result after all this effort :-). Best Regards, David
Re: HP-15C program - Gerson W. Barbosa - 04-21-2007 Hi David, Thanks again for testing.
Quote: You are right! I forgot to check the chronometer: last time I had checked about 1 hour and 50 minutes had elapsed. When I remembered to check it again 15 minutes later the calculator was still on and displaying 912.768.534,0. So, we can conclude it will take about about 4 hours and 30 minutes on a normal 15C if the following modification is made in the original program:
001- f LBL B This 75-step program may not be fastest one to solve Karl's problem on the 15C, even considering the cheating, but surely is one of the shortest ;-) Just a curiosity, from 1000 runs of the equivalent Turbo Pascal program:
mean: 61158.5180 min: 8 max: 422667 It is possible there is a magic seed that allows the solution to be found in only eight tries on the 15C as well, that is, in about five minutes! On the other hand, 422667 tries would require at least 6 months... Best regards, Gerson. ---------- P. S.:
This run is even more amazing:
mean: 61250.5890 min: 1 max: 593567 At least once the solution was found in the first try...
Edited: 21 Apr 2007, 12:42 a.m.
A physical HP-15C solution in 48 minutes - Valentin Albillo - 04-22-2007 Hi, Karl:
The following HP-15C program will find the solution in a deterministic way (i.e., not depending on random factors) and using nothing but several simple heuristics in a mere 48 minutes, when running on a physical HP-15C:
01 LBL A 27 LBL 3 RCL+ 5 RCL- 7 RCL 5 RCL 1 RCLx 0
To find the puzzle's solution: FIX 0, GSB A -> 9, R/S -> 12,i.e.: 9/12 +7/68 + 5/34 = 1, which is the one and only solution, found in just 48 minutes on my physical, normal speed HP-15C. A 750x emulator would run this program in less than 4 seconds. Some worthwhile programming techniques used:
Best regards from V. Re: A physical HP-15C solution in 48 minutes - Gerson W. Barbosa - 04-22-2007 Hi Valentin, That's the HP-15C solution Karl and all of us here were waiting for. That's what we would expect from you, no less!
Quote: I don't think anyone might have been led to believe this just because of my program. As I said earlier in this thread, a plain brute force program would be able to find the solution within hours, not weeks. I also said I thought I was unable to write one due to its intrinsic complexities. On the other hand, my solution based on random numbers was quite easy to implement, so easy even I was able to do it. My approach would apply only to today's blazingly fast computers though, which can find the solution in less than one second. A quite good compromise between developing and running times, in my opinion. Best regards, Gerson.
Re: A physical HP-15C solution in 48 minutes - Karl Schneider - 04-22-2007 Hi, Valentin -- Well, sir, that's quite impressive. I'll definitely run your program on my HP-15C, and perhaps install the emulator program to give it a try there. After I accelerate an HP-15C, I'll quite likely re-visit the program to measure the benefit. The intelligent heuristics you applied are abolutely necessary to make the program acceptably efficient. My "days/weeks" estimate was admittedly worst-case, as it included exhaustive trial of all possible combinations (or at least, 1/6-th * 9! = 60,480 combinations excluding mathematically-equivalent combinations), assuming no knowledge that only one solution existed, and not simply terminating upon finding one. An estimated five seconds per trial times 60,480 trials would still make 84 hours, which is unacceptable. Fixing one digit reduces the number of total trials to an eighth thereof, and counting digitsdownward from nine so that larger numerators are tried first is certainly a more intelligent way to find the answer quickly. Thank you much for your enlightening solution to an HP-15C challenge that has stumped me for years! Best regards, -- KS
Edited: 22 Apr 2007, 3:42 p.m.
Re: A physical HP-15C solution in 48 minutes - Valentin Albillo - 04-22-2007 Hi, Gerson:
Many times Monte Carlo-like methods provide very reasonable solutions for highly intractable problems, or even the only way to solve them, as is the case for multidimensional integration of high dimensionality ("the curse of dimension"). It's only that I got the impression that some people reading this thread could be led to the wrong conclusion that it would take excessively long for an HP-15C to try and solve this puzzle, and I won't suffer such a humiliating situation for my beloved HP-15C if I can do something about it, which I can. So, a couple of hours later I had written and run the posted program which, indeed, does find the solution in a pretty decent time. A first version using subroutines was very much shorter and elegant, but it took more than twice the time, at some 2 hours. Removing subroutines and unrolling some loops resulted in the 160-step, 48-min program posted, which can be further optimized but to no real purpose. As a 'concept proof' of the HP-15C capabilities, it's already more than adequate.
Thanks for your comments and Re: A physical HP-15C solution in 48 minutes - Valentin Albillo - 04-22-2007 Hi, Karl:
By the way, quoting some of your comments in your original post, here is how they apply to my posted solution: "I believe that the HP-15C offers sufficient programming features to tackle the problem using the brute-force method:
So, a workable HP-15C program could be written. However, I also believe that such a program might take literally weeks to run to completion on
A physical HP-71B solution under 20 minutes - Gerson W. Barbosa - 04-24-2007 Hello again Valentin,
Quote: I didn't try your technique but I did try another solution on the HP-71B. Accepting, without proving, the relationship provided by Karl, that is,
D=2*Bit's easy to obtain
D*E The program also assumes A is even, as Karl has suggested. The program runs in about 11 second on Emu71 (@500MHz), however the unique answer is shown after 6 seconds. On the real HP-71B the total running time was exactly 19 minutes and 58 seconds (Well, that's under 20 minutes :-) As always, my best solutions are 10 to 20 times slower than yours, but I am glad I was able to come up with something that would not take days or weeks on the real calculator :-) Best regards, Gerson.
----------------------------------------------------------------- Here is the equivalent Turbo Pascal program, for clarity:
--------------------------
Edited: 24 Apr 2007, 2:14 p.m.
|