Sunday Times Teaser 3119 – Hidden Powers

by BRG on July 2, 2022

by Victor Bryant

Published Sunday July 03 2022 (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?

From → Uncategorized

One Comment Leave one →

Brian Gladman permalink

Using the same method that Jim Randell first used with a performance improvement from Frits (see here). It is still quite slow though so I might look at speeding it up.


from itertools import permutations

# create the set of powers less than 2023 (and their
# digits) that have all different, non-zero digits
pwrs = {(1, (1,))}
for pwr in range(2, 12):
  n = 1
  while True:
    n += 1
    r = n ** pwr
    if r >= 2023:
      break
    dr = tuple(int(d) for d in str(r))
    if 0 in dr or len(set(dr)) != len(dr):
      continue
    pwrs.add((r, dr))

# check if the digits <pwrd> of a power can be
# made from the set of cards <cards>
def check(cards, pwrd):
  # find the positions of the power's digits
  # in the line of cards
  ix = [-1] + list(cards.index(d) for d in pwrd) + [9]
  # the digits must be in the right order on the line
  if ix == sorted(ix):
    # find the dice throws involved
    df = tuple(v - ix[i] for i, v in enumerate(ix[1:]))
    if min(df) >= 1 and max(df) <= 6:
      return True
  return False

pwr_min, cards = max(pwrs)[0] + 1, 0
# consider possible arrangements of the numbered cards
for p in permutations(range(1, 10)):
  # single digit powers cannot be in slots 3, 4, 5
  if {1, 4, 8, 9}.intersection(p[3:6]): 
    continue
  
  # check that no 2 or 3 digit powers can be made with this 
  # arrangement of the cards
  if any(check(p, pwrd) for pwr, pwrd in pwrs if pwr < 1000):
    continue

  # find four digit powers that can be made with this set of cards  
  sols = [pwr for pwr, pwrd in pwrs if check(p, pwrd) if pwr >= 1000]
  
  if sols and min(sols) >= 1066:
    pwr = min(sols)
    if pwr < pwr_min:
      pwr_min = pwr
      cards = p
      print(f"{cards} -> {pwr_min}")

from itertools import permutations

# create the set of powers less than 2023 (and their

# digits) that have all different, non-zero digits

pwrs = {(1, (1,))}

for pwr in range(2, 12):

n = 1

while True:

n += 1

r = n ** pwr

if r >= 2023:

break

dr = tuple(int(d) for d in str(r))

if 0 in dr or len(set(dr)) != len(dr):

continue

pwrs.add((r, dr))

# check if the digits <pwrd> of a power can be

# made from the set of cards <cards>

def check(cards, pwrd):

# find the positions of the power's digits

# in the line of cards

ix = [-1] + list(cards.index(d) for d in pwrd) + [9]

# the digits must be in the right order on the line

if ix == sorted(ix):

# find the dice throws involved

df = tuple(v - ix[i] for i, v in enumerate(ix[1:]))

if min(df) >= 1 and max(df) <= 6:

return True

return False

pwr_min, cards = max(pwrs)[0] + 1, 0

# consider possible arrangements of the numbered cards

for p in permutations(range(1, 10)):

# single digit powers cannot be in slots 3, 4, 5

if {1, 4, 8, 9}.intersection(p[3:6]):

continue

# check that no 2 or 3 digit powers can be made with this

# arrangement of the cards

if any(check(p, pwrd) for pwr, pwrd in pwrs if pwr < 1000):

continue

# find four digit powers that can be made with this set of cards

sols = [pwr for pwr, pwrd in pwrs if check(p, pwrd) if pwr >= 1000]

if sols and min(sols) >= 1066:

pwr = min(sols)

if pwr < pwr_min:

pwr_min = pwr

cards = p

print(f"{cards} -> {pwr_min}")

This is a shameless copy of Frits’s non-recursive method:


# method credit: Frits

from itertools import permutations
from collections import defaultdict

# create the set of powers less than 2023 that 
# have all different, non-zero digits
pwrs = defaultdict(list)
for pwr in range(2, 12):
  n = 1
  while True:
    n += 1
    r = n ** pwr
    if r >= 2023:
      break
    dr = tuple(int(d) for d in str(r))
    if 0 in dr or len(set(dr)) != len(dr):
      continue
    if 1 < len(dr) < 5:
      pwrs[len(dr)].append((r, dr))

# consider possible arrangements of the numbered cards
for perm in permutations(range(1, 10)):
  # single digit powers cannot be in slots 3, 4, 5
  if {1, 4, 8, 9}.intersection(perm[3:6]):
    continue

  # consider two and three digit powers
  for k in (2, 3):
    # for each power and its digits 
    for pwr, pdgts in pwrs[k]:
      # the index positions of its digits in the row of cards
      pos = [perm.index(i) for i in pdgts]
      # ensure that its first digit is reachable and that its
      # last digit can be the last digit (with a throw of six)
      if not (pos[0] < 6 and  pos[-1] > 2): 
        continue
      # if we can we make this power then ... 
      if all(y - x in set(range(1, 7)) for x, y in zip(pos, pos[1:])):
        break
    else:
      continue
    # ... this card arrangement fails because it can make a 2/3 digit power
    break    
  else:

    # check four digit powers
    for pwr, pdgts in sorted(pwrs[4]):
      pos = [perm.index(i) for i in pdgts]
      # ensure that its first digit is reachable and that its
      # last digit can be the last digit (with a throw of six)
      if not (pos[0] < 6 and  pos[-1] > 2): 
        continue
      # checking for the correct digit order is sufficient because
      # we know that only four digit powers can be made
      if pos == sorted(pos): 
        print(f"{perm} -> {pwr}")

# method credit: Frits

from itertools import permutations

from collections import defaultdict

# create the set of powers less than 2023 that

# have all different, non-zero digits

pwrs = defaultdict(list)

for pwr in range(2, 12):

n = 1

while True:

n += 1

r = n ** pwr

if r >= 2023:

break

dr = tuple(int(d) for d in str(r))

if 0 in dr or len(set(dr)) != len(dr):

continue

if 1 < len(dr) < 5:

pwrs[len(dr)].append((r, dr))

# consider possible arrangements of the numbered cards

for perm in permutations(range(1, 10)):

# single digit powers cannot be in slots 3, 4, 5

if {1, 4, 8, 9}.intersection(perm[3:6]):

continue

# consider two and three digit powers

for k in (2, 3):

# for each power and its digits

for pwr, pdgts in pwrs[k]:

# the index positions of its digits in the row of cards

pos = [perm.index(i) for i in pdgts]

# ensure that its first digit is reachable and that its

# last digit can be the last digit (with a throw of six)

if not (pos[0] < 6 and pos[-1] > 2):

continue

# if we can we make this power then ...

if all(y - x in set(range(1, 7)) for x, y in zip(pos, pos[1:])):

break

else:

continue

# ... this card arrangement fails because it can make a 2/3 digit power

break

else:

# check four digit powers

for pwr, pdgts in sorted(pwrs[4]):

pos = [perm.index(i) for i in pdgts]

# ensure that its first digit is reachable and that its

# last digit can be the last digit (with a throw of six)

if not (pos[0] < 6 and pos[-1] > 2):

continue

# checking for the correct digit order is sufficient because

# we know that only four digit powers can be made

if pos == sorted(pos):

print(f"{perm} -> {pwr}")

Sunday Times Teaser 3119 – Hidden Powers

by Victor Bryant

Published Sunday July 03 2022 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta