73 lines
2 KiB
Nim
73 lines
2 KiB
Nim
# Fraction reduction.
|
|
|
|
import strformat
|
|
import times
|
|
|
|
type Result = tuple[n: int, nine: array[1..9, int]]
|
|
|
|
template find[T; N: static int](a: array[1..N, T]; value: T): int =
|
|
## Return the one-based index of a value in an array.
|
|
## This is needed as "system.find" returns a 0-based index even if the
|
|
## array lower bound is not null.
|
|
system.find(a, value) + 1
|
|
|
|
func toNumber(digits: seq[int]; removeDigit: int = 0): int =
|
|
## Convert a list of digits into a number.
|
|
var digits = digits
|
|
if removeDigit != 0:
|
|
let idx = digits.find(removeDigit)
|
|
digits.delete(idx)
|
|
for d in digits:
|
|
result = 10 * result + d
|
|
|
|
func nDigits(n: int): seq[Result] =
|
|
var digits = newSeq[int](n + 1) # Allocating one more to work with one-based indexes.
|
|
var used: array[1..9, bool]
|
|
for i in 1..n:
|
|
digits[i] = i
|
|
used[i] = true
|
|
var terminated = false
|
|
while not terminated:
|
|
var nine: array[1..9, int]
|
|
for i in 1..9:
|
|
if used[i]:
|
|
nine[i] = digits.toNumber(i)
|
|
result &= (n: digits.toNumber(), nine: nine)
|
|
block searchLoop:
|
|
terminated = true
|
|
for i in countdown(n, 1):
|
|
let d = digits[i]
|
|
doAssert(used[d], "Encountered an inconsistency with 'used' array")
|
|
used[d] = false
|
|
for j in (d + 1)..9:
|
|
if not used[j]:
|
|
used[j] = true
|
|
digits[i] = j
|
|
for k in (i + 1)..n:
|
|
digits[k] = used.find(false)
|
|
used[digits[k]] = true
|
|
terminated = false
|
|
break searchLoop
|
|
|
|
|
|
let start = gettime()
|
|
|
|
for n in 2..6:
|
|
let rs = nDigits(n)
|
|
var count = 0
|
|
var omitted: array[1..9, int]
|
|
for i in 1..<rs.high:
|
|
let (xn, rn) = rs[i]
|
|
for j in (i + 1)..rs.high:
|
|
let (xd, rd) = rs[j]
|
|
for k in 1..9:
|
|
let yn = rn[k]
|
|
let yd = rd[k]
|
|
if yn != 0 and yd != 0 and xn * yd == yn * xd:
|
|
inc count
|
|
inc omitted[k]
|
|
if count <= 12:
|
|
echo &"{xn}/{xd} => {yn}/{yd} (removed {k})"
|
|
|
|
echo &"{n}-digit fractions found: {count}, omitted {omitted}\n"
|
|
echo &"Took {gettime() - start}"
|