99 lines
2.1 KiB
Nim
99 lines
2.1 KiB
Nim
import math
|
|
|
|
proc `^`[T](base, exp: T): T =
|
|
var (base, exp) = (base, exp)
|
|
result = 1
|
|
|
|
while exp != 0:
|
|
if (exp and 1) != 0:
|
|
result *= base
|
|
exp = exp shr 1
|
|
base *= base
|
|
|
|
proc gcd[T](u, v: T): T =
|
|
if v != 0:
|
|
gcd(v, u mod v)
|
|
else:
|
|
u.abs
|
|
|
|
proc lcm[T](a, b: T): T =
|
|
a div gcd(a, b) * b
|
|
|
|
type Rational* = tuple[num, den: int64]
|
|
|
|
proc fromInt*(x: SomeInteger): Rational =
|
|
result.num = x
|
|
result.den = 1
|
|
|
|
proc frac*(x: var Rational) =
|
|
let common = gcd(x.num, x.den)
|
|
x.num = x.num div common
|
|
x.den = x.den div common
|
|
|
|
proc `+` *(x, y: Rational): Rational =
|
|
let common = lcm(x.den, y.den)
|
|
result.num = common div x.den * x.num + common div y.den * y.num
|
|
result.den = common
|
|
result.frac
|
|
|
|
proc `+=` *(x: var Rational, y: Rational) =
|
|
let common = lcm(x.den, y.den)
|
|
x.num = common div x.den * x.num + common div y.den * y.num
|
|
x.den = common
|
|
x.frac
|
|
|
|
proc `-` *(x: Rational): Rational =
|
|
result.num = -x.num
|
|
result.den = x.den
|
|
|
|
proc `-` *(x, y: Rational): Rational =
|
|
x + -y
|
|
|
|
proc `-=` *(x: var Rational, y: Rational) =
|
|
x += -y
|
|
|
|
proc `*` *(x, y: Rational): Rational =
|
|
result.num = x.num * y.num
|
|
result.den = x.den * y.den
|
|
result.frac
|
|
|
|
proc `*=` *(x: var Rational, y: Rational) =
|
|
x.num *= y.num
|
|
x.den *= y.den
|
|
x.frac
|
|
|
|
proc reciprocal*(x: Rational): Rational =
|
|
result.num = x.den
|
|
result.den = x.num
|
|
|
|
proc `div`*(x, y: Rational): Rational =
|
|
x * y.reciprocal
|
|
|
|
proc toFloat*(x: Rational): float =
|
|
x.num.float / x.den.float
|
|
|
|
proc toInt*(x: Rational): int64 =
|
|
x.num div x.den
|
|
|
|
proc cmp*(x, y: Rational): int =
|
|
cmp x.toFloat, y.toFloat
|
|
|
|
proc `<` *(x, y: Rational): bool =
|
|
x.toFloat < y.toFloat
|
|
|
|
proc `<=` *(x, y: Rational): bool =
|
|
x.toFloat <= y.toFloat
|
|
|
|
proc abs*(x: Rational): Rational =
|
|
result.num = abs x.num
|
|
result.den = abs x.den
|
|
|
|
for candidate in 2'i64 .. <((2'i64)^19):
|
|
var sum: Rational = (1'i64, candidate)
|
|
for factor in 2'i64 .. pow(candidate.float, 0.5).int64:
|
|
if candidate mod factor == 0:
|
|
sum += (1'i64, factor) + (1'i64, candidate div factor)
|
|
if sum.den == 1:
|
|
echo "Sum of recipr. factors of ",candidate," = ",sum.num," exactly ",
|
|
if sum.num == 1: "perfect!" else: ""
|