S2T2

Jim Randell 11:51 am on 9 October 2019 Permalink Reply
Tags: by: Tom Wills-Sandford ( 5 )   

• 

  Jim Randell 11:51 am on 9 October 2019 Permalink | Reply

  If Alice has made a square of side n (so n < 100), then she has used n² tiles.

  The setter removes one corner tile from the square, leaving (n² − 1) tiles.

  Alice can then take the remaining (n − 1) tiles from the same row (or column) as the removed tile, to produce a rectangle with dimensions n × (n − 1), and the removed (n − 1) tiles can be added back to form an additional column (or row) of a rectangle with dimensions (n + 1) × (n − 1).

  We require both these dimensions to be prime, so we are looking for twin primes of the form (n − 1) and (n + 1).

  We need to find a set of primes that sum to 200, where each is the lower of a pair of twin primes.

  This Python program runs in 85ms.

  Run: [ @repl.it ]

  from enigma import (primes, tuples, subsets, printf)
  
  # find possible shapes, record p
  ps = list(p for (p, q) in tuples(primes.between(1, 100), 2) if q == p + 2)
  
  # find a subset that sums to 200
  for s in subsets(ps, min_size=3):
    if sum(s) == 200:
      # the sides of the original squares
      ns = list(p + 1 for p in s)
      printf("squares = {ns}")
  

  Solution: The lengths of the sides of the original squares were: 30, 42, 60, 72.

  ---

  Examining all subsets could be a costly approach if the parent set is large. In this case there are only 8 candidate primes, so there are at most 255 (non-empty) subsets to consider.

  So here is an alternative program, although on a small problem like this there isn’t much difference in execution time.

  from enigma import (primes, tuples, printf)
  
  # find possible shapes, record p
  ps = list(p for (p, q) in tuples(primes.between(1, 100), 2) if q == p + 2)
  
  # decompose <t> into numbers from <ns>
  def decompose(t, ns, s=[]):
    if t == 0:
      yield s
    else:
      for (i, n) in enumerate(ns):
        if n > t: break
        yield from decompose(t - n, ns[i + 1:], s + [n])
  
  # find a subset that sums to 200
  for s in decompose(200, ps):
    # the sides of the original squares
    ns = list(p + 1 for p in s)
    printf("squares = {ns}")
  

  LikeLike