Erdős-Nicolas numbers: Difference between revisions
Added Easylang
(Added Easylang) |
|||
| (15 intermediate revisions by 9 users not shown) | |||
Line 311:
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
</pre>
===slight improvement===
dsum and dcount are in "far" distance -> cache miss. Using an struct "typedef struct { int divsum, divcnt;} divs;" improves runtime to 32 s.
Calculating the count of divisors only at output saves 50% space and runtime too.
<syntaxhighlight lang=c>#include <stdio.h>
#include <stdlib.h>
void get_div_cnt(int n){
int lmt,f,divcnt,divsum;
divsum = 1;
divcnt = 1;
lmt = n/2;
f = 2;
for (;;) {
if (f > lmt ) break;
if (!(n % f)){
divsum +=f;
divcnt++;
}
if (divsum == n) break;
f++;
}
printf("%8d equals the sum of its first %d divisors\n", n, divcnt);
}
int main() {
const int maxNumber = 100*1000*1000;
int *dsum = (int *)malloc((maxNumber + 1) * sizeof(int));
int i, j;
for (i = 0; i <= maxNumber; ++i) {
dsum[i] = 1;
}
for (i = 2; i <= maxNumber; ++i) {
for (j = i + i; j <= maxNumber; j += i) {
if (dsum[j] == j) get_div_cnt(j);
dsum[j] += i;
}
}
free(dsum);
return 0;
}</syntaxhighlight>
{{out|TIO.RUN}}
<pre> the same.
compiler flags -march=native -O2
Real time: 23.893 s User time: 23.475 s Sys. time: 0.203 s CPU share: 99.10 %
//Sys. time: up to 8s for version before???
//with lmt 2,000,000 the results on TIO.RUN are more stable.
version before
User time: 0.304 s CPU share: 98.93 %
slight improvement version
User time: 0.139 s CPU share: 98.80 %
</pre>
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
class ErdosNicolasNumbers
{
static void Main(string[] args)
{
const int limit = 100_000_000;
int[] divisorSum = new int[limit + 1];
int[] divisorCount = new int[limit + 1];
for (int i = 0; i <= limit; i++)
{
divisorSum[i] = 1;
divisorCount[i] = 1;
}
for (int index = 2; index <= limit / 2; index++)
{
for (int number = 2 * index; number <= limit; number += index)
{
if (divisorSum[number] == number)
{
Console.WriteLine($"{number,8} equals the sum of its first {divisorCount[number],3} divisors");
}
divisorSum[number] += index;
divisorCount[number]++;
}
}
}
}
</syntaxhighlight>
{{out}}
<pre>
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
Line 403 ⟶ 503:
91963648 equals the sum of its first 142 divisors
</pre>
=={{header|EasyLang}}==
{{trans|FreeBASIC}}
<syntaxhighlight>
limit = 2000000
for i to limit
dsum[] &= 1
dcnt[] &= 1
.
for i = 2 to limit
j = i + i
while j <= limit
if dsum[j] = j
print j & " equals the sum of its first " & dcnt[j] & " divisors"
.
dsum[j] += i
dcnt[j] += 1
j += i
.
.
</syntaxhighlight>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
_limit = 500000
void local fn ErdosNicolasNumbers
long i, j, sum( _limit ), count( _limit )
for i = 0 to _limit
sum(i) = 1
count(i) = 1
next
for i = 2 to _limit
j = i + i
while ( j <= _limit )
if sum(j) == j then printf @"%8ld == sum of its first %3ld divisors", j, count(j)
sum(j) = sum(j) + i
count(j) = count(j) + 1
j = j + i
wend
next
end fn
fn ErdosNicolasNumbers
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
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
</pre>
=={{header|Go}}==
Line 459 ⟶ 617:
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.Arrays;
Line 472 ⟶ 630:
Arrays.fill(divisorCount, 1);
for ( int index = 2; index <= limit / 2; index++
for ( int number = 2 * index; number <= limit; number += index ) {
if ( divisorSum[number] == number ) {
Line 480 ⟶ 638:
divisorSum[number] += index;
}
}
Line 499 ⟶ 657:
61900800 equals the sum of its first 280 divisors
91963648 equals the sum of its first 142 divisors
</pre>
=={{header|jq}}==
'''Adapted from [[#Wren]]'''
'''Works with jq and gojq, the C and Go implementations of jq'''
The following program will also work using jaq provided `sqrt` is defined appropriately
and other minor adjustments are made.
<syntaxhighlight lang=jq>
# Output a stream of the (unsorted) proper divisors of . including 1
def proper_divisors:
. as $n
| if $n > 1 then 1,
( range(2; 1 + sqrt) as $i
| if ($n % $i) == 0 then $i,
(($n / $i) | if . == $i then empty else . end)
else empty
end)
else empty
end;
# Emit k if . is an Erdos-Nicolas number, otherwise emit 0
def erdosNicolas:
. as $n
| ([proper_divisors] | sort) as $divisors
| ($divisors|length) as $dc
| if $dc < 3 then 0
else {sum: ($divisors[0] + $divisors[1])}
# An Erdos-Nicolas is not perfect, and hence $dc-1 in the following line:
| first(
foreach range(2; $dc-1) as $i (.;
.sum += $divisors[$i]
| if .sum == $n then .emit = $i + 1
elif .sum > $n then .emit = 0
else .
end )
| select(.emit).emit ) // 0
end ;
limit(8;
range(2; infinite)
| . as $n
| erdosNicolas as $k
| select($k > 0)
| "\($n) from \($k)" )
</syntaxhighlight>
{{output}}
<pre>
24 from 6
2016 from 31
8190 from 43
42336 from 66
45864 from 66
392448 from 68
714240 from 113
1571328 from 115
</pre>
Line 534 ⟶ 749:
714240 equals the sum of its first 113 divisors.
1571328 equals the sum of its first 115 divisors.
</pre>
=={{header|Nim}}==
{{trans|Go}}
To get better performances, we use 32 bits integers rather than 64 bits integers. We got the best (and excellent) execution time with compilation command: <code>nim c -d:release -d:lto --gc:boehm erdos_nicolas_numbers.nim</code>
<syntaxhighlight lang="Nim">import std/[sequtils, strformat]
proc main() =
const MaxNumber = 100_000_000i32
var dsum, dcount = repeat(1'i32, MaxNumber + 1)
for i in 2i32..MaxNumber:
for j in countup(i + i, MaxNumber, i):
if dsum[j] == j:
echo &"{j:>8} equals the sum of its first {dcount[j]} divisors"
inc dsum[j], i
inc dcount[j]
main()
</syntaxhighlight>
{{out}}
<pre> 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
</pre>
Line 929 ⟶ 1,173:
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>use v5.36;
use enum qw(False True);
use
sub is_Erdos_Nicolas ($n) {
divisor_sum($n) > 2*$n or return False;
my $
foreach my $d (divisors($n)) {
++$count; $sum += $d;
return $count if ($sum == $n);
return False if ($sum > $n);
}
}
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++;
}
}</syntaxhighlight>
Line 995 ⟶ 1,237:
Output same as Julia
=={{header|Python}}==
{{trans|C}}
This is a translation of the "slight improvement" C code. I ran this script using PyPy7.3.13 (Python3.10.13) and it completes in ~10.5s on a AMD Ryzen 7 7800X3D.
<syntaxhighlight lang="python">
# erdos-nicolas.py by Xing216
from time import perf_counter
start = perf_counter()
def get_div_cnt(n: int) -> None:
divcnt,divsum = 1,1
lmt = n/2
f = 2
while True:
if f > lmt: break
if not (n % f):
divsum += f
divcnt += 1
if divsum == n: break
f+=1
print(f"{n:>8} equals the sum of its first {divcnt} divisors")
max_number = 91963649
dsum = [1 for _ in range(max_number+1)]
for i in range(2, max_number + 1):
for j in range(i + i, max_number + 1, i):
if (dsum[j] == j): get_div_cnt(j)
dsum[j] += i
done = perf_counter() - start
print(f"Done in: {done:.3f}s")
</syntaxhighlight>
{{out}}
<pre>
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
Done in: 10.478s
</pre>
=={{header|Raku}}==
<syntaxhighlight lang="raku" line>use Prime::Factor;
Line 1,061 ⟶ 1,345:
392448 equals the sum of its first 68 divisors
1571328 equals the sum of its first 115 divisors
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func is_Erdős_Nicolas(n) {
n.is_abundant || return false
var sum = 0
var count = 0
n.divisors.each {|d|
++count; sum += d
return count if (sum == n)
return false if (sum > n)
}
}
var count = 8 # how many terms to compute
^Inf -> by(2).each {|n|
if (is_Erdős_Nicolas(n)) { |v|
say "#{'%8s'%n} is the sum of its first #{'%3s'%v} divisors"
--count || break
}
}</syntaxhighlight>
{{out}}
<pre>
24 is the sum of its first 6 divisors
2016 is the sum of its first 31 divisors
8190 is the sum of its first 43 divisors
42336 is the sum of its first 66 divisors
45864 is the sum of its first 66 divisors
392448 is the sum of its first 68 divisors
714240 is the sum of its first 113 divisors
1571328 is the sum of its first 115 divisors
</pre>
Line 1,066 ⟶ 1,385:
===Version 1===
{{libheader|Wren-math}}
<syntaxhighlight lang="
var erdosNicolas = Fn.new { |n|
Line 1,112 ⟶ 1,431:
If `maxNum` is set to 2 million, then it finds the first 8 in about 5.2 seconds which is more than 10 times faster than Version 1's 58 seconds.
<syntaxhighlight lang="
var maxNum = 1e8
| |||