Teaser 3081: Connect four
From The Sunday Times, 10th October 2021 [link] [link]
I have four different two-digit numbers, each having at least one digit which is a three. When I multiply any three of these numbers together I get a product that, with the inclusion of a leading zero, is one or more repetitions of the repetend of the reciprocal of the fourth two-digit number. A repetend is the repeating or recurring decimal of a number. For example 1 divided by 27 is 0.037037…, giving a repetend of 037; in that case, the product would be 37 or 37037 or 37037037 etc.
What, in ascending order, are the four two-digit numbers?
[teaser3081]
Tony Brooke-Taylor, 
Jim Olson, and 3 others are discussing. 
S2T2 
Jim Randell 4:59 pm on 8 October 2021 Permalink |
This Python program uses the [[
recurring()]] function from the enigma.py library to calculate the repetends. It runs in 51ms.Run: [ @replit ]
from enigma import (enigma, irange, nsplit, subsets, multiply, format_recurring, printf) # find the repetend of 1/n (recurring part of the recurring decimal representation) recurring = enigma.cache(lambda n: enigma.recurring(1, n, recur=1)) # consider 2-digit numbers containing the digit 3 ns = list(n for n in irange(10, 99) if 3 in nsplit(n)) # check this set of numbers def check(ss, verbose=0): m = multiply(ss) for n in ss: # calculate the product p = str(m // n) # find the repetend (rr) (i, nr, rr) = recurring(n) # if the repetend has leading zeros extend the product for d in rr: if d != '0': break p = '0' + p # remove copies of the repetend from the product k = len(rr) while p.startswith(rr): p = p[k:] # anything left? if p: return False if verbose: printf("-> 1/{n} = {f}; product = {p}", f=format_recurring((i, nr, rr)), p=m // n) # if we get this far we've done it return True # select 4 of the numbers for ss in subsets(ns, size=4): if check(ss): printf("{ss}:") check(ss, verbose=1) printf()Solution: The four numbers are: 13, 33, 37, 63.
Without the requirement that each of the 2-digit number must contain at least one 3, we can find further sets:
All these sets have a product of 999999.
And this is a consequence of the fact that for any fraction f ≤ 1, if a k-length repdigit of 9, multiplied by f gives an integer result, then that result is a k-length repetend of f (suitably padded with leading zeros, and there will be no non-repeating part of the decimal expansion).
So any set of numbers that multiplies to a 9-repdigit will form such a set.
For example, multiplying the numbers in the solution to give pairs:
Or:
Programatically we can easily find 4-sets from the candidates that multiply together to give a 9-repdigit:
from enigma import (irange, nsplit, subsets, multiply, seq_all_same, printf) # candidate numbers (can't be divisible by 2 or 5) ns = list(n for n in irange(10, 99) if 3 in nsplit(n) and n % 2 and n % 5) # look for 4-subsets that multiply to a 9-repdigit for ss in subsets(ns, size=4): p = multiply(ss) if seq_all_same(nsplit(p), value=9): printf("{ss}; product={p}")Which we could then pass to the [[
check()]] function above to verify the solution and output information for each number.But there are sets that don’t have a 9-repdigit product, and do have decimal expansions with non-repeating parts, e.g.:
(Although I haven’t found any that aren’t a 9-repdigit multiplied by a power of 10).
But I did find that the four 2-digit numbers {28, 74, 78, 99} have the following property:
Unfortunately it doesn’t work for the reciprocals of the other terms, but I did notice:
LikeLike
Jim Randell 11:15 pm on 8 October 2021 Permalink |
And here is a faster (but slightly longer) version, using the same [[
check()]] function, that avoids looking at all possible 4-subsets of the candidate numbers, by discarding those with a repetend that is larger than the largest possible product.It runs in 48ms (and the internal runtime is 884µs).
Run: [ @replit ]
from enigma import (enigma, irange, nsplit, multiply, subsets, format_recurring, printf) # find the repetend of 1/n (recurring part of the recurring decimal representation) recurring = enigma.cached(lambda n: enigma.recurring(1, n, recur=1)) # consider 2-digit numbers containing the digit 3 ns = list(n for n in irange(10, 99) if 3 in nsplit(n)) # map numbers to repetends # [[ and rr[0] == '0' ]] to require repetend has a leading zero # [[ and (not nr) ]] to require no non-repeating part rep = dict((n, rr) for (n, (i, nr, rr)) in ((n, recurring(n)) for n in ns) if rr) # remove any numbers with repetends that are too big while True: M = multiply(ns[-3:]) ks = list() for (k, v) in rep.items(): if int(v) > M: ks.append(k) if not ks: break for k in ks: del rep[k] ns = sorted(rep.keys()) # check a set of numbers def check(ss, verbose=0): m = multiply(ss) if verbose: printf("{ss}: product = {m}") for n in ss: # calculate the product p = str(m // n) # find the repetend (rr) rr = rep[n] # if the repetend has leading zeros extend the product for d in rr: if d != '0': break p = '0' + p # remove copies of the repetend from the product k = len(rr) while p.startswith(rr): p = p[k:] # anything left? if p: return False if verbose: printf("-> 1/{n} = {f}; product = {p}", f=format_recurring(*recurring(n)), p=m // n) # if we get this far we've done it return True # select 4 of the numbers for ss in subsets(ns, size=4): if check(ss): check(ss, verbose=1) printf()LikeLike
GeoffR 10:35 pm on 8 October 2021 Permalink |
Instead of looking for repeating digit patterns, I thought I would try equating sets of digits in the multiplication of the three two-digit numbers with the digits in the reciprocal of the fourth two-digit number, Not a conventional approach, but it seems to work.
A set length of nine for reciprocals/multiplications proved adequate to capture the repeating digits patterns for this set comparison method. I omitted the leading zero and decimal point for reciprocal digits set to compare them with multiplication digits. I found the full length decimal reciprocal could give a last digit which was not part of the general repeating pattern.
from enigma import irange, nsplit from itertools import combinations N4 = [] # list for the groups of four two-digit numbers # consider 2-digit numbers containing the digit 3 ns = list(n for n in irange(10, 99) if 3 in nsplit(n)) for p in combinations(ns, 4): ab, cd, ef, gh = p # check 1st tuple of three numbers and the reciprocal s1 = set(str(ab * cd * ef)[:9]).difference(set(['0'])) r1 = set(str(1 / gh)[:9]).difference(set(['.', '0'])) if s1 == r1: # check 2nd tuple of three numbers and the reciprocal s2 = set(str(ab * cd * gh)[:9]).difference(set(['0'])) r2 = set(str(1 / ef)[:9]).difference(set(['.', '0'])) if s2 == r2: # check 3rd tuple of three numbers and the reciprocal s3 = set(str(ab * ef * gh)[:9]).difference(set(['0'])) r3 = set(str(1 / cd)[:9]).difference(set(['.', '0'])) if s3 == r3: # check 4th tuple of three numbers and the reciprocal s4 = set(str(cd * ef * gh)[:9]).difference(set(['0'])) r4 = set(str(1 / ab)[:9]).difference(set(['.', '0'])) if s4 == r4: L = sorted([ab, cd, ef, gh]) if L not in N4: N4.append(L) if len(N4) == 1: print(f"Four two digit numbers are {N4[0]}")LikeLike
Frits 5:09 pm on 9 October 2021 Permalink |
from enigma import divisors # consider 2-digit numbers containing the digit 3 nbrs = list(n for n in range(10, 100) if '3' in str(n)) # retrieve repeating decimals of 1 / n def repdec(n): c = 100 dgts = "" done = dict() i = 0 while True: if c in done: rep = dgts[done[c]:] if rep[-1] == '0': rep = '0' + rep[:-1] return rep done[c] = i q, r = divmod(c, n) dgts += str(q) c = 10 * r i += 1 # decompose number <t> into <k> numbers from <ns> # so that product of <k> numbers equals <t> def decompose(t, k, ns, s=[]): if k == 1: if t in ns and t >= s[-1]: yield s + [t] else: for n in ns: if n not in s and (not s or n >= s[-1]): yield from decompose(t // n, k - 1, ns.difference([n]), s + [n]) d = dict() for n in nbrs: rep = repdec(n) lngth = len(rep) if lngth > 7 or rep == 0: continue r = rep # extend up to 6 digits for _ in range(6 // lngth): prod = int(r) for _ in range(1): # dummy loop used for breaking # 13 * 23 * 30 <= product <= 73 * 83 * 93 if not(8970 <= prod <= 563487): break # collect all divisors of product divs = [x for x in divisors(prod) if x in nbrs] # skip if less than 3 valid divisors if len(divs) < 3: break # check if product of 3 numbers equals <prod> for decomp in decompose(prod, 3, set(divs)): n4 = tuple(sorted([n] + decomp)) d[n4] = d.get(n4, 0) + 1 r += rep # extend up to 6 digits # sets of four 2-digit numbers must have been encountered four times for k, v in d.items(): if v == 4: print(f"answer: {k}")LikeLike
Frits 11:15 am on 11 October 2021 Permalink |
or with a recursive function:
LikeLike
Jim Randell 12:34 pm on 11 October 2021 Permalink |
It’s certainly short, although not necessarily very readable. But it does produce the right answer for positive reciprocals with a non-terminating decimal expansion.
The puzzle text isn’t completely clear what the intended repetend is for fractions with a normally terminating decimal expansion. You could argue that in this case there is no repetend, and these numbers can be discarded.
But I prefer the definition that the repetend is the shortest and earliest repeating section of the non-terminating decimal representation of the fraction.
As every non-zero fraction has a unique non-terminating decimal expansion, this is well-defined.
And it just so happens it is what the [[
recurring()]] function returns when [[recur=1]] is set. (The [[recurring()]] function was originally written for Enigma 1247, but has proved useful in several other Enigma puzzles).So, for example, we have (with repetends in parentheses):
But, it does seem to be possible to solve this puzzle with a less well defined version of “repetend”.
LikeLike
Alex. T,Sutherland 1:59 pm on 10 October 2021 Permalink |
Each of the answer numbers must have a repeatable characteristic.
(a) Number of possible x3,3x numbers =17. (b) Only 6 from these 17 are repeatable.
(c) Evaluate any 4 from these 6 (15 possibles) to satisfy the constraints.Ony one solution.
The sum of the solution is between 140-150. Run time 25ms.
LikeLike
Jim Randell 6:41 pm on 10 October 2021 Permalink |
@Alex: I found that 8 of the numbers had viable repetends. (i.e. ones where a single repeat was not larger than the largest possible product of three numbers). Or 7 if we exclude numbers with a terminating decimal representation.
LikeLike
Tony Brooke-Taylor 9:50 am on 12 October 2021 Permalink |
Jim I think if you add the requirement for a leading zero you can reduce this number to five possibilities. I’d be curious to compare my 5 with Alex’s 6 and your 7, once the solution embargo is lifted.
LikeLike
Jim Randell 9:57 am on 12 October 2021 Permalink |
@Tony: Yes. If you require a leading zero in the repetend, then this reduces the number of candidates to 5. (I took the “inclusion of a leading zero” to be “(where necessary)”, rather than a strict requirement).
Reducing the set of candidates to 5, means there are only 5 sets of 4 numbers to check.
In fact multiplying the (numerically) first 3 numbers together, gives the repetend of one of the other 2, so the answer drops out immediately. All that’s left is to check the remaining combinations work as expected. A very simple manual solution.
LikeLike
Jim Olson 4:12 pm on 11 October 2021 Permalink |
Jim is your EnigmaticCode site down temporarily?
LikeLike
Jim Randell 4:15 pm on 11 October 2021 Permalink |
Unfortunately, yes.
It seems WordPress.com suspended the site without warning earlier today. I have contacted them to get it reinstated.
Hopefully normal service will be resumed before too long.
LikeLike
Jim Randell 6:06 pm on 12 October 2021 Permalink |
So here’s an interesting fact, repetend fans:
(And there are corresponding results for other bases).
Let’s see:
>>> format_recurring(recurring(1, sq(9))) '0.(012345679)...' >>> format_recurring(recurring(1, sq(99))) '0.(0001020304050607080910111213141516171819 2021222324252627282930313233343536373839 4041424344454647484950515253545556575859 6061626364656667686970717273747576777879 80818283848586878889909192939495969799)...' >>> format_recurring(recurring(1, sq(999))) '0.(000001002003004005006007008009010011012013014015016017018019 020021022023024025026027028029030031032033034035036037038039 ... 980981982983984985986987988989990991992993994995996997999)...'And if you want to know where that penultimate term has gone, here is Numberphile to explain it all [@youtube].
LikeLike