1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
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}") |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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() |