Erdős-Nicolas numbers
An Erdős–Nicolas number is a positive integer which is not perfect but is equal to the sum of its first k divisors (arranged in ascending order and including one) for some value of k greater than one.
- Definition
- Examples
24 is an Erdős–Nicolas number because the sum of its first 6 divisors (1, 2, 3, 4, 6 and 8) is equal to 24 and it is not perfect because 12 is also a divisor.
6 is not an Erdős–Nicolas number because it is perfect (1 + 2 + 3 = 6).
48 is not an Erdős–Nicolas number because its divisors are: 1, 2, 3, 4, 6, 8, 12, 16, 24 and 48. The first seven of these add up to 36, but the first eight add up to 52 which is more than 48.
- Task
Find and show here the first 8 Erdős–Nicolas numbers and the number of divisors needed (i.e. the value of 'k') to satisfy the definition.
- Stretch
Do the same for any further Erdős–Nicolas numbers which you have the patience for.
- Note
As all known Erdős–Nicolas numbers are even you may assume this to be generally true in order to quicken up the search. However, it is not obvious (to me at least) why this should necessarily be the case.
- Reference
J
Implementation:<lang J>divisors=: {{ /:~ ,*/@> { (^ i.@>:)&.>/__ q: y}} ::_: erdosnicolas=: {{ y e. +/\ _2}. divisors y }}"0</lang>Task example:<lang J> I.erdosnicolas i.1e7 24 2016 8190 42336 45864 392448 714240 1571328
(,. 1++/\@divisors i. ])@>24 2016 8190 42336 45864 392448 714240 1571328 24 6 2016 31 8190 43 42336 66 45864 66 392448 68 714240 113
1571328 115</lang>
Template:Header!Julia
<lang ruby>using Primes
function isErdősNicolas_with_k(n)
@assert n > 2 d = [one(n)] for (p, e) in eachfactor(n) d = reduce(vcat, [d * p^j for j in 1:e], init=d) end sort!(d) pop!(d) len = length(d) (len < 2 || sum(d) == n) && return false, 0 for k in 2:len sum(@view d[1:k]) == n && return true, k end return false, 0
end
for n in 3:2_000_000
isEN, k = isErdősNicolas_with_i(n) isEN && println(lpad(n, 8), " equals the sum of its first $k divisors.")
end
</lang>
- Output:
24 equals the sum of its first 6 divisors. 2016 equals the sum of its first 31 divisors. 8190 equals the sum of its first 43 divisors. 42336 equals the sum of its first 66 divisors. 45864 equals the sum of its first 66 divisors. 392448 equals the sum of its first 68 divisors. 714240 equals the sum of its first 113 divisors. 1571328 equals the sum of its first 115 divisors.
Phix
with javascript_semantics function erdos_nicolas(integer n) -- (The default for factors() is no 1 nor n, -- though you can change that if you want, -- ie ",1" -> 1 and n; ",-1" -> 1 but not n.) sequence divisors = factors(n) integer tot = 1 for i=1 to length(divisors)-1 do tot += divisors[i] if tot=n then return i+1 end if if tot>n then exit end if end for return 0 end function constant limit = 8 integer n = 2, count = 0 while count<limit do integer k = erdos_nicolas(n) if k>0 then printf(1,"%d from %d\n",{n,k}) count += 1 end if n += 2 end while
Output same as Wren
Raku
<lang perl6>use Prime::Factor;
sub is-Erdős-Nicolas ($n) {
my @divisors = $n.&proper-divisors: :s; ((@divisors.sum > $n) && (my $key = ([\+] @divisors).first: $n, :k)) ?? 1 + $key !! False
}
my $count;
(1..*).hyper(:2000batch).map( * × 2 ).map: {
if my $key = .&is-Erdős-Nicolas { printf "%8d\ == sum of its first %3d divisors\n", $_, $key; exit if ++$count >= 8; }
}</lang>
- Output:
24 == sum of its first 6 divisors 2016 == sum of its first 31 divisors 8190 == sum of its first 43 divisors 42336 == sum of its first 66 divisors 45864 == sum of its first 66 divisors 392448 == sum of its first 68 divisors 714240 == sum of its first 113 divisors 1571328 == sum of its first 115 divisors
Wren
<lang ecmascript>import "./math" for Int
var erdosNicolas = Fn.new { |n|
var divisors = Int.properDivisors(n) // excludes n itself var dc = divisors.count if (dc < 3) return 0 var sum = divisors[0] + divisors[1] for (i in 2...dc-1) { sum = sum + divisors[i] if (sum == n) return i + 1 if (sum > n) break } return 0
}
var limit = 8 var n = 2 var count = 0 while (true) {
var k = erdosNicolas.call(n) if (k > 0) { System.print("%(n) from %(k)") count = count + 1 if (count == limit) return } n = n + 2
}</lang>
- Output:
24 from 6 2016 from 31 8190 from 43 42336 from 66 45864 from 66 392448 from 68 714240 from 113 1571328 from 115