Mini-challenge: digits by half

[David Hayden]

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 1-9, 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 1-9 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.)

[Allen]

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 (1-9) 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]

[Albert Chan]

  6ABC
-------- = 1/2, remain digits = 248, 3579
1DEFG

1000*(2-D) + 100*(2*A-E) + 10*(2*B-F) + (2*C-G) = 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*(2-D) + 10*(2*A-E) + (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

ABC/EFG = 1/2, digits = 48, 3579

Only 2 even numbers, and even G, both C and F odd

A=3 → E=7 → G=8 → C=9 → F=5 we have 349 / 758 *bad*
A=4 → G=8 → C=9 → E=? *bad*

Thus, D=3, fraction reduced to:

ABC/1EFG = 1/2, digits = 248, 579

A = 7,8,9:

A=9 → E=8 → G=4 → C=7 → F=5 → 927/1854 *good*
A=8 → G=4 → C=7, but E=7 too           *bad*
A=7:
    E=4 → G=8 → C=9 → F=5 → 729/1458 *good*
    E=5:
        G=4 → C=2 → F=8 → 792/1584 *good*
        G=8 → C=4 → F=2 → 794/1528 *bad*

We have 3 solutions: 6927/13854 = 6729/13458 = 6792/13584 = 1/2

[Albert Chan]

(03-28-2022 10:34 PM)Allen Wrote:  I'm getting 12 unique pairs (a,b) of numbers that are nearly pandigital (1-9) 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.

[David Hayden]

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>

int digits(int num)
{
    int result = 0;
    div_t divRes;
    while(num) {
        divRes = div(num, 10);
        result |= 1<< divRes.rem;
        num = divRes.quot;
    }
    return result;
}

int
main()
{
    for (int x=1; x < 10000; ++x) {
        if ((digits(x) | digits(2*x)) == (0x3fe)) {
            std::cout << x << ' ' << 2*x << '\n';
        }
    }
}

[Albert Chan]

(03-29-2022 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)

[David Hayden]

(03-29-2022 01:47 PM)Albert Chan Wrote:  If C=4, we used up all even numbers, 6AB4 * 2 = 1DE28
This implied B = 1 or 6, both already used. Thus, C≠ 4

I don't follow. Why must F = 2?

[Albert Chan]

(03-29-2022 04:31 PM)David Hayden Wrote:  

(03-29-2022 01:47 PM)Albert Chan Wrote:  If C=4, we used up all even numbers, 6AB4 * 2 = 1DE28
This implied B = 1 or 6, both already used. Thus, C≠ 4

I don't follow. Why must F = 2?

1000*(2-D) + 100*(2*A-E) + 10*(2*B-F) + (2*C-G) = 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.

[David Hayden]

(03-29-2022 04:52 PM)Albert Chan Wrote:  If G=8, C=4 last term goes 0, thus F must be even ⇒ F=2 (only even left)

Got it. Thanks.

[DavidM]

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 built-in 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:

\<<
   9 LSEQ { 1 6 } LRMOV             @ digits for permutation
   DUP SIZE                         @ use all digits for each permutation
   \<<
      3 SPLIT                       @ split permutation into lists of 3 and 4
      6 ROT + NL\->I                @ prefix fixed digits (6 & 1), convert to
      1 ROT + NL\->I                @  integers
      2 \->LIST { / } + \->ALG      @ convert integers to algebraic fraction
      DUP \->NUM .5 SAME NOT DROPN  @ DROP the fraction if <> 1/2
   \>>
   DOPERM                           @ execute the above for each permutation
\>>

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.

[Albert Chan]

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):
    while x: t += 10**(x%10); x //= 10
    return t

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((6987-6234)/3) + 1 = 252 ... not bad

With permutations, removed non-multiples-of-3, 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

[DavidM]

(03-30-2022 04:25 PM)Albert Chan Wrote:  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 ?
...
(lots of possible optimizations)
...

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 non-optimized 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!