Sunday Times Teaser 3259 – Something To Get Your Teeth Into

by BRG on 9 March 2025

by Colin Vout

Published Sunday March 09 2025 (link)

My bicycle has a set of three toothed rings (“chainrings”) attached to the pedal mechanism; I’d chosen these, with different numbers of teeth, from offered values of 30, 41, 45, 47, 58. Correspondingly, the rear wheel mechanism is attached to a set of five toothed rings (“sprockets”), each with no more than 20 teeth. A chain passes over one ring from each set, as selected by the gear controls; at any time the gear ratio is the number of teeth on the selected chainring divided by the number of teeth on the selected sprocket.

There are exactly three pairs of chainring/sprocket combinations that give gear ratios whose difference equals one divided by a whole number more than 100.

What are the numbers of teeth on the sprockets, in ascending order?

From → Uncategorized

3 Comments Leave one →

BRG permalink

This is a slow but general solution that will find solutions for different lower limits on the gear ratio difference denominators:


from itertools import combinations, product

try:
  from gmpy2 import mpq as RF
except ImportError:
  from fractions import Fraction as RF

# the lower limit of the gear ratio difference denominator
N_limit = 100

sols = []
# consider all combinations of chainrings and sprockets
for cs in combinations((30, 41, 45, 47, 58), 3):
  for ss in combinations(range(5, 21), 5):
    
    # collect all the gear ratios
    grs = sorted(RF(c, s) for c, s in product(cs, ss))
    # collect gear ratio differences that are 1 / N with N > N_limit
    s = {(r1, r2) for r1, r2 in combinations(grs, 2)
         if (d := r2 - r1).numerator == 1 and d.denominator > N_limit}
    if len(s) == 3:
      sols.append((cs, ss))

for i, (cs, ss) in enumerate(sorted(sols), 1):
      print(f"{i:>2}: sprocket teeth: {ss} [chainring teeth: {cs}].")

from itertools import combinations, product

try:

from gmpy2 import mpq as RF

except ImportError:

from fractions import Fraction as RF

# the lower limit of the gear ratio difference denominator

N_limit = 100

sols = []

# consider all combinations of chainrings and sprockets

for cs in combinations((30, 41, 45, 47, 58), 3):

for ss in combinations(range(5, 21), 5):

# collect all the gear ratios

grs = sorted(RF(c, s) for c, s in product(cs, ss))

# collect gear ratio differences that are 1 / N with N > N_limit

s = {(r1, r2) for r1, r2 in combinations(grs, 2)

if (d := r2 - r1).numerator == 1 and d.denominator > N_limit}

if len(s) == 3:

sols.append((cs, ss))

for i, (cs, ss) in enumerate(sorted(sols), 1):

print(f"{i:>2}: sprocket teeth: {ss} [chainring teeth: {cs}].")

Here is a faster solution:


from itertools import combinations, permutations

# the numeric limit on the gear ratio difference denominator 
N_limit = 100

gear_pairs = set()
# consider all pairs of chainrings and sprockets and
# map chainring pairs to compliant sprocket pairs
for c1, c2 in combinations((30, 41, 45, 47, 58), 2):
  for s1, s2 in permutations(range(5, 21), 2):
    # collect chainring and sprocket pairs with gear
    # ratio differences that are 1 / N with N > N_limit
    b = abs(c1 * s2 - c2 * s1)
    if b and s1 * s2 % b == 0 and s1 * s2 // b > N_limit:
      gear_pairs.add(((c1, s1), (c2, s2)))

cnt = 0
# choose three gear ratio pairs
for gp1, gp2, gp3 in combinations(gear_pairs, 3):
  (c1, s1), (c2, s2) = gp1
  (c3, s3), (c4, s4) = gp2
  (c5, s5), (c6, s6) = gp3
  # collect the chainrings and sprockets used
  cs = tuple(sorted(set((c1, c2, c3, c4, c5, c6))))
  ss = set((s1, s2, s3, s4, s5, s6))
  if len(cs) == 3 and len(ss) <= 5:
    # add extra sprockets to make five if there are less
    for sx in combinations(set(range(5, 21)) - ss, 5 - len(ss)):
      ssx = tuple(sorted(ss | set(sx)))
      cnt += 1
      print(f"{cnt:>2} sprocket teeth: {ssx} [chainring teeth: {cs}].")

from itertools import combinations, permutations

# the numeric limit on the gear ratio difference denominator

N_limit = 100

gear_pairs = set()

# consider all pairs of chainrings and sprockets and

# map chainring pairs to compliant sprocket pairs

for c1, c2 in combinations((30, 41, 45, 47, 58), 2):

for s1, s2 in permutations(range(5, 21), 2):

# collect chainring and sprocket pairs with gear

# ratio differences that are 1 / N with N > N_limit

b = abs(c1 * s2 - c2 * s1)

if b and s1 * s2 % b == 0 and s1 * s2 // b > N_limit:

gear_pairs.add(((c1, s1), (c2, s2)))

cnt = 0

# choose three gear ratio pairs

for gp1, gp2, gp3 in combinations(gear_pairs, 3):

(c1, s1), (c2, s2) = gp1

(c3, s3), (c4, s4) = gp2

(c5, s5), (c6, s6) = gp3

# collect the chainrings and sprockets used

cs = tuple(sorted(set((c1, c2, c3, c4, c5, c6))))

ss = set((s1, s2, s3, s4, s5, s6))

if len(cs) == 3 and len(ss) <= 5:

# add extra sprockets to make five if there are less

for sx in combinations(set(range(5, 21)) - ss, 5 - len(ss)):

ssx = tuple(sorted(ss | set(sx)))

cnt += 1

print(f"{cnt:>2} sprocket teeth: {ssx} [chainring teeth: {cs}].")

Frits permalink


from itertools import combinations

wheels = []
# select 2 chainrings 
for cr1, cr2 in combinations([30, 41, 45, 47, 58], 2):
  # select 2 sprockets
  for spr1, spr2 in combinations(range(5, 21), 2):
    # abs(A / B - C / D) < 1/100 so abs(A.D - C.B)) < B.D / 100
    diff = abs(cr1 * spr2 - cr2 * spr1)
    if not diff: continue
    d, r = divmod(spr1 * spr2, diff)
    # gear ratios whose difference equals 1 / whole number more than 100
    if not r and d > 100:
      wheels.append(((cr1, spr2), (cr2, spr1)))
      
sols = set()
# select 3 gear ratio pairs   
for c in combinations(wheels, 3):
  # use at most 3 chainrings
  if len(cr := tuple({x[i][0] for x in c for i in range(2)})) > 3: continue
  
  # use at most 5 sprockets
  if len(spr := tuple({x[i][1] for x in c for i in range(2)})) > 5: continue
  
  # already three pairs and not using all sprockets?
  if (ln := len(spr)) < 5:
    # add other sprockets
    for m in combinations(set(range(5, 21)).difference(spr), 5 - ln):
      sols.add((cr, spr + m))
  else:
    sols.add((cr, spr))

for crs, sprs in sols:
  # exactly three pairs of chainring/sprocket combinations
  if sum({c1, c2}.issubset(crs) and {s1, s2}.issubset(sprs) 
     for ((c1, s2), (c2, s1)) in wheels) != 3: continue   
  print("answer:", sorted(sprs))

from itertools import combinations

wheels = []

# select 2 chainrings

for cr1, cr2 in combinations([30, 41, 45, 47, 58], 2):

# select 2 sprockets

for spr1, spr2 in combinations(range(5, 21), 2):

# abs(A / B - C / D) < 1/100 so abs(A.D - C.B)) < B.D / 100

diff = abs(cr1 * spr2 - cr2 * spr1)

if not diff: continue

d, r = divmod(spr1 * spr2, diff)

# gear ratios whose difference equals 1 / whole number more than 100

if not r and d > 100:

wheels.append(((cr1, spr2), (cr2, spr1)))

sols = set()

# select 3 gear ratio pairs

for c in combinations(wheels, 3):

# use at most 3 chainrings

if len(cr := tuple({x[i][0] for x in c for i in range(2)})) > 3: continue

# use at most 5 sprockets

if len(spr := tuple({x[i][1] for x in c for i in range(2)})) > 5: continue

# already three pairs and not using all sprockets?

if (ln := len(spr)) < 5:

# add other sprockets

for m in combinations(set(range(5, 21)).difference(spr), 5 - ln):

sols.add((cr, spr + m))

else:

sols.add((cr, spr))

for crs, sprs in sols:

# exactly three pairs of chainring/sprocket combinations

if sum({c1, c2}.issubset(crs) and {s1, s2}.issubset(sprs)

for ((c1, s2), (c2, s1)) in wheels) != 3: continue

print("answer:", sorted(sprs))

Frits permalink

This version is a bit more efficient as the second sprocket is estimated/calculated.
Performing an inaccurate check with an higher threshold (0.011) before an accurate check also brings the internal runtime down.


from itertools import combinations
from math import ceil 

# chainrings
crs = (30, 41, 45, 47, 58)  
pairs = []
# choose 2 chainrings
for c1, c2 in combinations(crs, 2):
  # choose 1st sprocket so 2nd sprocket <= 20
  # if not (4.5 < (s2 := c2 * s1 / c1) < 20.5): continue
  for s1 in range(5, ceil(20.5 * c1 / c2)):
    # now calculate the equivalent 2nd sprocket
    # eliminate options with inaccurate floating point precision
    if abs(c1 / s1 - c2 / (s2 := round(c2 * s1 / c1))) < 0.011:
      # abs(c1/s1 - c2/s2) < 1 / 100 so abs(c1.s2 - c2.s1)) < s1.s2 / 100
      if not (y := abs(c1 * s2 - c2 * s1)): continue
      d, r = divmod(s1 * s2, y)
      # gear ratios whose difference equals 1 / whole number more than 100
      if not r and d > 100:
        pairs.append(((c1, s1), (c2, s2)))
          
sols = set()
# select 3 gear ratio pairs   
for c in combinations(pairs, 3):
  # use 3 chainrings at most
  if len(cr := tuple({x[i][0] for x in c for i in range(2)})) > 3: continue
  
  # use 5 sprockets at most
  if len(spr := tuple({x[i][1] for x in c for i in range(2)})) > 5: continue
  
  # three pairs and not using all sprockets?
  if (ln := len(spr)) < 5:
    # add other sprockets
    for m in combinations(set(range(5, 21)).difference(spr), 5 - ln):
      sols.add((cr, spr + m))
  else:
    sols.add((cr, spr))
 
for crs, sprs in sols:
  # exactly three pairs of chainring/sprocket combinations
  if sum({c1, c2}.issubset(crs) and {s1, s2}.issubset(sprs) 
     for ((c1, s2), (c2, s1)) in pairs) != 3: continue   
  print("answer:", sorted(sprs))

from itertools import combinations

from math import ceil

# chainrings

crs = (30, 41, 45, 47, 58)

pairs = []

# choose 2 chainrings

for c1, c2 in combinations(crs, 2):

# choose 1st sprocket so 2nd sprocket <= 20

# if not (4.5 < (s2 := c2 * s1 / c1) < 20.5): continue

for s1 in range(5, ceil(20.5 * c1 / c2)):

# now calculate the equivalent 2nd sprocket

# eliminate options with inaccurate floating point precision

if abs(c1 / s1 - c2 / (s2 := round(c2 * s1 / c1))) < 0.011:

# abs(c1/s1 - c2/s2) < 1 / 100 so abs(c1.s2 - c2.s1)) < s1.s2 / 100

if not (y := abs(c1 * s2 - c2 * s1)): continue

d, r = divmod(s1 * s2, y)

# gear ratios whose difference equals 1 / whole number more than 100

if not r and d > 100:

pairs.append(((c1, s1), (c2, s2)))

sols = set()

# select 3 gear ratio pairs

for c in combinations(pairs, 3):

# use 3 chainrings at most

if len(cr := tuple({x[i][0] for x in c for i in range(2)})) > 3: continue

# use 5 sprockets at most

if len(spr := tuple({x[i][1] for x in c for i in range(2)})) > 5: continue

# three pairs and not using all sprockets?

if (ln := len(spr)) < 5:

# add other sprockets

for m in combinations(set(range(5, 21)).difference(spr), 5 - ln):

sols.add((cr, spr + m))

else:

sols.add((cr, spr))

for crs, sprs in sols:

# exactly three pairs of chainring/sprocket combinations

if sum({c1, c2}.issubset(crs) and {s1, s2}.issubset(sprs)

for ((c1, s2), (c2, s1)) in pairs) != 3: continue

print("answer:", sorted(sprs))

Sunday Times Teaser 3259 – Something To Get Your Teeth Into

by Colin Vout

Published Sunday March 09 2025 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta