Sunday Times Teaser 2971 – Six Sisters on the Ski Lift

by Bernardo Recaman

Published September 1 2019 (link)

The sum of the ages of six sisters known to me is 92. Though there is no single whole number greater than 1 that simultaneously divides the ages of any three of them, I did notice this morning, while they lined up for the ski lift, that the ages of any two of them standing one behind the other, had a common divisor greater than 1.

In increasing order, how old are the six sisters?

2 Comments Leave one →

Brian Gladman permalink


from itertools import combinations
from math import gcd

# find a sequence of <n> integers with sum (v) in which all consecutive
# pairs have common factors greater than one and all triples (consecutive
# or not) have no common factors greater than one 
def solve(n, v, seq=()):
  if not n:
    # if seq is a solution so is its reverse
    # so remove one of these
    if not v and seq[0] < seq[-1]:
      yield seq
  else:
    # select the next value for the sequence
    for i in range(1 if n > 1 else v, v + 1):
      # if it is not the first value, check that it shares
      # a common factor with the previous value 
      if not seq or gcd(i, seq[-1]) > 1:
        # and check that it does not form a triple with existing pairs
        # of sequence values which has a common factor greater than one
        if all(gcd(i, gcd(a, b)) == 1 for a, b in combinations(seq, 2)):
          yield from solve(n - 1, v - i, seq + (i,))

for s in solve(6, 92):
  print(sorted(s), s)

from itertools import combinations

from math import gcd

# find a sequence of <n> integers with sum (v) in which all consecutive

# pairs have common factors greater than one and all triples (consecutive

# or not) have no common factors greater than one

def solve(n, v, seq=()):

if not n:

# if seq is a solution so is its reverse

# so remove one of these

if not v and seq[0] < seq[-1]:

yield seq

else:

# select the next value for the sequence

for i in range(1 if n > 1 else v, v + 1):

# if it is not the first value, check that it shares

# a common factor with the previous value

if not seq or gcd(i, seq[-1]) > 1:

# and check that it does not form a triple with existing pairs

# of sequence values which has a common factor greater than one

if all(gcd(i, gcd(a, b)) == 1 for a, b in combinations(seq, 2)):

yield from solve(n - 1, v - i, seq + (i,))

for s in solve(6, 92):

print(sorted(s), s)

With the benefit of hindsight, here is a faster solution:


from itertools import count, permutations

# Take 5 primes (p, q, r, s, t) and constuct the sequence:
#
#   1.p, p.q, q.r, r.s, s.t, t.1
#
# By inspection consecutive values have a common prime 
# factor but no three values share a common prime.  So
# we have a solution of the right form if we can find
# five primes such that the above sequence sums to 92

pr = (2, 3, 5, 7, 11, 13, 17, 19, 23)

for n in count(5):
  for p5 in permutations(pr[:n], 5):
    s6 = tuple(a * b for a, b in zip((1,) + p5, p5 + (1,)))
    if sum(s6) == 92:
      print(sorted(s6), s6)
      exit()

from itertools import count, permutations

# Take 5 primes (p, q, r, s, t) and constuct the sequence:

# 1.p, p.q, q.r, r.s, s.t, t.1

# By inspection consecutive values have a common prime

# factor but no three values share a common prime. So

# we have a solution of the right form if we can find

# five primes such that the above sequence sums to 92

pr = (2, 3, 5, 7, 11, 13, 17, 19, 23)

for n in count(5):

for p5 in permutations(pr[:n], 5):

s6 = tuple(a * b for a, b in zip((1,) + p5, p5 + (1,)))

if sum(s6) == 92:

print(sorted(s6), s6)

exit()

GeoffR permalink


from itertools import combinations
from math import gcd

# check that a sequence (seq) has a sum not more than a target (t)
# and that it has no triples with common divisors greater than one
def check(seq, t):
  return (sum(seq) <= t and 
          all(gcd(x, gcd(y, z)) == 1 for x, y, z in combinations(seq, 3)))

# the maximum age considered
a_max = 50

# consider ages in queue order: a, b, c, d, e, f
# check that consecutive pairs have common divisors
# greater than one but that no triples have such 
# common divisors
for a in range(1, a_max):
  for b in range(1, a_max):
    if gcd(a, b) > 1:

      for c in range(1, a_max):
        t3 = (a, b, c)        
        if gcd(b, c) > 1 and check(t3, 92):

          for d in range(1, a_max):
            t4 = t3 + (d,)
            if gcd(c, d) > 1 and check(t4, 92):
              
              for e in range(1, a_max):
                t5 = t4 + (e,)
                if gcd(d, e) > 1 and check(t5, 92):

                  for f in range(1, a_max):
                    t6 = t5 + (f,)
                    if gcd(e, f) > 1 and check(t6, 92):
                      
                      if sum(t6) == 92 and a < f:
                        print(f"{sorted(t6)}, queue = {t6}")

from itertools import combinations

from math import gcd

# check that a sequence (seq) has a sum not more than a target (t)

# and that it has no triples with common divisors greater than one

def check(seq, t):

return (sum(seq) <= t and

all(gcd(x, gcd(y, z)) == 1 for x, y, z in combinations(seq, 3)))

# the maximum age considered

a_max = 50

# consider ages in queue order: a, b, c, d, e, f

# check that consecutive pairs have common divisors

# greater than one but that no triples have such

# common divisors

for a in range(1, a_max):

for b in range(1, a_max):

if gcd(a, b) > 1:

for c in range(1, a_max):

t3 = (a, b, c)

if gcd(b, c) > 1 and check(t3, 92):

for d in range(1, a_max):

t4 = t3 + (d,)

if gcd(c, d) > 1 and check(t4, 92):

for e in range(1, a_max):

t5 = t4 + (e,)

if gcd(d, e) > 1 and check(t5, 92):

for f in range(1, a_max):

t6 = t5 + (f,)

if gcd(e, f) > 1 and check(t6, 92):

if sum(t6) == 92 and a < f:

print(f"{sorted(t6)}, queue = {t6}")

Sunday Times Teaser 2971 – Six Sisters on the Ski Lift

by Bernardo Recaman

Published September 1 2019 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta