99 lines
2.7 KiB
Nim
99 lines
2.7 KiB
Nim
import std/[math, strformat, times]
|
|
from std/strutils import addSep
|
|
|
|
type
|
|
|
|
# Classification categories.
|
|
Category {.pure.} = enum
|
|
Unknown
|
|
Terminating = "terminating"
|
|
Perfect = "perfect"
|
|
Amicable = "amicable"
|
|
Sociable = "sociable"
|
|
Aspiring = "aspiring"
|
|
Cyclic = "cyclic"
|
|
NonTerminating = "non-terminating"
|
|
|
|
# Aliquot sequence.
|
|
AliquotSeq = seq[int64]
|
|
|
|
const Limit = 2^47 # Limit beyond which the category is considered to be "NonTerminating".
|
|
|
|
#---------------------------------------------------------------------------------------------------
|
|
|
|
proc sumProperDivisors(n: int64): int64 =
|
|
## Compute the sum of proper divisors.*
|
|
|
|
if n == 1: return 0
|
|
result = 1
|
|
for d in 2..sqrt(n.float).int:
|
|
if n mod d == 0:
|
|
inc result, d
|
|
if n div d != d:
|
|
result += n div d
|
|
|
|
#---------------------------------------------------------------------------------------------------
|
|
|
|
iterator aliquotSeq(n: int64): int64 =
|
|
## Yield the elements of the aliquot sequence of "n".
|
|
## Stopped if the current value is null or equal to "n".
|
|
|
|
var k = n
|
|
while true:
|
|
k = sumProperDivisors(k)
|
|
yield k
|
|
|
|
#---------------------------------------------------------------------------------------------------
|
|
|
|
proc `$`(a: AliquotSeq): string =
|
|
## Return the representation of an allquot sequence.
|
|
|
|
for n in a:
|
|
result.addSep(", ", 0)
|
|
result.addInt(n)
|
|
|
|
#---------------------------------------------------------------------------------------------------
|
|
|
|
proc classification(n: int64): tuple[cat: Category, values: AliquotSeq] =
|
|
## Return the category of the aliquot sequence of a number "n" and the sequence itself.
|
|
|
|
var count = 0 # Number of elements currently generated.
|
|
var prev = n # Previous element in the sequence.
|
|
result.cat = Unknown
|
|
for k in aliquotSeq(n):
|
|
inc count
|
|
if k == 0:
|
|
result.cat = Terminating
|
|
elif k == n:
|
|
result.cat = case count
|
|
of 1: Perfect
|
|
of 2: Amicable
|
|
else: Sociable
|
|
elif k > Limit or count > 16:
|
|
result.cat = NonTerminating
|
|
elif k == prev:
|
|
result.cat = Aspiring
|
|
elif k in result.values:
|
|
result.cat = Cyclic
|
|
prev = k
|
|
result.values.add(k)
|
|
if result.cat != Unknown:
|
|
break
|
|
|
|
#---------------------------------------------------------------------------------------------------
|
|
|
|
let t0 = getTime()
|
|
|
|
for n in 1..10:
|
|
let (cat, aseq) = classification(n)
|
|
echo fmt"{n:14}: {cat:<20} {aseq}"
|
|
|
|
echo ""
|
|
for n in [int64 11, 12, 28, 496, 220, 1184, 12496, 1264460,
|
|
790, 909, 562, 1064, 1488, 15355717786080]:
|
|
let (cat, aseq) = classification(n)
|
|
echo fmt"{n:14}: {cat:<20} {aseq}"
|
|
|
|
echo ""
|
|
echo fmt"Processed in {(getTime() - t0).inMilliseconds} ms."
|