Fractions

[cinelli]

Consider all numbers of the form xxxx/xxxxx, a 4-digit number divided by a 5-digit number, where the x’s are all the digits from 1 to 9. For example 9327/18654 equals precisely 1/2. This puzzle is to find similar arrangements to make

1/18, 1/37, 1/43 and 1/59.

Cinelli

[swill453]

Consider all numbers of the form xxxx/xxxxx, a 4-digit number divided by a 5-digit number, where the x’s are all the digits from 1 to 9. For example 9327/18654 equals precisely 1/2. This puzzle is to find similar arrangements to make

1/18, 1/37, 1/43 and 1/59.

Unless I'm misunderstanding the question, I don't see how you could have a 4-digit number divided by a 5-digit number equal to 1/59 (or anything less than 1/9). Can you explain a bit more? Or is there a trick I'm missing?

Scott.

[swill453]

Unless I'm misunderstanding the question, I don't see how you could have a 4-digit number divided by a 5-digit number equal to 1/59 (or anything less than 1/9).

Ignore this, I miscounted

Scott.

[UncleEbenezer]

Hmmm, not easy to see a better method than brute force on the 'puter (which is of course trivial).

1254/73986 = 1/59
1593/28674 = 1/18
1782/65934 = 1/37
2178/93654 = 1/43

Supplementary question: what's special about those numbers? Brute force finds 187 such 4/5 digit pairs giving integer multiples, up to a 1/68 (which I'll let you work out). And these are not numbers that feature in well-known patterns of decimal counting!

[GoSeigen]

Consider all numbers of the form xxxx/xxxxx, a 4-digit number divided by a 5-digit number, where the x’s are all the digits from 1 to 9. For example 9327/18654 equals precisely 1/2. This puzzle is to find similar arrangements to make

1/18, 1/37, 1/43 and 1/59.

Cinelli

Spoiler:

[EDIT: added additional explanation.]

I'll try 59. Apologies for the cryptic working. Geng will no doubt produce a beautifully worked, lucid solution! I'm happy to clarify any weirdness!


The four figure numerator will be less than 98765/59 so its range is from 1234 to 1673. The denominator will range from 1234*59 = 72,806 to 1673*59 = 98,707.

1. Try numerator from 1234 to 1298 : denominator is 72806 to 76582. Numbers 1,2 and 7 have been used. Thus denominator must be at least 73456 and numerator at least 73456/59; so numerator range: 1246 to 1298 denominator 73514 to 76582. The units cannot be 1,2,3,7,8 or 9 or indeed 5, so the units must be 4 and 6. Numbers 1,2,4,6,and 7 have been used. So now the numerator must be at least 1258. Num. range: 1254 to 1296. Denom. range: 73986 to 76464.

This gives one solution: 73986/1254 = 59. There may be others which can be found by continuing the process.

If 1 had failed we would try numerators from:
2. 1324 to 1398, then
3. 1423 to 1498, then
4. 1523 to 1598, and finally
5. 1623 to 1673.




GS

[UncleEbenezer]

Spoiler:
GS

I find your solution (which I briefly contemplated but dismissed as too much enumeration work) even less appealing than mine:
- though you've kind-of narrowed the problem space, it's still brute force: nothing elegant about it.
- you appear to have done more work to find one number than I did to find four. Or indeed 187.
- your approach doesn't appear to generalise well to the other numbers. Even the high-number cases[1] don't come straight out, while lower numbers leave you a rather big solution space.

I too am wondering if Gengulphus - or anyone - will be along with a more elegant solution. Can't see it myself.

[1] Above 59 are 62 (twice), 66 and 68.

[GoSeigen]

Spoiler:
GS

I find your solution (which I briefly contemplated but dismissed as too much enumeration work) even less appealing than mine:
- though you've kind-of narrowed the problem space, it's still brute force: nothing elegant about it.
- you appear to have done more work to find one number than I did to find four. Or indeed 187.
- your approach doesn't appear to generalise well to the other numbers. Even the high-number cases[1] don't come straight out, while lower numbers leave you a rather big solution space.

I too am wondering if Gengulphus - or anyone - will be along with a more elegant solution. Can't see it myself.

[1] Above 59 are 62 (twice), 66 and 68.

