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.

Erdős-Nicolas numbers
You are encouraged to solve this task according to the task description, using any language you may know.
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.

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

ALGOL 68

Builds tables of proper divisor counts and sums and finds the numbers whilst doing it. This means that the numbers are not found in numerical order.

```BEGIN # find some Erdos-Nicolas numbers: numbers equal to the sum of their    #
# first k proper divisors but k is not the count of all their proper    #
# divisors ( so the numbers aren't perfect )                            #
INT max number  = 2 000 000;      # largest number we will consider       #
# construct tables of the divisor counts and divisor sums and check for   #
# the numbers as we do it - note they will not necessarily be found in    #
#                                order                                    #
[ 1 : max number ]INT dsum;   FOR i TO UPB dsum   DO dsum[   i ] := 1 OD;
[ 1 : max number ]INT dcount; FOR i TO UPB dcount DO dcount[ i ] := 1 OD;
FOR i FROM 2 TO UPB dsum
DO FOR j FROM i + i BY i TO UPB dsum DO
# have another proper divisor                                     #
IF dsum[ j ] = j THEN
# the divisor sum is currently equal to the number but is     #
# about to increase, so we have an Erdos-Nicolas number       #
print( ( whole( j, -10 ), " equals the sum of its first "
, whole( dcount[ j ], 0 ), " divisors"
, newline
)
)
FI;
dsum[   j ] +:= i;
dcount[ j ] +:= 1
OD
OD
END```
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
714240 equals the sum of its first 113 divisors
392448 equals the sum of its first 68 divisors
1571328 equals the sum of its first 115 divisors
```

With max number set to 200 000 000, another two numbers can be found. Note that that would probably be too large for ALGOL 68G under Windows, so another compiler would need to be used:

```        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
714240 equals the sum of its first 113 divisors
392448 equals the sum of its first 68 divisors
1571328 equals the sum of its first 115 divisors
61900800 equals the sum of its first 280 divisors
91963648 equals the sum of its first 142 divisors
```

Arturo

```erdosNicolas: function [n][
facts: factors n
if facts > 2 [
loop 1..(size facts)-2 'k [
if n = sum first.n:k facts -> return @[n, k]
]
]

return ø
]

cnt: 0
i: 2
while [cnt < 8][
if enNum: <= erdosNicolas i [
print[enNum\0 "equals the sum of its first" enNum\1 "divisors"]
cnt: cnt + 1
]
i: i + 2
]```
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```

BASIC

Rosetta Code problem: https://rosettacode.org/wiki/Erdős-Nicolas_numbers

by Jjuanhdez, 02/2023

BASIC256

Translation of: FreeBASIC
```limite = 400000
dim DSum(limite+1) fill 1
dim DCount(limite+1) fill 1

for i = 2 to limite
j = i + i
while j <= limite
if DSum[j] = j then
print rjust(j,8); " equals the sum of its first "; rjust(DCount[j],3); " divisors"
end if
DSum[j] += i
DCount[j] += 1
j += i
end while
next i
```
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```

FreeBASIC

```Dim As Uinteger limite = 2e6
Dim As Uinteger DSum(limite+1), DCount(limite+1)
Dim As Integer i, j

For i = 0 To limite
DSum(i) = 1
DCount(i) = 1
Next i

For i = 2 To limite
j = i + i
While j <= limite
If DSum(j) = j Then
Print Using "######## equals the sum of its first ### divisors"; j; DCount(j)
End If
DSum(j) += i
DCount(j) += 1
j += i
Wend
Next i
```
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
714240 equals the sum of its first 113 divisors
392448 equals the sum of its first  68 divisors
1571328 equals the sum of its first 115 divisors```

QBasic

Works with: QBasic version 1.1
Works with: QuickBasic version 4.5
```limite = 50000
DIM DSum(limite + 1), DCount(limite + 1)

FOR i = 0 TO limite
DSum(i) = 1
DCount(i) = 1
NEXT i

FOR i = 2 TO limite
j = i + i
WHILE j <= limite
IF DSum(j) = j THEN
PRINT USING "######## equals the sum of its first ### divisors"; j; DCount(j)
END IF
DSum(j) = DSum(j) + i
DCount(j) = DCount(j) + 1
j = j + i
WEND
NEXT i
```

