Teaser 3119: Hidden powers
From The Sunday Times, 3rd July 2022 [link] [link]
My grandson is studying “History since the Battle of Hastings”. I made him a game, which consisted of a row of nine cards, each with a different non-zero digit on it. Throw a standard die, note the number of spots displayed, count that number of places along the row and pause there. Throw the die again, move the corresponding number of places further along and pause again. Repeat this until you come off the end of the row, noting the digit or digits you paused on and put these together in the same order, to produce a number.
Keeping the cards in the same order I asked my grandson to try to produce a square or cube or higher power. He eventually discovered that the lowest possible such number was equal to the number of one of the years that he had been studying.
What is the order of the nine digits along the row?
[teaser3119]
Frits and 
S2T2 
Jim Randell 5:54 pm on 1 July 2022 Permalink |
It took me a little while to understand how this puzzle is supposed to work.
And despite my initial misgivings there is only one possible arrangement of digits that can lead to the situation described.
The following Python program isn’t very quick (it tries all possible arrangements of digits), but it does find the required arrangement.
The code to generate powers is adapted from Teaser 683 and Enigma 1777.
It runs in 669ms.
Run: [ @replit ]
from enigma import (Primes, nsplit, subsets, irange, tuples, printf) # generate powers (x^y) in numerical order, x >= 0, y >= 2, def powers(): # powers less than 2^2 yield 0 yield 1 # powers from 2^2 upwards base = { 2: 2 } power = { 2: 4 } maxp = 2 primes = Primes(35, expandable=1).generate(maxp + 1) while True: # find the next power n = min(power.values()) yield n # what powers are involved ps = list(p for (p, v) in power.items() if v == n) # increase the powers for p in ps: base[p] += 1 power[p] = pow(base[p], p) # do we need to add in a new power? if maxp in ps: maxp = next(primes) base[maxp] = 2 power[maxp] = pow(2, maxp) # collect candidate powers pows = list() for n in powers(): if n > 2022: break # split the power into digits ds = nsplit(n) # no 0 digits, or repeated digits if 0 in ds or len(set(ds)) != len(ds): continue pows.append((n, ds)) # check powers that can be made with an arrangement of digits def play(ss): # find powers that can be made ns = list() for (n, ds) in pows: # find indices of the digits js = list(ss.index(d) for d in ds) # check entry and exit if js[0] > 5 or js[-1] < 3: continue js.insert(0, -1) # and corresponding dice throws ts = list(y - x for (x, y) in tuples(js, 2)) if min(ts) < 1 or max(ts) > 6: continue # check the power is permissible if n < 1066: return ns.append(n) # return the list of powers return ns # consider possible arrangements of digits for ss in subsets(irange(1, 9), size=len, select="P"): ns = play(ss) if ns: printf("{ss} -> {ns}")Solution: The order of the digits is: 1, 9, 8, 7, 5, 2, 3, 4, 6.
And the smallest (and onliest) power which can be made by rolling the die is 1936, with rolls of (1, 1, 5, 2, *).
Although the puzzle talks about the lowest power that can be generated, it turns out it is the only (non-trivial) power that can be generated with the required arrangement of cards.
The puzzle will continue to work in the future, until the year 4913 (= 17³) is incorporated into the history book.
LikeLike
Jim Randell 10:13 am on 2 July 2022 Permalink |
Here’s a faster (but slightly longer) program. Instead of just trying all possible arrangements of digits, it recursively constructs arrangements that cannot give powers less than 1066, and then finds which greater powers can be made.
It runs in 174ms.
Run: [ @replit ]
from enigma import (Primes, nsplit, subsets, tuples, diff, update, printf) # generate powers (x^y) in numerical order, x >= 0, y >= 2, def powers(): # powers less than 2^2 yield 0 yield 1 # powers from 2^2 upwards base = { 2: 2 } power = { 2: 4 } maxp = 2 primes = Primes(35, expandable=1).generate(maxp + 1) while True: # find the next power n = min(power.values()) yield n # what powers are involved ps = list(p for (p, v) in power.items() if v == n) # increase the powers for p in ps: base[p] += 1 power[p] = pow(base[p], p) # do we need to add in a new power? if maxp in ps: maxp = next(primes) base[maxp] = 2 power[maxp] = pow(2, maxp) # collect candidate powers (disallowed and allowed) (xpows, pows) = (list(), list()) for n in powers(): if n > 2022: break # split the power into digits ds = nsplit(n) # no 0 digits, or repeated digits if 0 in ds or len(set(ds)) != len(ds): continue (xpows if n < 1066 else pows).append((n, ds)) # check if digit sequence <ds> can be made from arrangement <ns> def play(ns, ds): # find indices of the digits js = list(ns.index(d) for d in ds) # check entry and exit if js[0] > 5 or js[-1] < 3: return False # check corresponding dice throws (1-6) js.insert(0, -1) return all(0 < y - x < 7 for (x, y) in tuples(js, 2)) # generate arrangements <ns> that don't allow sequences <xs> to be made # ns = digit arrangement # xs = disallowed sequences # ss = allocated digits # js = indices of empty slots def solve(ns, xs, ss=set(), js=None): if not xs: yield ns else: # find the shortest sequences with the fewest missing digits fn = lambda ds: (len(set(ds).difference(ss)), len(ds)) ds = min(xs, key=fn) # choose placements for the missing digits ms = diff(ds, ss) if not js: js = set(j for (j, n) in enumerate(ns) if n is None) for ks in subsets(js, size=len(ms), select="P"): ns_ = update(ns, ks, ms) if not play(ns_, ds): # solve the rest yield from solve(ns_, xs.difference([ds]), ss.union(ms), js.difference(ks)) # find layouts that do not permit sequences from xpows for ns in solve([None] * 9, set(ds for (_, ds) in xpows)): # look for permissible powers ps = list(n for (n, ds) in pows if play(ns, ds)) if ps: printf("{ns} -> {ps}")LikeLiked by 1 person
Frits 11:28 pm on 1 July 2022 Permalink |
Reusing my code of Teaser 683 and using Jim’s early performance enhancement (also considering number 1 as a power).
from itertools import permutations def prime_factors(n): i = 2 factors = [] while i * i <= n: if n % i: i = 3 if i == 2 else i + 2 else: n //= i factors.append(i) if n > 1: factors.append(n) return factors def is_a_power(n): pf = prime_factors(n) if len(pf) < 2: return False # occurences of digits oc = {pf.count(x) for x in set(pf)} if mult_gcd(list(oc)) == 1: return False return True # calculate greatest common divisor of multiple numbers def mult_gcd(li): if len(li) == 1: return li[0] for i in range(len(li) - 1): a = li[i] b = li[i+1] while b: (a, b) = (b, a % b) if a == 1: return a li[i+1] = a return a # generate powers, stop if you encounter one less than 1067 def solve(k, s, pw=0, ns=[], rs=set()): if k > 0: # year must be before 2023 if k == 1 and pw > 202: return [] ls = len(s) for i in range(6): # check if you come off the end of the row if i > ls - 1: break p = 10 * pw + s[i] if p in pows and ls - i < 7: return [p] # recurse if worthwhile if p in powstart: res = solve(k - 1, s[i + 1:], p, ns + [i + 1], rs) if len(res) == 1: rs.add(res[0]) if res[0] < 1067: return [] # no solution # if we didn't encounter a low power return list of powers return list(rs) # collect candidate powers pows = {i for i in range(1, 2023) if is_a_power(i) and \ len(s:= str(i)) == len(set(s)) and "0" not in s} powstart = {int(str(p)[:i]) for p in pows for i in range(1, 4)} # consider possible arrangements of digits for perm in permutations(range(1, 10)): # [performance] single digit powers cannot be in slots 3, 4, 5 if {1, 4, 8, 9}.intersection(perm[3:6]): continue r = sorted(solve(4, perm, rs=set())) if r and r[0] > 1066: print(perm, "number", r[0])LikeLike
Frits 9:29 am on 2 July 2022 Permalink |
Python 3.9 introduced multiple arguments version of math.gcd so math.gcd() can be used instead of mult_gcd().
LikeLike
Jim Randell 10:14 am on 2 July 2022 Permalink |
Or you can use enigma.mgcd() which will work in a wide variety of Python implementations.
LikeLike
Frits 2:50 pm on 2 July 2022 Permalink |
Just as with Jim ‘s third program only calling solve() for 49 permutations.
Doing the checks for 2-digit and 3-digit powers in a general way is a bit slower.
Also storing digit positions in a dictionary to minimize index() calls is a bit slower.
from itertools import permutations from math import gcd def prime_factors(n): i = 2 factors = [] while i * i <= n: if n % i: i = 3 if i == 2 else i + 2 else: n //= i factors.append(i) if n > 1: factors.append(n) return factors def is_a_power(n): pf = prime_factors(n) if len(pf) < 2: return False # occurences of digits oc = {pf.count(x) for x in set(pf)} if gcd(*oc) == 1: return False return True # generate powers, stop if you encounter one less than 1067 def solve(k, s, pw=0, ns=[], rs=set()): if k > 0: # year must be before 2023 if k == 1 and pw > 202: return [] ls = len(s) for i in range(6): # check if you come off the end of the row if i > ls - 1: break p = 10 * pw + s[i] if p in pows and ls - i < 7: return [p] # recurse if worthwhile if p in powstart: res = solve(k - 1, s[i + 1:], p, ns + [i + 1], rs) if len(res) == 1: rs.add(res[0]) if res[0] < 1067: return [] # no solution # if we didn't encounter a low power return list of powers return list(rs) # collect candidate powers pows = {i for i in range(1, 2023) if is_a_power(i) and \ len(s:= str(i)) == len(set(s)) and "0" not in s} powstart = {int(str(p)[:i]) for p in pows for i in range(1, 4)} # 2-digit powers pows2 = [(x // 10, x % 10) for x in pows if 9 < x < 100] # 3-digit powers pows3 = [(x // 100, (x // 10) % 10, x % 10) for x in pows if 99 < x < 1000] # consider possible arrangements of digits for perm in permutations(range(1, 10)): # [performance] single digit powers cannot be in slots 3, 4, 5 if {1, 4, 8, 9}.intersection(perm[3:6]): continue # check 2-digit powers for a, b in pows2: posa = perm.index(a) posb = perm.index(b) # can we make the power in 2 jumps and then come off the end of the row? if 0 < (posb - posa) < 7 and posa < 6 and posb > 2: break else: # no break # check 3-digit powers for a, b, c in pows3: posa = perm.index(a) posb = perm.index(b) posc = perm.index(c) # can we make the power in 3 jumps and # then come off the end of the row? if not (0 < (posb - posa) < 7 and 0 < (posc - posb) < 7): continue if posa < 6 or posc > 2: break else: # no break # no 2- or 3-digit power can be formed r = sorted(solve(4, perm, rs=set())) if r and r[0] > 1066: print(perm, "number", r[0])LikeLike
Frits 4:04 pm on 2 July 2022 Permalink |
Without recursion.
from itertools import permutations from enigma import mgcd def prime_factors(n): i = 2 factors = [] while i * i <= n: if n % i: i = 3 if i == 2 else i + 2 else: n //= i factors.append(i) if n > 1: factors.append(n) return factors def is_a_power(n): pf = prime_factors(n) if len(pf) < 2: return False # occurences of digits oc = {pf.count(x) for x in set(pf)} if mgcd(*oc) == 1: return False return True # collect candidate powers pows = {i for i in range(1, 2023) if is_a_power(i) and \ len(s:= str(i)) == len(set(s)) and "0" not in s} # powers grouped by number of digits pws = [[[int(x) for x in str(p)] for p in pows if 10**i <= p < 10**(i + 1)] for i in range(1, 4)] # do powers exists >= 2000 ? exists2xxx = any(x for x in pws[2] if x[0] == 2) # consider possible arrangements of digits for perm in permutations(range(1, 10)): # [performance] single digit powers cannot be in slots 3, 4, 5 if {1, 4, 8, 9}.intersection(perm[3:6]): continue for ps in pws[:-1]: for p in ps: pos = [perm.index(i) for i in p] # first digit reachable and then come off the end of the row? if not(pos[0] < 6 and pos[-1] > 2): continue # can we make the power in <len(pos)> jumps ... if any(y - x not in {1, 2, 3, 4, 5, 6} for x, y in zip(pos, pos[1:])): continue # we have found a valid 2- or 3-digit power break else: # no break continue break # break if break occurred else: # no break if not exists2xxx: # check position of 1 if perm.index(1) > 5: continue # check 4-digit powers for p in sorted(pws[2]): pos = [perm.index(i) for i in p] # it is enough to only check for increasing numbers if pos != sorted(pos): continue print(perm, "number", "".join(str(x) for x in p)) breakLikeLike
Frits 5:48 pm on 8 July 2022 Permalink |
from itertools import permutations from functools import reduce from math import gcd def prime_factors(n): i = 2 factors = [] while i * i <= n: if n % i: i = 3 if i == 2 else i + 2 else: n //= i factors.append(i) if n > 1: factors.append(n) return factors def is_a_power(n): if n == 1: return [1] pf = prime_factors(n) if len(pf) < 2: return False # occurences of digits oc = {pf.count(x) for x in set(pf)} if gcd(*oc) == 1: return False return True # group type gtype = lambda i: "first" if i == 0 else "middle" if i == 1 else "last" # collect all candidate powers pows = {i for i in range(1, 2023) if is_a_power(i) and len(s:= str(i)) == len(set(s)) and "0" not in s} # powers grouped by number of digits pws = [set(str(p) for p in pows if 10**i <= p < 10**(i + 1)) for i in range(4)] # return possible arrangements of digits in group <grp> for 2-digit powers def arrangements(grp): return [p for p in permutations(grp) if all(fdgt + sdgt not in pws[1] for fdgt, sdgt in [(p[0], p[1]), (p[0], p[2]), (p[1], p[2])]) ] # return all numbers per group that don't occur in other groups def calc_known(grp): return [[x for x in grp[i] if all(x not in t for t in [y for j, y in enumerate(grp) if j != i])] for i in range(3)] # for all combinations in <lst> check if a 3-digit power can be made # with a digit in the last group def check_last_group(grp, lst): forbidden = [set() for _ in range(len(lst))] for i, n in enumerate(lst): # for all combinations in <lst> for x in [(n[0] + n[1]), (n[0] + n[2]), (n[1] + n[2])]: for p in pws[2]: if x in {p[:-1]}: # x + p[-1] is 3-digit power so p[-1] is forbidden in last group forbidden[i].add(p[-1]) # return numbers in the last group which are forbidden for all <lst> entries return reduce((lambda x, y: x & y), map(set, forbidden)) # maintain groups if all numbers in a group are known def maintain_groups(grp, fixed): for i, fix in enumerate(fixed): # all numbers in a group are known? if len(fix) == 3: # remove other numbers from this group for n in [x for x in grp[i] if x not in fix]: print(f"{gtype(i)} group must be {','.join(fix)}:" f" remove {n} from {gtype(i)} group") grp[i] = set(fix) def print_groups(g): print("----- groups:", ",".join(sorted(g[0])), "--", ",".join(sorted(g[1])), "--", ",".join(sorted(g[2])), "-----") # maintain and print groups def update(g): known = calc_known(g) maintain_groups(g, known) print_groups(g) return known print("-------- START -----------") print("split the nine digits in three groups of three digits") # list <g> contains candidate digits for each group g = [set("123456789"), set("123456789"), set("123456789")] print_groups(g) print(f"removing 1 from last group" f" as we need a 4-digit power 1xxx as an answer") g[2] -= {'1'} # we need a 4-digit power print("removing", ", ".join(sorted(pws[0])), "from middle group to prevent single digit powers") g[1] -= set(pws[0]) for x in calc_known(g)[0]: # can we can make a 2-digit power with <x>? for p in [p2 for p2 in pws[1] if p2[0] == x]: print("removing", p[1], "from middle group to prevent power", p) g[1].remove(p[1]) print_groups(g) # check middle group if len(g[1]) == 4: # see what happens if we remove <m> from middle group for m in g[1]: middle = [x for x in g[1] if x != m] for m2 in middle: # if combination is a 2-digit power <m> must occur in middle group if m2 + m in pws[1]: g[2] -= {m} if m + m2 in pws[1]: g[0] -= {m} # get arrangements from <middle> without a 2-digit power lst = arrangements(middle) if len(lst) == 1: # we have only one arrangement for slots 3, 4 and 5 # can we can make a 3-digit power with this arrangement? arr = lst[0] for a in [(arr[0] + arr[1]), (arr[0] + arr[2]), (arr[1] + arr[2])]: # 3-digit powers that can be made from <a> tdp = [p3 for p3 in pws[2] if a in p3[:-1]] for p in tdp: # last digit of 3-digit power may not be used yet if p[-1] in (arr + ('1', )): continue # removing m has lead to a valid 3-digit power print(f"removing {m} from the middle group can lead to" f" power {p}, remove {m} from first and last group") g[0] -= {m} g[2] -= {m} # maintain and print groups known = update(g) # for every 3-digit power check if two of it's digits have to occur in two # groups, if so we can remove the other digit from the other group first = 1 for p in pws[2]: unknown = [i for i in range(3) if p[i] not in known[i]] if len(unknown) != 1: continue i = unknown[0] if first: print("known digits per group:", known) first = 0 print(f"digits {' and '.join(p[j] for j in range(3) if j != i)}" f" of power {p} each have to occur in a different specific group:" f" remove {p[i]} from {gtype(i)} group") g[i] -= {p[i]} update(g) # get numbers in the last group which make a 3-digit power for all # valid combinations in the middle group for s in check_last_group(g, arrangements(g[1])): print(f"all valid combinations of middle group combined with the number" f" {s} lead to 3-digit power: remove {s} from last group") g[2] -= {s} update(g) print() # consider possible arrangements of digits for p0 in permutations(g[0]): for p1 in arrangements(g[1]): for p2 in permutations(g[2]): perm = p0 + p1 + p2 # check 2-digit and 3-digit powers for ps in pws[1:-1]: for p in ps: # the index positions of its digits in the row of cards pos = [perm.index(i) for i in p] # ensure that its first digit is reachable and that its # last digit can be the final digit (with a throw of six) if not(pos[0] < 6 and pos[-1] > 2): continue # can we make the power in intervals of 1 - 6 jumps? if any(y - x not in set(range(1, 7)) for x, y in zip(pos, pos[1:])): continue # we have found a valid 2-digit or 3-digit power break else: continue break # break again if break occurred else: # check 4-digit powers for p in sorted(pws[3]): pos = [perm.index(i) for i in p] # checking for the correct digit order is sufficient because # the highest gap between digits is five empty slots if pos != sorted(pos): continue print(perm, "number", p) break # only print the lowest 4-digit powerLikeLike