It's the least common multiple of the integers 1 through n, or
equivalently the product over all primes p <= n of the highest power
of p not exceeding n. So for n = 100, it's:
64 * 81 * 25 * 49 * 11 * 13 * 17 * ... rest of primes up to 100.
For general n, this number is of roughly the same order of magnitude
as e**n.
Ah, yes, I meant product(primes(n)), please forgive my honest mistake
which is partially caused by me not supposed to still be awake at this
time of the day. And thanks for Mark for noticing the mistake, and
here is the code I used:
import fraction
import random
frac = fraction.frac
ops = (frac.__add__, frac.__sub__)
a = frac(random.randrange(1, 10), random.randrange(1, 10))
b = frac(random.randrange(1, 10), random.randrange(1, 10))
while True:
o = ops[random.randrange(0, 2)]
a = o(a, b)
b = frac(random.randrange(1, 10), random.randrange(1, 10))
print a
I decided to keep the num/den limit low (10) because higher values
might obscure the fact that it do have limits. And through further
observations, I think it is sufficient if the limit is imposed in the
denominator only (numerator can have any values it wanted to,
denominator growth is determined only by the limit of denominator
growth).
I think I'll also post the code for the fraction class I used, if you
have other fraction class that can automatically simplify, you could
use that instead as this class suffers from a naive GCD
implementation:
==== fraction.py ====
from __future__ import division
def GCD(a, b):
if b == 0: return a
return GCD(b, a % b)
class frac:
''' Fraction Class
A fraction class.
Attributes:
num -> the numerator of a fraction
den -> the denominator of a fraction
Methods:
add(a, b) -> add fraction a to fraction b and return a
new fraction
sub(a, b) -> subtract fraction b from fraction a and
return a new fraction
mul(a, b) -> multiply fraction a with fraction b and
return a new fraction
div(a, b) -> divides fraction b from fraction a and
return a new fraction
invert(a) -> invert the fraction (switch the numerator
and denominator)
neg(a) -> negates the fraction (negates numerator)
powr(a, b) -> raise fraction a to the power of b
simplify(a, b) -> simplify fraction to its canonical
representation
__init__(a, b) -> creates a new fraction
__str__(a, b) -> returns a string representation. Mixed
fraction if possible
__repr__(a, b) -> returns a string representation. Always
return vulgar fraction
Operators:
Conversion to fractions will be done automatically whenever
possible, in-place
operation is fully supported. Both regular and reflected
operation is supported.
a + b -> Calls frac.add(a, b)
a - b -> Calls frac.sub(a, b)
a * b -> Calls frac.mul(a, b)
a / b -> Calls frac.div(a, b)
a // b -> Floors the resulting fraction from frac.div(a, b)
-a -> Negates a fraction
+a -> Returns a copy of the fraction
~a -> Return the reciprocal of a
Comparisons:
Implemented through __cmp__(a, b), no rich comparison.
a == b -> a equals b
a != b -> a not equal b
a > b -> a greater than b
a < b -> a less than b
a >= b -> a greater than or equal to b
a <= b -> a less than or equal to b
Casting:
__complex__ -> Converts the fraction to floats and return the
result as complex number
__int__ -> Returns the whole part of the fraction in
Integer
__long__ -> Returns the whole part of the fraction in Long
__float__ -> Returns the value of the fractino in Float
Exceptions:
ZeroDenominatorError
-> A fraction cannot have zero as its denominator
Bugs:
- At the meantime, the fraction class doesn't mix well if used
together with floating type numbers. Inline operators and
initializers implicitly assumed that numbers are either
integers or
fraction. So if there are operations involving floating
point or
you initialized a fraction with a floating point number, the
result
would be something like a "floating point fraction".
'''
def __init__(self, a = 0, b = 1):
dev = GCD(a, b)
if b > 0:
self.num = a // dev
elif b < 0:
self.num = -a // dev
else:
raise frac.ZeroDenominatorError
self.den = abs(b) // dev
def simplify(self):
dev = GCD(self.num, self.den)
self.num //= dev
self.den //= dev
return self
def add(a, b):
return frac(a.num * b.den + b.num * a.den, a.den * b.den)
def sub(a, b):
return frac(a.num * b.den - b.num * a.den, a.den * b.den)
def mul(a, b):
return frac(a.num * b.num, a.den * b.den)
def div(a, b):
return frac(a.num * b.den, a.den * b.num)
def invert(a):
return frac(a.den, a.num)
def neg(a):
return frac(-a.num, a.den)
def powr(x, y):
return frac(x.num ** y, x.den ** y)
def __add__(self, other):
return self.add(other)
def __radd__(self, other):
return other.add(self)
def __sub__(self, other):
return self.sub(other)
def __rsub__(self, other):
return other.sub(self)
def __mul__(self, other):
return self.mul(other)
def __rmul__(self, other):
return other.mul(self)
def __div__(self, other):
return self.div(other)
def __rdiv__(self, other):
return other.div(self)
def __truediv__(self, other):
return self.div(other)
def __rtruediv__(self, other):
return other.div(self)
def __floordiv__(self, other):
ret = self.div(other)
return ret.num // ret.den
def __rfloordiv__(self, other):
ret = other.div(self)
return ret.num // ret.den
def __iadd__(a, b):
a.num, a.den = a.num * b.den + b.num * a.den, a.den * b.den
return a.simplify()
def __isub__(a, b):
a.num, a.den = a.num * b.den - b.num * a.den, a.den * b.den
return a.simplify()
def __imul__(a, b):
a.num, a.den = a.num * b.num, a.den * b.den
return a.simplify()
def __idiv__(a, b):
a.num, a.den = a.num * b.den, a.den * b.num
return a.simplify()
def __itruediv__(a, b):
a.num, a.den = a.num * b.den, a.den * b.num
return a.simplify()
def __ifloordiv__(self, other):
self /= other
return self.num // self.den
def __str__(self):
''' String Function
Convert the function to its human-friendly representation.
Tries
to convert smartly.
'''
ret = ''
if self.num < 0: ret = '-'
w, n, d = abs(self.num // self.den), abs(self.num) % self.den,
self.den
if w != 0:
if n != 0 and d != 1:
ret += '%s %s/%s' % (w, n, d)
else:
ret += str(w)
else:
if n != 0 and d != 1:
ret += '%s/%s' % (n, d)
else:
ret = '0'
return ret
def __repr__(self):
return str(self.num) + '/' + str(self.den)
def __complex__(self):
return complex(float(self))
def __int__(self):
return int(self.num / self.den)
def __long__(self):
return long(self.num / self.den)
def __float__(self):
return self.num / self.den
def __neg__(self):
return frac.neg(self)
def __pos__(self):
return frac(self.num, self.den)
def __abs__(self):
return frac(abs(self.num), self.den)
def __invert__(self):
return frac.invert(self)
def __pow__(x, y):
return powr(x, y)
def __coerce__(self, other):
try:
self.num, self.den
except AttributeError:
self = frac(self)
try:
other.num, other.den
except AttributeError:
other = frac(other)
return self, other
def __cmp__(self, other):
a = self.num * other.den
b = other.num * self.den
return cmp(a, b)
class ZeroDenominatorError(Exception):
''' Exception for having a zero as the denominator in a
Fraction Class
'''
def __init__(self):
pass
def __str__(self):
return "A fraction cannot have zero as denominator
(frac.den != 0)"
