Sunday Times Teaser 2541 – Lotto Luck


from itertools import count
from fractions import Fraction as RF

# It is faster to work the sequence in reverse from what
# is left back to the original win.

# convert a fraction to an integer but only if it is one
fn = lambda x: x if x.denominator != 1 else x.numerator

# try values for the final remainder
for rem in count():
  # a list for the intermediate remainders and the win
  r = [rem]
  
  # now run backwards through the five gifts, not
  # assuming that intermediate results are integer
  for g in range(5):
    r.append(RF(5 * (r[-1] + 1), 4))
  
  # the final (win) must be an integer
  if r[-1].denominator == 1:
    
    # the win is less than £5000
    if r[-1] > 5000:
      break
    # work out the gifted amounts
    r = r[::-1]
    gifts = map(fn, (a - b for a, b in zip(r, r[1:])))
    
    f, s, l = ', £'.join(str(x) for x in gifts).rpartition(', ')
    gs = '£{} and {}'.format(f, l)
    print(f'He kept £{rem} from a £{r[0]} win with gifts of {gs}.')

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

from itertools import count

from fractions import Fraction as RF

# It is faster to work the sequence in reverse from what

# is left back to the original win.

# convert a fraction to an integer but only if it is one

fn = lambda x: x if x.denominator != 1 else x.numerator

# try values for the final remainder

for rem in count():

# a list for the intermediate remainders and the win

r = [rem]

# now run backwards through the five gifts, not

# assuming that intermediate results are integer

for g in range(5):

r.append(RF(5 * (r[-1] + 1), 4))

# the final (win) must be an integer

if r[-1].denominator == 1:

# the win is less than £5000

if r[-1] > 5000:

break

# work out the gifted amounts

r = r[::-1]

gifts = map(fn, (a - b for a, b in zip(r, r[1:])))

f, s, l = ', £'.join(str(x) for x in gifts).rpartition(', ')

gs = '£{} and {}'.format(f, l)

print(f'He kept £{rem} from a £{r[0]} win with gifts of {gs}.')

Reply

Frits permalink

Maybe way too complex but it was interesting to me..
I had to write a procedure to “solve” one equation with 2 integer variables.


from fractions import Fraction as RF
from math import gcd

# return a and b so that after <n> gifts the remainder = a * w + b
remainder = lambda n: (RF(4, 5) **n, RF(-1 * sum(1 * (5**i * 4**(n - i - 1))
                       for i in range(n)), 5 ** (n - 1)))