The solution came out in about 20 minutes, with calculator just to do the handful of divisions by 59 (which of course could have been done by hand if necessary). Now it was a bit lucky that the answer appeared relatively early. Even if not though, the method would have worked acceptably quickly to find the solution(s) I think. I'm not sure elegance was a requirement in the OP, but perhaps I missed it.

If I have time I'll try one of the other numbers which as you say might not be amenable to the same approach.


I haven't read your solutions yet to avoid spoiling my fun so can't comment on how much better your method was.


GS

[GoSeigen]

I find your solution (which I briefly contemplated but dismissed as too much enumeration work) even less appealing than mine:
- though you've kind-of narrowed the problem space, it's still brute force: nothing elegant about it.

Just to be clear, the solution I posted involved no more than perhaps a dozen calculations (multiply or divide by 59).


I've sneaked a look back at the thread and see that your post is very short with a note saying the method was brute force. How long do you reckon it would have taken to do without the computer?

GS

[UncleEbenezer]

I find your solution (which I briefly contemplated but dismissed as too much enumeration work) even less appealing than mine:
- though you've kind-of narrowed the problem space, it's still brute force: nothing elegant about it.

Just to be clear, the solution I posted involved no more than perhaps a dozen calculations (multiply or divide by 59).


I've sneaked a look back at the thread and see that your post is very short with a note saying the method was brute force. How long do you reckon it would have taken to do without the computer?

GS

Oh, I wouldn't've attempted it that way without the 'puter. The size of the problem space is 9!, modified only by the constraints you pointed out arising from the high multiple (which also informed a pure brute-force approach into starting at 1234 and working upwards over eligible pairs). So if compelled, my approach would then have had to turn into yours.

I guess it's all in a mindset. Mine goes back to school maths lessons, when my teacher explained how mathematicians are lazy and never do more work than is necessary to solve the problem (and are out having fun while science students are in the lab and arts students writing essays). It appealed to me then, and over my years in systems&software it's fed my keenness to automate wherever possible. In a case of a problem like this one, if I can't see an elegant approach based on properties of numbers, I'd always rather hack up a ten-minute program than do trial-and-error by hand.

I'm sure it's very bad for my problem-solving, as witness the number of times I've got puzzles posted here wrong. I think (hope) I'd've been more like our esteemed sage back in the days when my recreational reading was Martin Gardner.

[GoSeigen]

I guess it's all in a mindset. Mine goes back to school maths lessons, when my teacher explained how mathematicians are lazy and never do more work than is necessary to solve the problem (and are out having fun while science students are in the lab and arts students writing essays).

Heh, that's why I started with 1/59 and approached it the way I did. Possibly a similar method would be a lot more work for the other fractions, and some other trick necessary. I suppose it would be nice if we could dream up a quick elegant algorithm to deal with all cases, but of course such an algorithm might not exist!

There is a class of puzzles where the puzzle-setter knows there is an elegant solution and the task for the solver is to discover it. [Maybe there's a name for these??] There is another class where the solution is not so "clever" but using logic and reason the task can be made easier. I think sudoku is a good example. Clearly a brute force method would find a solution but the fun is in figuring out the shortcuts. One couldn't really argue that sudoku is solved by some "elegant" method; nevertheless many people derive satisfaction from doing them -- not I, I'd hasten to add! There are other classes -- riddles for example -- which are seen on this board sometimes.

My suspicion is that the puzzle is in the second class i.e. more sudoku-like than amenable to discovery of an "elegant" solution. The earlier light switch puzzle seemed to me to be in the first class.


GS

[UncleEbenezer]

Hmm. Speaking as a sudoku player, I'm minded to take issue with you, at least a little. Sudoku is about finding and recognising patterns. A brute force approach would be seriously long-winded and tedious, and that applies even to much-narrowed brute force as in your 59 above. I also think sudoku would be better with visually-distinct texture/patterns and/or colours than with numbers, though of course for sudoku-on-paper it needs to be something easy to write.

[Gengulphus]

I too am wondering if Gengulphus - or anyone - will be along with a more elegant solution. ...

Below are my best efforts so far for 1/59 and 1/43. I've done 1/59 is a great deal of detail - almost certainly far too much for the more dedicated mathematicians and more mathematically-inclined puzzlers among you! But hopefully the detail will help the less mathematically-inclined puzzlers, and I've done 1/43 in more abbreviated form. I have not done 1/37 or 1/18, but 1/37 should be solvable pretty similarly to 1/43, though probably requires a somewhat longer search due to the somewhat larger search space. I'd expect a similar search for solutions for 1/18 to involve a significantly bigger search space, but the fact that 18 is a multiple of 9 to make the argument have a somewhat different structure, which might also affect the size of the search.

Note I'm not claiming that these solutions are especially elegant. They are however done almost entirely by hand - the only exception being that I used a calculator to do the divisions and multiplications by 59 and 43, to keep tedium and errors down. So what I'm claiming is just that out of the solutions done essentially without computer aid, they're the most elegant ones I've managed.


ABCD/EFGHI = 1/59

We want a 4-digit number n = ABCD such that 59n = EFGHI with (A,B,C,D,E,F,G,H,I) being the digits 1-9 in some order. Whenever one sees a puzzle involving the digits 1-9 (or 0-9) appearing once each, one should immediately think of 'digital roots' (take the sum of the digits, repeatedly until one gets down to a single digit), which are the same as remainders on division by 9 (provided one takes a 'digital root' of 9 as meaning remainder 0) or in mathematical parlance, the values mod 9.

Since 54n is divisible by 9, the remainder of 59n when divided by 9 is the same as the remainder of 59n-54n = 5n when divided by 9, or more briefly 59n mod 9 = 5n mod 9. Furthermore, the difference between n and n mod 9 is divisible by 9, i.e. n - (n mod 9) is a multiple of 9. Multiplying through by 5, that implies that 5n - 5 * (n mod 9) is a multiple of 5, so 5n and 5 * (n mod 9) have the same 'digital root'. Putting those together, 59n and 5 * (n mod 9) have the same 'digital root', so if we know the digital root of n, we can work out the 'digital root' of 59n by multiplying by 5 and taking the 'digital root' of the result. So the possibilities (1,2,3,4,5,6,7,8,9) for the digital root of n (*) get multiplied by 5 to give (5,10,15,20,25,30,35,40,45) and 'digital roots' taken to produce the corresponding 'digital roots' of 59n as (5,1,6,2,7,3,8,4,9).

But we also know that the sum of the digits of n and 59n is A+B+C+D+E+F+G+H+I = 45, a multiple of 9. So the possibilities (1,2,3,4,5,6,7,8,9) for the 'digital root' of n must also correspond to possibilities (8,7,6,5,4,3,2,1,9) for the digital root of 59n. Those two results about the 'digital root' of 59n conflict with each other except when the 'digital root' of n is 3, 6 or 9, i.e. when n has remainder 3, 6 or 0 when divided by 9, or more briefly, when n is a multiple of 3. So n = ABCD must be a multiple of 3.

Another observation is that 60n = n+59n = ABCD+EFGHI has last digit 0, while neither D nor I is 0. It follows that D+I = 10, and thus that (a) neither D nor I is 5; (b) at any time that the digits already used for A, B, C, E, F, G and H (and thus not OK for allocating to the rest of them) include a digit d, both d and 10-d are not OK for allocating to D and I.

These make it possible to refine a set of bounds on either n or 59n, together with two sets of forbidden digits for as-yet-undetermined digits (one for D and I and the other for the rest) by:

* Adjusting the lower bound upwards if necessary first to get to a number with no repeated or forbidden digits (which can be done by assuming the digits are the lowest that remain possible, in highest-to-lowest significance order), then up by 1 or 2 if needed to get to a multiple of 3, then successively up by 3 at a time as needed to avoid using repeated or forbidden digits.

* Adjusting the upper bound downwards if necessary, in a corresponding way with all directions reversed.

If this tightens the bounds on n, we can produce tighter bounds on 59n than we had previously by multiplying those on n by 59; similarly, if this tightens the bounds on 59n, we can produce tighter bounds on n by dividing those on 59n by 59, rounding the lower bound upwards and the upper bound downwards. This allows us to continue tightening the bounds on both until we fail to tighten the bounds on one or the other.

At some points, we may get the bounds on n or 59n tight enough to determine a further digit or digits. When that happens, the sets of forbidden digits will become larger, potentially allowing further refining of the bounds. We might alternatively get the bounds on n tight enough to mean that there are only a few possibilities left, in which case just listing them and multiplying by 59 to see whether we get a solution will be the quickest way to close off the case.

If we get stuck or if we're making too slow progress, we'll split into cases - but obviously we want to keep such splitting into cases down to a low level!

So to start the process, we know that 59n is a 5-digit number, so 10000 <= 59n <= 99999, with forbidden sets {0,5} for D and I and {0} for the rest. Refining the lower bound first takes it to 12345, which doesn't need any further increases to get to a multiple of 3 that avoids using repeated or forbidden digits. Refining the upper bound takes it to 98765, which needs reducing to 98763 to take it to a multiple of 3, but no further reductions by 3 to avoid repeated or forbidden digits. So the bounds on 59n become 12345 <= 59n <= 98763.

Those bounds on 59n imply 210 <= n <= 1673, and the fact that n is a 4-digit number allows us to tighten them to 1000 <= n <= 1673. We now know that A=1, so can extend the forbidden sets to {0,1,5,9} for D and I and {0,1} for the rest.

Refining those bounds on n takes 1000 first to 1234, then to 1236, and 1673 first to itself, then to 1671 to make it a multiple of 3, then avoids the repeated digits in 1671, 1668, 1665 and 1662 (and the forbidden D=5 in 1665) to end up at 1659. So 1236 <= n <= 1659.

Multiplying by 59 gives 72924 <= 59n <= 97881. I could refine that further, but progress would be pretty slow, only getting up to 72936 <= 59n <= 97863 (from here on, I'll omit detailed descriptions of the exact stages of refinement). So at this point, I will split into the three cases that E=7, E=8 or E=9:

E=7

The forbidden digits become {0,1,3,5,7,9} for D and I, and {0,1,7} for the rest, and the known bounds on 59n are 72924 <= 59n <= 79999. Refining those gives 72936 <= 59n <= 79863.

Dividing by 59 gives 1237 <= n <= 1353. Refining that produces 1248 <= n <= 1326. Multiplying by 59 gives 73632 <= 59n <= 78234, and refining that only makes slow progress. So instead, we stick to 1248 <= n <= 1326, and split into the two cases B=2 and B=3:

B=2: The forbidden digits become {0,1,2,3,5,7,8,9} for D and I, and {0,1,2,7} for the rest, and 1248 <= n <= 1299 refines to 1254 <= n <= 1296. The multiple-of-3 requirement and the large number of forbidden digits for D mean that only 1254, 1284 and 1296 are possibilities; the corresponding values of 59n are 73986, 75756 and 76464. The last two are not solutions, while the first is the solution n = 1254, 59n = 73986.

B=3: The forbidden digits become {0,1,3,5,7,9} for D and I, and {0,1,3,7} for the rest, and 1300 <= n <= 1326 refines to 1326 <= n <= 1326. So n = 1326 is the only possibility, and for that, 59n = 78234 does not produce a solution.

E=8

The forbidden digits become {0,1,2,5,8,9} for D and I, and {0,1,8} for the rest, and the known bounds on 59n are 80000 <= 59n <= 89999. Refining those gives 82347 <= 59n <= 89763.

Dividing by 59 gives 1396 <= n <= 1521, which refines to 1437 <= n <= 1497. So we know that B=4, and the non-OK digits become forbidden digits become {0,1,2,4,5,6,8,9} for D and I, and {0,1,4,8} for the rest. Those constraints reduce the remaining possibilities to 1437, 1467, 1473 and 1497; multiplying by 59 gives 84783, 86553, 86907 and 88323 respectively, none of which is a solution.

E=9

The forbidden digits become {0,1,5,9} for D and I, and {0,1,9} for the rest, and the known bounds on 59n are 90000 <= 59n <= 97881. Refining those gives 92346 <= 59n <= 97863.

Dividing by 59 gives 1566 <= n <= 1658. Refining that produces 1572 <= n <= 1653. Multiplying by 59 gives 92748 <= 59n <= 97527, and refining that only makes slow progress. So instead, we stick to 1572 <= n <= 1653, and split into the two cases B=5 and B=6:

B=5: The forbidden digits become {0,1,5,9} for D and I, and {0,1,5,9} for the rest, and 1572 <= n <= 1599 refines to 1572 <= n <= 1596. The possibilities are 1572, 1578, 1584, 1587, 1593 and 1596, corresponding to 92748, 93102, 93456, 93633, 93987 and 94164 for 59n, none of which is a solution.

B=6: The forbidden digits become {0,1,4,5,6,9} for D and I, and {0,1,6,9} for the rest, and 1600 <= n <= 1653 refines to 1623 <= n <= 1653. The possibilities are 1623, 1632, 1638, 1647 and 1653, corresponding to 95757, 96288, 96642, 97173 and 97527 for 59n, none of which is a solution.

So the only solution is 1254/73986 = 1/59.

(*) A 'digital root' can be 0, but only if the number we're taking the digital root of is 0. I.e. that's a very special case which obviously doesn't apply here.


ABCD/EFGHI = 1/43

We want a 4-digit number n = ABCD such that 43n = EFGHI with (A,B,C,D,E,F,G,H,I) being the digits 1-9 in some order. A similar argument to that for 1/59 says that if n has 'digital root' (1,2,3,4,5,6,7,8,9), 43n must have 'digital root' both the corresponding one of (7,5,3,1,8,6,4,2,9) and the corresponding one of (8,7,6,5,4,3,2,1,9). Inspection shows that this is only possible when n has 'digital root' 9, i.e. when n is a multiple of 9. So multiples of 9 play the same role in solutions for 1/43 that multiples of 3 played for 1/59 (this cuts the density of possibilities in the search space down a great deal, which is distinctly useful given that the search space is larger).

The observation arising from 60n = n+59n = ABCD+EFGHI having last digit 0 that D and I cannot be 5, nor 10-d if d is another digit they cannot be, only has a more complicated analogue arising from ABCD + 3*EFGHI = n+3*43*n = 130n. It is that if D is (1,2,3,4,5,6,7,8,9), then I is the corresponding one of (3,6,9,2,5,8,1,4,7), and vice versa. That implies (a) that 5 is a forbidden digit for D and I; (b) that if 1 is a digit already used for one of A, B, C, E, F, G or H, then 7 is also a forbidden digit for D and 3 for I, and corresponding statements for (2,4,6), (3,1,9), (4,8,2), (6,2,8), (7,9,1), (8,6,4) and (9,3,7) replacing (1,7,3).

To start the process, we know that 43n is a 5-digit number, so 10000 <= 43n <= 99999, with forbidden sets {0,5} for D, {0,5} for I, and {0} for the rest. That refines to 12348 <= 43n <= 98721. Dividing by 43 produces 288 <= n <= 2295, which refines to 1269 <= n <= 2196. This produces 54567 <= 43n <= 94428, with 54567 <= 43n <= 85999 corresponding to values of n below 2000 (and A=1) and 86000 <= 43n <= 94428 to values of n that are 2000 or greater (so A=2). That gives five possible combinations of A and E:

A=1, E=5

These correspond to 54567 <= 43n <= 59999 and 1269 <= n <= 1395. The forbidden sets become {0,1,5,7} for D, {0,1,3,5} for I, and {0,1,5} for the rest.

Refining 54567 <= 43n <= 59999 produces 54639 <= 43n <= 59832. Dividing by 43 produces 1271 <= n <= 1391, which refines to 1278 <= n <= 1386. Listing the possibilities gives 1278, 1296, 1368 and 1386, which produce 54954, 55728, 58824 and 59598 respectively for 43n, none of which is a solution.

A=1, E=6

These correspond to 60000 <= 43n <= 69999 and 1396 <= n <= 1627. The forbidden sets become {0,1,2,5,6,7} for D, {0,1,3,5,6,8} for I, and {0,1,6} for the rest.

Refining 60000 <= 43n <= 69999 produces 62379 <= 43n <= 69732. Dividing by 43 produces 1451 <= n <= 1621, which refines to 1458 <= n <= 1593. Listing the possibilities gives 1458, 1494, 1539, 1548, 1584 and 1593, which produce 62694, 64242, 66177, 66564, 68112 and 68499 respectively for 43n, none of which is a solution.

A=1, E=7

These correspond to 70000 <= 43n <= 79999 and 1628 <= n <= 1860. The forbidden sets become {0,1,5,7,9} for D, {0,1,3,5,7} for I, and {0,1,7} for the rest.

Refining 70000 <= 43n <= 79999 produces 72369 <= 43n <= 79632. Dividing by 43 produces 1683 <= n <= 1851, which refines to 1683 <= n <= 1836. The fact that 7 is a forbidden digit for B restricts the possibilities to 1683, 1692, 1800, 1809, 1818, 1827 and 1836, and only 1683, 1692 and 1836 are left after eliminating possibilities with repeated or other forbidden digits. They produce 72369, 72756 and 78948 respectively for 43n, none of which is a solution.

A=1, E=8

These correspond to 80000 <= 43n <= 85999 and 1861 <= n <= 1999. The forbidden sets become {0,1,5,6,7,8} for D, {0,1,3,4,5,8} for I, and {0,1,8} for the rest.

Refining 80000 <= 43n <= 85999 produces 82359 <= 43n <= 85932. Dividing by 43 produces 1916 <= n <= 1998, which refines to 1953 <= n <= 1962. The only two possibilities are 1953 and 1962, which produce 83979 and 84366 respectively for 43n, neither of which is a solution.

A=2, E=8

These correspond to 86000 <= 43n <= 89999 and 2000 <= n <= 2093. This implies that B=0, which is impossible, so doesn't lead to any solutions.

A=2, E=9

These correspond to 90000 <= 43n <= 94428 and 2094 <= n <= 2196. The forbidden sets become {0,2,3,4,5,9} for D, {0,2,5,6,7,9} for I, and {0,2,9} for the rest.

Refining 2094 <= n <= 2196 leads to 2178 <= n <= 2187. The only two possibilities are 2178 and 2187, which led to 93654 and 94041 for 43n. The first of those is the only solution 2178/93654 = 1/43.

Gengulphus

[Gengulphus]

In the context of the thread, it seems worth pointing out that "solve a new decimal alphametic-style puzzle with computer aid, in as little elapsed time as possible" is a completely-solved problem. In particular, such puzzles involve finding a permutation of the nine digits 1-9 (or ten digits 0-9) that when assigned to nine variables A-I (or ten variables A-J) satisfies a particular set of simple conditions. The solution is to write a 'brute force' program in an efficient computer language that works though the 9! = 362880 or 10! = 3628800 permutations, checking whether a particular formula is true for each of them and printing the permutation as a solution if it is. An efficient set of loops to work though the 9! or 10! permutations is an interesting programming challenge, but is the same across all such puzzles with a given set of digits. The formula check and printing of the solution if true is a single statement in the middle of the program, along the lines of (for the C language and the ABCD/EFGHI = 1/43 problem):

if (59*(1000*A+100*B+10*C+D) == 10000*E+1000*F+100*G+10*H+I) print_solution();

Once one has such a program for one puzzle involving a particular digit set, the quickest solution for another such puzzle is probably going to be:

1) Dig out a previous program for such a puzzle and take a copy of it;
2) Rewrite the condition in that formula-checking statement;
3) Recompile the modified program;
4) Run the newly-compiled program.