Run BASIC

Works with: Just BASIC
Works with: Liberty BASIC
```limite = 1000000-1
'Maximum array size is 1,000,001 elements
dim DSum(limite+1)
dim DCount(limite+1)

for i = 0 to limite
DSum(i) = 1
DCount(i) = 1
next i

for i = 2 to limite
j = i + i
while j <= limite
if DSum(j) = j then
print using("########", j); " equals the sum of its first"; using("###", DCount(j)); " divisors"
end if
DSum(j) = DSum(j) + i
DCount(j) = DCount(j) + 1
j = j + i
wend
next i```

PureBasic

Translation of: FreeBASIC
```OpenConsole()

limite.l = 2e6
Dim DSum.l(limite+1)
Dim DCount.l(limite+1)

For i.l = 0 To limite
DSum(i) = 1
DCount(i) = 1
Next i

For i = 2 To limite
j.l = i + i
While j <= limite
If DSum(j) = j
PrintN(RSet(Str(j), 8) + " equals the sum of its first " + RSet(Str(DCount(j)), 3) + " divisors")
EndIf
DSum(j) = DSum(j) + i
DCount(j) = DCount(j) + 1
j = j + i
Wend
Next i

PrintN(#CRLF\$ + "--- terminado, pulsa RETURN---"): Input()
CloseConsole()
```
Output:
`Same as FreeBASIC entry.`

Yabasic

```limite = 2e6
dim DSum(limite+1), DCount(limite+1)

for i = 0 to limite
DSum(i) = 1
DCount(i) = 1
next i

for i = 2 to limite
j = i + i
while j <= limite
if DSum(j) = j  print j using ("########"), " equals the sum of its first ", DCount(j) using ("###"), " divisors"
DSum(j) = DSum(j) + i
DCount(j) = DCount(j) + 1
j = j + i
wend
next i```
Output:
`Same as FreeBASIC entry.`

C++

Translation of: ALGOL 68
```#include <iomanip>
#include <iostream>
#include <vector>

int main() {
const int max_number = 100000000;
std::vector<int> dsum(max_number + 1, 1);
std::vector<int> dcount(max_number + 1, 1);
for (int i = 2; i <= max_number; ++i) {
for (int j = i + i; j <= max_number; j += i) {
if (dsum[j] == j) {
std::cout << std::setw(8) << j
<< " equals the sum of its first " << dcount[j]
<< " divisors\n";
}
dsum[j] += i;
++dcount[j];
}
}
}
```
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
714240 equals the sum of its first 113 divisors
392448 equals the sum of its first 68 divisors
1571328 equals the sum of its first 115 divisors
61900800 equals the sum of its first 280 divisors
91963648 equals the sum of its first 142 divisors
```

J

Implementation:
```divisors=: {{ /:~ ,*/@> { (^ i.@>:)&.>/__ q: y}} ::_:
erdosnicolas=: {{ y e. +/\ _2}. divisors y }}"0
```
```   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
```

Julia

```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_k(n)
isEN && println(lpad(n, 8), " equals the sum of its first \$k divisors.")
end
```
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.
```

Pascal

Free Pascal

