Aliquot sequence classifications: Difference between revisions
Content added Content deleted
(Optional largest number to simplify task implementation.) |
(+ D entry (without last input value)) |
||
Line 29: | Line 29: | ||
* [[Proper divisors]] |
* [[Proper divisors]] |
||
* [[Amicable pairs]] |
* [[Amicable pairs]] |
||
=={{header|D}}== |
|||
{{trans|Python}} |
|||
<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> |
|||
{{out}} |
|||
<pre>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]</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 20:07, 25 December 2014
Aliquot sequence classifications is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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]