If you're like me, step 1 is likely to take the most time! Step 2 may take a bit of time, especially as some translation of the original problem or support by e.g. C preprocessor directives might be needed. Step 3 should take a second or two (at least once one has eliminated any typos introduced in step 2), and step 4 should take a matter of seconds - it really doesn't take a well-programmed computer long to run through a few million possibilities, doing a simple check on each.

Overall, the four steps are pretty certain to take less time than writing a new, more efficient program or finding a good 'manual' solution. For example, for the 1/43 problem, one could put in the thought required to see that [spoiler-protected argument based on work in preceding post] EFGHI must be a multiple of both 9 and 43, thus of LCM(9,43) = 387. So its possible values are the 233 multiples of 387 from 26*387 = 10062 to 258*387 = 99846. Similarly, ABCD must be a multiple of 9 from 112*9 = 1008 to 1111*9 = 9999, and the two multiples must use the same multiplier, so there are actually just the 147 multiples of 387 from 112*387 = 43344 to 258*387 = 99846 to check. A program to check out those 147 values would have a more expensive check than "59*(1000*A+100*B+10*C+D) == 10000*E+1000*F+100*G+10*H+I" to do, but it's nothing like the couple of thousand times more expensive required to outweigh doing 147 checks rather than 362880... So if the objective were to make the time taken to run the program (i.e. for step 4 alone) as small as possible, it would be better. But as it is, it will save at most a few seconds on step 4, while writing a new program is liable to take many minutes more than steps 1 and 2, so it will take more total elapsed time.