# solve equation with 2 integer variables  (a.x = b.y + c)
# try to find a f(n) = p.n + r for either the x or y variable
def solve_eq_2_ints(a, b, c):
  g = gcd(a, b, c)
  yield from reduce_eq(a // g, b // g, c // g)
  
# a.x = b.y + c  
def reduce_eq(a, b, c):
  if a == 1 or b == 1:
    yield (a, b, c)
  else:
    # parities
    pa, pb, pc = a % 2, b % 2, c % 2 
    if pa:
      if not pb and pc:         # x must be odd 
        yield from reduce_eq(a, b // 2, (c - a) // 2)
      elif not pb and not pc:   # x must be even
        yield from reduce_eq(a, b // 2, c // 2)
      else:
        yield (a, b, c)
    else:    
      if pb and not pc:         # y must be even
        yield from reduce_eq(a // 2, b, c // 2)
      elif pb and pc:           # y must be odd
        yield from reduce_eq(a // 2, b, (c - b) // 2)
      else:
        yield (a, b, c)

# analysis leads to:  5**5.chris = 4**5.win + 5.k 

# return a and b so that after 5 gifts the remainder = a * w + b
(a, b) = remainder(5)
k = b.numerator 

# try to solve equation p.x = q.y + r (finding a function for x or y)
for (p, q, r) in solve_eq_2_ints(5**5, 4**5, 5 * k):
  # we know <q> must have been reduced to 1 as 1st parameter is odd and 
  # 2nd parameter a power of 2
  print(f"win = {p} * n {'+' if r < 0 else '-'} {abs(r)}")
  
  for n, _ in enumerate(iter(bool, 1), 0): # infinite loop
    w = p * n - r
    if w >= 5000: break
    # calculate the remainder after 5 gifts (J, C, F, B and G)
    print("answer:", a * w + b)

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

from fractions import Fraction as RF

from math import gcd

# return a and b so that after <n> gifts the remainder = a * w + b

remainder = lambda n: (RF(4, 5) **n, RF(-1 * sum(1 * (5**i * 4**(n - i - 1))

for i in range(n)), 5 ** (n - 1)))

# solve equation with 2 integer variables (a.x = b.y + c)

# try to find a f(n) = p.n + r for either the x or y variable

def solve_eq_2_ints(a, b, c):

g = gcd(a, b, c)

yield from reduce_eq(a // g, b // g, c // g)

# a.x = b.y + c

def reduce_eq(a, b, c):

if a == 1 or b == 1:

yield (a, b, c)

else:

# parities

pa, pb, pc = a % 2, b % 2, c % 2

if pa:

if not pb and pc: # x must be odd

yield from reduce_eq(a, b // 2, (c - a) // 2)

elif not pb and not pc: # x must be even

yield from reduce_eq(a, b // 2, c // 2)

else:

yield (a, b, c)

else:

if pb and not pc: # y must be even

yield from reduce_eq(a // 2, b, c // 2)

elif pb and pc: # y must be odd

yield from reduce_eq(a // 2, b, (c - b) // 2)

else:

yield (a, b, c)

# analysis leads to: 5**5.chris = 4**5.win + 5.k

# return a and b so that after 5 gifts the remainder = a * w + b

(a, b) = remainder(5)

k = b.numerator

# try to solve equation p.x = q.y + r (finding a function for x or y)

for (p, q, r) in solve_eq_2_ints(5**5, 4**5, 5 * k):

# we know <q> must have been reduced to 1 as 1st parameter is odd and

# 2nd parameter a power of 2

print(f"win = {p} * n {'+' if r < 0 else '-'} {abs(r)}")

for n, _ in enumerate(iter(bool, 1), 0): # infinite loop

w = p * n - r

if w >= 5000: break

# calculate the remainder after 5 gifts (J, C, F, B and G)

print("answer:", a * w + b)

Reply

Frits permalink

Using xgcd.


from fractions import Fraction as RF
from number_theory import xgcd

# return a and b so that after <n> gifts the remainder = a * w + b
remainder = lambda n: (RF(4, 5) **n, RF(-1 * sum(1 * (5**i * 4**(n - i - 1))
                       for i in range(n)), 5 ** (n - 1)))

# solve equation with 2 integer variables  (a.x = b.y + c)
# try to find a f(n) = p.n + r for either the x or y variable

# analysis leads to:  5**5.chris - 4**5.win = 5.k 

# return a and b so that after 5 gifts the remainder = a * w + b
(a, b) = remainder(5)
k5 = 5 * b.numerator 

'''  from Brian's xgcd:
Euclid's Extended GCD Algorithm - given (a, b) find 
(u, v, g) such that u.a + v.b = g = gcd(a, b)

the solutions of a.x + b.y = c  with both x and y integer occur if,
and only if, g = gcd(a, b) divides c; the equations for x and y are:

x = (c/g).u + (b/g).t  \
                        | for t = ... -2, -1, 0, 1, 2 ... 
y = (c/g).v - (a/g).t  /
'''

(u, v, g) = xgcd(5**5, -4**5)   
(c, d) = (5**5, (k5 * v) % 5**5)  # win = c.n + d (work with positive c)
strt = - ((d - 1) // c) # make sure w > 0
print(f"win = {c} * n + {d}, n >= {strt}")
for n, _ in enumerate(iter(bool, 1), strt): # infinite loop
  w = c * n + d
  if w >= 5000: break
  # calculate the remainder after 5 gifts (J, C, F, B and G)
  print("answer:", a * w + b)

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

from number_theory import xgcd

# return a and b so that after <n> gifts the remainder = a * w + b

remainder = lambda n: (RF(4, 5) **n, RF(-1 * sum(1 * (5**i * 4**(n - i - 1))

for i in range(n)), 5 ** (n - 1)))

# solve equation with 2 integer variables (a.x = b.y + c)

# try to find a f(n) = p.n + r for either the x or y variable

# analysis leads to: 5**5.chris - 4**5.win = 5.k

# return a and b so that after 5 gifts the remainder = a * w + b

(a, b) = remainder(5)

k5 = 5 * b.numerator

''' from Brian's xgcd:

Euclid's Extended GCD Algorithm - given (a, b) find

(u, v, g) such that u.a + v.b = g = gcd(a, b)

the solutions of a.x + b.y = c with both x and y integer occur if,

and only if, g = gcd(a, b) divides c; the equations for x and y are:

x = (c/g).u + (b/g).t \

| for t = ... -2, -1, 0, 1, 2 ...

y = (c/g).v - (a/g).t /

'''

(u, v, g) = xgcd(5**5, -4**5)

(c, d) = (5**5, (k5 * v) % 5**5) # win = c.n + d (work with positive c)

strt = - ((d - 1) // c) # make sure w > 0

print(f"win = {c} * n + {d}, n >= {strt}")

for n, _ in enumerate(iter(bool, 1), strt): # infinite loop

w = c * n + d

if w >= 5000: break

# calculate the remainder after 5 gifts (J, C, F, B and G)

print("answer:", a * w + b)

Reply

BRG permalink

I have just added a linear diophantine equation solver to my number_theory library for this type of teaser. Its new so bear in mind it needs more testing.


from number_theory import lde_solve

#     Chris's remainders       Gifts to sons      Son 
#       w                  4^0.(w + 5) / 5^1     John
#  (4^1.w -     5) / 5^1   4^1.(w + 5) / 5^2   Ciaran
#  (4^2.w -    45) / 5^2   4^2.(w + 5) / 5^3   Fergal
#  (4^3.w -   305) / 5^3   4^3.(w + 5) / 5^4  Brendan
#  (4^4.w -  1845) / 5^4   4^4.(w + 5) / 5^5  Grainne
#  (4^5.w - 10505) / 5^5

# use Euclid's extended Greatest Common Divisor algorithm
# to solve for Chris's final remainder being a positive 
# integer: 
# 
#   4^5.w - 5^5.r = 10505 

(xc, xk), (yc, yk) = lde_solve(4 ** 5, -5 ** 5, 10505)
 
gifts = tuple(4 ** i * (xc + 5) // 5 ** (i + 1) for i in range(5))
f, s, l = ', £'.join(str(x) for x in gifts).rpartition(', ')
gs = '£{} and {}'.format(f, l)
print(f"He kept £{yc} from a £{xc} win with gifts of {gs}.")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

from number_theory import lde_solve

# Chris's remainders Gifts to sons Son

# w 4^0.(w + 5) / 5^1 John

# (4^1.w - 5) / 5^1 4^1.(w + 5) / 5^2 Ciaran

# (4^2.w - 45) / 5^2 4^2.(w + 5) / 5^3 Fergal

# (4^3.w - 305) / 5^3 4^3.(w + 5) / 5^4 Brendan

# (4^4.w - 1845) / 5^4 4^4.(w + 5) / 5^5 Grainne

# (4^5.w - 10505) / 5^5

# use Euclid's extended Greatest Common Divisor algorithm

# to solve for Chris's final remainder being a positive

# integer:

#

# 4^5.w - 5^5.r = 10505

(xc, xk), (yc, yk) = lde_solve(4 ** 5, -5 ** 5, 10505)

gifts = tuple(4 ** i * (xc + 5) // 5 ** (i + 1) for i in range(5))

f, s, l = ', £'.join(str(x) for x in gifts).rpartition(', ')

gs = '£{} and {}'.format(f, l)

print(f"He kept £{yc} from a £{xc} win with gifts of {gs}.")

Reply

Sunday Times Teaser 2541 – Lotto Luck

by H Bradley and C Higgins

Published: 5 June 2011 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta