Sunday Times Teaser 2657 – Puzzling Book

by Danny Roth

A couple mantain a book of puzzles numbered from 1 to 30, some of which they have solved. The solutions are also numbered from 1 to 30 but these solution numbers do not necessarily match the numbers of the puzzle that they solve.

For each puzzle solved the sum of the puzzle and solution numbers is a perfect power of their difference. The sum of the puzzle numbers of solved puzzles has three digits and is less than the sum of the related solution numbers. In fact the digits of both are all non-zero and are the same but in a different order.

What, in increasing order, are the numbers of the solved puzzles?

3 Comments Leave one →

brian gladman permalink


from itertools import product, combinations
from collections import defaultdict
from math import log

# test if y is a perfect power of x
def is_power(x, y):
  return y == x ** round(log(y) / log(x))

# for each puzzle number (p) list the solution numbers (s)
# for which p + s is a perfect power of |p - s|
p2s = defaultdict(tuple)
for p in range(1, 31):
  for s in range(1, p - 1):
    if p != s and is_power(p - s, p + s):
      p2s[p] += (s,)
      p2s[s] += (p,)

# now find the minimum number of puzzles for
# which their numbers have a three digit sum
sumv = min_cnt = 0
# add puzzle numbers largest first
for x in sorted(p2s, reverse=True):
  sumv += x
  min_cnt += 1
  if sumv >= 100:
    break

# choose an alllowable number of solved puzzles
for n in range(min_cnt, len(p2s) + 1):
  
  # check all combinations of this number of puzzles
  for p in combinations(p2s, n): 
    # find the sum of the puzzle numbers and its digits
    sum_p = sum(p)
    digits_p = set(str(sum_p))    
    # this sum must have three non-zero digits
    if sum_p > 100 and '0' not in digits_p:
      
      # now check all combinations of solutions
      # for this particular combination of puzzles
      for s in product(*(p2s[x] for x in p)):
        
        # solution numbers must all be different since
        # each solution can only solve one puzzle
        if len(s) == len(set(s)):
        
          # the solution number sum has the same digits as 
          # the puzzle number sum but is larger
          sum_s = sum(s)
          digits_s = set(str(sum_s))
          if digits_s == digits_p and sum_s > sum_p:
            # output the puzzle numbers in increasing order
            print('Puzzles:  ', p)
            print('Solutions:', s)

from itertools import product, combinations

from collections import defaultdict

from math import log

# test if y is a perfect power of x

def is_power(x, y):

return y == x ** round(log(y) / log(x))

# for each puzzle number (p) list the solution numbers (s)

# for which p + s is a perfect power of |p - s|

p2s = defaultdict(tuple)

for p in range(1, 31):

for s in range(1, p - 1):

if p != s and is_power(p - s, p + s):

p2s[p] += (s,)

p2s[s] += (p,)

# now find the minimum number of puzzles for

# which their numbers have a three digit sum

sumv = min_cnt = 0

# add puzzle numbers largest first

for x in sorted(p2s, reverse=True):

sumv += x

min_cnt += 1

if sumv >= 100:

break

# choose an alllowable number of solved puzzles

for n in range(min_cnt, len(p2s) + 1):

# check all combinations of this number of puzzles

for p in combinations(p2s, n):

# find the sum of the puzzle numbers and its digits

sum_p = sum(p)

digits_p = set(str(sum_p))

# this sum must have three non-zero digits

if sum_p > 100 and '0' not in digits_p:

# now check all combinations of solutions

# for this particular combination of puzzles

for s in product(*(p2s[x] for x in p)):

# solution numbers must all be different since

# each solution can only solve one puzzle

if len(s) == len(set(s)):

# the solution number sum has the same digits as

# the puzzle number sum but is larger

sum_s = sum(s)

digits_s = set(str(sum_s))

if digits_s == digits_p and sum_s > sum_p:

# output the puzzle numbers in increasing order

print('Puzzles: ', p)

print('Solutions:', s)

Arthur Vause permalink

Here is my variation:


from itertools import combinations as comb
candidates=set()
for p in xrange(1,31):
  for s in xrange(p+2,31):
    q,r = p+s, 0
    while q>1 and r==0:
      q,r =divmod(q,s-p)
    if r==0:  
      candidates.add( (p,s) )
      candidates.add( (s,p) )

for n in xrange(3,len(candidates)/2+1):
  for c in comb( candidates,n):
    if len(set(x[0] for x in c))==n and len(set(x[1] for x in c))==n:
      puzzlesum = sum(x[0] for x in c)
      solutionsum = sum(x[1] for x in c)
      if 100 <= puzzlesum < solutionsum and 
         set(str(puzzlesum))==set(str(solutionsum)) 
         and '0' not in set(str(puzzlesum)):
        print "puzzle and solution sums", puzzlesum, solutionsum
        print "solved puzzles", sorted(x[0] for x in c)
        print "puzzle / solution pairs",c

from itertools import combinations as comb

candidates=set()

for p in xrange(1,31):

for s in xrange(p+2,31):

q,r = p+s, 0

while q>1 and r==0:

q,r =divmod(q,s-p)

if r==0:

candidates.add( (p,s) )

candidates.add( (s,p) )

for n in xrange(3,len(candidates)/2+1):

for c in comb( candidates,n):

if len(set(x[0] for x in c))==n and len(set(x[1] for x in c))==n:

puzzlesum = sum(x[0] for x in c)

solutionsum = sum(x[1] for x in c)

if 100 <= puzzlesum < solutionsum and

set(str(puzzlesum))==set(str(solutionsum))

and '0' not in set(str(puzzlesum)):

print "puzzle and solution sums", puzzlesum, solutionsum

print "solved puzzles", sorted(x[0] for x in c)

print "puzzle / solution pairs",c

Arthur Vause permalink

Brian, thanks for tidying up my attempts at python tags.

Here is a much faster version


from itertools import combinations as comb, product
import collections

candidates = collections.defaultdict(list)
for power, base in [(b**n,b) for b in xrange(2,8) for n in xrange(2,6)
                    if b**n <= 60]:
  a,b =(power+base)/2, (power-base)/2
  candidates[a].append(b)
  candidates[b].append(a)
  power*=base

puzzlecandidates = sorted([x for x in candidates])
for n in xrange(3,len(puzzlecandidates)+1):
  for c in comb( puzzlecandidates,n):
    puzzlesum = sum(c)
    if 100 < puzzlesum and '0' not in set(str(puzzlesum)):
      for s in product(*[candidates[x] for x in c]):
        solutionsum=sum(s)
        if puzzlesum < solutionsum and 
           set(str(puzzlesum))==set(str(solutionsum)) 
           and len(set(s))==n:
          print "puzzle / solution sums",puzzlesum, solutionsum
          print "puzzle / solution",c,"/",s

from itertools import combinations as comb, product

import collections

candidates = collections.defaultdict(list)

for power, base in [(b**n,b) for b in xrange(2,8) for n in xrange(2,6)

if b**n <= 60]:

a,b =(power+base)/2, (power-base)/2

candidates[a].append(b)

candidates[b].append(a)

power*=base

puzzlecandidates = sorted([x for x in candidates])

for n in xrange(3,len(puzzlecandidates)+1):

for c in comb( puzzlecandidates,n):

puzzlesum = sum(c)

if 100 < puzzlesum and '0' not in set(str(puzzlesum)):

for s in product(*[candidates[x] for x in c]):

solutionsum=sum(s)

if puzzlesum < solutionsum and

set(str(puzzlesum))==set(str(solutionsum))

and len(set(s))==n:

print "puzzle / solution sums",puzzlesum, solutionsum

print "puzzle / solution",c,"/",s

Sunday Times Teaser 2657 – Puzzling Book

by Danny Roth

Leave a comment to Arthur Vause Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta