Factor-perfect numbers: Difference between revisions
m (→{{header|Wren}}: Oops, formatting not quite right,) |
(Added Sidef) |
||
(24 intermediate revisions by 8 users not shown) | |||
Line 1: | Line 1: | ||
{{draft task}} |
{{draft task}} |
||
Consider the list of factors (divisors) of an integer, such as 12. The factors of 12 are [1, 2, 3, 4, 6, 12]. Consider all sorted sequences of the factors of n such that each succeeding number in such a |
Consider the list of factors (divisors) of an integer, such as 12. The factors of 12 are [1, 2, 3, 4, 6, 12]. Consider all sorted sequences of the factors of n such that each succeeding number in such a sequence is a multiple of its predecessor. So, for 6, |
||
we have the factors (divisors) [1, 2, 3, 6]. The 3 unique lists of sequential multiples starting with 1 and ending with 6 that can be derived from these factors are [1, 6], [1, 2, 6], and [1, 3, 6]. |
we have the factors (divisors) [1, 2, 3, 6]. The 3 unique lists of sequential multiples starting with 1 and ending with 6 that can be derived from these factors are [1, 6], [1, 2, 6], and [1, 3, 6]. |
||
Line 21: | Line 21: | ||
* Show all 48 ordered sequences for each of the two methods for n = 48, which is the first non-trivial factor-perfect number. |
* Show all 48 ordered sequences for each of the two methods for n = 48, which is the first non-trivial factor-perfect number. |
||
<br> |
|||
According to the paper listed below by P. Erdos, the number of these sequences is |
|||
: <math display="block"> F(n) = \sum_{k} F(\frac{n}{a_k}) + 1 </math> |
|||
where a is a list of the factors of n, including n, but excluding 1. F(n) is here the same as a function for calculating the number of different factorizations according to the second definition above except that F(1)=0 (where the number of factorizations of 1 must be 1 for it to be included in the sequence of factor-perfect numbers). |
|||
<br /> |
|||
* Write a program to calculate and show the first 7 numbers of the factor-perfect numbers. |
* Write a program to calculate and show the first 7 numbers of the factor-perfect numbers. |
||
Line 31: | Line 40: | ||
<br /> |
<br /> |
||
; see also: |
; see also: |
||
[https://oeis.org/A163272 OEIS A163272] |
[https://oeis.org/A163272 OEIS A163272] (Numbers k such that k = A074206(k), the number of ordered factorizations of k) |
||
[https://oeis.org/A074206 OEIS A074206] (Kalmár's [Kalmar's] problem: number of ordered factorizations of n.) |
|||
[https://doi.org/10.1016/j.jnt.2006.10.003 On the maximal order of numbers in the “factorisatio numerorum” problem] |
|||
[https://doi.org/10.1016/j.jnt.2006.10.003 On the maximal order of numbers in the “factorisatio numerorum” problem] (Klazar/Luca) |
|||
[[wp:Enumerative_combinatorics|Wikipedia: Enumerative Combinatorics]] |
|||
[https://www.jstor.org/stable/1968777?origin=crossref On Some Asymptotic Formulas in The Theory of The "Factorisatio Numerorum"] (P. Erdos) |
|||
<br /><br /><br /> |
<br /><br /><br /> |
||
=={{header|J}}== |
|||
Implementation: |
|||
<syntaxhighlight lang=J>factors=: {{/:~*/@>,{(^ i.)&.>/0 1+__ q:y}} |
|||
fp1=: {{ {{y#~0*/ .=~2|/\&>y}} y<@#"1~1,.~1,.#:i.2^_2+#y }}@factors |
|||
fp2=: 2 %~/\&.> fp1 |
|||
Fi=: i.0 |
|||
F=: {{ |
|||
if. y>:#Fi do. Fi=: Fi{.~1+y end. |
|||
if. (1<y)*0=y{Fi do. Fi=: Fi y}~ 1++/F y%}.factors y end. |
|||
y{Fi |
|||
}}"0</syntaxhighlight> |
|||
Task examples (formed into 8 columns for easy viewing): |
|||
<syntaxhighlight lang=J> _8,\fp1 48 |
|||
┌────────────┬───────────┬───────────┬──────────────┬──────────────┬───────────┬─────────────┬──────────────┐ |
|||
│1 48 │1 24 48 │1 16 48 │1 12 48 │1 12 24 48 │1 8 48 │1 8 24 48 │1 8 16 48 │ |
|||
├────────────┼───────────┼───────────┼──────────────┼──────────────┼───────────┼─────────────┼──────────────┤ |
|||
│1 6 48 │1 6 24 48 │1 6 12 48 │1 6 12 24 48 │1 4 48 │1 4 24 48 │1 4 16 48 │1 4 12 48 │ |
|||
├────────────┼───────────┼───────────┼──────────────┼──────────────┼───────────┼─────────────┼──────────────┤ |
|||
│1 4 12 24 48│1 4 8 48 │1 4 8 24 48│1 4 8 16 48 │1 3 48 │1 3 24 48 │1 3 12 48 │1 3 12 24 48 │ |
|||
├────────────┼───────────┼───────────┼──────────────┼──────────────┼───────────┼─────────────┼──────────────┤ |
|||
│1 3 6 48 │1 3 6 24 48│1 3 6 12 48│1 3 6 12 24 48│1 2 48 │1 2 24 48 │1 2 16 48 │1 2 12 48 │ |
|||
├────────────┼───────────┼───────────┼──────────────┼──────────────┼───────────┼─────────────┼──────────────┤ |
|||
│1 2 12 24 48│1 2 8 48 │1 2 8 24 48│1 2 8 16 48 │1 2 6 48 │1 2 6 24 48│1 2 6 12 48 │1 2 6 12 24 48│ |
|||
├────────────┼───────────┼───────────┼──────────────┼──────────────┼───────────┼─────────────┼──────────────┤ |
|||
│1 2 4 48 │1 2 4 24 48│1 2 4 16 48│1 2 4 12 48 │1 2 4 12 24 48│1 2 4 8 48 │1 2 4 8 24 48│1 2 4 8 16 48 │ |
|||
└────────────┴───────────┴───────────┴──────────────┴──────────────┴───────────┴─────────────┴──────────────┘ |
|||
_8,\fp2 48 |
|||
┌───────┬───────┬───────┬─────────┬─────────┬───────┬─────────┬─────────┐ |
|||
│48 │24 2 │16 3 │12 4 │12 2 2 │8 6 │8 3 2 │8 2 3 │ |
|||
├───────┼───────┼───────┼─────────┼─────────┼───────┼─────────┼─────────┤ |
|||
│6 8 │6 4 2 │6 2 4 │6 2 2 2 │4 12 │4 6 2 │4 4 3 │4 3 4 │ |
|||
├───────┼───────┼───────┼─────────┼─────────┼───────┼─────────┼─────────┤ |
|||
│4 3 2 2│4 2 6 │4 2 3 2│4 2 2 3 │3 16 │3 8 2 │3 4 4 │3 4 2 2 │ |
|||
├───────┼───────┼───────┼─────────┼─────────┼───────┼─────────┼─────────┤ |
|||
│3 2 8 │3 2 4 2│3 2 2 4│3 2 2 2 2│2 24 │2 12 2 │2 8 3 │2 6 4 │ |
|||
├───────┼───────┼───────┼─────────┼─────────┼───────┼─────────┼─────────┤ |
|||
│2 6 2 2│2 4 6 │2 4 3 2│2 4 2 3 │2 3 8 │2 3 4 2│2 3 2 4 │2 3 2 2 2│ |
|||
├───────┼───────┼───────┼─────────┼─────────┼───────┼─────────┼─────────┤ |
|||
│2 2 12 │2 2 6 2│2 2 4 3│2 2 3 4 │2 2 3 2 2│2 2 2 6│2 2 2 3 2│2 2 2 2 3│ |
|||
└───────┴───────┴───────┴─────────┴─────────┴───────┴─────────┴─────────┘ |
|||
(#~ (=*>.F)) i.30000 |
|||
0 1 48 1280 2496 28672 29808 |
|||
</syntaxhighlight> |
|||
=={{header|jq}}== |
|||
''Adapted from [[#Wren|Wren]]'' |
|||
{{works with|jq}} |
|||
'''Also works with gojq, the Go implementation of jq''' provided a |
|||
definition of _nwise is provided. |
|||
<syntaxhighlight lang=jq> |
|||
# unordered |
|||
def proper_divisors: |
|||
. as $n |
|||
| if $n > 1 then 1, |
|||
( range(2; 1 + (sqrt|floor)) as $i |
|||
| if ($n % $i) == 0 then $i, |
|||
(($n / $i) | if . == $i then empty else . end) |
|||
else empty |
|||
end) |
|||
else empty |
|||
end; |
|||
# Uses the first definition and recursion to generate the sequences. |
|||
def moreMultiples($toSeq; $fromSeq): |
|||
reduce $fromSeq[] as $i ({oneMores: []}; |
|||
if ($i > $toSeq[-1]) and ($i % $toSeq[-1]) == 0 |
|||
then .oneMores += [$toSeq + [$i]] |
|||
else . |
|||
end) |
|||
| reduce range(0; .oneMores|length) as $i (.; |
|||
.oneMores += moreMultiples(.oneMores[$i]; $fromSeq) ) |
|||
| .oneMores ; |
|||
# Input: {cache, ...} |
|||
# Output: {cache, count, ... } |
|||
def erdosFactorCount($n): |
|||
def properDivisors: proper_divisors | select(. != 1); |
|||
# Since this is a recursive function, the local and global states |
|||
# must be managed separately: |
|||
(reduce ($n|properDivisors) as $d ([0, .]; # count, global |
|||
($n/$d) as $t |
|||
| ($t|tostring) as $ts |
|||
| if .[1].cache|has($ts) then . else .[1].cache[$ts] = (.[1]|erdosFactorCount($t).count) end |
|||
| .[0] += (.[1].cache[$ts]) |
|||
)) as $update |
|||
| .count = $update[0] + 1 |
|||
| .cache = ($update[1].cache) ; |
|||
def task1: |
|||
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .; |
|||
def neatly: _nwise(4) | map(tostring|lpad(20)) | join(" "); |
|||
moreMultiples([1]; [48|proper_divisors]) |
|||
| sort |
|||
| map(. + [48]) + [[1, 48]] |
|||
| "\(length) sequences using first definition:", neatly, |
|||
(. as $listing |
|||
| reduce range(0; $listing|length) as $i ([]; |
|||
$listing[$i] as $seq |
|||
| (if ($seq[-1] != 48) then $seq + [48] else $seq end) as $seq |
|||
| . + [[ range(1; $seq|length) as $i | ($seq[$i]/$seq[$i-1]) | floor ]] ) |
|||
| "\n\(length) sequences using second definition:", neatly ); |
|||
# Stream the values of A163272: |
|||
def A163272: |
|||
0,1, |
|||
({n:4} |
|||
| while(true; |
|||
.emit=null |
|||
| erdosFactorCount(.n) # update the cache |
|||
| if .count == .n then .emit =.n else . end |
|||
| .n += 4 ) |
|||
| select(.emit).emit); |
|||
task1, |
|||
"", |
|||
"OEIS A163272:", limit(7; A163272) |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<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 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Revised to reflect a faster counting method (see second paper in the references). |
|||
<syntaxhighlight lang="julia">using Primes |
<syntaxhighlight lang="julia">using Primes |
||
using Memoize |
|||
""" Return the factors of n, including 1, n """ |
""" Return the factors of n, including 1, n """ |
||
Line 51: | Line 224: | ||
end |
end |
||
""" Uses the first definition and recursion to count the sequences with less memory usage """ |
|||
""" See reference paper by Erdos, page 1 """ |
|||
function count_multiples(to_seq, from_seq) |
|||
@memoize function kfactors(n) |
|||
onemores = [[to_seq; i] for i in from_seq if i > to_seq[end] && i % to_seq[end] == 0] |
|||
a = factors(n) |
|||
isempty(onemores) && return 0 |
|||
return |
return sum(kfactors(n ÷ d) for d in a[begin+1:end]) + 1 |
||
end |
end |
||
""" count all the factorization sequences of n """ |
|||
factorization_counts(n) = count_multiples([1], factors(n)[begin+1:end-1]) + 1 # + 1 for [1, n] |
|||
listing = sort!(push!(map(a -> push!(a, 48), more_multiples([1], factors(48)[begin+1:end-1])), [1, 48])) |
listing = sort!(push!(map(a -> push!(a, 48), more_multiples([1], factors(48)[begin+1:end-1])), [1, 48])) |
||
Line 75: | Line 245: | ||
println("\nOEIS A163272: ") |
println("\nOEIS A163272: ") |
||
for n in 0:2_400_000 |
for n in 0:2_400_000 |
||
n |
if n == 0 || kfactors(n) == n |
||
if n == 0 || factorization_counts(n) == n |
|||
print(n, ", ") |
print(n, ", ") |
||
end |
end |
||
end |
end |
||
</syntaxhighlight>{{out}} |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Line 113: | Line 283: | ||
0, 1, 48, 1280, 2496, 28672, 29808, 454656, 2342912, |
0, 1, 48, 1280, 2496, 28672, 29808, 454656, 2342912, |
||
</pre> |
</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> |
|||
=={{header|Perl}}== |
|||
{{trans|Raku}} |
|||
<syntaxhighlight lang="perl" line>use v5.36; |
|||
sub table (@V) { my $t = 3 * (my $w = 2 + 20); ( sprintf( ('%-'.$w.'s')x@V, @V) ) =~ s/.{1,$t}\K/\n/gr } |
|||
sub proper_divisors ($x) { |
|||
my @l; |
|||
@l = 1 if $x > 1; |
|||
for my $d (2 .. int sqrt $x) { |
|||
if (0 == $x % $d) { push @l, $d; my $y = int($x/$d); push @l, $y if $y != $d } |
|||
} |
|||
@l |
|||
} |
|||
sub erdosFactorCount ($n) { |
|||
my @foo = proper_divisors($n); shift @foo; |
|||
state %cache; |
|||
my ($sum,@divs) = (0, @foo); #(proper_divisors $n)[1..*]); |
|||
for my $d (@divs) { |
|||
my $t = int($n/$d); |
|||
$cache{$t} = erdosFactorCount($t) unless $cache{$t}; |
|||
$sum += $cache{$t} |
|||
} |
|||
++$sum |
|||
} |
|||
sub moreMultiples ($to, $from) { |
|||
my @oneMores; |
|||
for my $j (@$from) { |
|||
push @oneMores, [@$to, $j] if $j > $$to[-1] && 0 == $j % $$to[-1] |
|||
} |
|||
return unless @oneMores; |
|||
for (0 .. $#oneMores) { |
|||
push @oneMores, moreMultiples($oneMores[$_], $from); |
|||
} |
|||
@oneMores |
|||
} |
|||
my @listing = [1]; |
|||
push @listing, moreMultiples [1], [proper_divisors(48)]; |
|||
map { push @$_, 48 } @listing; |
|||
my @lists; map { push @lists, join ' ', @$_ } @listing; |
|||
say @listing . " sequences using first definition:\n" . table(@lists); |
|||
my @listing2; |
|||
for my $j (0.. $#listing) { |
|||
my @seq = @{$listing[$j]}; |
|||
push @seq, 48 if $seq[-1] != 48; |
|||
push @listing2, join ' ', map { int $seq[$_] / $seq[$_-1] } 1 .. $#seq; |
|||
} |
|||
say @listing2 . " sequences using second definition:\n" . table(@listing2); |
|||
my($n,@fpns) = (4, 0,1); |
|||
while ($#fpns < 6) { push(@fpns, $n) if erdosFactorCount($n) == $n; $n += 4 } |
|||
say "OEIS A163272: @fpns";</syntaxhighlight> |
|||
{{out}} |
|||
<pre>48 sequences using first definition: |
|||
1 48 1 2 48 1 24 48 |
|||
1 3 48 1 16 48 1 4 48 |
|||
1 12 48 1 6 48 1 8 48 |
|||
1 2 24 48 1 2 16 48 1 2 4 48 |
|||
1 2 12 48 1 2 6 48 1 2 8 48 |
|||
1 2 4 24 48 1 2 4 16 48 1 2 4 12 48 |
|||
1 2 4 8 48 1 2 4 12 24 48 1 2 4 8 24 48 |
|||
1 2 4 8 16 48 1 2 12 24 48 1 2 6 24 48 |
|||
1 2 6 12 48 1 2 6 12 24 48 1 2 8 24 48 |
|||
1 2 8 16 48 1 3 24 48 1 3 12 48 |
|||
1 3 6 48 1 3 12 24 48 1 3 6 24 48 |
|||
1 3 6 12 48 1 3 6 12 24 48 1 4 24 48 |
|||
1 4 16 48 1 4 12 48 1 4 8 48 |
|||
1 4 12 24 48 1 4 8 24 48 1 4 8 16 48 |
|||
1 12 24 48 1 6 24 48 1 6 12 48 |
|||
1 6 12 24 48 1 8 24 48 1 8 16 48 |
|||
48 sequences using second definition: |
|||
48 2 24 24 2 |
|||
3 16 16 3 4 12 |
|||
12 4 6 8 8 6 |
|||
2 12 2 2 8 3 2 2 12 |
|||
2 6 4 2 3 8 2 4 6 |
|||
2 2 6 2 2 2 4 3 2 2 3 4 |
|||
2 2 2 6 2 2 3 2 2 2 2 2 3 2 |
|||
2 2 2 2 3 2 6 2 2 2 3 4 2 |
|||
2 3 2 4 2 3 2 2 2 2 4 3 2 |
|||
2 4 2 3 3 8 2 3 4 4 |
|||
3 2 8 3 4 2 2 3 2 4 2 |
|||
3 2 2 4 3 2 2 2 2 4 6 2 |
|||
4 4 3 4 3 4 4 2 6 |
|||
4 3 2 2 4 2 3 2 4 2 2 3 |
|||
12 2 2 6 4 2 6 2 4 |
|||
6 2 2 2 8 3 2 8 2 3 |
|||
OEIS A163272: 0 1 48 1280 2496 28672 29808</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{libheader|Phix/online}} |
{{libheader|Phix/online}} |
||
You can run this online [http://phix.x10.mx/p2js/fpn.htm here] |
You can run this online [http://phix.x10.mx/p2js/fpn.htm here] (expect a blank screen for ~30s). |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #000080;font-style:italic;">-- |
|||
-- demo/rosetta/factor-perfect_numbers.exw |
|||
--</span> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;"> |
<span style="color: #008080;">function</span> <span style="color: #000000;">get_factor_set</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
||
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
<span style="color: #008080;">if</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
||
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span> <span style="color: #008080;">in</span> <span style="color: #000000;"> |
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span> <span style="color: #008080;">in</span> <span style="color: #000000;">get_factor_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">&</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> |
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">&</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
Line 148: | Line 525: | ||
<span style="color: #008080;">constant</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">48</span> |
<span style="color: #008080;">constant</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">48</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rN</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;"> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rN</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_factor_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">jbm</span><span style="color: #0000FF;">(</span><span style="color: #004080;">bool</span> <span style="color: #000000;">munge</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">jbm</span><span style="color: #0000FF;">(</span><span style="color: #004080;">bool</span> <span style="color: #000000;">munge</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">if</span> <span style="color: #000000;">munge</span> <span style="color: #008080;">then</span> <span style="color: #000000;">rN</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rN</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
<span style="color: #008080;">if</span> <span style="color: #000000;">munge</span> <span style="color: #008080;">then</span> <span style="color: #000000;">rN</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rN</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
Line 157: | Line 534: | ||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d sequences using second definition:\n%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">jbm</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">))</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d sequences using second definition:\n%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">jbm</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">))</span> |
||
<span style="color: # |
<span style="color: #004080;">integer</span> <span style="color: #000000;">efc_cache</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">erdosFactorCount</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;"> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">divs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
||
<span style="color: # |
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
||
<span style="color: #008080;">for</span> <span style="color: #000000;">d</span> <span style="color: #008080;">in</span> <span style="color: #000000;">divs</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">d</span><span style="color: #0000FF;"> |
<span style="color: #004080;">integer</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">node</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">efc_cache</span><span style="color: #0000FF;">)</span> |
||
<span style="color: # |
<span style="color: #008080;">if</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span> |
||
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">erdosFactorCount</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: # |
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">efc_cache</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">else</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">></span><span style="color: #000000;">l</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: # |
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_by_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">,</span><span style="color: #000000;">efc_cache</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">r</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<span style="color: #008080;">return</span> <span style="color: #000000;"> |
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
Line 179: | Line 555: | ||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span> |
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1"</span><span style="color: #0000FF;">}</span> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1"</span><span style="color: #0000FF;">}</span> |
||
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)<</span><span style="color: #000000;"> |
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)<</span><span style="color: #7060A8;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">8</span><span style="color: #0000FF;">:</span><span style="color: #000000;">9</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
||
<span style="color: #008080;">if</span> <span style="color: #000000;"> |
<span style="color: #008080;">if</span> <span style="color: #000000;">erdosFactorCount</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span> |
||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))</span> |
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
Line 191: | Line 567: | ||
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span> |
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Found %d: %s (%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Found %d: %s (%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)})</span> |
||
<span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span> |
|||
<!--</syntaxhighlight>--> |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
Line 222: | Line 600: | ||
{12,4} {16,3} {24,2} {48} |
{12,4} {16,3} {24,2} {48} |
||
Found |
Found 9: 0 1 48 1280 2496 28672 29808 454656 2342912 (1 minute and 9s) |
||
</pre> |
</pre> |
||
Unfortunately it takes 4 minutes 13 seconds to find 9 under p2js, so I've limited that to 8 (as mentioned above, ~30s) |
|||
It takes about 6s under p2js, and 4½ minutes to get the eighth on desktop/Phix, compared to 39:18 for Julia (7 in 13s), and since python took 2:20 for 7 I didn't bother trying 8. |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
<syntaxhighlight lang=python>''' Rosetta Code task Factor-perfect_numbers ''' |
<syntaxhighlight lang=python>''' Rosetta Code task Factor-perfect_numbers ''' |
||
from functools import cache |
|||
from sympy import divisors |
from sympy import divisors |
||
Line 245: | Line 623: | ||
listing = [a + [48 |
listing = [a + [48] |
||
for a in sorted(more_multiples([1], divisors(48)[1:-1]))] + [[1, 48]] |
|||
print('48 sequences using first definition:') |
print('48 sequences using first definition:') |
||
for j, seq in enumerate(listing): |
for j, seq in enumerate(listing): |
||
Line 258: | Line 637: | ||
@cache |
|||
def count_multiple_sequences(number): |
|||
def erdos_factor_count(number): |
|||
''' Counts using the first definition, plus one extra for [1, n] ''' |
|||
''' 'Erdos method ''' |
|||
return len(more_multiples([1], divisors(number)[1:-1])) + 1 |
|||
return sum(erdos_factor_count(number // d) for d in divisors(number)[1:-1]) + 1 |
|||
print("\nOEIS A163272: ", end='') |
print("\nOEIS A163272: ", end='') |
||
for num in range( |
for num in range(2_400_000): |
||
if num == 0 or |
if num == 0 or erdos_factor_count(num) == num: |
||
print(num, end=', ') |
print(num, end=', ') |
||
</syntaxhighlight>{{out}} |
</syntaxhighlight>{{out}} |
||
Line 297: | Line 677: | ||
[12, 2, 2] [16, 3] [24, 2] [48] |
[12, 2, 2] [16, 3] [24, 2] [48] |
||
OEIS A163272: 0, 1, 48, 1280, 2496, 28672, 29808, 454656, |
OEIS A163272: 0, 1, 48, 1280, 2496, 28672, 29808, 454656, 2342912, |
||
</pre> |
|||
=={{header|Raku}}== |
|||
{{trans|Wren}} |
|||
<syntaxhighlight lang="raku" line># 20221029 Raku programming solution |
|||
sub propdiv (\x) { |
|||
my @l = 1 if x > 1; |
|||
for (2 .. x.sqrt.floor) -> \d { |
|||
unless x % d { @l.push: d; my \y = x div d; @l.push: y if y != d } |
|||
} |
|||
@l |
|||
} |
|||
sub moreMultiples (@toSeq, @fromSeq) { |
|||
my @oneMores = gather for @fromSeq -> \j { |
|||
take @toSeq.clone.push(j) if j > @toSeq[*-1] and j %% @toSeq[*-1] |
|||
} |
|||
return () unless @oneMores.Bool; |
|||
for 0..^@oneMores { |
|||
@oneMores.append: moreMultiples @oneMores[$_], @fromSeq |
|||
} |
|||
@oneMores |
|||
} |
|||
sub erdosFactorCount (\n) { |
|||
state %cache; |
|||
my ($sum,@divs) = 0, |(propdiv n)[1..*]; |
|||
for @divs -> \d { |
|||
unless %cache{my \t = n div d}:exists { %cache{t} = erdosFactorCount(t) } |
|||
$sum += %cache{t} |
|||
} |
|||
++$sum |
|||
} |
|||
my @listing = moreMultiples [1], propdiv(48); |
|||
given @listing { $_.map: *.push: 48; $_.push: [1,48] } |
|||
say @listing.elems," sequences using first definition:"; |
|||
for @listing.rotor(4) -> \line { line.map: { printf "%-20s", $_ } ; say() } |
|||
my @listing2 = gather for (0..^+@listing) -> \j { |
|||
my @seq = |@listing[j]; |
|||
@seq.append: 48 if @seq[*-1] != 48; |
|||
take (1..^@seq).map: { @seq[$_] div @seq[$_-1] } |
|||
} |
|||
say "\n{@listing2.elems} sequences using second definition:"; |
|||
for @listing2.rotor(4) -> \line { line.map: { printf "%-20s", $_ } ; say() } |
|||
say "\nOEIS A163272:"; |
|||
my ($n,@fpns) = 4, 0,1; |
|||
while (@fpns < 7) { @fpns.push($n) if erdosFactorCount($n) == $n; $n += 4 } |
|||
say ~@fpns;</syntaxhighlight> |
|||
{{out}} |
|||
<pre>48 sequences using first definition: |
|||
1 2 48 1 24 48 1 3 48 1 16 48 |
|||
1 4 48 1 12 48 1 6 48 1 8 48 |
|||
1 2 24 48 1 2 16 48 1 2 4 48 1 2 12 48 |
|||
1 2 6 48 1 2 8 48 1 2 4 24 48 1 2 4 16 48 |
|||
1 2 4 12 48 1 2 4 8 48 1 2 4 12 24 48 1 2 4 8 24 48 |
|||
1 2 4 8 16 48 1 2 12 24 48 1 2 6 24 48 1 2 6 12 48 |
|||
1 2 6 12 24 48 1 2 8 24 48 1 2 8 16 48 1 3 24 48 |
|||
1 3 12 48 1 3 6 48 1 3 12 24 48 1 3 6 24 48 |
|||
1 3 6 12 48 1 3 6 12 24 48 1 4 24 48 1 4 16 48 |
|||
1 4 12 48 1 4 8 48 1 4 12 24 48 1 4 8 24 48 |
|||
1 4 8 16 48 1 12 24 48 1 6 24 48 1 6 12 48 |
|||
1 6 12 24 48 1 8 24 48 1 8 16 48 1 48 |
|||
48 sequences using second definition: |
|||
2 24 24 2 3 16 16 3 |
|||
4 12 12 4 6 8 8 6 |
|||
2 12 2 2 8 3 2 2 12 2 6 4 |
|||
2 3 8 2 4 6 2 2 6 2 2 2 4 3 |
|||
2 2 3 4 2 2 2 6 2 2 3 2 2 2 2 2 3 2 |
|||
2 2 2 2 3 2 6 2 2 2 3 4 2 2 3 2 4 |
|||
2 3 2 2 2 2 4 3 2 2 4 2 3 3 8 2 |
|||
3 4 4 3 2 8 3 4 2 2 3 2 4 2 |
|||
3 2 2 4 3 2 2 2 2 4 6 2 4 4 3 |
|||
4 3 4 4 2 6 4 3 2 2 4 2 3 2 |
|||
4 2 2 3 12 2 2 6 4 2 6 2 4 |
|||
6 2 2 2 8 3 2 8 2 3 48 |
|||
OEIS A163272: |
|||
0 1 48 1280 2496 28672 29808</pre> |
|||
=={{header|Sidef}}== |
|||
{{trans|Perl}} |
|||
<syntaxhighlight lang="ruby">func erdosFactorCount (n) is cached { |
|||
var sum = 1 |
|||
var divs = proper_divisors(n).slice(1) |
|||
divs.each {|d| |
|||
sum += __FUNC__(idiv(n,d)) |
|||
} |
|||
return sum |
|||
} |
|||
func moreMultiples (to, from) { |
|||
var oneMores = [] |
|||
from.each {|j| |
|||
if (j > to.tail && to.tail.divides(j)) { |
|||
oneMores << [to..., j] |
|||
} |
|||
} |
|||
for k in (oneMores.range) { |
|||
oneMores << __FUNC__(oneMores[k], from)... |
|||
} |
|||
return oneMores |
|||
} |
|||
var listing = [[1]] |
|||
listing << moreMultiples([1], proper_divisors(48))... |
|||
listing.each {|a| a << 48 } |
|||
say "#{listing.len} sequences using first definition:" |
|||
listing.slices(3).each { .map { .join(' ') }.map{ '%-20s' % _ }.join.say } |
|||
var listing2 = gather { |
|||
for j in (^listing.len) { |
|||
var seq = listing[j] |
|||
take(1..seq.end -> map {|j| seq[j] / seq[j-1] }) |
|||
} |
|||
} |
|||
say "\n#{listing2.len} sequences using second definition:" |
|||
listing2.slices(3).each { .map { .join(' ') }.map{ '%-20s' % _ }.join.say } |
|||
print "\nOEIS A163272: " |
|||
say [0, 1, (1..Inf -> lazy.map {|n| 4*n }.grep{|n| erdosFactorCount(n) == n }.first(5))...]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
48 sequences using first definition: |
|||
1 48 1 2 48 1 3 48 |
|||
1 4 48 1 6 48 1 8 48 |
|||
1 12 48 1 16 48 1 24 48 |
|||
1 2 4 48 1 2 6 48 1 2 8 48 |
|||
1 2 12 48 1 2 16 48 1 2 24 48 |
|||
1 2 4 8 48 1 2 4 12 48 1 2 4 16 48 |
|||
1 2 4 24 48 1 2 4 8 16 48 1 2 4 8 24 48 |
|||
1 2 4 12 24 48 1 2 6 12 48 1 2 6 24 48 |
|||
1 2 6 12 24 48 1 2 8 16 48 1 2 8 24 48 |
|||
1 2 12 24 48 1 3 6 48 1 3 12 48 |
|||
1 3 24 48 1 3 6 12 48 1 3 6 24 48 |
|||
1 3 6 12 24 48 1 3 12 24 48 1 4 8 48 |
|||
1 4 12 48 1 4 16 48 1 4 24 48 |
|||
1 4 8 16 48 1 4 8 24 48 1 4 12 24 48 |
|||
1 6 12 48 1 6 24 48 1 6 12 24 48 |
|||
1 8 16 48 1 8 24 48 1 12 24 48 |
|||
48 sequences using second definition: |
|||
48 2 24 3 16 |
|||
4 12 6 8 8 6 |
|||
12 4 16 3 24 2 |
|||
2 2 12 2 3 8 2 4 6 |
|||
2 6 4 2 8 3 2 12 2 |
|||
2 2 2 6 2 2 3 4 2 2 4 3 |
|||
2 2 6 2 2 2 2 2 3 2 2 2 3 2 |
|||
2 2 3 2 2 2 3 2 4 2 3 4 2 |
|||
2 3 2 2 2 2 4 2 3 2 4 3 2 |
|||
2 6 2 2 3 2 8 3 4 4 |
|||
3 8 2 3 2 2 4 3 2 4 2 |
|||
3 2 2 2 2 3 4 2 2 4 2 6 |
|||
4 3 4 4 4 3 4 6 2 |
|||
4 2 2 3 4 2 3 2 4 3 2 2 |
|||
6 2 4 6 4 2 6 2 2 2 |
|||
8 2 3 8 3 2 12 2 2 |
|||
OEIS A163272: [0, 1, 48, 1280, 2496, 28672, 29808] |
|||
</pre> |
</pre> |
||
Line 304: | Line 854: | ||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
Timings are about: 0.19 secs for 7, 8.5 secs for 8 and 97 secs for 9 factor-perfect numbers. |
|||
However, using Phix's 'g' function for the last part which is considerably quicker than generating a bunch of lists and then counting them - overall time down from 76 to 7 seconds. Still not really worth attempting stretch goal though. |
|||
<syntaxhighlight lang=" |
<syntaxhighlight lang="wren">import "./math" for Int, Nums |
||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
Line 322: | Line 872: | ||
} |
} |
||
var cache = {} |
|||
// Get factorization sequence count. |
|||
var countMultipleSequences = Fn.new { |n| |
|||
var erdosFactorCount |
|||
var f = Int.properDivisors(n) |
|||
erdosFactorCount = Fn.new { |n| |
|||
f.removeAt(0) |
|||
var |
var divs = Int.properDivisors(n) |
||
divs.removeAt(0) |
|||
var sum = 0 |
|||
for (d in divs) { |
|||
var t = (n/d).floor |
|||
if (!cache.containsKey(t)) cache[t] = erdosFactorCount.call(t) |
|||
var j = i + 1 |
|||
sum = sum + cache[t] |
|||
while (x <= n) { |
|||
while (j < l && f[j] < x) j = j + 1 |
|||
if (j > l-1) break |
|||
if (f[j] == x) d[i] = d[i] + d[j] |
|||
x = x + k |
|||
} |
|||
} |
} |
||
return |
return sum + 1 |
||
} |
} |
||
Line 372: | Line 916: | ||
var n = 4 |
var n = 4 |
||
var fpns = [0, 1] |
var fpns = [0, 1] |
||
while (fpns.count < |
while (fpns.count < 9) { |
||
if ( |
if (erdosFactorCount.call(n) == n) fpns.add(n) |
||
n = n + 4 |
n = n + 4 |
||
} |
} |
||
Line 392: | Line 936: | ||
[1, 6, 48] [1, 6, 12, 48] [1, 6, 12, 24, 48] [1, 6, 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, 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] |
[1, 12, 24, 48] [1, 16, 48] [1, 24, 48] [1, 48] |
||
48 sequences using second definition: |
48 sequences using second definition: |
||
[2, 24] [2, 2, 12] [2, 2, 2, 6] [2, 2, 2, 2, 3] |
[2, 24] [2, 2, 12] [2, 2, 2, 6] [2, 2, 2, 2, 3] |
||
Line 409: | Line 953: | ||
OEIS A163272: |
OEIS A163272: |
||
[0, 1, 48, 1280, 2496, 28672, 29808] |
[0, 1, 48, 1280, 2496, 28672, 29808, 454656, 2342912] |
||
</pre> |
</pre> |
Latest revision as of 15:54, 7 December 2023
Consider the list of factors (divisors) of an integer, such as 12. The factors of 12 are [1, 2, 3, 4, 6, 12]. Consider all sorted sequences of the factors of n such that each succeeding number in such a sequence is a multiple of its predecessor. So, for 6, we have the factors (divisors) [1, 2, 3, 6]. The 3 unique lists of sequential multiples starting with 1 and ending with 6 that can be derived from these factors are [1, 6], [1, 2, 6], and [1, 3, 6].
Another way to see these sequences is as an set of all the ordered factorizations of a number taken so that their product is that number (excluding 1 from the sequence). So, for 6, we would have [6], [2, 3], and [3, 2]. In this description of the sequences, we are looking at the numbers needed to multiply by, in order to generate the next element in the sequences previously listed in our first definition of the sequence type, as we described it in the preceding paragraph, above.
For example, for the factorization of 6, if the first type of sequence is [1, 6], this is generated by [6] since 1 * 6 = 6. Similarly, the first type of sequence [1, 2, 6] is generated by the second type of sequence [2, 3] because 1 * 2 = 2 and 2 * 3 = 6. Similarly, [1, 3, 6] is generated by [3, 2] because 1 * 3 = 3 and 3 * 2 = 6.
If we count the number of such sorted sequences of multiples, or ordered factorizations, and using that count find all integers `n` for which the count of such sequences equals `n`, we have re-created the sequence of the "factor-perfect" numbers (OEIS 163272).
By some convention, on its OEIS page, the factor-perfect number sequence starts with 0 rather than 1. As might be expected
with a sequence involving factorization and combinations, finding factor-perfect numbers becomes
more demanding on CPU time as the numbers become large.
- Task
- Show all 48 ordered sequences for each of the two methods for n = 48, which is the first non-trivial factor-perfect number.
According to the paper listed below by P. Erdos, the number of these sequences is
where a is a list of the factors of n, including n, but excluding 1. F(n) is here the same as a function for calculating the number of different factorizations according to the second definition above except that F(1)=0 (where the number of factorizations of 1 must be 1 for it to be included in the sequence of factor-perfect numbers).
- Write a program to calculate and show the first 7 numbers of the factor-perfect numbers.
- Stretch task
- Calculate and show more of the subsequent numbers in the sequence.
- see also
OEIS A163272 (Numbers k such that k = A074206(k), the number of ordered factorizations of k) OEIS A074206 (Kalmár's [Kalmar's] problem: number of ordered factorizations of n.) On the maximal order of numbers in the “factorisatio numerorum” problem (Klazar/Luca) On Some Asymptotic Formulas in The Theory of The "Factorisatio Numerorum" (P. Erdos)
J
Implementation:
factors=: {{/:~*/@>,{(^ i.)&.>/0 1+__ q:y}}
fp1=: {{ {{y#~0*/ .=~2|/\&>y}} y<@#"1~1,.~1,.#:i.2^_2+#y }}@factors
fp2=: 2 %~/\&.> fp1
Fi=: i.0
F=: {{
if. y>:#Fi do. Fi=: Fi{.~1+y end.
if. (1<y)*0=y{Fi do. Fi=: Fi y}~ 1++/F y%}.factors y end.
y{Fi
}}"0
Task examples (formed into 8 columns for easy viewing):
_8,\fp1 48
┌────────────┬───────────┬───────────┬──────────────┬──────────────┬───────────┬─────────────┬──────────────┐
│1 48 │1 24 48 │1 16 48 │1 12 48 │1 12 24 48 │1 8 48 │1 8 24 48 │1 8 16 48 │
├────────────┼───────────┼───────────┼──────────────┼──────────────┼───────────┼─────────────┼──────────────┤
│1 6 48 │1 6 24 48 │1 6 12 48 │1 6 12 24 48 │1 4 48 │1 4 24 48 │1 4 16 48 │1 4 12 48 │
├────────────┼───────────┼───────────┼──────────────┼──────────────┼───────────┼─────────────┼──────────────┤
│1 4 12 24 48│1 4 8 48 │1 4 8 24 48│1 4 8 16 48 │1 3 48 │1 3 24 48 │1 3 12 48 │1 3 12 24 48 │
├────────────┼───────────┼───────────┼──────────────┼──────────────┼───────────┼─────────────┼──────────────┤
│1 3 6 48 │1 3 6 24 48│1 3 6 12 48│1 3 6 12 24 48│1 2 48 │1 2 24 48 │1 2 16 48 │1 2 12 48 │
├────────────┼───────────┼───────────┼──────────────┼──────────────┼───────────┼─────────────┼──────────────┤
│1 2 12 24 48│1 2 8 48 │1 2 8 24 48│1 2 8 16 48 │1 2 6 48 │1 2 6 24 48│1 2 6 12 48 │1 2 6 12 24 48│
├────────────┼───────────┼───────────┼──────────────┼──────────────┼───────────┼─────────────┼──────────────┤
│1 2 4 48 │1 2 4 24 48│1 2 4 16 48│1 2 4 12 48 │1 2 4 12 24 48│1 2 4 8 48 │1 2 4 8 24 48│1 2 4 8 16 48 │
└────────────┴───────────┴───────────┴──────────────┴──────────────┴───────────┴─────────────┴──────────────┘
_8,\fp2 48
┌───────┬───────┬───────┬─────────┬─────────┬───────┬─────────┬─────────┐
│48 │24 2 │16 3 │12 4 │12 2 2 │8 6 │8 3 2 │8 2 3 │
├───────┼───────┼───────┼─────────┼─────────┼───────┼─────────┼─────────┤
│6 8 │6 4 2 │6 2 4 │6 2 2 2 │4 12 │4 6 2 │4 4 3 │4 3 4 │
├───────┼───────┼───────┼─────────┼─────────┼───────┼─────────┼─────────┤
│4 3 2 2│4 2 6 │4 2 3 2│4 2 2 3 │3 16 │3 8 2 │3 4 4 │3 4 2 2 │
├───────┼───────┼───────┼─────────┼─────────┼───────┼─────────┼─────────┤
│3 2 8 │3 2 4 2│3 2 2 4│3 2 2 2 2│2 24 │2 12 2 │2 8 3 │2 6 4 │
├───────┼───────┼───────┼─────────┼─────────┼───────┼─────────┼─────────┤
│2 6 2 2│2 4 6 │2 4 3 2│2 4 2 3 │2 3 8 │2 3 4 2│2 3 2 4 │2 3 2 2 2│
├───────┼───────┼───────┼─────────┼─────────┼───────┼─────────┼─────────┤
│2 2 12 │2 2 6 2│2 2 4 3│2 2 3 4 │2 2 3 2 2│2 2 2 6│2 2 2 3 2│2 2 2 2 3│
└───────┴───────┴───────┴─────────┴─────────┴───────┴─────────┴─────────┘
(#~ (=*>.F)) i.30000
0 1 48 1280 2496 28672 29808
jq
Adapted from Wren
Also works with gojq, the Go implementation of jq provided a definition of _nwise is provided.
# unordered
def proper_divisors:
. as $n
| if $n > 1 then 1,
( range(2; 1 + (sqrt|floor)) as $i
| if ($n % $i) == 0 then $i,
(($n / $i) | if . == $i then empty else . end)
else empty
end)
else empty
end;
# Uses the first definition and recursion to generate the sequences.
def moreMultiples($toSeq; $fromSeq):
reduce $fromSeq[] as $i ({oneMores: []};
if ($i > $toSeq[-1]) and ($i % $toSeq[-1]) == 0
then .oneMores += [$toSeq + [$i]]
else .
end)
| reduce range(0; .oneMores|length) as $i (.;
.oneMores += moreMultiples(.oneMores[$i]; $fromSeq) )
| .oneMores ;
# Input: {cache, ...}
# Output: {cache, count, ... }
def erdosFactorCount($n):
def properDivisors: proper_divisors | select(. != 1);
# Since this is a recursive function, the local and global states
# must be managed separately:
(reduce ($n|properDivisors) as $d ([0, .]; # count, global
($n/$d) as $t
| ($t|tostring) as $ts
| if .[1].cache|has($ts) then . else .[1].cache[$ts] = (.[1]|erdosFactorCount($t).count) end
| .[0] += (.[1].cache[$ts])
)) as $update
| .count = $update[0] + 1
| .cache = ($update[1].cache) ;
def task1:
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def neatly: _nwise(4) | map(tostring|lpad(20)) | join(" ");
moreMultiples([1]; [48|proper_divisors])
| sort
| map(. + [48]) + [[1, 48]]
| "\(length) sequences using first definition:", neatly,
(. as $listing
| reduce range(0; $listing|length) as $i ([];
$listing[$i] as $seq
| (if ($seq[-1] != 48) then $seq + [48] else $seq end) as $seq
| . + [[ range(1; $seq|length) as $i | ($seq[$i]/$seq[$i-1]) | floor ]] )
| "\n\(length) sequences using second definition:", neatly );
# Stream the values of A163272:
def A163272:
0,1,
({n:4}
| while(true;
.emit=null
| erdosFactorCount(.n) # update the cache
| if .count == .n then .emit =.n else . end
| .n += 4 )
| select(.emit).emit);
task1,
"",
"OEIS A163272:", limit(7; A163272)
- Output:
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
Julia
Revised to reflect a faster counting method (see second paper in the references).
using Primes
using Memoize
""" Return the factors of n, including 1, n """
function factors(n::T)::Vector{T} where T <: Integer
sort(vec(map(prod, Iterators.product((p.^(0:m) for (p, m) in eachfactor(n))...))))
end
""" Uses the first definition and recursion to generate the sequences """
function more_multiples(to_seq, from_seq)
onemores = [[to_seq; i] for i in from_seq if i > to_seq[end] && i % to_seq[end] == 0]
isempty(onemores) && return Int[]
return append!(onemores, mapreduce(seq -> more_multiples(seq, from_seq), append!, onemores))
end
""" See reference paper by Erdos, page 1 """
@memoize function kfactors(n)
a = factors(n)
return sum(kfactors(n ÷ d) for d in a[begin+1:end]) + 1
end
listing = sort!(push!(map(a -> push!(a, 48), more_multiples([1], factors(48)[begin+1:end-1])), [1, 48]))
println("48 sequences using first definition:")
for (i, seq) in enumerate(listing)
print(rpad(seq, 22), i % 4 == 0 ? "\n" : "")
end
println("\n48 sequences using second definition:")
for (i, seq) in enumerate(listing)
seq2 = [seq[j] ÷ seq[j - 1] for j in 2:length(seq)]
print(rpad(seq2, 20), i % 4 == 0 ? "\n" : "")
end
println("\nOEIS A163272: ")
for n in 0:2_400_000
if n == 0 || kfactors(n) == n
print(n, ", ")
end
end
- Output:
48 sequences using first definition: [1, 2, 4, 8, 16, 48] [1, 2, 4, 8, 24, 48] [1, 2, 4, 8, 48] [1, 2, 4, 12, 24, 48] [1, 2, 4, 12, 48] [1, 2, 4, 16, 48] [1, 2, 4, 24, 48] [1, 2, 4, 48] [1, 2, 6, 12, 24, 48] [1, 2, 6, 12, 48] [1, 2, 6, 24, 48] [1, 2, 6, 48] [1, 2, 8, 16, 48] [1, 2, 8, 24, 48] [1, 2, 8, 48] [1, 2, 12, 24, 48] [1, 2, 12, 48] [1, 2, 16, 48] [1, 2, 24, 48] [1, 2, 48] [1, 3, 6, 12, 24, 48] [1, 3, 6, 12, 48] [1, 3, 6, 24, 48] [1, 3, 6, 48] [1, 3, 12, 24, 48] [1, 3, 12, 48] [1, 3, 24, 48] [1, 3, 48] [1, 4, 8, 16, 48] [1, 4, 8, 24, 48] [1, 4, 8, 48] [1, 4, 12, 24, 48] [1, 4, 12, 48] [1, 4, 16, 48] [1, 4, 24, 48] [1, 4, 48] [1, 6, 12, 24, 48] [1, 6, 12, 48] [1, 6, 24, 48] [1, 6, 48] [1, 8, 16, 48] [1, 8, 24, 48] [1, 8, 48] [1, 12, 24, 48] [1, 12, 48] [1, 16, 48] [1, 24, 48] [1, 48] 48 sequences using second definition: [2, 2, 2, 2, 3] [2, 2, 2, 3, 2] [2, 2, 2, 6] [2, 2, 3, 2, 2] [2, 2, 3, 4] [2, 2, 4, 3] [2, 2, 6, 2] [2, 2, 12] [2, 3, 2, 2, 2] [2, 3, 2, 4] [2, 3, 4, 2] [2, 3, 8] [2, 4, 2, 3] [2, 4, 3, 2] [2, 4, 6] [2, 6, 2, 2] [2, 6, 4] [2, 8, 3] [2, 12, 2] [2, 24] [3, 2, 2, 2, 2] [3, 2, 2, 4] [3, 2, 4, 2] [3, 2, 8] [3, 4, 2, 2] [3, 4, 4] [3, 8, 2] [3, 16] [4, 2, 2, 3] [4, 2, 3, 2] [4, 2, 6] [4, 3, 2, 2] [4, 3, 4] [4, 4, 3] [4, 6, 2] [4, 12] [6, 2, 2, 2] [6, 2, 4] [6, 4, 2] [6, 8] [8, 2, 3] [8, 3, 2] [8, 6] [12, 2, 2] [12, 4] [16, 3] [24, 2] [48] OEIS A163272: 0, 1, 48, 1280, 2496, 28672, 29808, 454656, 2342912,
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(", ")
- Output:
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
Perl
use v5.36;
sub table (@V) { my $t = 3 * (my $w = 2 + 20); ( sprintf( ('%-'.$w.'s')x@V, @V) ) =~ s/.{1,$t}\K/\n/gr }
sub proper_divisors ($x) {
my @l;
@l = 1 if $x > 1;
for my $d (2 .. int sqrt $x) {
if (0 == $x % $d) { push @l, $d; my $y = int($x/$d); push @l, $y if $y != $d }
}
@l
}
sub erdosFactorCount ($n) {
my @foo = proper_divisors($n); shift @foo;
state %cache;
my ($sum,@divs) = (0, @foo); #(proper_divisors $n)[1..*]);
for my $d (@divs) {
my $t = int($n/$d);
$cache{$t} = erdosFactorCount($t) unless $cache{$t};
$sum += $cache{$t}
}
++$sum
}
sub moreMultiples ($to, $from) {
my @oneMores;
for my $j (@$from) {
push @oneMores, [@$to, $j] if $j > $$to[-1] && 0 == $j % $$to[-1]
}
return unless @oneMores;
for (0 .. $#oneMores) {
push @oneMores, moreMultiples($oneMores[$_], $from);
}
@oneMores
}
my @listing = [1];
push @listing, moreMultiples [1], [proper_divisors(48)];
map { push @$_, 48 } @listing;
my @lists; map { push @lists, join ' ', @$_ } @listing;
say @listing . " sequences using first definition:\n" . table(@lists);
my @listing2;
for my $j (0.. $#listing) {
my @seq = @{$listing[$j]};
push @seq, 48 if $seq[-1] != 48;
push @listing2, join ' ', map { int $seq[$_] / $seq[$_-1] } 1 .. $#seq;
}
say @listing2 . " sequences using second definition:\n" . table(@listing2);
my($n,@fpns) = (4, 0,1);
while ($#fpns < 6) { push(@fpns, $n) if erdosFactorCount($n) == $n; $n += 4 }
say "OEIS A163272: @fpns";
- Output:
48 sequences using first definition: 1 48 1 2 48 1 24 48 1 3 48 1 16 48 1 4 48 1 12 48 1 6 48 1 8 48 1 2 24 48 1 2 16 48 1 2 4 48 1 2 12 48 1 2 6 48 1 2 8 48 1 2 4 24 48 1 2 4 16 48 1 2 4 12 48 1 2 4 8 48 1 2 4 12 24 48 1 2 4 8 24 48 1 2 4 8 16 48 1 2 12 24 48 1 2 6 24 48 1 2 6 12 48 1 2 6 12 24 48 1 2 8 24 48 1 2 8 16 48 1 3 24 48 1 3 12 48 1 3 6 48 1 3 12 24 48 1 3 6 24 48 1 3 6 12 48 1 3 6 12 24 48 1 4 24 48 1 4 16 48 1 4 12 48 1 4 8 48 1 4 12 24 48 1 4 8 24 48 1 4 8 16 48 1 12 24 48 1 6 24 48 1 6 12 48 1 6 12 24 48 1 8 24 48 1 8 16 48 48 sequences using second definition: 48 2 24 24 2 3 16 16 3 4 12 12 4 6 8 8 6 2 12 2 2 8 3 2 2 12 2 6 4 2 3 8 2 4 6 2 2 6 2 2 2 4 3 2 2 3 4 2 2 2 6 2 2 3 2 2 2 2 2 3 2 2 2 2 2 3 2 6 2 2 2 3 4 2 2 3 2 4 2 3 2 2 2 2 4 3 2 2 4 2 3 3 8 2 3 4 4 3 2 8 3 4 2 2 3 2 4 2 3 2 2 4 3 2 2 2 2 4 6 2 4 4 3 4 3 4 4 2 6 4 3 2 2 4 2 3 2 4 2 2 3 12 2 2 6 4 2 6 2 4 6 2 2 2 8 3 2 8 2 3 OEIS A163272: 0 1 48 1280 2496 28672 29808
Phix
You can run this online here (expect a blank screen for ~30s).
-- -- demo/rosetta/factor-perfect_numbers.exw -- with javascript_semantics function get_factor_set(integer x) if x=1 then return {1} end if sequence res = {} for k=1 to x-1 do if remainder(x,k)=0 then for y in get_factor_set(k) do res = append(res,y&x) end for end if end for res = sort(res) return res end function function m(sequence s, integer f) sequence res = {} for x in s do x = deep_copy(x) if x[$]!=f then x &= f end if for i=length(x) to 2 by -1 do x[i] /= x[i-1] end for res = append(res,x[2..$]) end for return res end function constant N = 48 sequence rN = get_factor_set(N) function jbm(bool munge) if munge then rN = m(rN,N) end if return {length(rN),join_by(apply(rN,ppf),1,4," ",fmt:="%-16s")} end function ppOpt({pp_IntCh,false,pp_StrFmt,3}) printf(1,"%d sequences using first definition:\n%s\n",jbm(false)) printf(1,"%d sequences using second definition:\n%s\n",jbm(true)) integer efc_cache = new_dict() function erdosFactorCount(integer n) sequence divs = factors(n) integer res = 1 for d in divs do integer t = n/d, r, node = getd_index(t,efc_cache) if node=NULL then r = erdosFactorCount(t) setd(t,r,efc_cache) else r = getd_by_index(node,efc_cache) end if res += r end for return res end function atom t = time(), t1 = t+1 integer n = 4 sequence res = {"0","1"} while length(res)<iff(platform()=JS?8:9) do if erdosFactorCount(n)=n then res = append(res,sprintf("%d",n)) end if n += 4 if time()>t1 then progress("%d found, checking %d...\r",{length(res),n}) t1 = time()+1 end if end while progress("") printf(1,"Found %d: %s (%s)\n",{length(res),join(res," "),elapsed(time()-t)}) wait_key()
- Output:
48 sequences using first definition: {1,2,4,8,16,48} {1,2,4,8,24,48} {1,2,4,8,48} {1,2,4,12,24,48} {1,2,4,12,48} {1,2,4,16,48} {1,2,4,24,48} {1,2,4,48} {1,2,6,12,24,48} {1,2,6,12,48} {1,2,6,24,48} {1,2,6,48} {1,2,8,16,48} {1,2,8,24,48} {1,2,8,48} {1,2,12,24,48} {1,2,12,48} {1,2,16,48} {1,2,24,48} {1,2,48} {1,3,6,12,24,48} {1,3,6,12,48} {1,3,6,24,48} {1,3,6,48} {1,3,12,24,48} {1,3,12,48} {1,3,24,48} {1,3,48} {1,4,8,16,48} {1,4,8,24,48} {1,4,8,48} {1,4,12,24,48} {1,4,12,48} {1,4,16,48} {1,4,24,48} {1,4,48} {1,6,12,24,48} {1,6,12,48} {1,6,24,48} {1,6,48} {1,8,16,48} {1,8,24,48} {1,8,48} {1,12,24,48} {1,12,48} {1,16,48} {1,24,48} {1,48} 48 sequences using second definition: {2,2,2,2,3} {2,2,2,3,2} {2,2,2,6} {2,2,3,2,2} {2,2,3,4} {2,2,4,3} {2,2,6,2} {2,2,12} {2,3,2,2,2} {2,3,2,4} {2,3,4,2} {2,3,8} {2,4,2,3} {2,4,3,2} {2,4,6} {2,6,2,2} {2,6,4} {2,8,3} {2,12,2} {2,24} {3,2,2,2,2} {3,2,2,4} {3,2,4,2} {3,2,8} {3,4,2,2} {3,4,4} {3,8,2} {3,16} {4,2,2,3} {4,2,3,2} {4,2,6} {4,3,2,2} {4,3,4} {4,4,3} {4,6,2} {4,12} {6,2,2,2} {6,2,4} {6,4,2} {6,8} {8,2,3} {8,3,2} {8,6} {12,2,2} {12,4} {16,3} {24,2} {48} Found 9: 0 1 48 1280 2496 28672 29808 454656 2342912 (1 minute and 9s)
Unfortunately it takes 4 minutes 13 seconds to find 9 under p2js, so I've limited that to 8 (as mentioned above, ~30s)
Python
''' Rosetta Code task Factor-perfect_numbers '''
from functools import cache
from sympy import divisors
def more_multiples(to_seq, from_seq):
''' Uses the first definition and recursion to generate the sequences '''
onemores = [to_seq + [i]
for i in from_seq if i > to_seq[-1] and i % to_seq[-1] == 0]
if len(onemores) == 0:
return []
for i in range(len(onemores)):
for arr in more_multiples(onemores[i], from_seq):
onemores.append(arr)
return onemores
listing = [a + [48]
for a in sorted(more_multiples([1], divisors(48)[1:-1]))] + [[1, 48]]
print('48 sequences using first definition:')
for j, seq in enumerate(listing):
print(f'{str(seq):22}', end='\n' if (j + 1) % 4 == 0 else '')
# Derive second definition's sequences
print('\n48 sequences using second definition:')
for k, seq in enumerate(listing):
seq2 = [seq[i] // seq[i - 1] for i in range(1, len(seq))]
print(f'{str(seq2):20}', end='\n' if (k + 1) % 4 == 0 else '')
@cache
def erdos_factor_count(number):
''' 'Erdos method '''
return sum(erdos_factor_count(number // d) for d in divisors(number)[1:-1]) + 1
print("\nOEIS A163272: ", end='')
for num in range(2_400_000):
if num == 0 or erdos_factor_count(num) == num:
print(num, end=', ')
- Output:
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,
Raku
# 20221029 Raku programming solution
sub propdiv (\x) {
my @l = 1 if x > 1;
for (2 .. x.sqrt.floor) -> \d {
unless x % d { @l.push: d; my \y = x div d; @l.push: y if y != d }
}
@l
}
sub moreMultiples (@toSeq, @fromSeq) {
my @oneMores = gather for @fromSeq -> \j {
take @toSeq.clone.push(j) if j > @toSeq[*-1] and j %% @toSeq[*-1]
}
return () unless @oneMores.Bool;
for 0..^@oneMores {
@oneMores.append: moreMultiples @oneMores[$_], @fromSeq
}
@oneMores
}
sub erdosFactorCount (\n) {
state %cache;
my ($sum,@divs) = 0, |(propdiv n)[1..*];
for @divs -> \d {
unless %cache{my \t = n div d}:exists { %cache{t} = erdosFactorCount(t) }
$sum += %cache{t}
}
++$sum
}
my @listing = moreMultiples [1], propdiv(48);
given @listing { $_.map: *.push: 48; $_.push: [1,48] }
say @listing.elems," sequences using first definition:";
for @listing.rotor(4) -> \line { line.map: { printf "%-20s", $_ } ; say() }
my @listing2 = gather for (0..^+@listing) -> \j {
my @seq = |@listing[j];
@seq.append: 48 if @seq[*-1] != 48;
take (1..^@seq).map: { @seq[$_] div @seq[$_-1] }
}
say "\n{@listing2.elems} sequences using second definition:";
for @listing2.rotor(4) -> \line { line.map: { printf "%-20s", $_ } ; say() }
say "\nOEIS A163272:";
my ($n,@fpns) = 4, 0,1;
while (@fpns < 7) { @fpns.push($n) if erdosFactorCount($n) == $n; $n += 4 }
say ~@fpns;
- Output:
48 sequences using first definition: 1 2 48 1 24 48 1 3 48 1 16 48 1 4 48 1 12 48 1 6 48 1 8 48 1 2 24 48 1 2 16 48 1 2 4 48 1 2 12 48 1 2 6 48 1 2 8 48 1 2 4 24 48 1 2 4 16 48 1 2 4 12 48 1 2 4 8 48 1 2 4 12 24 48 1 2 4 8 24 48 1 2 4 8 16 48 1 2 12 24 48 1 2 6 24 48 1 2 6 12 48 1 2 6 12 24 48 1 2 8 24 48 1 2 8 16 48 1 3 24 48 1 3 12 48 1 3 6 48 1 3 12 24 48 1 3 6 24 48 1 3 6 12 48 1 3 6 12 24 48 1 4 24 48 1 4 16 48 1 4 12 48 1 4 8 48 1 4 12 24 48 1 4 8 24 48 1 4 8 16 48 1 12 24 48 1 6 24 48 1 6 12 48 1 6 12 24 48 1 8 24 48 1 8 16 48 1 48 48 sequences using second definition: 2 24 24 2 3 16 16 3 4 12 12 4 6 8 8 6 2 12 2 2 8 3 2 2 12 2 6 4 2 3 8 2 4 6 2 2 6 2 2 2 4 3 2 2 3 4 2 2 2 6 2 2 3 2 2 2 2 2 3 2 2 2 2 2 3 2 6 2 2 2 3 4 2 2 3 2 4 2 3 2 2 2 2 4 3 2 2 4 2 3 3 8 2 3 4 4 3 2 8 3 4 2 2 3 2 4 2 3 2 2 4 3 2 2 2 2 4 6 2 4 4 3 4 3 4 4 2 6 4 3 2 2 4 2 3 2 4 2 2 3 12 2 2 6 4 2 6 2 4 6 2 2 2 8 3 2 8 2 3 48 OEIS A163272: 0 1 48 1280 2496 28672 29808
Sidef
func erdosFactorCount (n) is cached {
var sum = 1
var divs = proper_divisors(n).slice(1)
divs.each {|d|
sum += __FUNC__(idiv(n,d))
}
return sum
}
func moreMultiples (to, from) {
var oneMores = []
from.each {|j|
if (j > to.tail && to.tail.divides(j)) {
oneMores << [to..., j]
}
}
for k in (oneMores.range) {
oneMores << __FUNC__(oneMores[k], from)...
}
return oneMores
}
var listing = [[1]]
listing << moreMultiples([1], proper_divisors(48))...
listing.each {|a| a << 48 }
say "#{listing.len} sequences using first definition:"
listing.slices(3).each { .map { .join(' ') }.map{ '%-20s' % _ }.join.say }
var listing2 = gather {
for j in (^listing.len) {
var seq = listing[j]
take(1..seq.end -> map {|j| seq[j] / seq[j-1] })
}
}
say "\n#{listing2.len} sequences using second definition:"
listing2.slices(3).each { .map { .join(' ') }.map{ '%-20s' % _ }.join.say }
print "\nOEIS A163272: "
say [0, 1, (1..Inf -> lazy.map {|n| 4*n }.grep{|n| erdosFactorCount(n) == n }.first(5))...]
- Output:
48 sequences using first definition: 1 48 1 2 48 1 3 48 1 4 48 1 6 48 1 8 48 1 12 48 1 16 48 1 24 48 1 2 4 48 1 2 6 48 1 2 8 48 1 2 12 48 1 2 16 48 1 2 24 48 1 2 4 8 48 1 2 4 12 48 1 2 4 16 48 1 2 4 24 48 1 2 4 8 16 48 1 2 4 8 24 48 1 2 4 12 24 48 1 2 6 12 48 1 2 6 24 48 1 2 6 12 24 48 1 2 8 16 48 1 2 8 24 48 1 2 12 24 48 1 3 6 48 1 3 12 48 1 3 24 48 1 3 6 12 48 1 3 6 24 48 1 3 6 12 24 48 1 3 12 24 48 1 4 8 48 1 4 12 48 1 4 16 48 1 4 24 48 1 4 8 16 48 1 4 8 24 48 1 4 12 24 48 1 6 12 48 1 6 24 48 1 6 12 24 48 1 8 16 48 1 8 24 48 1 12 24 48 48 sequences using second definition: 48 2 24 3 16 4 12 6 8 8 6 12 4 16 3 24 2 2 2 12 2 3 8 2 4 6 2 6 4 2 8 3 2 12 2 2 2 2 6 2 2 3 4 2 2 4 3 2 2 6 2 2 2 2 2 3 2 2 2 3 2 2 2 3 2 2 2 3 2 4 2 3 4 2 2 3 2 2 2 2 4 2 3 2 4 3 2 2 6 2 2 3 2 8 3 4 4 3 8 2 3 2 2 4 3 2 4 2 3 2 2 2 2 3 4 2 2 4 2 6 4 3 4 4 4 3 4 6 2 4 2 2 3 4 2 3 2 4 3 2 2 6 2 4 6 4 2 6 2 2 2 8 2 3 8 3 2 12 2 2 OEIS A163272: [0, 1, 48, 1280, 2496, 28672, 29808]
Wren
Timings are about: 0.19 secs for 7, 8.5 secs for 8 and 97 secs for 9 factor-perfect numbers.
import "./math" for Int, Nums
import "./fmt" for Fmt
// Uses the first definition and recursion to generate the sequences.
var moreMultiples
moreMultiples = Fn.new { |toSeq, fromSeq|
var oneMores = []
for (i in fromSeq) {
if (i > toSeq[-1] && i%toSeq[-1] == 0) oneMores.add(toSeq + [i])
}
if (oneMores.isEmpty) return []
for (i in 0...oneMores.count) {
oneMores.addAll(moreMultiples.call(oneMores[i], fromSeq))
}
return oneMores
}
var cache = {}
var erdosFactorCount
erdosFactorCount = Fn.new { |n|
var divs = Int.properDivisors(n)
divs.removeAt(0)
var sum = 0
for (d in divs) {
var t = (n/d).floor
if (!cache.containsKey(t)) cache[t] = erdosFactorCount.call(t)
sum = sum + cache[t]
}
return sum + 1
}
var listing = moreMultiples.call([1], Int.properDivisors(48))
listing.sort { |l1, l2|
var c1 = l1.count
var c2 = l2.count
for (i in 1...c1.min(c2)) {
if (l1[i] < l2[i]) return true
if (l1[i] > l2[i]) return false
}
if (c1 < c2) return true
return false
}
listing.each { |l| l.add(48) }
listing.add([1, 48])
System.print("%(listing.count) sequences using first definition:")
Fmt.tprint("$-21n", listing, 4)
System.print("\n%(listing.count) sequences using second definition:")
var listing2 = []
for (i in 0...listing.count) {
var seq = listing[i]
if (seq[-1] != 48) seq.add(48)
var seq2 = (1...seq.count).map { |i| (seq[i]/seq[i-1]).floor }.toList
listing2.add(seq2)
}
Fmt.tprint("$-17n", listing2, 4)
System.print("\nOEIS A163272:")
var n = 4
var fpns = [0, 1]
while (fpns.count < 9) {
if (erdosFactorCount.call(n) == n) fpns.add(n)
n = n + 4
}
System.print(fpns)
- Output:
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]