```program ErdoesNumb;
//formerly program FacOfInt;
// gets factors of consecutive integers fast
// limited to 1.2e11
{\$IFDEF FPC}
{\$MODE DELPHI}  {\$OPTIMIZATION ON,ALL}  {\$COPERATORS ON}
{\$ENDIF}
{\$IFDEF WINDOWS}
{\$APPTYPE CONSOLE}
{\$ENDIF}
uses
sysutils
{\$IFDEF WINDOWS},Windows{\$ENDIF}
;
//######################################################################
//prime decomposition
const
//HCN(86) > 1.2E11 = 128,501,493,120     count of divs = 4096   7 3 1 1 1 1 1 1 1
HCN_DivCnt  = 4096;
type
tItem = Uint64;
tDivisors = array [0..HCN_DivCnt] of tItem;
tpDivisor = pUint64;

type
//the first number with 11 different prime factors =
//2*3*5*7*11*13*17*19*23*29*31 = 2E11
//56 byte
tprimeFac = packed record
pfSumOfDivs,
pfRemain  : Uint64;
pfDivCnt  : Uint32;
pfMaxIdx  : Uint32;
pfpotPrimIdx : array[0..9] of word;
pfpotMax  : array[0..11] of byte;
end;
tpPrimeFac = ^tprimeFac;
tPrimes = array[0..65535] of Uint32;

var
SmallPrimes: tPrimes;

procedure InitSmallPrimes;
//get primes. #0..65535.Sieving only odd numbers
const
MAXLIMIT = (821641-1) shr 1;
var
pr : array[0..MAXLIMIT] of byte;
p,j,d,flipflop :NativeUInt;
Begin
SmallPrimes[0] := 2;
fillchar(pr[0],SizeOf(pr),#0);
p := 0;
repeat
repeat
p +=1
until pr[p]= 0;
j := (p+1)*p*2;
if j>MAXLIMIT then
BREAK;
d := 2*p+1;
repeat
pr[j] := 1;
j += d;
until j>MAXLIMIT;
until false;

SmallPrimes[1] := 3;
SmallPrimes[2] := 5;
j := 3;
d := 7;
flipflop := (2+1)-1;//7+2*2,11+2*1,13,17,19,23
p := 3;
repeat
if pr[p] = 0 then
begin
SmallPrimes[j] := d;
inc(j);
end;
d += 2*flipflop;
p+=flipflop;
flipflop := 3-flipflop;
until (p > MAXLIMIT) OR (j>High(SmallPrimes));
end;

function smplPrimeDecomp(n:Uint64):tprimeFac;
var
pr,i,pot,fac,q :NativeUInt;
Begin
with result do
Begin
pfDivCnt := 1;
pfSumOfDivs := 1;
pfRemain := n;
pfMaxIdx := 0;
pfpotPrimIdx[0] := 1;
pfpotMax[0] := 0;

i := 0;
while i < High(SmallPrimes) do
begin
pr := SmallPrimes[i];
q := n DIV pr;
//if n < pr*pr
if pr > q then
BREAK;
if n = pr*q then
Begin
pfpotPrimIdx[pfMaxIdx] := i;
pot := 0;
fac := pr;
repeat
n := q;
q := n div pr;
pot+=1;
fac *= pr;
until n <> pr*q;
pfpotMax[pfMaxIdx] := pot;
pfDivCnt *= pot+1;
pfSumOfDivs *= (fac-1)DIV(pr-1);
inc(pfMaxIdx);
end;
inc(i);
end;
pfRemain := n;
if n > 1 then
Begin
pfDivCnt *= 2;
pfSumOfDivs *= n+1
end;
end;
end;

procedure InsertSort(pDiv:tpDivisor; Left, Right : NativeInt );
var
I, J: NativeInt;
Pivot : tItem;
begin
for i:= 1 + Left to Right do
begin
Pivot:= pDiv[i];
j:= i - 1;
while (j >= Left) and (pDiv[j] > Pivot) do
begin
pDiv[j+1]:=pDiv[j];
Dec(j);
end;
pDiv[j+1]:= pivot;
end;
end;

procedure GetDivisors(pD:tpPrimeFac;var Divs:tDivisors);
var
pDivs : tpDivisor;
pPot : UInt64;
i,len,j,l,p,k: Int32;
Begin
pDivs := @Divs[0];
pDivs[0] := 1;
len := 1;
l   := 1;
with pD^ do
Begin
For i := 0 to pfMaxIdx-1 do
begin
//Multiply every divisor before with the new primefactors
//and append them to the list
k := pfpotMax[i];
p := SmallPrimes[pfpotPrimIdx[i]];
pPot :=1;
repeat
pPot *= p;
For j := 0 to len-1 do
Begin
pDivs[l]:= pPot*pDivs[j];
inc(l);
end;
dec(k);
until k<=0;
len := l;
end;
p := pfRemain;
If p >1 then
begin
For j := 0 to len-1 do
Begin
pDivs[l]:= p*pDivs[j];
inc(l);
end;
len := l;
end;
end;
//Sort. Insertsort much faster than QuickSort in this special case
InsertSort(pDivs,0,len-1);
//end marker
pDivs[len] :=0;
end;

var
Mypd : tPrimeFac;
Divs:tDivisors;
pDivs : tpDivisor;
T0:Int64;
i: NativeInt;
n,s : NativeUInt;
Begin
InitSmallPrimes;
T0 := GetTickCount64;
n := 1;
pDivs := @Divs[0];
repeat
Mypd:= smplPrimeDecomp(n);
if Mypd.pfSumOfDivs>2*n then
begin
GetDivisors(@Mypd,Divs);
s := 1;
For i := 1 to Mypd.pfDivCnt-3 do
Begin
inc(s,pDivs[i]);
if s = n then
writeln(Format('%8d equals the sum of its first %4d divisors',
[n,i+1]));
if s>n then
break;
end;
end;
n += 1;
until n > 2*1000*1000+1;
T0 := GetTickCount64-T0;
writeln('runtime ',T0/1000:0:3,' s');
end.
```
@TIO.RUN:
```TIO.RUN
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
runtime 1.219 s
@home
...
1571328 equals the sum of its first  115 divisors
61900800 equals the sum of its first  280 divisors
91963648 equals the sum of its first  142 divisors
runtime 40.504 s```

