Factor-perfect numbers: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) (Added Perl) |
(Created Nim solution.) |
||
Line 282: | Line 282: | ||
OEIS A163272: |
OEIS A163272: |
||
0, 1, 48, 1280, 2496, 28672, 29808, 454656, 2342912, |
0, 1, 48, 1280, 2496, 28672, 29808, 454656, 2342912, |
||
</pre> |
|||
=={{header|Nim}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="Nim">import std/[algorithm, strutils, sugar, tables] |
|||
func moreMultiples(toSeq, fromSeq: seq[int]): seq[seq[int]] = |
|||
## Uses the first definition and recursion to generate the sequences. |
|||
result = collect: |
|||
for i in fromSeq: |
|||
if i > toSeq[^1] and i mod toSeq[^1] == 0: |
|||
toSeq & i |
|||
for i in 0..result.high: |
|||
for arr in moreMultiples(result[i], fromSeq): |
|||
result.add arr |
|||
func divisors(n: int): seq[int] = |
|||
## Return the list of divisors of "n". |
|||
var d = 1 |
|||
while d * d <= n: |
|||
if n mod d == 0: |
|||
let q = n div d |
|||
result.add d |
|||
if q != d: |
|||
result.add q |
|||
inc d |
|||
result.sort() |
|||
func cmp(x, y: seq[int]): int = |
|||
## Compare two sequences. |
|||
for i in 0..<min(x.len, y.len): |
|||
result = cmp(x[i], y[i]) |
|||
if result != 0: return |
|||
result = cmp(x.len, y.len) |
|||
let listing = collect( |
|||
for a in sorted(moreMultiples(@[1], divisors(48)[1..^2]), cmp): |
|||
a & 48) & @[@[1, 48]] |
|||
echo "48 sequences using first definition:" |
|||
for i, s in listing: |
|||
let item = '[' & s.join(", ") & ']' |
|||
stdout.write alignLeft(item, 22) |
|||
stdout.write if i mod 4 == 3: '\n' else: ' ' |
|||
# Derive second definition's sequences |
|||
echo "\n48 sequences using second definition:" |
|||
for i, s1 in listing: |
|||
let s2 = collect: |
|||
for j in 1..s1.high: |
|||
s1[j] div s1[j - 1] |
|||
let item = '[' & s2.join(", ") & ']' |
|||
stdout.write alignLeft(item, 20) |
|||
stdout.write if i mod 4 == 3: '\n' else: ' ' |
|||
var cache: Table[int, int] |
|||
proc erdosFactorCount(n: int): int = |
|||
## Erdos method. |
|||
if n in cache: return cache[n] |
|||
let ds = divisors(n) |
|||
if ds.len >= 2: |
|||
for d in ds[1..^2]: |
|||
result += erdosFactorCount(n div d) |
|||
inc result |
|||
cache[n] = result |
|||
stdout.write "\nOEIS A163272: " |
|||
let s = collect: |
|||
for num in 0..<2_400_000: |
|||
if num == 0 or erdosFactorCount(num) == num: |
|||
num |
|||
echo s.join(", ") |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>48 sequences using first definition: |
|||
[1, 2, 48] [1, 2, 4, 48] [1, 2, 4, 8, 48] [1, 2, 4, 8, 16, 48] |
|||
[1, 2, 4, 8, 24, 48] [1, 2, 4, 12, 48] [1, 2, 4, 12, 24, 48] [1, 2, 4, 16, 48] |
|||
[1, 2, 4, 24, 48] [1, 2, 6, 48] [1, 2, 6, 12, 48] [1, 2, 6, 12, 24, 48] |
|||
[1, 2, 6, 24, 48] [1, 2, 8, 48] [1, 2, 8, 16, 48] [1, 2, 8, 24, 48] |
|||
[1, 2, 12, 48] [1, 2, 12, 24, 48] [1, 2, 16, 48] [1, 2, 24, 48] |
|||
[1, 3, 48] [1, 3, 6, 48] [1, 3, 6, 12, 48] [1, 3, 6, 12, 24, 48] |
|||
[1, 3, 6, 24, 48] [1, 3, 12, 48] [1, 3, 12, 24, 48] [1, 3, 24, 48] |
|||
[1, 4, 48] [1, 4, 8, 48] [1, 4, 8, 16, 48] [1, 4, 8, 24, 48] |
|||
[1, 4, 12, 48] [1, 4, 12, 24, 48] [1, 4, 16, 48] [1, 4, 24, 48] |
|||
[1, 6, 48] [1, 6, 12, 48] [1, 6, 12, 24, 48] [1, 6, 24, 48] |
|||
[1, 8, 48] [1, 8, 16, 48] [1, 8, 24, 48] [1, 12, 48] |
|||
[1, 12, 24, 48] [1, 16, 48] [1, 24, 48] [1, 48] |
|||
48 sequences using second definition: |
|||
[2, 24] [2, 2, 12] [2, 2, 2, 6] [2, 2, 2, 2, 3] |
|||
[2, 2, 2, 3, 2] [2, 2, 3, 4] [2, 2, 3, 2, 2] [2, 2, 4, 3] |
|||
[2, 2, 6, 2] [2, 3, 8] [2, 3, 2, 4] [2, 3, 2, 2, 2] |
|||
[2, 3, 4, 2] [2, 4, 6] [2, 4, 2, 3] [2, 4, 3, 2] |
|||
[2, 6, 4] [2, 6, 2, 2] [2, 8, 3] [2, 12, 2] |
|||
[3, 16] [3, 2, 8] [3, 2, 2, 4] [3, 2, 2, 2, 2] |
|||
[3, 2, 4, 2] [3, 4, 4] [3, 4, 2, 2] [3, 8, 2] |
|||
[4, 12] [4, 2, 6] [4, 2, 2, 3] [4, 2, 3, 2] |
|||
[4, 3, 4] [4, 3, 2, 2] [4, 4, 3] [4, 6, 2] |
|||
[6, 8] [6, 2, 4] [6, 2, 2, 2] [6, 4, 2] |
|||
[8, 6] [8, 2, 3] [8, 3, 2] [12, 4] |
|||
[12, 2, 2] [16, 3] [24, 2] [48] |
|||
OEIS A163272: 0, 1, 48, 1280, 2496, 28672, 29808, 454656, 2342912 |
|||
</pre> |
</pre> |
||