Sunday Times Teaser 2948 – A Hardy Annual

Brian Gladman permalink


from itertools import permutations
from number_theory import is_prime

# Numbers made from exactly eight non-zero digits that
# sum to numbers between 2009 and 2019 inclusive might
# have lengths of (4, 4, 0), ((4, 3, 1) or (3, 3, 2);
# it is easy to find that only the (4, 3, 1) option is
# possible with the four digit number starting with 1

# a set for years that are not possible
yrs = set(range(2009, 2020))

# sets for storing the three digit primes that arise
# in the solutions for 2018 and 2019
p2018, p2019 = set(), set()

for p in permutations('23456789', 7):
  
  # the four and three digit numbers
  # and the resulting year
  a = int('1' + ''.join(p[:3]))
  b = int(''.join(p[3:6]))
  year = a + b + int(p[6])

  if 2009 <= year <= 2019:
    
    # remove this year from the set that
    # cannot be made
    yrs.difference_update([year])
    
    # we are looking for 2018 and 2019 solutions 
    # in which the three digit number is a prime
    if 2018 <= year <= 2019 and is_prime(b):
      [p2018, p2019][year - 2018].add(b)

# output the year that is not possible 
yrs, = yrs
print(f"(a) {yrs} ", end='')

# primes common to the 2018 and 2019 solutions 
prm, = p2018 & p2019
print(f"(b) {prm}")

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 permutations

from number_theory import is_prime

# Numbers made from exactly eight non-zero digits that

# sum to numbers between 2009 and 2019 inclusive might

# have lengths of (4, 4, 0), ((4, 3, 1) or (3, 3, 2);

# it is easy to find that only the (4, 3, 1) option is

# possible with the four digit number starting with 1

# a set for years that are not possible

yrs = set(range(2009, 2020))

# sets for storing the three digit primes that arise

# in the solutions for 2018 and 2019

p2018, p2019 = set(), set()

for p in permutations('23456789', 7):

# the four and three digit numbers

# and the resulting year

a = int('1' + ''.join(p[:3]))

b = int(''.join(p[3:6]))

year = a + b + int(p[6])

if 2009 <= year <= 2019:

# remove this year from the set that

# cannot be made

yrs.difference_update([year])

# we are looking for 2018 and 2019 solutions

# in which the three digit number is a prime

if 2018 <= year <= 2019 and is_prime(b):

[p2018, p2019][year - 2018].add(b)

# output the year that is not possible

yrs, = yrs

print(f"(a) {yrs} ", end='')

# primes common to the 2018 and 2019 solutions

prm, = p2018 & p2019

print(f"(b) {prm}")

Reply

Frits permalink

You seem to dismiss (4, 2, 2) (like 24 + 37+ 1958 = 2019) and (4, 2, 1, 1) (like 2 + 4 + 35 + 1978 = 2019) as an option for the year he was unable to complete the task.

(4, 1, 1, 1, 1) is not possible unless you go back to the year 2005. I would certainly go back to 2005 as it says “each year for over ten years”. So he may have started in fi 2003.

Reply

BRG permalink

Yes, I only consider numbers of the form set out in the comments since
numbers of these forms are sufficient to find the solutions for part
(b) and, as it turns out, for part (a) as well .

At the time I didn’t publish the solution I used to check for all part (a)
solutions:


from itertools import permutations
from number_theory import is_prime
from functools import reduce

# <nv>   the sum of numbers to achieve 
# <nd>   the number of digits available
# <dgts> the digits available
# <ls>   the length of the number currently being made
# <seqs> the sequence of numbers made
def compose(nv, nd=8, dgts=set(range(1, 10)), ls=(4,), seqs=()):
  if not nd:
    if not nv:
      yield seqs
  else:
    # the number of digits in the next number to be made
    for ndg in range(ls[-1], 0, -1):
      # consider the possible numbers that can be made
      for p in permutations(dgts, ndg):
        ns = reduce(lambda x, y: 10 * x + y, p)
        if nv - ns >= 0:
          # continue to the next number to be made
          yield from compose(nv - ns, nd - ndg, dgts.difference(p),
                             ls + (ndg,), seqs + (ns,))
