Aliquot sequence classifications: Difference between revisions
({{header|Racket}} implementation added) |
(Spacing) |
||
Line 5: | Line 5: | ||
:* If the terms eventually reach 0 then the series for K is said to '''terminate'''. |
:* If the terms eventually reach 0 then the series for K is said to '''terminate'''. |
||
:There are several classifications for non termination: |
:<br>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 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 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'''. |
:* 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... |
:<br>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 <code>95, 25, 6, 6, 6, ...</code> such K are called '''aspiring'''. |
:* 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 <code>95, 25, 6, 6, 6, ...</code> 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 <code>562, 284, 220, 284, 220, ...</code> such K are called '''cyclic'''. |
:* 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 <code>562, 284, 220, 284, 220, ...</code> such K are called '''cyclic'''. |
||
:And finally: |
:<br>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'''. <br>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'''. <br>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. |
||
Revision as of 23:23, 30 December 2014
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]
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)