And similarly, any 'manual' solution is liable to take quite a lot longer than steps 1 and 2. That incidentally applies even to checking out the 147 multiples of 387, which one can run through quite quickly (at least on my calculator, by typing "43344+387" and then clicking the = key repeatedly) to find the ones with 5 distinct nonzero digits, which are:

45279, 46287, 48375, 48762, 49536, 58437, 69273, 71982, 72369, 74691, 76239, 78561, 81657, 82431, 83592, 84753, 85914, 87462, 93267, 93654, 94815, 97524

Dividing each of those 22 possibilities by 43 then finds that 93654/43 = 2178 is the only one that leads to a solution. That's probably a quicker 'manual' solution than the one I've given above (it certainly takes less time to type!), but it's still slower than the quick edits required to a program written earlier to do a pure 'brute force' search for solutions to a decimal alphametic-style puzzle.

So why do it a longer way? I've two answers to that, the first of which is that it's simply more fun - and having fun is the point of doing puzzles! Slogging through a list of hundreds of possibilities, doing something fairly trivial for each of them, is both tedious and unchallenging, even though it may well be quicker than finding a way to make tricky logical deductions, divide the problem up into half a dozen cases or so and deal with each of them by a separate argument, etc. If someone were willing to employ me at piece rate to solve such problems before computers were invented and I simply wanted to maximise my earnings, I would probably use methods like those in the last paragraph and put up with the tedium. But with my actual objective being to have fun, I'll enjoy the intellectual challenge of finding the more sophisticated method much more!

