Sunday Times Teaser 3169 – Cancel Culture — Amp It Up!


from itertools import combinations

# two digit primes above 20
pr2d = {n for n in range(23, 100, 2) if all(n % p for p in {3, 5, 7})}

# fractions n / d less than 1 / 20 with two digit prime denominators  
frs = [(n, d) for d in pr2d for n in range(1, (d - 1) // 20 + 1)]

# consider two digit intrinsic gains
for g in range(10, 100):
  # consider all combinations of three fractions less than 1 / 20
  for (u, p), (v, q), (w, r) in combinations(frs, 3):
    
    # compute the effective gain, which must be an integer
    eg, _r = divmod((p - u) * (q - v) * (r - w) * g, p * q * r)
    if not _r and g // 10 == eg // 10:
      f3 = '  '.join(f'{x}/{y}' for x, y in
          sorted(((u, p), (v, q), (w, r)), key=lambda x: x[0] / x[1]))
      print(f"{f3}  (gain {g} -> {eg}]")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

from itertools import combinations

# two digit primes above 20

pr2d = {n for n in range(23, 100, 2) if all(n % p for p in {3, 5, 7})}

# fractions n / d less than 1 / 20 with two digit prime denominators

frs = [(n, d) for d in pr2d for n in range(1, (d - 1) // 20 + 1)]

# consider two digit intrinsic gains

for g in range(10, 100):

# consider all combinations of three fractions less than 1 / 20

for (u, p), (v, q), (w, r) in combinations(frs, 3):

# compute the effective gain, which must be an integer

eg, _r = divmod((p - u) * (q - v) * (r - w) * g, p * q * r)

if not _r and g // 10 == eg // 10:

f3 = ' '.join(f'{x}/{y}' for x, y in

sorted(((u, p), (v, q), (w, r)), key=lambda x: x[0] / x[1]))

print(f"{f3} (gain {g} -> {eg}]")

A faster version.


from itertools import combinations, product
from math import gcd

# with fractions (u/p), (v/q) and (w/r) the ratio of the gains is:
# 
#        eg / ig = (p - u).(q - v).(r - w) / (p.q.r) 

# two digit primes above 20
pr2d = {n for n in range(23, 100, 2) if all(n % p for p in {3, 5, 7})}

# map prime denominators <d> to lists of numerators <n> with n/d < 1/20
frd = {d: [n for n in range(1, (d - 1) // 20 + 1)] for d in pr2d}

# consider all combinations of three possible denominators
for p, q, r in combinations(frd, 3):
  # and all arrangements of their numerators
  for u, v, w in product(*(frd[d] for d in (p, q, r))):
    # put the ratio of the two gains (eg and ig) in its lowest terms
    eg = (p - u) * (q - v) * (r - w)
    ig = p * q * r
    g = gcd(eg, ig)
    eg //= g
    ig //= g
    # the two gains must be two digit values with the same first digits
    if 10 <= eg < ig < 100 and eg // 10 == ig // 10:
      f3 = '  '.join(f'{x}/{y}' for x, y in
        sorted(((u, p), (v, q), (w, r)), key=lambda x: x[0] / x[1]))
      print(f"{f3}  (gain {ig} -> {eg}).")

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 math import gcd

# with fractions (u/p), (v/q) and (w/r) the ratio of the gains is:

#

# eg / ig = (p - u).(q - v).(r - w) / (p.q.r)

# two digit primes above 20

pr2d = {n for n in range(23, 100, 2) if all(n % p for p in {3, 5, 7})}

# map prime denominators <d> to lists of numerators <n> with n/d < 1/20

frd = {d: [n for n in range(1, (d - 1) // 20 + 1)] for d in pr2d}

# consider all combinations of three possible denominators

for p, q, r in combinations(frd, 3):

# and all arrangements of their numerators

for u, v, w in product(*(frd[d] for d in (p, q, r))):

# put the ratio of the two gains (eg and ig) in its lowest terms

eg = (p - u) * (q - v) * (r - w)

ig = p * q * r

g = gcd(eg, ig)

eg //= g

ig //= g

# the two gains must be two digit values with the same first digits

if 10 <= eg < ig < 100 and eg // 10 == ig // 10:

f3 = ' '.join(f'{x}/{y}' for x, y in

sorted(((u, p), (v, q), (w, r)), key=lambda x: x[0] / x[1]))

print(f"{f3} (gain {ig} -> {eg}).")

Reply

Frits permalink

Very compact.

Reply
- BRG permalink
  
  Yes, I went for simplicity rather than speed on this one. But updated now to
  improve the speed without a large increase in the number of lines of code.
  
  Reply

Frits permalink

Under 10 ms (reusing some of your techniques).


from itertools import combinations, product
from math import gcd

# use I * abc/stu = E  (I = intrinsic gain, E = effective gain)

# prime numbers higher than 20
P = [x for x in range(23, 100, 2) if all(x % p for p in [3, 5, 7])]

# allowable numerators per prime number denominator
d = {p: [x for x in range(1, p) if 20 * x > 19 * p] for p in P}

# choose three denominators
for s, t, u in combinations(P, 3):
  # choose two numerators
  for a, b in product(d[s], d[t]):
    # is abc/stu a fraction between two 2-digit numbers?
    # then gcd(abc, stu) must be the product of 2 prime numbers
    # so at least one of s, t, u must be cancelled by a or b
    if all((a * b) % x for x in [s, t, u]): continue
    stu = s * t * u
    for c in d[u]:
      abc = a * b * c
      # gcd is the product of 2 prime numbers
      if (g := gcd(abc, stu)) < 100:  continue

      I, E = stu // g, abc // g
      # different way to check same first digit
      if I - E > (I % 10): continue

      # print the fractions in ascending order
      fs = sorted([((y - x), y) for x, y in zip([a, b, c], [s, t, u])],
                  key=lambda x: x[0] / x[1])
      print("answer:", ', '.join(str(x) + '/' + str(y) for x, y in fs))

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

from itertools import combinations, product

from math import gcd

# use I * abc/stu = E (I = intrinsic gain, E = effective gain)

# prime numbers higher than 20

P = [x for x in range(23, 100, 2) if all(x % p for p in [3, 5, 7])]

# allowable numerators per prime number denominator

d = {p: [x for x in range(1, p) if 20 * x > 19 * p] for p in P}

# choose three denominators

for s, t, u in combinations(P, 3):

# choose two numerators

for a, b in product(d[s], d[t]):

# is abc/stu a fraction between two 2-digit numbers?

# then gcd(abc, stu) must be the product of 2 prime numbers

# so at least one of s, t, u must be cancelled by a or b

if all((a * b) % x for x in [s, t, u]): continue

stu = s * t * u

for c in d[u]:

abc = a * b * c

# gcd is the product of 2 prime numbers

if (g := gcd(abc, stu)) < 100: continue

I, E = stu // g, abc // g

# different way to check same first digit

if I - E > (I % 10): continue

# print the fractions in ascending order

fs = sorted([((y - x), y) for x, y in zip([a, b, c], [s, t, u])],

key=lambda x: x[0] / x[1])

print("answer:", ', '.join(str(x) + '/' + str(y) for x, y in fs))

Reply

Frits permalink


from itertools import combinations
from fractions import Fraction as RF

# use I * abc/fgh = E  (I = intrinsic gain, E = effective gain)

# primes higher than 20
P = {3, 5, 7}
P |= {x for x in range(11, 100, 2) if all(x % p for p in P)}
P = [x for x in P if x > 20]

# allowable fractions for E / I
F = set(f for i in range(10, 100) for j in range(10 * (i // 10), i)
     if (f := RF(j, i)) > (19 / 20)**3)

# allowable numerators per prime number denominator
d = dict()
for p in P:
  d[p] = []
  for x in range(p - 1, 0, -1):
    if 20 * x  <= 19 * p: break
    d[p] += [x]

# choose three denominators
for f, g, h in combinations(P, 3):
  # choose two numerators
  for a in d[f]:
    for b in d[g]:
      fr = RF(a * b, f * g)
      # if denominator is a 3 or 4 digit number
      # then c * I must be a multiple of the denominator to cancel this denominator
      if fr.denominator > 99 and (a * b) % h: continue
      for c in d[h]:
        # is abc/fgh a fraction of two 2-digit numbers?
        if RF(a * b * c, f * g * h) not in F: continue

        # print the fractions in ascending order
        fs = sorted(RF((y - x), y) for x, y in zip([a, b, c], [f, g, h]))
        print(f"answer: {fs[0]}, {fs[1]}, {fs[2]}")

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 fractions import Fraction as RF

# use I * abc/fgh = E (I = intrinsic gain, E = effective gain)

# primes higher than 20

P = {3, 5, 7}

P |= {x for x in range(11, 100, 2) if all(x % p for p in P)}

P = [x for x in P if x > 20]

# allowable fractions for E / I

F = set(f for i in range(10, 100) for j in range(10 * (i // 10), i)

if (f := RF(j, i)) > (19 / 20)**3)

# allowable numerators per prime number denominator

d = dict()

for p in P:

d[p] = []

for x in range(p - 1, 0, -1):

if 20 * x <= 19 * p: break

d[p] += [x]

# choose three denominators

for f, g, h in combinations(P, 3):

# choose two numerators

for a in d[f]:

for b in d[g]:

fr = RF(a * b, f * g)

# if denominator is a 3 or 4 digit number

# then c * I must be a multiple of the denominator to cancel this denominator

if fr.denominator > 99 and (a * b) % h: continue

for c in d[h]:

# is abc/fgh a fraction of two 2-digit numbers?

if RF(a * b * c, f * g * h) not in F: continue

# print the fractions in ascending order

fs = sorted(RF((y - x), y) for x, y in zip([a, b, c], [f, g, h]))

print(f"answer: {fs[0]}, {fs[1]}, {fs[2]}")

Reply

Frits permalink

A little different.


from itertools import combinations

# prime numbers higher than 20
P = [x for x in range(23, 100, 2) if all(x % p for p in [3, 5, 7])]

# allowable numerators per prime number denominator
d = {p: [x for x in range(p - 4, p) if 20 * x > 19 * p] for p in P}

# use I * abc/stu = E  (I = intrinsic gain, E = effective gain)

# choose three prime numbers (P has to be ordered)
for s, t, u in combinations(P, 3):
  # I must be a multiple m of the highest prime number (u)
  # as a, b and c are all less than u.

  # mabc = stE
  # c must be a multiple of s or t otherwise mab must be a multiple of st
  # which is not possible as 0 < m < 5 and 0.9025 < ab/st < 1
  for c, p1 in [(x, p1) for x in d[u] for p1 in [s, t] if x % p1 == 0]:
    p2 = (s * t) // p1                               # other prime number
    # c = k.p1, mabk = p2.E
    # check if numerator a or b is a multiple of p2
    for i, n1 in [(i, y) for i, p in enumerate([s, t])
                   for y in d[p] if y % p2 == 0]:
      # get other numerator (a or b)
      for n2 in d[[s, t][1 - i]]:
        # check all multiples of u
        for I in range(u, 100, u):

          E = I * n1 * n2 * c // (s * t * u)             # E = I * abc/stu

          if E // 10 != I // 10: continue
          (a, b) = (n1, n2) if i == 0 else (n2, n1)
          # print the fractions in ascending order
          fs = sorted([((y - x), y) for x, y in zip([a, b, c], [s, t, u])],
                            key=lambda x: x[0] / x[1])
          print("answer:", ', '.join(str(x) + '/' + str(y) for x, y in fs))

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

from itertools import combinations

# prime numbers higher than 20

P = [x for x in range(23, 100, 2) if all(x % p for p in [3, 5, 7])]

# allowable numerators per prime number denominator

d = {p: [x for x in range(p - 4, p) if 20 * x > 19 * p] for p in P}

# use I * abc/stu = E (I = intrinsic gain, E = effective gain)

# choose three prime numbers (P has to be ordered)

for s, t, u in combinations(P, 3):

# I must be a multiple m of the highest prime number (u)

# as a, b and c are all less than u.

# mabc = stE

# c must be a multiple of s or t otherwise mab must be a multiple of st

# which is not possible as 0 < m < 5 and 0.9025 < ab/st < 1

for c, p1 in [(x, p1) for x in d[u] for p1 in [s, t] if x % p1 == 0]:

p2 = (s * t) // p1 # other prime number

# c = k.p1, mabk = p2.E

# check if numerator a or b is a multiple of p2

for i, n1 in [(i, y) for i, p in enumerate([s, t])

for y in d[p] if y % p2 == 0]:

# get other numerator (a or b)

for n2 in d[[s, t][1 - i]]:

# check all multiples of u

for I in range(u, 100, u):

E = I * n1 * n2 * c // (s * t * u) # E = I * abc/stu

if E // 10 != I // 10: continue

(a, b) = (n1, n2) if i == 0 else (n2, n1)

# print the fractions in ascending order

fs = sorted([((y - x), y) for x, y in zip([a, b, c], [s, t, u])],

key=lambda x: x[0] / x[1])

print("answer:", ', '.join(str(x) + '/' + str(y) for x, y in fs))

Reply

Sunday Times Teaser 3169 – Cancel Culture — Amp It Up!

by Stephen Hogg

Published Sunday June 18 2023 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta