Erdős-Nicolas numbers

Erdős-Nicolas numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Definition

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.

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

• OEIS:A194472 - Erdős–Nicolas numbers

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

J

Implementation:

divisors=: {{ /:~ ,*/@> { (^ i.@>:)&.>/__ q: y}} ::_:
erdosnicolas=: {{ y e. +/\ _2}. divisors y }}"0

Task example:

   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.

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

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