Perl

Library: ntheory
```use v5.36;
use ntheory 'divisors';
use enum qw(False True);
use List::AllUtils <firstidx sum>;

sub proper_divisors (\$n) {
return 1 if \$n == 0;
my @d = divisors(\$n);
pop @d;
@d;
}

sub is_Erdos_Nicolas (\$n) {
my @divisors = proper_divisors(\$n);
return False unless sum(@divisors) > \$n;
my \$sum;
my \$key = firstidx { \$_ == \$n } map { \$sum += \$_ } @divisors;
\$key ? 1 + \$key : False;
}

my(\$n,\$count) = (2,0);
until (\$count == 8) {
next unless 0 == ++\$n % 2;
if (my \$key = is_Erdos_Nicolas \$n) {
printf "%8d == sum of its first %3d divisors\n", \$n, \$key;
\$count++
}
}
```
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```

Phix

Translation of: Wren
```with javascript_semantics
function erdos_nicolas(integer 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,"%8d equals the sum of its first %d divisors.\n",{n,k})
count += 1
end if
n += 2
end while
```

Aside: The default for factors() is to return neither 1 nor n, though you can change that if you want, ie ",1" -> 1 and n; ",-1" -> 1 but not n.
Output same as Julia

Raku

```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;
}
}
```
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```

Ring

```see "works..." + nl
erdos = []
limit = 1600000
for n = 1 to limit
num = 0
sum = 0
erdos = []
for m = 1 to n/2
if n%m = 0
ok
next
lenErdos = len(erdos)
for p = 1 to lenErdos
sum = sum + erdos[p]
if sum = n and p < lenErdos
num++
see "" + n + " equals the sum of its first " + p + " divisors" + nl
exit
ok
next
if num = 8
exit
ok
next
see "done..." + nl```
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
714240 equals the sum of its first 113 divisors
392448 equals the sum of its first 68 divisors
1571328 equals the sum of its first 115 divisors
```

Wren

Library: Wren-math
```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
}
```
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
```

XPL0

Translation of Algol 68 and C++.

```def Max = 2_000_000;
int DSum(Max+1), DCount(Max+1);
int I, J;
[for I:= 0 to Max do
[DSum(I):= 1;
DCount(I):= 1;
];
Format(8, 0);
for I:= 2 to Max do
[J:= I+I;
while J <= Max do
[if DSum(J) = J then
[RlOut(0, float(J));
Text(0, " equals the sum of its first ");
IntOut(0, DCount(J));
Text(0, " divisors^j^m");
];
DSum(J):= DSum(J)+I;
DCount(J):= DCount(J)+1;
J:= J+I;
]
]
]```
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
714240 equals the sum of its first 113 divisors
392448 equals the sum of its first 68 divisors
1571328 equals the sum of its first 115 divisors
```