Aliquot sequence classifications
You are encouraged to solve this task according to the task description, using any language you may know.
An aliquot sequence of a positive integer K is defined recursively as the first member being K and subsequent members being the sum of the Proper divisors of the previous term.
- If the terms eventually reach 0 then the series for K is said to terminate.
There are several classifications for non termination:- If the second term is K then all future terms are also K and so the sequence repeats from the first term with period 1 and K is called perfect.
- If the third term would be repeating K then the sequence repeats with period 2 and K is called amicable.
- If the N'th term would be repeating K for the first time, with N > 3 then the sequence repeats with period N - 1 and K is called sociable.
Perfect, amicable and sociable numbers eventually repeat the original number K; there are other repetitions...- Some K have a sequence that eventually forms a periodic repetition of period 1 but of a number other than K, for example 95 which forms the sequence
95, 25, 6, 6, 6, ...
such K are called aspiring. - K that have a sequence that eventually forms a periodic repetition of period >= 2 but of a number other than K, for example 562 which forms the sequence
562, 284, 220, 284, 220, ...
such K are called cyclic.
- Some K have a sequence that eventually forms a periodic repetition of period 1 but of a number other than K, for example 95 which forms the sequence
And finally:- Some K form aliquot sequences that are not known to be either terminating or periodic. these K are to be called non-terminating.
For the purposes of this task, K is to be classed as non-terminating if it has not been otherwise classed after generating 16 terms or if any term of the sequence is greater than 2**47 = 140737488355328.
- Some K form aliquot sequences that are not known to be either terminating or periodic. these K are to be called non-terminating.
- Task
- Create routine(s) to generate the aliquot sequence of a positive integer enough to classify it according to the classifications given above.
- Use it to display the classification and sequences of the numbers one to ten inclusive.
- Use it to show the classification and sequences of the following integers, in order:
- 11, 12, 28, 496, 220, 1184, 12496, 1264460, 790, 909, 562, 1064, 1488, and optionally 15355717786080.
Show all output on this page.
- Cf.
- Abundant, deficient and perfect number classifications. (Classifications from only the first two members of the whole sequence).
- Proper divisors
- Amicable pairs
D
<lang d>import std.stdio, std.range, std.algorithm, std.typecons, std.conv;
auto properDivisors(in ulong n) pure nothrow @safe /*@nogc*/ {
return iota(1UL, (n + 1) / 2 + 1).filter!(x => n % x == 0 && n != x);
}
enum pDivsSum = (in ulong n) pure nothrow @safe /*@nogc*/ =>
n.properDivisors.sum;
auto aliquot(in ulong n,
in size_t maxLen=16, in ulong maxTerm=2UL^^47) pure nothrow @safe { if (n == 0) return tuple("Terminating", [0UL]); ulong[] s = [n]; size_t sLen = 1; ulong newN = n;
while (sLen <= maxLen && newN < maxTerm) { newN = s.back.pDivsSum; if (s.canFind(newN)) { if (s[0] == newN) { if (sLen == 1) { return tuple("Perfect", s); } else if (sLen == 2) { return tuple("Amicable", s); } else return tuple(text("Sociable of length ", sLen), s); } else if (s.back == newN) { return tuple("Aspiring", s); } else return tuple(text("Cyclic back to ", newN), s); } else if (newN == 0) { return tuple("Terminating", s ~ 0); } else { s ~= newN; sLen++; } }
return tuple("Non-terminating", s);
}
void main() {
foreach (immutable n; 1 .. 11) writefln("%s: %s", n.aliquot[]); writeln; foreach (immutable n; [11, 12, 28, 496, 220, 1184, 12496, 1264460, 790, 909, 562, 1064, 1488]) writefln("%s: %s", n.aliquot[]);
}</lang>
- Output:
Terminating: [1, 0] Terminating: [2, 1, 0] Terminating: [3, 1, 0] Terminating: [4, 3, 1, 0] Terminating: [5, 1, 0] Perfect: [6] Terminating: [7, 1, 0] Terminating: [8, 7, 1, 0] Terminating: [9, 4, 3, 1, 0] Terminating: [10, 8, 7, 1, 0] Terminating: [11, 1, 0] Terminating: [12, 16, 15, 9, 4, 3, 1, 0] Perfect: [28] Perfect: [496] Amicable: [220, 284] Amicable: [1184, 1210] Sociable of length 5: [12496, 14288, 15472, 14536, 14264] Sociable of length 4: [1264460, 1547860, 1727636, 1305184] Aspiring: [790, 650, 652, 496] Aspiring: [909, 417, 143, 25, 6] Cyclic back to 284: [562, 284, 220] Cyclic back to 1184: [1064, 1336, 1184, 1210] Non-terminating: [1488, 2480, 3472, 4464, 8432, 9424, 10416, 21328, 22320, 55056, 95728, 96720, 236592, 459792, 881392, 882384, 1474608]
Perl
<lang perl>use ntheory qw/divisor_sum/;
sub aliquot {
my($n, $maxterms, $maxn) = @_; $maxterms = 16 unless defined $maxterms; $maxn = 2**47 unless defined $maxn;
my %terms = ($n => 1); my @allterms = ($n); for my $term (2 .. $maxterms) { $n = divisor_sum($n)-$n; # push onto allterms here if we want the cyclic term to display last if $n > $maxn; return ("terminates",@allterms, 0) if $n == 0; if (defined $terms{$n}) { return ("perfect",@allterms) if $term == 2 && $terms{$n} == 1; return ("amicible",@allterms) if $term == 3 && $terms{$n} == 1; return ("sociable-".($term-1),@allterms) if $term > 3 && $terms{$n} == 1; return ("aspiring",@allterms) if $terms{$n} == $term-1; return ("cyclic-".($term-$terms{$n}),@allterms) if $terms{$n} < $term-1; } $terms{$n} = $term; push @allterms, $n; } ("non-term",@allterms);
}
for my $n (1..10) {
my($class, @seq) = aliquot($n); printf "%14d %10s [@seq]\n", $n, $class;
} print "\n"; for my $n (qw/11 12 28 496 220 1184 12496 1264460 790 909 562 1064 1488 15355717786080/) {
my($class, @seq) = aliquot($n); printf "%14d %10s [@seq]\n", $n, $class;
}</lang>
- Output:
1 terminates [1 0] 2 terminates [2 1 0] 3 terminates [3 1 0] 4 terminates [4 3 1 0] 5 terminates [5 1 0] 6 perfect [6] 7 terminates [7 1 0] 8 terminates [8 7 1 0] 9 terminates [9 4 3 1 0] 10 terminates [10 8 7 1 0] 11 terminates [11 1 0] 12 terminates [12 16 15 9 4 3 1 0] 28 perfect [28] 496 perfect [496] 220 amicible [220 284] 1184 amicible [1184 1210] 12496 sociable-5 [12496 14288 15472 14536 14264] 1264460 sociable-4 [1264460 1547860 1727636 1305184] 790 aspiring [790 650 652 496] 909 aspiring [909 417 143 25 6] 562 cyclic-2 [562 284 220] 1064 cyclic-2 [1064 1336 1184 1210] 1488 non-term [1488 2480 3472 4464 8432 9424 10416 21328 22320 55056 95728 96720 236592 459792 881392 882384] 15355717786080 non-term [15355717786080 44534663601120]
Python
Importing Proper divisors from prime factors:
<lang python>from proper_divisors import proper_divs from functools import lru_cache
@lru_cache()
def pdsum(n):
return sum(proper_divs(n))
def aliquot(n, maxlen=16, maxterm=2**47):
if n == 0: return 'terminating', [0] s, slen, new = [n], 1, n while slen <= maxlen and new < maxterm: new = pdsum(s[-1]) if new in s: if s[0] == new: if slen == 1: return 'perfect', s elif slen == 2: return 'amicable', s else: return 'sociable of length %i' % slen, s elif s[-1] == new: return 'aspiring', s else: return 'cyclic back to %i' % new, s elif new == 0: return 'terminating', s + [0] else: s.append(new) slen += 1 else: return 'non-terminating', s
if __name__ == '__main__':
for n in range(1, 11): print('%s: %r' % aliquot(n)) print() for n in [11, 12, 28, 496, 220, 1184, 12496, 1264460, 790, 909, 562, 1064, 1488, 15355717786080]: print('%s: %r' % aliquot(n))</lang>
- Output:
terminating: [1, 0] terminating: [2, 1, 0] terminating: [3, 1, 0] terminating: [4, 3, 1, 0] terminating: [5, 1, 0] perfect: [6] terminating: [7, 1, 0] terminating: [8, 7, 1, 0] terminating: [9, 4, 3, 1, 0] terminating: [10, 8, 7, 1, 0] terminating: [11, 1, 0] terminating: [12, 16, 15, 9, 4, 3, 1, 0] perfect: [28] perfect: [496] amicable: [220, 284] amicable: [1184, 1210] sociable of length 5: [12496, 14288, 15472, 14536, 14264] sociable of length 4: [1264460, 1547860, 1727636, 1305184] aspiring: [790, 650, 652, 496] aspiring: [909, 417, 143, 25, 6] cyclic back to 284: [562, 284, 220] cyclic back to 1184: [1064, 1336, 1184, 1210] non-terminating: [1488, 2480, 3472, 4464, 8432, 9424, 10416, 21328, 22320, 55056, 95728, 96720, 236592, 459792, 881392, 882384, 1474608] non-terminating: [15355717786080, 44534663601120, 144940087464480]
Racket
fold-divisors is used from Proper_divisors#Racket, but for the truly big numbers, we use divisors from math/number-theory.
<lang racket>#lang racket (require "proper-divisors.rkt" math/number-theory)
(define SCOPE 20000)
(define P
(let ((P-v (vector))) (λ (n) (cond [(> n SCOPE) (apply + (drop-right (divisors n) 1))] [else (set! P-v (fold-divisors P-v n 0 +)) (vector-ref P-v n)]))))
- initialise P-v
(void (P SCOPE))
(define (aliquot-sequence-class K)
;; note that seq is reversed as a list, since we're consing (define (inr-asc seq) (match seq [(list 0 _ ...) (values "terminating" seq)] [(list (== K) (== K) _ ...) (values "perfect" seq)] [(list n n _ ...) (values (format "aspiring to ~a" n) seq)] [(list (== K) ami (== K) _ ...) (values (format "amicable with ~a" ami) seq)] [(list (== K) cycle ... (== K)) (values (format "sociable length ~a" (add1 (length cycle))) seq)] [(list n cycle ... n _ ...) (values (format "cyclic on ~a length ~a" n (add1 (length cycle))) seq)] [(list X _ ...) #:when (> X 140737488355328) (values "non-terminating big number" seq)] [(list seq ...) #:when (> (length seq) 16) (values "non-terminating long sequence" seq)] [(list seq1 seq ...) (inr-asc (list* (P seq1) seq1 seq))]))
(inr-asc (list K)))
(define (report-aliquot-sequence-class n)
(define-values (c s) (aliquot-sequence-class n)) (printf "~a:\t~a\t~a~%" n c (reverse s)))
(for ((i (in-range 1 10)))
(report-aliquot-sequence-class i))
(newline)
(for ((i (in-list '(11 12 28 496 220 1184 12496 1264460 790 909 562 1064 1488 15355717786080))))
(report-aliquot-sequence-class i))</lang>
- Output:
1: terminating (1 0) 2: terminating (2 1 0) 3: terminating (3 1 0) 4: terminating (4 3 1 0) 5: terminating (5 1 0) 6: perfect (6 6) 7: terminating (7 1 0) 8: terminating (8 7 1 0) 9: terminating (9 4 3 1 0) 11: terminating (11 1 0) 12: terminating (12 16 15 9 4 3 1 0) 28: perfect (28 28) 496: perfect (496 496) 220: amicable with 284 (220 284 220) 1184: amicable with 1210 (1184 1210 1184) 12496: sociable length 5 (12496 14288 15472 14536 14264 12496) 1264460: sociable length 4 (1264460 1547860 1727636 1305184 1264460) 790: aspiring to 496 (790 650 652 496 496) 909: aspiring to 6 (909 417 143 25 6 6) 562: cyclic on 284 length 2 (562 284 220 284) 1064: cyclic on 1184 length 2 (1064 1336 1184 1210 1184) 1488: non-terminating long sequence (1488 2480 3472 4464 8432 9424 10416 21328 22320 55056 95728 96720 236592 459792 881392 882384 1474608) 15355717786080: non-terminating big number (15355717786080 44534663601120 144940087464480)