The second answer is to do with scalability. A 'brute force' search is very effective for dealing with decimal alphametic-style puzzles because they only have 10! = 3628800 possible solutions, a number that a computer can easily enumerate and test individually in a matter of seconds. But what if one were faced with a hexadecimal alphametic-style puzzle, for which the 'brute force' search will need to enumerate and individually test over 20 trillion (16! = 20922789888000) possibilities. A 2.5 GHz 8-core processor would do 20 billion processor-core-cycles per second, so would take over 1000 seconds (or a bit more than a quarter of a hour) to do a single processor-core-cycle for each possibility. And even a very carefully optimised 'brute force' search program is likely to take quite a few hundreds of processor-core-cycles to enumerate and test each possibility, i.e. quite a few days to complete the search (100 quarter hours = 25 hours = a bit over a day). And doing it that quickly is likely to take quite a bit of optimisation work - e.g. hand-coding the inner loops in assembly language. Just using ordinary compilation of a high-level language, think in terms of weeks or even months to complete the search.

To deal with that, one needs to find better methods than pure 'brute force'. They're not usually difficult to find. For example, a program to solve ABCD/EFGHI = 1/n could do the search by trying out the 9 possibilities for D, using ABCD*n = EFGHI to deduce I, then try out the 7 possibilities for C, using ABCD*n = EFGHI again to deduce H, etc. It will end up with something like 9*7*5*3*1 = 945 possibilities to check rather than 9! = 362880. Which for a decimal alphametic-style problem like that one is unlikely to be worth the extra programming effort and taking on the job of choosing a good order in which to tackle the nine variables A-I. But for a similar hexadecimal problem, it's the difference between 15*13*11*9*7*5*3*1 = 2027025 and 15! = 1307674368000 possibilities, which will make a big difference to how long the program takes to run! In particular, that simple non-'brute force' optimisation of the search which brings the solution down to something like the human scale in the decimal case, also brings it down from the weeks-or-even-months computer scale to the few-seconds computer scale in the hexadecimal case.

So basically, the second reason is that study of how one might find solutions to small-scale instances of a problem without significant computer aid can also serve to bring larger-scale instances of it within the feasible range for computers. But I will finally add that (at least IMHO) having the fun of an intellectual challenge is the more important reason. Indeed, I think it's almost implicit in the description 'puzzle' that unless otherwise stated, one should solve it without significant computer aid and that presenting a solution done with significant computer aid is essentially an admission of defeat. If computers are supposed to be used, either the puzzle statement should say that they are, or a description like 'programming challenge' should be used instead.

Gengulphus

[GoSeigen]

I too am wondering if Gengulphus - or anyone - will be along with a more elegant solution. ...

Below are my best efforts so far for 1/59 and 1/43. I've done 1/59 is a great deal of detail - almost certainly far too much for the more dedicated mathematicians and more mathematically-inclined puzzlers among you!

Gengulphus, thank you, that is a very comprehensive description of the method, a vast improvement on my very brief and sloppy notes!

I've only had a couple of minutes to skim through your notes and don't know if I missed it, but did you mention for the solution of ABCD/EFGHI = 1/59, that that the units of the four and five digit numbers always sum to ten, i.e. D+I=10? In my solution this fact shortened the search a little.

Sorry if you did indeed cover this point. Will read your post carefully later.


GS

[Gengulphus]

I've only had a couple of minutes to skim through your notes and don't know if I missed it, but did you mention for the solution of ABCD/EFGHI = 1/59, that that the units of the four and five digit numbers always sum to ten, i.e. D+I=10? In my solution this fact shortened the search a little.

Yes, I did - fourth paragraph of that solution. And yes, once I realised that, it shortened the search considerably compared with my initial attempt! And indeed, a rather more complex variant of the same idea helped with the ABCD/EFGHI = 1/43 problem, and should help with the ABCD/EFGHI = 1/37 problem. The ABCD/EFGHI = 1/18 problem should also be helped by a similar observation, though of a rather trickier form due to 18 having a common factor 2 with the base 10: it basically says that I must be even, and that for each possible value of I, there are two possible values of D: 4 and 9 for I=2, 3 and 8 for I=4, 2 and 7 for I=6, and 1 and 6 for I=8. Correspondingly, each possible value of D uniquely determines I.

Gengulphus

[cinelli]

UncleEbenezer was very quick off the mark with the correct solution:

1593/28674 = 1/18
1782/65934 = 1/37
2178/93654 = 1/43
1254/73986 = 1/59

My own solution was a brute force approach. I am not at all proud of my clumsy program which makes very heavy weather of generating the 9! permutations. I am sure there are problems for which a “sledge hammer” approach is the best. After all we are all using computers. Then a prize could be given for the most elegant program.

When listing all the possible fractions, I looked for a pattern and wondered about the digital roots of possibilities but could see no pattern. I agree with Uncle’s total of 187 and those fractions which can be created are 1/n where n takes the values

2 3 4 5 6 7 8 9 12 13 14 15 16 17 18 19 22 23 24 26 27 28 29 32 35 37
38 43 44 46 52 53 59 62 66 68

The value of n with most different arrangements is 8 followed, perhaps surprisingly, by 17. Only 18, 22, 28, 32, 37, 43, 46, 52, 59, 66 and 68 have unique arrangements. And that is why I selected 18, 37, 43 and 59 in the puzzle – you don’t want to set a brain teaser with many solutions.

Missing from the above list are (fairly clearly?) all multiples of 10 plus 11 21 25 31 33 34 36 39 41 42 45 47 48 49 51 54 55 56 57 58 61 63 64 65 67. Do these numbers have anything in common? Is any digital root excluded? No. Are they all prime or non-prime? No.

Cinelli

[Gengulphus]

My own solution was a brute force approach. I am not at all proud of my clumsy program which makes very heavy weather of generating the 9! permutations. ...

If you want a quick method to do so, take a look at https://en.wikipedia.org/wiki/Heap%27s_algorithm.

Edit: I'll add that producing a reasonably concise explanation of why it generates all permutations is a not entirely trivial puzzle!

Gengulphus

[cinelli]

If you want a quick method to do so, take a look at https://en.wikipedia.org/wiki/Heap%27s_algorithm.

Edit: I'll add that producing a reasonably concise explanation of why it generates all permutations is a not entirely trivial puzzle!

Thanks, Gengulphus, for that very interesting link. You weren't kidding when you said it is not entirely trivial! I wonder if I could program it without completely understanding the method ...

And thank you for your comprehensive 1400-word solution for 1/59. I am delighted that you enjoy solving not only this puzzle but all the others posted here. I look forward to a puzzling 2019, and possibly a not too taxing brain teaser on Christmas Day.

Cinelli