return m/3
return None
+def most_trivial(n, m):
+ """The most trivial possible bound."""
+ return m
+
+def trivial(n, m):
+ """Trivial upper bound of m/2.
+
+If m does not divide n, then at least one m-stick must be cut into
+more than one piece, reducing the best option to at most m/2."""
+ if n % m == 0:
+ return None
+ return Fraction(m, 2)
+
bounds = [
(writinghawk, "writinghawk's piece-counting bound"),
(fivemack, "fivemack's conditional m/3 bound"),
+ (trivial, "trivial bound of m/2"),
+ (most_trivial, "trivial bound of m"),
]
def upper_bound(n, m):
assert n > m
- best = m, "trivial bound of m"
+ best = m+1, None
for boundtype in bounds:
b = boundtype[0](n, m)
if b is not None:
- if b < m:
+ if b < best[0]:
best = b, boundtype[1]
- elif b == m:
+ elif b == best[0]:
best = b, best[1] + ", " + boundtype[1]
return best