Sunday Times Teaser 2717 – Round the Garden

brian gladman permalink

Here is an iterative solution:


from itertools import combinations, permutations
from number_theory import Primes

# primes less than a thousand
pr = tuple(Primes(1000))
# primes less than a thousand without repeated digits mapped to 
# the sets of digits they contain
pc = { p:set(str(p)) for p in pr if len(str(p)) == len(set(str(p))) }

# pick three primes for the longest sides
for a, b, c in combinations(pc, 3):
  # eliminate any that share digits
  if pc[a] & pc[b] or pc[b] & pc[c] or pc[c] & pc[a]:
    continue
  # check that no pairs of sides differ by a prime
  if any(abs(x - y) in pr for x, y in ((a, b), (b, c), (c, a))):
    continue
  # find the unused digits
  set_rem = set(str('0123456789')) - (pc[a] | pc[b] | pc[c])
  # find the minimum number of digits in the perimeter
  min_len = len(str(a + b + c))
  # permute the remaining digits for the perimeter and side four 
  for ps in permutations(set_rem):
    # consider the possible number of digits in the perimeter
    for lp in range(min_len, len(set_rem)):
      # split the digits between the perimeter and side four
      per, d = int(''.join(ps[:lp])), int(''.join(ps[lp:]))
      sides = (a, b, c, d)
      # check that the perimeter is correct and that the sides
      # can form a quadrilateral
      if sum(sides) == per and 2 * max(sides) < per:
        # check that sides (a, b, c) and side d don't differ by a prime
        if any(abs(x - d) in pr for x in (a, b, c)):
          continue
        # if side four is not prime it must be the smallest side
        if d not in pr and d != min(sides):
          continue
        print('sides = {}, perimeter = {}'.format(tuple(sorted(sides)), per))

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, permutations

from number_theory import Primes

# primes less than a thousand

pr = tuple(Primes(1000))

# primes less than a thousand without repeated digits mapped to

# the sets of digits they contain

pc = { p:set(str(p)) for p in pr if len(str(p)) == len(set(str(p))) }

# pick three primes for the longest sides

for a, b, c in combinations(pc, 3):

# eliminate any that share digits

if pc[a] & pc[b] or pc[b] & pc[c] or pc[c] & pc[a]:

continue

# check that no pairs of sides differ by a prime

if any(abs(x - y) in pr for x, y in ((a, b), (b, c), (c, a))):

continue

# find the unused digits

set_rem = set(str('0123456789')) - (pc[a] | pc[b] | pc[c])

# find the minimum number of digits in the perimeter

min_len = len(str(a + b + c))

# permute the remaining digits for the perimeter and side four

for ps in permutations(set_rem):

# consider the possible number of digits in the perimeter

for lp in range(min_len, len(set_rem)):

# split the digits between the perimeter and side four

per, d = int(''.join(ps[:lp])), int(''.join(ps[lp:]))

sides = (a, b, c, d)

# check that the perimeter is correct and that the sides

# can form a quadrilateral

if sum(sides) == per and 2 * max(sides) < per:

# check that sides (a, b, c) and side d don't differ by a prime

if any(abs(x - d) in pr for x in (a, b, c)):

continue

# if side four is not prime it must be the smallest side

if d not in pr and d != min(sides):

continue

print('sides = {}, perimeter = {}'.format(tuple(sorted(sides)), per))

and here is a recursive version:


from itertools import combinations, permutations
from number_theory import Primes

# primes less than a thousand
pr = tuple(Primes(1000))
# primes less than a thousand without repeated digits mapped in
# a dictionary to the sets of digits that they contain
pc = { p:set(str(p)) for p in pr if len(str(p)) == len(set(str(p))) }

# sides = the list of prime sides so far (in increasing order)
# unused = the digits used so far 
def solve(sides, unused):
  if len(sides) < 3:
    # add another longer side to the list ...
    for s in pc:
      # checking that its digits are available 
      if (not sides or s > sides[-1]) and (pc[s] < unused):
        # check that no two sides differ by a prime
        if all(abs(x - s) not in pr for x in sides):
          yield from solve(sides + [s], unused - pc[s])
  else:    
    # we have three prime sides
    l3 = sum(sides)
    # permute the remaining digits for the perimeter and side four 
    for p in permutations(unused):
      # consider the possible numbers of digits in the perimeter
      for lp in range(len(str(l3)), len(unused)):
        # split the digits between the perimeter and side four
        per, d = int(''.join(p[:lp])), int(''.join(p[lp:]))
        # check that the perimeter is correct and that the sides
        # can form a quadrilateral
        if l3 + d == per and 2 * max(sides[-1], d) < per:
          # if side four is not prime it must be the smallest side
          if d not in pr and d > min(sides):
            continue
          # check that side four and the other three don't
          # differ by a prime
          if all(abs(x - d) not in pr for x in sides):
            yield tuple(sorted(sides + [d]))

for s in solve([], set('0123456789')):
  print('sides = {}, perimeter = {}'.format(s, sum(s)))

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

41

42

43

44

from itertools import combinations, permutations

from number_theory import Primes

# primes less than a thousand

pr = tuple(Primes(1000))

# primes less than a thousand without repeated digits mapped in

# a dictionary to the sets of digits that they contain

pc = { p:set(str(p)) for p in pr if len(str(p)) == len(set(str(p))) }

# sides = the list of prime sides so far (in increasing order)

# unused = the digits used so far

def solve(sides, unused):

if len(sides) < 3:

# add another longer side to the list ...

for s in pc:

# checking that its digits are available

if (not sides or s > sides[-1]) and (pc[s] < unused):

# check that no two sides differ by a prime

if all(abs(x - s) not in pr for x in sides):

yield from solve(sides + [s], unused - pc[s])

else:

# we have three prime sides

l3 = sum(sides)

# permute the remaining digits for the perimeter and side four

for p in permutations(unused):

# consider the possible numbers of digits in the perimeter

for lp in range(len(str(l3)), len(unused)):

# split the digits between the perimeter and side four

per, d = int(''.join(p[:lp])), int(''.join(p[lp:]))

# check that the perimeter is correct and that the sides

# can form a quadrilateral

if l3 + d == per and 2 * max(sides[-1], d) < per:

# if side four is not prime it must be the smallest side

if d not in pr and d > min(sides):

continue

# check that side four and the other three don't

# differ by a prime

if all(abs(x - d) not in pr for x in sides):

yield tuple(sorted(sides + [d]))

for s in solve([], set('0123456789')):

print('sides = {}, perimeter = {}'.format(s, sum(s)))

Reply

tony smith permalink

Brian
I am a pen-and-paper solver and a lurker on your other site.
I think that your programs impose the ” no two sides differ by a prime” condition.I assume that they do not produce the second set which would solve the teaser if the condition was not included and which you mention on the other site..
This makes me wonder whether you also did an analytical solution (which I found to be an enjoyable exercise).
Regards
Tony Smith

Reply

Brian Gladman permalink

Hi Tony,
No, I just ran one of the programs above without the lines that apply this condition. In fact, as I mention on my other site, I left out the ‘three largest primes’ condition as well.

Reply

Peter Hayes permalink

there is a near-miss in the form a + b + cd + efg = hij which I will leave you to (re)discover.

the no-differences prime rules it out; also the fact that the four sides couldn’t form a quadrilateral in any case!

Reply

Peter Hayes permalink

ie “no-differences-prime”; you knew what I meant.

Reply

Peter Hayes permalink

okay, you’ve had long enough, so here’s the near-miss answer

4 + 5 + 23 + 769 = 801

Reply

Sunday Times Teaser 2717 – Round the Garden

by Danny Roth

Leave a comment to Peter Hayes Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta