Aliquot sequence classifications: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,083: / Line 2,083: @@
 {1488, Non-terminating, {1488, 2480, 3472, 4464, 8432, 9424, 10416, 21328, 22320, 55056, 95728, 96720, 236592, 459792, 881392, 882384, 1474608}}
 {15355717786080, Non-terminating, {15355717786080, 44534663601120, 144940087464480, 471714103310688, 1130798979186912, 2688948041357088, 6050151708497568, 13613157922639968, 35513546724070632, 74727605255142168, 162658586225561832, 353930992506879768, 642678347124409032, 1125102611548462968, 1977286128289819992, 3415126495450394808, 7156435369823219592}}</pre>
+=={{header|Nim}}
+No special optimizations, but quite efficient.
+<lang Nim>
+import math
+import strformat
+from strutils import addSep
+import times
+type
+  # Classification categories.
+  Category = enum
+    Unknown
+    Terminating = "terminating"
+    Perfect = "perfect"
+    Amicable = "amicable"
+    Sociable = "sociable"
+    Aspiring = "aspiring"
+    Cyclic = "cyclic"
+    NonTerminating = "non-terminating"
+  # Aliquot sequence.
+  AliquotSeq = seq[int]
+const Limit = 2^47    # Limit beyond which the category is considered to be "NonTerminating".
+#---------------------------------------------------------------------------------------------------
+proc sumProperDivisors(n: int): int =
+  ## Compute the sum of proper divisors.*
+  if n == 1: return 0
+  result = 1
+  for d in 2..sqrt(n.toFloat).int:
+    if n mod d == 0:
+      inc result, d
+      if n div d != d:
+        inc result, n div d
+#---------------------------------------------------------------------------------------------------
+iterator aliquotSeq(n: int): int =
+  ## 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: int): 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 [11, 12, 28, 496, 220, 1184, 12496, 1264460,
+, 909, 562, 1064, 1488, 15355717786080.int]:
+  let (cat, aseq) = classification(n)
+  echo fmt"{n:14}:  {cat:<20} {aseq}"
+echo ""
+echo fmt"Processed in {(getTime() - t0).inMilliseconds} ms."
+</lang>
+{{out}}
+<pre>
+: terminating          0
+: terminating          1, 0
+: terminating          1, 0
+: terminating          3, 1, 0
+: terminating          1, 0
+: perfect              6
+: terminating          1, 0
+: terminating          7, 1, 0
+: terminating          4, 3, 1, 0
+: terminating          8, 7, 1, 0
+:  terminating          1, 0
+:  terminating          16, 15, 9, 4, 3, 1, 0
+:  perfect              28
+:  perfect              496
+:  amicable             284, 220
+:  amicable             1210, 1184
+:  sociable             14288, 15472, 14536, 14264, 12496
+       1264460:  sociable             1547860, 1727636, 1305184, 1264460
+:  aspiring             650, 652, 496, 496
+:  aspiring             417, 143, 25, 6, 6
+:  cyclic               284, 220, 284
+:  cyclic               1336, 1184, 1210, 1184
+:  non-terminating      2480, 3472, 4464, 8432, 9424, 10416, 21328, 22320, 55056, 95728, 96720, 236592, 459792, 881392, 882384, 1474608, 2461648
+15355717786080:  non-terminating      44534663601120, 144940087464480
+Processed in 110 ms.
+</pre>
 =={{header|Oforth}}==