Aliquot sequence classifications: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
(Added C++ solution) |
||
Line 571: | Line 571: | ||
Integer : 153557177860800, Type : Non-Terminating, Series : 153557177860800, 470221741508000, 685337334283120, 908681172226160, 1276860840159280, 1867115442105104, 1751034184622896, 16436297 |
Integer : 153557177860800, Type : Non-Terminating, Series : 153557177860800, 470221741508000, 685337334283120, 908681172226160, 1276860840159280, 1867115442105104, 1751034184622896, 16436297 |
||
336056, 1405725265675144, 1230017019320456, 68719476751 |
336056, 1405725265675144, 1230017019320456, 68719476751 |
||
</pre> |
|||
=={{header|C++}}== |
|||
This one follows the trail blazed by the "Number Theoretic" C example above. |
|||
<lang cpp>#include <cstdint> |
|||
#include <iostream> |
|||
#include <string> |
|||
using integer = uint64_t; |
|||
// See https://en.wikipedia.org/wiki/Divisor_function |
|||
integer divisor_sum(integer n) { |
|||
integer total = 1, power = 2; |
|||
// Deal with powers of 2 first |
|||
for (; n % 2 == 0; power *= 2, n /= 2) |
|||
total += power; |
|||
// Odd prime factors up to the square root |
|||
for (integer p = 3; p * p <= n; p += 2) { |
|||
integer sum = 1; |
|||
for (power = p; n % p == 0; power *= p, n /= p) |
|||
sum += power; |
|||
total *= sum; |
|||
} |
|||
// If n > 1 then it's prime |
|||
if (n > 1) |
|||
total *= n + 1; |
|||
return total; |
|||
} |
|||
// See https://en.wikipedia.org/wiki/Aliquot_sequence |
|||
void classify_aliquot_sequence(integer n) { |
|||
constexpr int limit = 16; |
|||
integer terms[limit]; |
|||
terms[0] = n; |
|||
std::string classification("non-terminating"); |
|||
int length = 1; |
|||
for (int i = 1; i < limit; ++i) { |
|||
++length; |
|||
terms[i] = divisor_sum(terms[i - 1]) - terms[i - 1]; |
|||
if (terms[i] == n) { |
|||
classification = |
|||
(i == 1 ? "perfect" : (i == 2 ? "amicable" : "sociable")); |
|||
break; |
|||
} |
|||
int j = 1; |
|||
for (; j < i; ++j) { |
|||
if (terms[i] == terms[i - j]) |
|||
break; |
|||
} |
|||
if (j < i) { |
|||
classification = (j == 1 ? "aspiring" : "cyclic"); |
|||
break; |
|||
} |
|||
if (terms[i] == 0) { |
|||
classification = "terminating"; |
|||
break; |
|||
} |
|||
} |
|||
std::cout << n << ": " << classification << ", sequence: " << terms[0]; |
|||
for (int i = 1; i < length && terms[i] != terms[i - 1]; ++i) |
|||
std::cout << ' ' << terms[i]; |
|||
std::cout << '\n'; |
|||
} |
|||
int main() { |
|||
for (integer i = 1; i <= 10; ++i) |
|||
classify_aliquot_sequence(i); |
|||
for (integer i : {11, 12, 28, 496, 220, 1184, 12496, 1264460, 790, 909, 562, |
|||
1064, 1488}) |
|||
classify_aliquot_sequence(i); |
|||
classify_aliquot_sequence(15355717786080); |
|||
classify_aliquot_sequence(153557177860800); |
|||
return 0; |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
1: terminating, sequence: 1 0 |
|||
2: terminating, sequence: 2 1 0 |
|||
3: terminating, sequence: 3 1 0 |
|||
4: terminating, sequence: 4 3 1 0 |
|||
5: terminating, sequence: 5 1 0 |
|||
6: perfect, sequence: 6 |
|||
7: terminating, sequence: 7 1 0 |
|||
8: terminating, sequence: 8 7 1 0 |
|||
9: terminating, sequence: 9 4 3 1 0 |
|||
10: terminating, sequence: 10 8 7 1 0 |
|||
11: terminating, sequence: 11 1 0 |
|||
12: terminating, sequence: 12 16 15 9 4 3 1 0 |
|||
28: perfect, sequence: 28 |
|||
496: perfect, sequence: 496 |
|||
220: amicable, sequence: 220 284 220 |
|||
1184: amicable, sequence: 1184 1210 1184 |
|||
12496: sociable, sequence: 12496 14288 15472 14536 14264 12496 |
|||
1264460: sociable, sequence: 1264460 1547860 1727636 1305184 1264460 |
|||
790: aspiring, sequence: 790 650 652 496 |
|||
909: aspiring, sequence: 909 417 143 25 6 |
|||
562: cyclic, sequence: 562 284 220 284 |
|||
1064: cyclic, sequence: 1064 1336 1184 1210 1184 |
|||
1488: non-terminating, sequence: 1488 2480 3472 4464 8432 9424 10416 21328 22320 55056 95728 96720 236592 459792 881392 882384 |
|||
15355717786080: non-terminating, sequence: 15355717786080 44534663601120 144940087464480 471714103310688 1130798979186912 2688948041357088 6050151708497568 13613157922639968 35513546724070632 74727605255142168 162658586225561832 353930992506879768 642678347124409032 1125102611548462968 1977286128289819992 3415126495450394808 |
|||
153557177860800: non-terminating, sequence: 153557177860800 470221741508000 685337334283120 908681172226160 1276860840159280 1867115442105104 1751034184622896 1643629718341256 1441432897905784 1647351883321016 1557892692704584 1363939602434936 1194001297910344 1597170567336056 1405725265675144 1230017019320456 |
|||
</pre> |
</pre> |
||