Minichallenge: digits by half

03282022, 05:46 PM
(This post was last modified: 03292022 12:28 PM by David Hayden.)
Post: #1




Minichallenge: digits by half
Here's a fun little diversion from The Calculator Game Book by Arlene Hartman (1977) page 88.
Half a Loaf Suggested grade span  7 and up This puzzler should not be attempted unless you have lots of time and patience. We saw in Chapter 5 (#13) a special quotient which used each of the digits 19, the answer for which was 9. Therefore, the unit fraction 1/9 can be found by 6381/57429. Check to see if their decimal equivalents are the same. There is also a fraction which uses each of the digits 19 exactly once which equals 1/2. Can you find it? (A hint to save some time  the numerator begins with 6; the denominator with 1.) 

03282022, 10:34 PM
Post: #2




RE: Minichallenge: digits by half
Afternoon! ♥ the mini challenge, but I'm not sure there is a unique answer??
I'm getting 12 unique pairs (a,b) of numbers that are nearly pandigital (19) and 2*a=b. All of the a's are multiples of 3 and all the b's are multiples of 6. If sorted according to the smallest number in each pair (a,b) the discrete derivative with respect to a is [63, 135, 342, 24, 36, 363, 231, 9, 1335, 6, 54] 17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

03282022, 10:48 PM
Post: #3




RE: Minichallenge: digits by half
6ABC
 = 1/2, remain digits = 248, 3579 1DEFG 1000*(2D) + 100*(2*AE) + 10*(2*BF) + (2*CG) = 0 From equation ⇒ D = 2 or 3, G = 4 or 8 With G = 4 or 8, if C is even, last term is gone. If C is odd, last term is 10. If (C, G) is picked correctly, we have: 100*(2D) + 10*(2*AE) + (2*B  F+parity(C)) = 0 parity(C) = parity(F) Note that we group remaining digits by its parity. Code: If D=2, then A = 3 or 4 

03282022, 11:33 PM
Post: #4




RE: Minichallenge: digits by half
(03282022 10:34 PM)Allen Wrote: I'm getting 12 unique pairs (a,b) of numbers that are nearly pandigital (19) and 2*a=b. Ignoring the hint, I get 12 answers too ! Here is by brute force: >>> from itertools import permutations >>> for x in permutations(range(2,10)): ... n = 1000*x[0] + 100*x[1] + 10*x[2] + x[3] ... d = 1000*(10+x[4]) + 100*x[5] + 10*x[6] + x[7] ... if n+n==d: print n,'/',d ... 6729 / 13458 6792 / 13584 6927 / 13854 7269 / 14538 7293 / 14586 7329 / 14658 7692 / 15384 7923 / 15846 7932 / 15864 9267 / 18534 9273 / 18546 9327 / 18654 Quote:All of the a's are multiples of 3 and all the b's are multiples of 6. Yes ! That reduce search cases by a lot ! Because digits are limited from 1 to 9: (num + den) ≡ 0 (mod 9) num * 2 ≡ den (mod 9) num * 3 ≡ 0 (mod 9) num ≡ 0 (mod 3) Denominator, being even, is divible by 6. 

03292022, 12:42 PM
Post: #5




RE: Minichallenge: digits by half
Nice solutions, Albert and Alan. I, too, was surprised to find multiple answers.
My approach is similar to Albert's. Using his notation (6ABC * 2 = 1DEFG), it's clear that D is 2 or 3. Next I used the fact that the least significant N digits of 1DEFG are fully determined by the least significant N digits of 6ABC * 2. This leads to C being 2,4,7 or 9. Then I figured the possibilities for the least significant 2 digits. I don't have my notes in front of me, but I think that led to 4 dropping out as a candidate for C Moving to the least significant 3 gave the answer. A simple C++ program gives them all: Code: #include <iostream> 

03292022, 01:47 PM
Post: #6




RE: Minichallenge: digits by half
(03292022 12:42 PM)David Hayden Wrote: Then I figured the possibilities for the least significant 2 digits. I don't have my notes in front of me, but I think that led to 4 dropping out as a candidate for C 6ABC * 2 = 1DEFG If C=4, we used up all even numbers, 6AB4 * 2 = 1DE28 This implied B = 1 or 6, both already used. Thus, C≠ 4 BTW, reciprocal of 9, we have 3 solutions: 6381/57429 = 6471/58239 = 8361/75249 = 1/9 You have to go upto reciprocal of 18, to have unique solution. (hint: 1ABC * 18 = 2DEFG) 

03292022, 04:31 PM
Post: #7




RE: Minichallenge: digits by half  
03292022, 04:52 PM
Post: #8




RE: Minichallenge: digits by half
(03292022 04:31 PM)David Hayden Wrote:(03292022 01:47 PM)Albert Chan Wrote: If C=4, we used up all even numbers, 6AB4 * 2 = 1DE28I don't follow. Why must F = 2? 1000*(2D) + 100*(2*AE) + 10*(2*BF) + (2*CG) = 0 If G=8, C=4 last term goes 0, thus F must be even ⇒ F=2 (only even left) To generalize, for G=4,8, (C+F) must be even. 

03292022, 08:21 PM
Post: #9




RE: Minichallenge: digits by half  
03302022, 11:32 AM
(This post was last modified: 03302022 11:47 AM by DavidM.)
Post: #10




RE: Minichallenge: digits by half
Solving this puzzle with just the naive approach is still "within reach" of the later hp calculators. This focuses on a 50g implementation.
The ListExt library has a couple of useful commands for this. The following was quite easy to conceive  I spent more time trying to figure out how to keep the calculator from automatically simplifying the fraction than anything else. I ended up avoiding the simplification by manually building the algebraic fraction as a list and using the builtin development library's →ALG function to convert it to an algebraic. If you don't normally have the development library attached, you may need to do that first with "256 ATTACH". Code: \<< The output is "{ '6729/13458' '6792/13584' '6927/13854' }". It takes about 670 seconds on a real 50g. I suspect NewRPL or Prime versions would complete in a fraction of that time (pun slightly intended). Using some of the aforementioned optimizations would help considerably, of course. But even the "check every permutation" approach with 7 digits floating is reasonable. 

03302022, 04:25 PM
(This post was last modified: 03312022 07:43 PM by Albert Chan.)
Post: #11




RE: Minichallenge: digits by half
If the goal is efficiency, even with brute force, I would reduce search space more.
Instead of 7! = 5040 cases, split between n and d. Why not just do n ? This reduce search cases to 7P3 = 210 cases Even without hint, 9P4 = 3024, instead of 9! = 362880 We just need a function to count frequencies of digits. (real code probably does base 16, turning pow, div into bit shifts) Code: def dcount(x, t=0): For digits 1 to 9, (n+d) divisible by 9. With n/d = 1/2, n is divisible by 3. >>> for n in range(6234, 6987+1, 3): ... if dcount(100002*n) == 1111111110: print n,'/',2*n ... 6729 / 13458 6792 / 13584 6927 / 13854 Without permutations, cases = floor((69876234)/3) + 1 = 252 ... not bad With permutations, removed nonmultiplesof3, cases goes down to 78. But, probably not worth the effort. (it still loop thru 210 permutations) >>> from itertools import permutations >>> for x in permutations([2,3,4,5,7,8,9], 3): ... n = 6000 + 100*x[0] + 10*x[1] + x[2] ... if n%3: continue # mod test ... if dcount(100002*n) == 1111111110: print n,'/',2*n ... 6729 / 13458 6792 / 13584 6927 / 13854 

03312022, 11:07 AM
Post: #12




RE: Minichallenge: digits by half
(03302022 04:25 PM)Albert Chan Wrote: If the goal is efficiency, even with brute force, I would reduce search space more. My goal wasn't computation efficiency, but rather my efficiency. I wanted to get the answer(s) in as little of my time as was needed. True confession: I only ran my code on a real 50g out of curiosity to see how long it would take. In actuality, the above RPL code was written using an emulator running on my laptop, and the final answer was produced in slightly over 14 seconds. It would definitely take me longer than 14 seconds to start altering the approach to limit the search using optimizations. I suspect you (and most everyone else here) would come up with shortcuts much faster than I could, though, so I don't mean to imply that my limitations apply to everyone else. My point is simply that this particular problem can easily be solved using our calculators in a reasonable amount of time, even with the nonoptimized brute force approach. I'm not suggesting that it is wrong to optimize the approach, just that I had no particular need or inclination to do so once the problem was already solved. The available tools allowed me to do this quite easily, which was enough to satisfy my curiosity. The fun of this kind of puzzle is in the analysis and seeking out those optimizations that you and others have found, which is exactly the kind of thing I look forward to doing when I can find the time. Perhaps if I can ever retire! 

« Next Oldest  Next Newest »

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