Anonymous user
Chowla numbers: Difference between revisions
m
no edit summary
imported>Wilm mNo edit summary |
|||
| (13 intermediate revisions by 6 users not shown) | |||
Line 1,387:
{{trans|Go}}
<syntaxhighlight lang="text">
sum = 0
i = 2
while i * i <= n
if n mod i = 0
j = n div i
if i = j
sum += i
else
sum += i + j
.
.
return sum
.
i = 3
while i * 3 <= len c[]
if c[i] = 0
while j <=
.
.
.
s$[] = strchars n
s$ = ""
l = len s$[]
for i = 1 to len s$[]
if i > 1 and l mod 3 = 0
s$ &= ","
.
l -= 1
s$ &= s$[i]
.
.
print "chowla number from 1 to 37"
for i = 1 to 37
print " " & i & ": " & chowla i
.
print ""
len c[] 10000000
count = 1
power = 100
i = 3
while i <= len c[]
if c[i] = 0
count += 1
.
if i = power - 1
print "There are " & c$ & " primes up to " & p$
power *= 10
.
i += 2
.
print ""
limit = 35000000
count = 0
i = 2
k = 2
kk = 3
repeat
p = k * kk
until p > limit
print s$ & " is a perfect number"
commatize limit s$
print "There are " & count & " perfect mumbers up to " & s$
.
</syntaxhighlight>
{{out}}
Line 1,532 ⟶ 1,530:
33,550,336 is a perfect number
There are 5 perfect mumbers up to 35,000,000
</pre>
=={{header|EMal}}==
{{trans|Go}}
<syntaxhighlight lang="emal">
fun chowla = int by int n
int sum = 0
int j = 0
for int i = 2; i * i <= n; i++ do
if n % i == 0 do sum += i + when(i == (j = n / i), 0, j) end
end
return sum
end
fun sieve = List by int limit
List c = logic[].with(limit)
for int i = 3; i * 3 < limit; i += 2
if c[i] or chowla(i) != 0 do continue end
for int j = 3 * i; j < limit; j += 2 * i do c[j] = true end
end
return c
end
# find and display (1 per line) for the 1st 37 integers
for int i = 1; i <= 37; i++ do writeLine("chowla(" + i + ") = " + chowla(i)) end
int count = 1
int limit = 10000000
int power = 100
List c = sieve(limit)
for int i = 3; i < limit; i += 2
if not c[i] do count++ end
if i == power - 1
writeLine("Count of primes up to " + power + " = " + count)
power *= 10
end
end
count = 0
limit = 35000000
int k = 2
int kk = 3
int p
for int i = 2; ; i++
if (p = k * kk) > limit do break end
if chowla(p) == p - 1
writeLine(p + " is a number that is perfect")
count++
end
k = kk + 1
kk += k
end
writeLine("There are " + count + " perfect numbers <= 35,000,000")
</syntaxhighlight>
It takes about fifteen minutes to complete on my i7-8650U with 8.00GB of RAM.
{{out}}
<pre>
chowla(1) = 0
chowla(2) = 0
chowla(3) = 0
chowla(4) = 2
chowla(5) = 0
chowla(6) = 5
chowla(7) = 0
chowla(8) = 6
chowla(9) = 3
chowla(10) = 7
chowla(11) = 0
chowla(12) = 15
chowla(13) = 0
chowla(14) = 9
chowla(15) = 8
chowla(16) = 14
chowla(17) = 0
chowla(18) = 20
chowla(19) = 0
chowla(20) = 21
chowla(21) = 10
chowla(22) = 13
chowla(23) = 0
chowla(24) = 35
chowla(25) = 5
chowla(26) = 15
chowla(27) = 12
chowla(28) = 27
chowla(29) = 0
chowla(30) = 41
chowla(31) = 0
chowla(32) = 30
chowla(33) = 14
chowla(34) = 19
chowla(35) = 12
chowla(36) = 54
chowla(37) = 0
Count of primes up to 100 = 25
Count of primes up to 1000 = 168
Count of primes up to 10000 = 1229
Count of primes up to 100000 = 9592
Count of primes up to 1000000 = 78498
Count of primes up to 10000000 = 664579
6 is a number that is perfect
28 is a number that is perfect
496 is a number that is perfect
8128 is a number that is perfect
33550336 is a number that is perfect
There are 5 perfect numbers <= 35,000,000
</pre>
Line 1,616 ⟶ 1,716:
33,550,336 is perfect
</pre>
=={{header|
{{works with|VAX Fortran|V4.6-244}}
{{libheader|VAX/VMS V4.6}}This compiler implements the Fortran-77 standard. The VAX/VMS operating system runs on simulated hardware using the open source [https://opensimh.org/ opensimh] platform.
{{trans|Ada}}
Run time on a Raspberry Pi 4 Model B Rev 1.1 (Raspbian GNU/Linux 10 buster) was 7h 21m
<syntaxhighlight lang="fortran" line="1">
PROGRAM CHOWLA
CALL PUT_1ST_37
CALL PUT_PRIME
CALL PUT_PERFECT
END
INTEGER*4 FUNCTION CHOWLA1(N)
C The Chowla number of N is the sum of the divisors of N
C excluding unity and N where N is a positive integer
IMPLICIT INTEGER*4 (A-Z)
IF (N .LE. 0) STOP 'Argument to Chowla function must be > 0'
SUM = 0
I = 2
100 CONTINUE
IF (I * I .GT. N) GOTO 200
IF (MOD(N, I) .NE. 0) GOTO 110
J = N / I
SUM = SUM + I
IF ( I .NE. J) SUM = SUM + J
110 CONTINUE
I = I + 1
GOTO 100
200 CONTINUE
CHOWLA1 = SUM
RETURN
END
SUBROUTINE PUT_1ST_37
IMPLICIT INTEGER*4 (A-Z)
DO 100 I = 1, 37
PRINT 900, I, CHOWLA1(I)
100 CONTINUE
RETURN
900 FORMAT(1H , 'CHOWLA(', I2, ') = ', I2)
END
SUBROUTINE PUT_PRIME
IMPLICIT INTEGER*4 (A-Z)
PARAMETER LIMIT = 10000000
COUNT = 0
POWER = 100
DO 200 N = 2, LIMIT
IF (CHOWLA1(N) .EQ. 0) COUNT = COUNT + 1
IF (MOD(N, POWER) .NE. 0) GOTO 100
PRINT 900, COUNT, POWER
POWER = POWER * 10
100 CONTINUE
200 CONTINUE
RETURN
900 FORMAT(1H ,'There are ', I12, ' primes < ', I12)
END
SUBROUTINE PUT_PERFECT
IMPLICIT INTEGER*4 (A-Z)
PARAMETER LIMIT = 35000000
COUNT = 0
K = 2
KK = 3
100 CONTINUE
P = K * KK
IF (P .GT. LIMIT) GOTO 300
IF (CHOWLA1(P) .NE. P - 1) GOTO 200
PRINT 900, P
COUNT = COUNT + 1
200 CONTINUE
K = KK + 1
KK = KK + K
GOTO 100
300 CONTINUE
PRINT 910, COUNT, LIMIT
RETURN
900 FORMAT(1H , I10, ' is a perfect number')
910 FORMAT(1H , 'There are ', I10, ' perfect numbers < ', I10)
END
</syntaxhighlight>
{{out}}<pre>
CHOWLA( 1) = 0
CHOWLA( 2) = 0
CHOWLA( 3) = 0
CHOWLA( 4) = 2
CHOWLA( 5) = 0
CHOWLA( 6) = 5
CHOWLA( 7) = 0
CHOWLA( 8) = 6
CHOWLA( 9) = 3
CHOWLA(10) = 7
CHOWLA(11) = 0
CHOWLA(12) = 15
CHOWLA(13) = 0
CHOWLA(14) = 9
CHOWLA(15) = 8
CHOWLA(16) = 14
CHOWLA(17) = 0
CHOWLA(18) = 20
CHOWLA(19) = 0
CHOWLA(20) = 21
CHOWLA(21) = 10
CHOWLA(22) = 13
CHOWLA(23) = 0
CHOWLA(24) = 35
CHOWLA(25) = 5
CHOWLA(26) = 15
CHOWLA(27) = 12
CHOWLA(28) = 27
CHOWLA(29) = 0
CHOWLA(30) = 41
CHOWLA(31) = 0
CHOWLA(32) = 30
CHOWLA(33) = 14
CHOWLA(34) = 19
CHOWLA(35) = 12
CHOWLA(36) = 54
CHOWLA(37) = 0
There are 25 primes < 100
There are 168 primes < 1000
There are 1229 primes < 10000
There are 9592 primes < 100000
There are 78498 primes < 1000000
There are 664579 primes < 10000000
6 is a perfect number
28 is a perfect number
496 is a perfect number
8128 is a perfect number
33550336 is a perfect number
There are 5 perfect numbers < 35000000
</pre>
== {{header|FreeBASIC}} ==
{{trans|Visual Basic}}
<syntaxhighlight lang="freebasic">
Line 1,762 ⟶ 2,037:
Pulsa una tecla para salir
</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
local fn Chowla( n as NSUInteger ) as NSUInteger
NSUInteger i, j, r = 0
i = 2
while ( i * i <= n )
j = n / i
if ( n mod i == 0 )
r += i
if ( i != j )
r += j
end if
end if
i++
wend
end fn = r
local fn DoIt
NSUInteger n, count = 0, power = 100, limit, k, kk, p = 0
for n = 1 to 37
printf @"chowla(%u) = %u", n, fn Chowla( n )
next
for n = 2 to 10000000
if ( fn Chowla(n) == 0 ) then count ++
if ( n mod power == 0 ) then printf @"There are %u primes < %-7u", count, power : power *= 10
next
count = 0
limit = 350000000
k = 2 : kk = 3
do
p = k * kk
if ( fn Chowla( p ) == p - 1 )
printf @"%9u is a perfect number", p
count++
end if
k = kk + 1
kk = kk + k
until ( p > limit )
printf @"There are %u perfect numbers < %u", count, limit
end fn
fn DoIt
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
chowla(1) = 0
chowla(2) = 0
chowla(3) = 0
chowla(4) = 2
chowla(5) = 0
chowla(6) = 5
chowla(7) = 0
chowla(8) = 6
chowla(9) = 3
chowla(10) = 7
chowla(11) = 0
chowla(12) = 15
chowla(13) = 0
chowla(14) = 9
chowla(15) = 8
chowla(16) = 14
chowla(17) = 0
chowla(18) = 20
chowla(19) = 0
chowla(20) = 21
chowla(21) = 10
chowla(22) = 13
chowla(23) = 0
chowla(24) = 35
chowla(25) = 5
chowla(26) = 15
chowla(27) = 12
chowla(28) = 27
chowla(29) = 0
chowla(30) = 41
chowla(31) = 0
chowla(32) = 30
chowla(33) = 14
chowla(34) = 19
chowla(35) = 12
chowla(36) = 54
chowla(37) = 0
There are 25 primes < 100
There are 168 primes < 1,000
There are 1,229 primes < 10,000
There are 9,592 primes < 100,000
There are 78,498 primes < 1,000,000
There are 664,579 primes < 10,000,000
6 is a perfect number
28 is a perfect number
496 is a perfect number
8,128 is a perfect number
33,550,336 is a perfect number
There are 5 perfect numbers < 35,000,000
</pre>
=={{header|Go}}==
<syntaxhighlight lang="go">package main
Line 3,054 ⟶ 3,433:
There are 5 perfect numbers < 350,000,000
</pre>
=={{header|PARI/GP}}==
{{trans|Julia}}
<syntaxhighlight lang="PARI/GP">
chowla(n) = {
if (n < 1, error("Chowla function argument must be positive"));
if (n < 4, return(0));
my(divs = divisors(n));
sum(i=1, #divs, divs[i]) - n - 1;
}
\\ Function to count Chowla numbers
countchowlas(n, asperfect = 1, verbose = 1) = {
my(count = 0, chow, i);
for (i = 2, n,
chow = chowla(i);
if ( (asperfect && (chow == i - 1)) || ((!asperfect) && (chow == 0)),
count++;
if (verbose, print("The number " i " is " if (asperfect, "perfect.", "prime.")));
);
);
count;
}
\\ Main execution block
{
print("The first 37 chowla numbers are:");
for (i = 1, 37, printf("Chowla(%s) is %s\n", Str(i), Str(chowla(i)) ) );
m=100;
while(m<=10000000, print("The count of the primes up to " m " is " countchowlas(m, 0, 0)); m=m*10);
print("The count of perfect numbers up to 35,000,000 is " countchowlas(35000000, 1, 1));
}
</syntaxhighlight>
{{out}}
<pre>
The first 37 chowla numbers are:
Chowla(1) is 0
Chowla(2) is 0
Chowla(3) is 0
Chowla(4) is 2
Chowla(5) is 0
Chowla(6) is 5
Chowla(7) is 0
Chowla(8) is 6
Chowla(9) is 3
Chowla(10) is 7
Chowla(11) is 0
Chowla(12) is 15
Chowla(13) is 0
Chowla(14) is 9
Chowla(15) is 8
Chowla(16) is 14
Chowla(17) is 0
Chowla(18) is 20
Chowla(19) is 0
Chowla(20) is 21
Chowla(21) is 10
Chowla(22) is 13
Chowla(23) is 0
Chowla(24) is 35
Chowla(25) is 5
Chowla(26) is 15
Chowla(27) is 12
Chowla(28) is 27
Chowla(29) is 0
Chowla(30) is 41
Chowla(31) is 0
Chowla(32) is 30
Chowla(33) is 14
Chowla(34) is 19
Chowla(35) is 12
Chowla(36) is 54
Chowla(37) is 0
The count of the primes up to 100 is 25
The count of the primes up to 1000 is 168
The count of the primes up to 10000 is 1229
The count of the primes up to 100000 is 9592
The count of the primes up to 1000000 is 78498
The count of the primes up to 10000000 is 664579
The number 6 is perfect.
The number 28 is perfect.
The number 496 is perfect.
The number 8128 is perfect.
The number 33550336 is perfect.
The count of perfect numbers up to 35000000 is 5.
</pre>
=={{header|Pascal}}==
{{works with|Free Pascal}}
Line 4,402 ⟶ 4,869:
33550336 is a perfect number
There are 5 perfect numbers < 350000000</pre>
=={{header|Rust}}==
{{trans|C++}}
<syntaxhighlight lang="Rust">
fn chowla(n: usize) -> usize {
let mut sum = 0;
let mut i = 2;
while i * i <= n {
if n % i == 0 {
sum += i;
let j = n / i;
if i != j {
sum += j;
}
}
i += 1;
}
sum
}
fn sieve(limit: usize) -> Vec<bool> {
let mut c = vec![false; limit];
let mut i = 3;
while i * i < limit {
if !c[i] && chowla(i) == 0 {
let mut j = 3 * i;
while j < limit {
c[j] = true;
j += 2 * i;
}
}
i += 2;
}
c
}
fn main() {
for i in 1..=37 {
println!("chowla({}) = {}", i, chowla(i));
}
let mut count = 1;
let limit = 1e7 as usize;
let mut power = 100;
let c = sieve(limit);
for i in (3..limit).step_by(2) {
if !c[i] {
count += 1;
}
if i == power - 1 {
println!("Count of primes up to {} = {}", power, count);
power *= 10;
}
}
count = 0;
let limit = 35000000;
let mut k = 2;
let mut kk = 3;
loop {
let p = k * kk;
if p > limit {
break;
}
if chowla(p) == p - 1 {
println!("{} is a number that is perfect", p);
count += 1;
}
k = kk + 1;
kk += k;
}
println!("There are {} perfect numbers <= 35,000,000", count);
}
</syntaxhighlight>
{{out}}
<pre>
chowla(1) = 0
chowla(2) = 0
chowla(3) = 0
chowla(4) = 2
chowla(5) = 0
chowla(6) = 5
chowla(7) = 0
chowla(8) = 6
chowla(9) = 3
chowla(10) = 7
chowla(11) = 0
chowla(12) = 15
chowla(13) = 0
chowla(14) = 9
chowla(15) = 8
chowla(16) = 14
chowla(17) = 0
chowla(18) = 20
chowla(19) = 0
chowla(20) = 21
chowla(21) = 10
chowla(22) = 13
chowla(23) = 0
chowla(24) = 35
chowla(25) = 5
chowla(26) = 15
chowla(27) = 12
chowla(28) = 27
chowla(29) = 0
chowla(30) = 41
chowla(31) = 0
chowla(32) = 30
chowla(33) = 14
chowla(34) = 19
chowla(35) = 12
chowla(36) = 54
chowla(37) = 0
Count of primes up to 100 = 25
Count of primes up to 1000 = 168
Count of primes up to 10000 = 1229
Count of primes up to 100000 = 9592
Count of primes up to 1000000 = 78498
Count of primes up to 10000000 = 664579
6 is a number that is perfect
28 is a number that is perfect
496 is a number that is perfect
8128 is a number that is perfect
33550336 is a number that is perfect
There are 5 perfect numbers <= 35,000,000
</pre>
=={{header|Scala}}==
This solution uses a lazily-evaluated iterator to find and sum the divisors of a number, and speeds up the large searches using parallel vectors.
Line 5,122 ⟶ 5,717:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="
import "./math" for Int, Nums
Line 5,211 ⟶ 5,806:
There are 5 perfect numbers <= 35,000,000
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">func Chowla(N); \Return sum of divisors
| |||