# solve part (a)
for y in range(2000, 2020):
  for s in compose(y):
    break
  else:
    print(f"(a) Impossible year: {y}")

# solve part (b)
y2ps = {}
# consider the years 2018 and 2019
for y in (2018, 2019):
  for s in compose(y):
    # save any three digit primes in the answers
    t = set(n for n in s if 100 < n < 1000 and is_prime(n)) 
    y2ps[y] = y2ps.get(y, set()) | t
# find the common three digit prime
print(f"(b) Common Prime: {(y2ps[2018] & y2ps[2019]).pop()}")

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

from itertools import permutations

from number_theory import is_prime

from functools import reduce

# <nv> the sum of numbers to achieve

# <nd> the number of digits available

# <dgts> the digits available

# <ls> the length of the number currently being made

# <seqs> the sequence of numbers made

def compose(nv, nd=8, dgts=set(range(1, 10)), ls=(4,), seqs=()):

if not nd:

if not nv:

yield seqs

else:

# the number of digits in the next number to be made

for ndg in range(ls[-1], 0, -1):

# consider the possible numbers that can be made

for p in permutations(dgts, ndg):

ns = reduce(lambda x, y: 10 * x + y, p)

if nv - ns >= 0:

# continue to the next number to be made

yield from compose(nv - ns, nd - ndg, dgts.difference(p),

ls + (ndg,), seqs + (ns,))

# solve part (a)

for y in range(2000, 2020):

for s in compose(y):

break

else:

print(f"(a) Impossible year: {y}")

# solve part (b)

y2ps = {}

# consider the years 2018 and 2019

for y in (2018, 2019):

for s in compose(y):

# save any three digit primes in the answers

t = set(n for n in s if 100 < n < 1000 and is_prime(n))

y2ps[y] = y2ps.get(y, set()) | t

# find the common three digit prime

print(f"(b) Common Prime: {(y2ps[2018] & y2ps[2019]).pop()}")

because it was slow (and not needed) . But it shows that 2006 is a second
impossible year.

Reply

Frits permalink

Thanks for the code.

Jim ingeneously found a way to use combinations instead of permutations in a recursive routine.

Reply

Erling Torkildsen permalink


from itertools import permutations

sums = list()          # An evil global variable! Didn't make it without..
               
def possible():        # Routine for checking possible years
  yrs = set(range(2009, 2018))
  s1 = set(range(2, 10))
  for n in range(2, 10):
    s2 = s1.difference((n,))
    for b, c, d in permutations(s2, 3):
      s3 = s2.difference((1, b, c, d))
      for e, f, g in permutations(s3, 3):
        s4 = s2.difference((1, b, c, d, e, f, g))
        for h in s4: 
          t = 1000 + 100 * b + 10 * c + d + 100 * e + 10 * f + g + h 
          if t in yrs:
            yrs.discard(t)
  return yrs

def get_p():           # Be self-sufficient when it comes to primes
  p = set()
  for x in range(101, 1000, 2):
    pr = True
    for div in range(2, 33):
      if x % div == 0:
        pr = False
        break      
    if pr:
      p.add(x)
  return p

# the set of three digit primes
prms = get_p()

def p_year(year):
  prime = set()        # For collecting primes for return
  s1 = set(range(2, 10))
  for n in range(2, 10):
    s2 = s1.difference((n,))
    for b, c, d in permutations(s2, 3):
      s3 = s2.difference((1, b, c, d))
      for e, f, g in permutations(s3, 3):
        s4 = s2.difference((1, b, c, d, e, f, g))
        for h in s4:
          u = 1000 + 100 * b + 10 * c + d
          v = 100 * e + 10 * f + g
          if u + v + h == year and v in prms:
            prime.add(f"{v}")
            sums.append(f"{u} + {v} + {h} = {year}")
  return prime
 
for y in possible():
  print(f"Not possible in {y}\n")
  
for cp in p_year(2018).intersection(p_year(2019)):
  print(f"Common prime {cp} in:")
  for s in sums: 
    if '+ ' + str(cp) in s:
      print(" ", 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

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

from itertools import permutations

sums = list() # An evil global variable! Didn't make it without..

def possible(): # Routine for checking possible years

yrs = set(range(2009, 2018))

s1 = set(range(2, 10))

for n in range(2, 10):

s2 = s1.difference((n,))

for b, c, d in permutations(s2, 3):

s3 = s2.difference((1, b, c, d))

for e, f, g in permutations(s3, 3):

s4 = s2.difference((1, b, c, d, e, f, g))

for h in s4:

t = 1000 + 100 * b + 10 * c + d + 100 * e + 10 * f + g + h

if t in yrs:

yrs.discard(t)

return yrs

def get_p(): # Be self-sufficient when it comes to primes

p = set()

for x in range(101, 1000, 2):

pr = True

for div in range(2, 33):

if x % div == 0:

pr = False

break

if pr:

p.add(x)

return p

# the set of three digit primes

prms = get_p()

def p_year(year):

prime = set() # For collecting primes for return

s1 = set(range(2, 10))

for n in range(2, 10):

s2 = s1.difference((n,))

for b, c, d in permutations(s2, 3):

s3 = s2.difference((1, b, c, d))

for e, f, g in permutations(s3, 3):

s4 = s2.difference((1, b, c, d, e, f, g))

for h in s4:

u = 1000 + 100 * b + 10 * c + d

v = 100 * e + 10 * f + g

if u + v + h == year and v in prms:

prime.add(f"{v}")

sums.append(f"{u} + {v} + {h} = {year}")

return prime

for y in possible():

print(f"Not possible in {y}\n")

for cp in p_year(2018).intersection(p_year(2019)):

print(f"Common prime {cp} in:")

for s in sums:

if '+ ' + str(cp) in s:

print(" ", s)

Reply

Brian Gladman permalink

If you would like to complete it, i will update your post if you let me have the revised version.

Reply

Erling Torkildsen permalink

Yes, please do. I have a patched version ready. It gets rid of some variables with no function at all as well as it pays attention to both questions.

Reply

GeoffR permalink


from itertools import permutations

def is_prime(n): 
    for x in range(2, int(n**0.5) + 1): 
        if n % x == 0: 
            return False 
    return True

a = 1

s2018, s2019 = set(), set()
all_years= {2009,2010,2011,2012,2013,2014,2015,2016,2017,2018,2019}

years_ok = set()

digits = set(range(2,10))

for p in permutations(digits, 3):
  b, c, d = p
  abcd = 1000*a + 100*b + 10*c + d
  
  s2 = set(digits.difference([b,c,d]))
  for q in permutations(s2,4):
    e, f, g, h = q
    efg = 100*e + 10*f + g
    
    if not is_prime(efg): continue
    year = abcd + efg + h

    if year == 2018:
        s2018.add(efg)

    if year == 2019:
        s2019.add(efg)
        
    if 2009 <= year <= 2019:
      years_ok.add(year)

# Find a prime number common to years 2018 and 2019      
z, = s2018.intersection(s2019)
print('Three figure prime number common to years 2018 and 2019 =', z)

zz, = all_years.difference(years_ok)
print('Year unable to complete task is',zz)

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

45

46

from itertools import permutations

def is_prime(n):

for x in range(2, int(n**0.5) + 1):

if n % x == 0:

return False

return True

a = 1

s2018, s2019 = set(), set()

all_years= {2009,2010,2011,2012,2013,2014,2015,2016,2017,2018,2019}

years_ok = set()

digits = set(range(2,10))

for p in permutations(digits, 3):

b, c, d = p

abcd = 1000*a + 100*b + 10*c + d

s2 = set(digits.difference([b,c,d]))

for q in permutations(s2,4):

e, f, g, h = q

efg = 100*e + 10*f + g

if not is_prime(efg): continue

year = abcd + efg + h

if year == 2018:

s2018.add(efg)

if year == 2019:

s2019.add(efg)

if 2009 <= year <= 2019:

years_ok.add(year)

# Find a prime number common to years 2018 and 2019

z, = s2018.intersection(s2019)

print('Three figure prime number common to years 2018 and 2019 =', z)

zz, = all_years.difference(years_ok)

print('Year unable to complete task is',zz)

Reply

Sunday Times Teaser 2948 – A Hardy Annual

by Victor Bryant

Published March 24 2019 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta