Sunday Times Teaser 2824 – New Extension

Brian Gladman permalink


from itertools import combinations, product
from functools import reduce

# the set of primes below 100
pr = set((2, 3, 5, 7))
pr = pr | set(x for x in range(11, 100, 2) if all (x % p for p in pr))

# the thousands digit of the four digit extension number
for th in range(10):
  
  # if the leftmost digit is zero the other digits must be single digit
  # primes;  otherwise they must be the unit digits of two digit primes
  s = (2, 3, 5, 7) if not th else (1, 3, 7, 9)
  for others in product(s, repeat=3):
    digits = (th,) + others
  
    # find all the numbers when two digts are left out
    lp = set(10 * x + y for x, y in combinations(digits, 2))

    # all six must be prime
    if len(pr & lp) == 6:
      
      # form the extension number
      nbr = reduce(lambda x, y: 10 * x + y, digits)

      # which must be divisible by more than one of the primes      
      if [nbr % p for p in lp].count(0) > 1:
        print("George's extension number is {}.".format(nbr))

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

from itertools import combinations, product

from functools import reduce

# the set of primes below 100

pr = set((2, 3, 5, 7))

pr = pr | set(x for x in range(11, 100, 2) if all (x % p for p in pr))

# the thousands digit of the four digit extension number

for th in range(10):

# if the leftmost digit is zero the other digits must be single digit

# primes; otherwise they must be the unit digits of two digit primes

s = (2, 3, 5, 7) if not th else (1, 3, 7, 9)

for others in product(s, repeat=3):

digits = (th,) + others

# find all the numbers when two digts are left out

lp = set(10 * x + y for x, y in combinations(digits, 2))

# all six must be prime

if len(pr & lp) == 6:

# form the extension number

nbr = reduce(lambda x, y: 10 * x + y, digits)

# which must be divisible by more than one of the primes

if [nbr % p for p in lp].count(0) > 1:

print("George's extension number is {}.".format(nbr))

Reply

geoffrounce permalink


from itertools import permutations
from number_theory import is_prime

for p in permutations('123456789',4):
    a, b, c, d = p
    num = int(a + b + c + d)
    cnt = 0
    # find the six 2-digit prime numbers
    ab, ac, ad = int(a + b), int(a + c), int(a + d)
    bc, bd, cd = int(b + c), int(b + d), int(c + d)
    if all(is_prime(x) for x in (ab, ac, ad, bc, bd, cd)):
       for div in (ab, ac, ad, bc, bd, cd):
           if num % div == 0:
               cnt += 1
               if cnt > 1:
                   print('George’s new extension number is',num)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

from itertools import permutations

from number_theory import is_prime

for p in permutations('123456789',4):

a, b, c, d = p

num = int(a + b + c + d)

cnt = 0

# find the six 2-digit prime numbers

ab, ac, ad = int(a + b), int(a + c), int(a + d)

bc, bd, cd = int(b + c), int(b + d), int(c + d)

if all(is_prime(x) for x in (ab, ac, ad, bc, bd, cd)):

for div in (ab, ac, ad, bc, bd, cd):

if num % div == 0:

cnt += 1

if cnt > 1:

print('George’s new extension number is',num)

Reply

geoffrounce permalink


from number_theory import is_prime

for num in range(1000,10000):
  # split the 4-digit number into single digits
  a, b = num // 1000,  num // 100 % 10
  c, d = num // 10 % 10,  num % 10
  
  # form 6 no. 2-digit numbers
  ab, ac, ad = 10 * a + b, 10 * a + c, 10 * a + d
  bc, bd, cd = 10 * b + c, 10 * b + d, 10 * c + d

  # check all 2-digit numbers are prime
  if all(is_prime(x) for x in (ab, ac, ad, bc, bd, cd)):

    # check all 6 prime numbers are different
    if len(set((ab, ac, ad, bc, bd, cd))) != 6: continue

    # more than one of the prime numbers divide exactly the 4-digit number
    if not sum(1 for x in (ab, ac, ad, bc, bd, cd) if num % x == 0) > 1:
      continue
    print('Extension number =', num)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

from number_theory import is_prime

for num in range(1000,10000):

# split the 4-digit number into single digits

a, b = num // 1000, num // 100 % 10

c, d = num // 10 % 10, num % 10

# form 6 no. 2-digit numbers

ab, ac, ad = 10 * a + b, 10 * a + c, 10 * a + d

bc, bd, cd = 10 * b + c, 10 * b + d, 10 * c + d

# check all 2-digit numbers are prime

if all(is_prime(x) for x in (ab, ac, ad, bc, bd, cd)):

# check all 6 prime numbers are different

if len(set((ab, ac, ad, bc, bd, cd))) != 6: continue

# more than one of the prime numbers divide exactly the 4-digit number

if not sum(1 for x in (ab, ac, ad, bc, bd, cd) if num % x == 0) > 1:

continue

print('Extension number =', num)

Reply

Jim Randell permalink

A fairly direct Python interpretation runs in 215ms.


from itertools import product, combinations
from enigma import irange, nconcat, is_prime, printf

# choose the 4 digit sequence
for s in product(irange(0, 9), repeat=4):

  # form the 6 2-digit subsequences
  ss = set(nconcat(x) for x in combinations(s, 2))

  # they are all different
  if len(ss) != 6: continue

  # and all prime
  if not all(is_prime(x) for x in ss): continue

  # and more than 1 divides into the original number
  n = nconcat(s)
  if not sum(1 for x in ss if n % x == 0) > 1: continue

  printf("n={n} {ss}")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

from itertools import product, combinations

from enigma import irange, nconcat, is_prime, printf

# choose the 4 digit sequence

for s in product(irange(0, 9), repeat=4):

# form the 6 2-digit subsequences

ss = set(nconcat(x) for x in combinations(s, 2))

# they are all different

if len(ss) != 6: continue

# and all prime

if not all(is_prime(x) for x in ss): continue

# and more than 1 divides into the original number

n = nconcat(s)

if not sum(1 for x in ss if n % x == 0) > 1: continue

printf("n={n} {ss}")

Using the general alphametic solver from the enigma.py library gives a solution in 82ms.


#!/usr/bin/env python enigma.py -r

# solver to use
SubstitutedExpression

# solver parameters
--distinct=0
--invalid=0,
--answer="ABCD"

# 2-digit subsequences are prime
"is_prime(AB)"
"is_prime(AC)"
"is_prime(AD)"
"is_prime(BC)"
"is_prime(BD)"
"is_prime(CD)"

# and all different
"len(set((AB, AC, AD, BC, BD, CD))) == 6"

# and more than 1 of them divides ABCD
"sum(1 for x in (AB, AC, AD, BC, BD, CD) if ABCD % x == 0) > 1"

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

#!/usr/bin/env python enigma.py -r

# solver to use

SubstitutedExpression

# solver parameters

--distinct=0

--invalid=0,

--answer="ABCD"

# 2-digit subsequences are prime

"is_prime(AB)"

"is_prime(AC)"

"is_prime(AD)"

"is_prime(BC)"

"is_prime(BD)"

"is_prime(CD)"

# and all different

"len(set((AB, AC, AD, BC, BD, CD))) == 6"

# and more than 1 of them divides ABCD

"sum(1 for x in (AB, AC, AD, BC, BD, CD) if ABCD % x == 0) > 1"

We can use analysis to limit the digits that can be assigned to each letter (e.g. C and D both appear as the units digit of two different primes, so cannot be even, etc.), but I’m not sure it’s worth it for a programmatic solution.

Reply

Sunday Times Teaser 2824 – New Extension

by Danny Roth

Published: 6 November 2016 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta