Teaser 3232: Digital processing
From The Sunday Times, 1st September 2024 [link] [link]
I divided 1 by 5 in base 7 in the following way. I started with 1, multiplied by the base (7), recorded the result on division by 5 as a digit (1), then used the remainder (2) to repeat the process until the remainder became 0 or the pattern was about to repeat. The result was 0.1254 with those four digits then repeating.
For some base no more than 20 I also calculated the result of dividing 1 by all numbers from 2 up to the base minus 1. With one of these divisors the result had the “digit” 14 at one point followed immediately by the “digit” 13. Some “digits” never occurred in the fractional part with any of these divisors.
What “digits” (in increasing order) never occurred?
[teaser3232]
Frits, 
GeoffR are discussing. 
S2T2 
Jim Randell 6:36 am on 1 September 2024 Permalink |
We can use the [[
recurring()]] function from the enigma.py library to calculate the expansion of a fraction in different bases. (Originally written for Enigma 1247).The following Python program runs in 69ms. (Internal runtime is 949µs).
Run: [ @jdoodle ]
from enigma import (irange, recurring, int2base, base2int, format_recurring, printf) # look for digit X followed by digit Y (X, Y) = (14, 13) # {14}:{13} = "ED" # examine reciprocals in base <b> def solve(b, verbose=0): # look for subsequence X:Y i2b = lambda n: int2base(n, base=b) (ss, f) = (i2b(X) + i2b(Y), 0) # unused digits ds = set(i2b(n) for n in irange(0, b - 1)) for k in irange(2, b - 1): (i, nr, rr) = recurring(1, k, base=b) if verbose: printf("[{b}] {k} -> {x}", x=format_recurring((i, nr, rr))) if ss in nr + rr + rr[:1]: f = 1 ds.difference_update(nr, rr) if f: # output solution (using integer digits) ds = list(base2int(d, base=b) for d in ds) printf("base={b} -> unused digits = {ds}", ds=sorted(ds)) # consider bases up to 20 for b in irange(max(X, Y) + 1, 20): solve(b)Solution: The unused digits are: 0, 12, 15, 17.
In base 18 the reciprocals from 1/2 to 1/17 have the following expansions:
The digits (from 0123456789ABCDEFGH) that do not occur in the fractional parts of these expansions are:
The puzzle limits us to bases up to 20, but the next solutions don’t occur until bases 58, 86, 142.
LikeLike
Frits 3:00 pm on 2 September 2024 Permalink |
@Jim, Brian’s counting of the divisors that have the special subsequence is more pure than our approach (as it doesn’t say “With at least one of these divisors”).
LikeLike
Jim Randell 4:11 pm on 2 September 2024 Permalink |
@Frits: Unless the puzzle is explicit about there being exactly one case, I usually take a relaxed interpretation where the finding of one case is sufficient (a logical existential quantification). In this puzzle we don’t need to use the strict interpretation of “exactly one”.
LikeLike
Frits 10:44 am on 1 September 2024 Permalink |
# does list <lst2> occur in list <lst1> inList = lambda lst1, lst2: any(lst1[i:i + len(lst2)] == lst2 for i in range(len(lst1) - len(lst2) + 1)) # return digits in base b in the fraction k / b (where k < b) # (not repeating decimals) def divide(b, k): r, s, rs = 1, [], set() while True: (d, r) = divmod(r * b, k) s.append(d) # break if no remainder or repeating decimals encountered if not r or r in rs: break rs.add(r) return s # consider bases from 15 to 20 (base must be higher than 14) for b in range(15, 21): found1413, seen = 0, set() for k in range(2, b): dgts = divide(b, k) # does list [14, 13] occur in <dgts>? if inList(dgts, [14, 13]): found1413 = 1 seen |= set(dgts) if found1413: print(f"answer: {sorted(set(range(b)).difference(seen))}")LikeLike
Jim Randell 11:31 am on 2 September 2024 Permalink |
@Frits: I don’t see how you can differentiate between recurring and non-recurring expansions returned by your [[
divide()]] routine.Would your program spot the occurrence of adjacent digits D and 6 in the expansion of 1/15 in base 20?
LikeLike
Frits 2:48 pm on 2 September 2024 Permalink |
@Jim, the divide function has been made with the comment “(where k less than b)” so the first question I don’t understand. I don’t think I need to differentiate between recurring and non-recurring except for the valid 2nd point you make (divide(20, 15)).
Here is the adjustment (assuming we have have to scan for only 2 “digits”):
# does list <lst2> occur in list <lst1> isSubList = lambda lst1, lst2: any(lst1[i:i + len(lst2)] == lst2 for i in range(len(lst1) - len(lst2) + 1)) # return "digits" in base b in the fraction 1 / k (where k < b) # (not repeating "decimals") def divide(b, k): assert b > k r, s, dct = 1, [], dict() while True: p = r (d, r) = divmod(r * b, k) s.append(d) if not r: return s # repeating "decimals" encountered? if r in dct: # also suffix first "digit" of repetend as we have to look # for a sequence of two "digits" return s if r == p else s + [dct[r]] dct[p] = d # consider bases from 15 to 20 (base must be higher than 14) for b in range(15, 21): found1413, seen = 0, set() for k in range(2, b): dgts = divide(b, k) # does list [14, 13] occur in <dgts>? if isSubList(dgts, [14, 13]): found1413 = 1 seen |= set(dgts) if found1413: print(f"answer: {sorted(set(range(b)).difference(seen))}")LikeLike
Jim Randell 4:15 pm on 2 September 2024 Permalink |
@Frits: It was the same point really. I was trying to show a case where the return value was obviously ambiguous. But I strayed outside the acceptable parameters of your function. I should have used a different example.
LikeLike
GeoffR 11:38 am on 2 September 2024 Permalink |
@Jim:
Can you please show how the first paragraph works to get an answer of 0.1245 with th same repeating digits? (as the main teaser is the second paragraph)
LikeLike
Jim Randell 12:02 pm on 2 September 2024 Permalink |
@GeoffR:
Starting with 1 we perform the following calculations:
At the end of these 4 steps we have written down 1254 and are about to start the next step with the remainder 1. But this is the same as the value we started with at the beginning, so we will just go through the same steps again.
So the result is:
LikeLike
Frits 9:07 pm on 4 September 2024 Permalink |
Limiting the calls to divide().
# return "digits" in base b in the fraction 1 / k (where k < b) # (not repeating "decimals") def divide(b, k): assert b > k r, s, dct = 1, [], dict() while True: p = r (d, r) = divmod(r * b, k) s.append(d) if not r: return s # repeating "decimals" encountered? if r in dct: # also suffix first "digit" of repetend as we have to look # for a sequence of two "digits" return s if r == p else s + [dct[r]] dct[p] = d seq = [14, 13] # consider bases to 20 for b in range(max(seq) + 1, 21): for k in range(2, b): # 14 = (r * b) // k r1 = (seq[0] * k) // b + 1 (d2, r2) = divmod(r1 * b, k) if d2 != seq[0]: continue (d3, r3) = divmod(r2 * b, k) # seq[0] has to be followed by seq[1] if d3 != seq[1]: continue # check if first specified item is one of the "digits" in the fraction dgts = divide(b, k) if seq[0] not in dgts: continue seen = set(dgts) for k2 in range(2, b): if k2 == k: continue seen |= set(divide(b, k2)) print(f"answer: {sorted(set(range(b)).difference(seen))}") breakLikeLike