Anonymous user
Chowla numbers: Difference between revisions
m
no edit summary
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: Reinstate comments about Perl 6 entry. Remove any humour to not offend the humour impaired.) |
imported>Wilm mNo edit summary |
||
| (125 intermediate revisions by 41 users not shown) | |||
Line 1:
{{
Chowla numbers are also known as:
::* Chowla's function
::* chowla numbers
::* the chowla function
::* the chowla number
Line 21 ⟶ 22:
German mathematician Carl Friedrich Gauss (1777─1855) said
"Mathematics is the queen of the sciences ─ and number theory is the queen of mathematics".
Line 28 ⟶ 29:
;Definitions:
Chowla numbers can also be expressed as:
<big>
chowla(<big>'''n'''</big>) = sum of divisors of <big>'''n'''</big> excluding unity and <big>'''n'''</big>
chowla(<big>'''n'''</big>) = sum( divisors(<big>'''n'''</big>)) <big>'''- 1 - n''' </big>
chowla(<big>'''n'''</big>) = sum( properDivisors(<big>'''n'''</big>)) <big>'''- 1''' </big>
chowla(<big>'''n'''</big>) = sum(aliquotDivisors(<big>'''n'''</big>)) <big>'''- 1''' </big>
chowla(<big>'''n'''</big>) = aliquot(<big>'''n'''</big>) <big>'''- 1''' </big>
chowla(<big>'''n'''</big>) = sigma(<big>'''n'''</big>) <big>'''- 1 - n''' </big>
chowla(<big>'''n'''</big>) = sigmaProperDivisiors(<big>'''n'''</big>) <big>'''- 1''' </big>
if chowla(<big>'''n'''</big>) = <big>'''0'''</big>, and <big>'''n > 1'''</big>, then <big>'''n'''</big> is prime
if chowla(<big>'''n'''</big>) = <big>'''n - 1'''</big>, and <big>'''n > 1'''</big>, then <big>'''n'''</big> is a perfect number
</big>
;Task:
Line 71 ⟶ 74:
:* the OEIS entry for [http://oeis.org/A048050 A48050 Chowla's function].
<br><br>
=={{header|11l}}==
{{trans|C}}
<syntaxhighlight lang="11l">F chowla(n)
V sum = 0
V i = 2
L i * i <= n
I n % i == 0
sum += i
V j = n I/ i
I i != j
sum += j
i++
R sum
L(n) 1..37
print(‘chowla(’n‘) = ’chowla(n))
V count = 0
V power = 100
L(n) 2..10'000'000
I chowla(n) == 0
count++
I n % power == 0
print(‘There are ’count‘ primes < ’power)
power *= 10
count = 0
V limit = 350'000'000
V k = 2
V kk = 3
L
V p = k * kk
I p > limit
L.break
I chowla(p) == p - 1
print(p‘ is a perfect number’)
count++
k = kk + 1
kk += k
print(‘There are ’count‘ perfect numbers < ’limit)</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 < 350000000
</pre>
=={{header|Ada}}==
{{trans|C}}
<syntaxhighlight lang="ada">with Ada.Text_IO;
procedure Chowla_Numbers is
function Chowla (N : Positive) return Natural is
Sum : Natural := 0;
I : Positive := 2;
J : Positive;
begin
while I * I <= N loop
if N mod I = 0 then
J := N / I;
Sum := Sum + I + (if I = J then 0 else J);
end if;
I := I + 1;
end loop;
return Sum;
end Chowla;
procedure Put_37_First is
use Ada.Text_IO;
begin
for A in Positive range 1 .. 37 loop
Put_Line ("chowla(" & A'Image & ") = " & Chowla (A)'Image);
end loop;
end Put_37_First;
procedure Put_Prime is
use Ada.Text_IO;
Count : Natural := 0;
Power : Positive := 100;
begin
for N in Positive range 2 .. 10_000_000 loop
if Chowla (N) = 0 then
Count := Count + 1;
end if;
if N mod Power = 0 then
Put_Line ("There is " & Count'Image & " primes < " & Power'Image);
Power := Power * 10;
end if;
end loop;
end Put_Prime;
procedure Put_Perfect is
use Ada.Text_IO;
Count : Natural := 0;
Limit : constant := 350_000_000;
K : Natural := 2;
Kk : Natural := 3;
P : Natural;
begin
loop
P := K * Kk;
exit when P > Limit;
if Chowla (P) = P - 1 then
Put_Line (P'Image & " is a perfect number");
Count := Count + 1;
end if;
K := Kk + 1;
Kk := Kk + K;
end loop;
Put_Line ("There are " & Count'Image & " perfect numbers < " & Limit'Image);
end Put_Perfect;
begin
Put_37_First;
Put_Prime;
Put_Perfect;
end Chowla_Numbers;</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 is 25 primes < 100
There is 168 primes < 1000
There is 1229 primes < 10000
There is 9592 primes < 100000
There is 78498 primes < 1000000
There is 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 < 350000000</pre>
=={{header|ALGOL 68}}==
{{Trans|C}}
<syntaxhighlight lang="algol68">BEGIN # find some Chowla numbers ( Chowla n = sum of divisors of n exclusing n and 1 ) #
# returs the Chowla number of n #
PROC chowla = ( INT n )INT:
BEGIN
INT sum := 0;
FOR i FROM 2 WHILE i * i <= n DO
IF n MOD i = 0 THEN
INT j = n OVER i;
sum +:= i + IF i = j THEN 0 ELSE j FI
FI
OD;
sum
END # chowla # ;
FOR n TO 37 DO print( ( "chowla(", whole( n, 0 ), ") = ", whole( chowla( n ), 0 ), newline ) ) OD;
INT count := 0, power := 100;
FOR n FROM 2 TO 10 000 000 DO
IF chowla( n ) = 0 THEN count +:= 1 FI;
IF n MOD power = 0 THEN
print( ( "There are ", whole( count, 0 ), " primes < ", whole( power, 0 ), newline ) );
power *:= 10
FI
OD;
count := 0;
INT limit = 350 000 000;
INT k := 2, kk := 3;
WHILE INT p = k * kk;
p <= limit
DO
IF chowla( p ) = p - 1 THEN
print( ( whole( p, 0 ), " is a perfect number", newline ) );
count +:= 1
FI;
k := kk + 1; kk +:= k
OD;
print( ( "There are ", whole( count, 0 ), " perfect numbers < ", whole( limit, 0 ), newline ) )
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 < 350000000
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">chowla: function [n]-> sum remove remove factors n 1 n
countPrimesUpTo: function [limit][
count: 1
loop 3.. .step: 2 limit 'x [
if zero? chowla x -> count: count + 1
]
return count
]
loop 1..37 'i -> print [i "=>" chowla i]
print ""
loop [100 1000 10000 100000 1000000 10000000] 'lim [
print ["primes up to" lim "=>" countPrimesUpTo lim]
]
print ""
print "perfect numbers up to 35000000:"
i: 2
while [i < 35000000][
if (chowla i) = i - 1 -> print i
i: i + 2
]</syntaxhighlight>
{{out}}
<pre>1 => 0
2 => 0
3 => 0
4 => 2
5 => 0
6 => 5
7 => 0
8 => 6
9 => 3
10 => 7
11 => 0
12 => 15
13 => 0
14 => 9
15 => 8
16 => 14
17 => 0
18 => 20
19 => 0
20 => 21
21 => 10
22 => 13
23 => 0
24 => 35
25 => 5
26 => 15
27 => 12
28 => 27
29 => 0
30 => 41
31 => 0
32 => 30
33 => 14
34 => 19
35 => 12
36 => 54
37 => 0
primes up to 100 => 25
primes up to 1000 => 168
primes up to 10000 => 1229
primes up to 100000 => 9592
primes up to 1000000 => 78498
primes up to 10000000 => 664579
perfect numbers up to 35000000:
6
28
496
8128
33550336</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f CHOWLA_NUMBERS.AWK
# converted from Go
BEGIN {
for (i=1; i<=37; i++) {
printf("chowla(%2d) = %s\n",i,chowla(i))
}
printf("\nCount of primes up to:\n")
count = 1
limit = 1e7
sieve(limit)
power = 100
for (i=3; i<limit; i+=2) {
if (!c[i]) {
count++
}
if (i == power-1) {
printf("%10s = %s\n",commatize(power),commatize(count))
power *= 10
}
}
printf("\nPerfect numbers:")
count = 0
limit = 35000000
k = 2
kk = 3
while (1) {
if ((p = k * kk) > limit) {
break
}
if (chowla(p) == p-1) {
printf(" %s",commatize(p))
count++
}
k = kk + 1
kk += k
}
printf("\nThere are %d perfect numbers <= %s\n",count,commatize(limit))
exit(0)
}
function chowla(n, i,j,sum) {
if (n < 1 || n != int(n)) {
return sprintf("%s is invalid",n)
}
for (i=2; i*i<=n; i++) {
if (n%i == 0) {
j = n / i
sum += (i == j) ? i : i + j
}
}
return(sum+0)
}
function commatize(x, num) {
if (x < 0) {
return "-" commatize(-x)
}
x = int(x)
num = sprintf("%d.",x)
while (num ~ /^[0-9][0-9][0-9][0-9]/) {
sub(/[0-9][0-9][0-9][,.]/,",&",num)
}
sub(/\.$/,"",num)
return(num)
}
function sieve(limit, i,j) {
for (i=1; i<=limit; i++) {
c[i] = 0
}
for (i=3; i*3<limit; i+=2) {
if (!c[i] && chowla(i) == 0) {
for (j=3*i; j<limit; j+=2*i) {
c[j] = 1
}
}
}
}
</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
1,000 = 168
10,000 = 1,229
100,000 = 9,592
1,000,000 = 78,498
10,000,000 = 664,579
Perfect numbers: 6 28 496 8,128 33,550,336
There are 5 perfect numbers <= 35,000,000
</pre>
=={{header|C}}==
<syntaxhighlight lang="c">#include <stdio.h>
unsigned chowla(const unsigned n) {
unsigned sum = 0;
for (unsigned i = 2, j; i * i <= n; i ++) if (n % i == 0) sum += i + (i == (j = n / i) ? 0 : j);
return sum;
}
int main(int argc, char const *argv[]) {
unsigned a;
for (unsigned n = 1; n < 38; n ++) printf("chowla(%u) = %u\n", n, chowla(n));
unsigned n, count = 0, power = 100;
for (n = 2; n < 10000001; n ++) {
if (chowla(n) == 0) count ++;
if (n % power == 0) printf("There is %u primes < %u\n", count, power), power *= 10;
}
count = 0;
unsigned limit = 350000000;
unsigned k = 2, kk = 3, p;
for ( ; ; ) {
if ((p = k * kk) > limit) break;
if (chowla(p) == p - 1) {
printf("%d is a perfect number\n", p);
count ++;
}
k = kk + 1; kk += k;
}
printf("There are %u perfect numbers < %u\n", count, limit);
return 0;
}</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 is 25 primes < 100
There is 168 primes < 1000
There is 1229 primes < 10000
There is 9592 primes < 100000
There is 78498 primes < 1000000
There is 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 < 350000000</pre>
=={{header|C sharp|C#}}==
{{trans|Go}}
<
namespace chowla_cs
Line 132 ⟶ 733:
}
}
}</
{{out}}
<pre>chowla(1) = 0
Line 184 ⟶ 785:
There are 5 perfect numbers <= 35,000,000
</pre>
=={{header|C++}}==
{{trans|Go}}
<
#include <iostream>
Line 243 ⟶ 843:
cout << "There are " << count << " perfect numbers <= 35,000,000\n";
return 0;
}</
{{out}}
<pre>chowla(1) = 0
Line 294 ⟶ 894:
33,550,336 is a number that is perfect
There are 5 perfect numbers <= 35,000,000</pre>
=={{header|CLU}}==
<syntaxhighlight lang="clu">% Chowla's function
chowla = proc (n: int) returns (int)
sum: int := 0
i: int := 2
while i*i <= n do
if n//i = 0 then
sum := sum + i
j: int := n/i
if i ~= j then
sum := sum + j
end
end
i := i + 1
end
return(sum)
end chowla
% A number is prime iff chowla(n) is 0
prime = proc (n: int) returns (bool)
return(chowla(n) = 0)
end prime
% A number is perfect iff chowla(n) equals n-1
perfect = proc (n: int) returns (bool)
return(chowla(n) = n-1)
end perfect
start_up = proc ()
LIMIT = 35000000
po: stream := stream$primary_output()
% Show chowla(1) through chowla(37)
for i: int in int$from_to(1, 37) do
stream$putl(po, "chowla(" || int$unparse(i) || ") = "
|| int$unparse(chowla(i)))
end
% Count primes up to powers of 10
pow10: int := 2 % start with 100
primecount: int := 1 % assume 2 is prime, then test only odd numbers
candidate: int := 3
while pow10 <= 7 do
if candidate >= 10**pow10 then
stream$putl(po, "There are "
|| int$unparse(primecount)
|| " primes up to "
|| int$unparse(10**pow10))
pow10 := pow10 + 1
end
if prime(candidate) then primecount := primecount + 1 end
candidate := candidate + 2
end
% Find perfect numbers up to 35 million
perfcount: int := 0
k: int := 2
kk: int := 3
while true do
n: int := k * kk
if n >= LIMIT then break end
if perfect(n) then
perfcount := perfcount + 1
stream$putl(po, int$unparse(n) || " is a perfect number.")
end
k := kk + 1
kk := kk + k
end
stream$putl(po, "There are " || int$unparse(perfcount) ||
" perfect numbers < 35,000,000.")
end start_up</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 up to 100
There are 168 primes up to 1000
There are 1229 primes up to 10000
There are 9592 primes up to 100000
There are 78498 primes up to 1000000
There are 664579 primes up to 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 < 35,000,000.</pre>
=={{header|Cowgol}}==
{{trans|C}}
<syntaxhighlight lang="cowgol">include "cowgol.coh";
sub chowla(n: uint32): (sum: uint32) is
sum := 0;
var i: uint32 := 2;
while i*i <= n loop
if n % i == 0 then
sum := sum + i;
var j := n / i;
if i != j then
sum := sum + j;
end if;
end if;
i := i + 1;
end loop;
end sub;
var n: uint32 := 1;
while n <= 37 loop
print("chowla(");
print_i32(n);
print(") = ");
print_i32(chowla(n));
print("\n");
n := n + 1;
end loop;
n := 2;
var power: uint32 := 100;
var count: uint32 := 0;
while n <= 10000000 loop
if chowla(n) == 0 then
count := count + 1;
end if;
if n % power == 0 then
print("There are ");
print_i32(count);
print(" primes < ");
print_i32(power);
print_nl();
power := power * 10;
end if;
n := n + 1;
end loop;
count := 0;
const LIMIT := 35000000;
var k: uint32 := 2;
var kk: uint32 := 3;
loop
n := k * kk;
if n > LIMIT then break; end if;
if chowla(n) == n-1 then
print_i32(n);
print(" is a perfect number.\n");
count := count + 1;
end if;
k := kk + 1;
kk := kk + k;
end loop;
print("There are ");
print_i32(count);
print(" perfect numbers < ");
print_i32(LIMIT);
print_nl();</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|D}}==
{{trans|C#}}
<syntaxhighlight lang="d">import std.stdio;
int chowla(int n) {
int sum;
for (int i = 2, j; i * i <= n; ++i) {
if (n % i == 0) {
sum += i + (i == (j = n / i) ? 0 : j);
}
}
return sum;
}
bool[] sieve(int limit) {
// True denotes composite, false denotes prime.
// Only interested in odd numbers >= 3
auto c = new bool[limit];
for (int i = 3; i * 3 < limit; i += 2) {
if (!c[i] && (chowla(i) == 0)) {
for (int j = 3 * i; j < limit; j += 2 * i) {
c[j] = true;
}
}
}
return c;
}
void main() {
foreach (i; 1..38) {
writefln("chowla(%d) = %d", i, chowla(i));
}
int count = 1;
int limit = cast(int)1e7;
int power = 100;
bool[] c = sieve(limit);
for (int i = 3; i < limit; i += 2) {
if (!c[i]) {
count++;
}
if (i == power - 1) {
writefln("Count of primes up to %10d = %d", power, count);
power *= 10;
}
}
count = 0;
limit = 350_000_000;
int k = 2;
int kk = 3;
int p;
for (int i = 2; ; ++i) {
p = k * kk;
if (p > limit) {
break;
}
if (chowla(p) == p - 1) {
writefln("%10d is a number that is perfect", p);
count++;
}
k = kk + 1;
kk += k;
}
writefln("There are %d 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|Delphi}}==
See [[#Pascal]].
=={{header|Dyalect}}==
{{trans|C#}}
<syntaxhighlight lang="dyalect">func chowla(n) {
var sum = 0
var i = 2
var j = 0
while i * i <= n {
if n % i == 0 {
j = n / i
var app = if i == j {
0
} else {
j
}
sum += i + app
}
i += 1
}
return sum
}
func sieve(limit) {
var c = Array.Empty(limit)
var i = 3
while i * 3 < limit {
if !c[i] && (chowla(i) == 0) {
var j = 3 * i
while j < limit {
c[j] = true
j += 2 * i
}
}
i += 2
}
return c
}
for i in 1..37 {
print("chowla(\(i)) = \(chowla(i))")
}
var count = 1
var limit = 10000000
var power = 100
var c = sieve(limit)
var i = 3
while i < limit {
if !c[i] {
count += 1
}
if i == power - 1 {
print("Count of primes up to \(power) = \(count)")
power *= 10
}
i += 2
}
count = 0
limit = 35000000
var k = 2
var kk = 3
var p
i = 2
while true {
p = k * kk
if p > limit {
break
}
if chowla(p) == p - 1 {
print("\(p) is a number that is perfect")
count += 1
}
k = kk + 1
kk += k
}
print("There are \(count) perfect numbers <= 35,000,000")</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|EasyLang}}==
{{trans|Go}}
<syntaxhighlight lang="text">
fastfunc chowla n .
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
.
.
i += 1
.
return sum
.
proc sieve . c[] .
i = 3
while i * 3 <= len c[]
if c[i] = 0
if chowla i = 0
j = 3 * i
while j <= len c[]
c[j] = 1
j += 2 * i
.
.
.
i += 2
.
.
proc commatize n . s$ .
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
.
proc main . .
print ""
len c[] 10000000
count = 1
sieve c[]
power = 100
i = 3
while i <= len c[]
if c[i] = 0
count += 1
.
if i = power - 1
commatize power p$
commatize count c$
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
if chowla p = p - 1
commatize p s$
print s$ & " is a perfect number"
count += 1
.
k = kk + 1
kk += k
i += 1
.
commatize limit s$
print "There are " & count & " perfect mumbers up to " & s$
.
main
</syntaxhighlight>
{{out}}
<pre>
chowla number from 1 to 37
1: 0
2: 0
3: 0
4: 2
5: 0
6: 5
7: 0
8: 6
9: 3
10: 7
11: 0
12: 15
13: 0
14: 9
15: 8
16: 14
17: 0
18: 20
19: 0
20: 21
21: 10
22: 13
23: 0
24: 35
25: 5
26: 15
27: 12
28: 27
29: 0
30: 41
31: 0
32: 30
33: 14
34: 19
35: 12
36: 54
37: 0
There are 25 primes up to 100
There are 168 primes up to 1,000
There are 1,229 primes up to 10,000
There are 9,592 primes up to 100,000
There are 78,498 primes up to 1,000,000
There are 664,579 primes up to 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 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>
=={{header|Factor}}==
<syntaxhighlight lang="factor">USING: formatting fry grouping.extras io kernel math
math.primes.factors math.ranges math.statistics sequences
tools.memory.private ;
IN: rosetta-code.chowla-numbers
: chowla ( n -- m )
dup 1 = [ 1 - ] [ [ divisors sum ] [ - 1 - ] bi ] if ;
: show-chowla ( n -- )
[1,b] [ dup chowla "chowla(%02d) = %d\n" printf ] each ;
: count-primes ( seq -- )
dup 0 prefix [ [ 1 + ] dip 2 <range> ] 2clump-map
[ [ chowla zero? ] count ] map cum-sum
[ [ commas ] bi@ "Primes up to %s: %s\n" printf ] 2each ;
: show-perfect ( n -- )
[ 2 3 ] dip '[ 2dup * dup _ > ] [
dup [ chowla ] [ 1 - = ] bi
[ commas "%s is perfect\n" printf ] [ drop ] if
[ nip 1 + ] [ nip dupd + ] 2bi
] until 3drop ;
: chowla-demo ( -- )
37 show-chowla nl { 100 1000 10000 100000 1000000 10000000 }
count-primes nl 35e7 show-perfect ;
MAIN: chowla-demo</syntaxhighlight>
{{out}}
<pre>
chowla(01) = 0
chowla(02) = 0
chowla(03) = 0
chowla(04) = 2
chowla(05) = 0
chowla(06) = 5
chowla(07) = 0
chowla(08) = 6
chowla(09) = 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
Primes up to 100: 25
Primes up to 1,000: 168
Primes up to 10,000: 1,229
Primes up to 100,000: 9,592
Primes up to 1,000,000: 78,498
Primes up to 10,000,000: 664,579
6 is perfect
28 is perfect
496 is perfect
8,128 is perfect
33,550,336 is perfect
</pre>
=={{header|Fortran}}==
{{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">
' Chowla_numbers
#include "string.bi"
Dim Shared As Long limite
limite = 10000000
Dim Shared As Boolean c(limite)
Dim As Long count, topenumprimo, a
count = 1
topenumprimo = 100
Dim As Longint p, k, kk, limitenumperfect
limitenumperfect = 35000000
k = 2: kk = 3
Declare Function chowla(Byval n As Longint) As Longint
Declare Sub sieve(Byval limite As Long, c() As Boolean)
Function chowla(Byval n As Longint) As Longint
Dim As Long i, j, r
i = 2
Do While i * i <= n
j = n \ i
If n Mod i = 0 Then
r += i
If i <> j Then r += j
End If
i += 1
Loop
chowla = r
End Function
Sub sieve(Byval limite As Long, c() As Boolean)
Dim As Long i, j
Redim As Boolean c(limite - 1)
i = 3
Do While i * 3 < limite
If Not c(i) Then
If chowla(i) = false Then
j = 3 * i
Do While j < limite
c(j) = true
j += 2 * i
Loop
End If
End If
i += 2
Loop
End Sub
Print "Chowla numbers"
For a = 1 To 37
Print "chowla(" & Trim(Str(a)) & ") = " & Trim(Str(chowla(a)))
Next a
' Si chowla(n) = falso and n > 1 Entonces n es primo
Print: Print "Contando los numeros primos hasta: "
sieve(limite, c())
For a = 3 To limite - 1 Step 2
If Not c(a) Then count += 1
If a = topenumprimo - 1 Then
Print Using "########## hay"; topenumprimo;
Print count
topenumprimo *= 10
End If
Next a
' Si chowla(n) = n - 1 and n > 1 Entonces n es un número perfecto
Print: Print "Buscando numeros perfectos... "
count = 0
Do
p = k * kk : If p > limitenumperfect Then Exit Do
If chowla(p) = p - 1 Then
Print Using "##########,# es un numero perfecto"; p
count += 1
End If
k = kk + 1 : kk += k
Loop
Print: Print "Hay " & count & " numeros perfectos <= " & Format(limitenumperfect, "###############################,#")
Print: Print "Pulsa una tecla para salir"
Sleep
End
</syntaxhighlight>
{{out}}
<pre>
Chowla numbers
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
Contando los numeros primos hasta:
100 hay 25
1000 hay 168
10000 hay 1229
100000 hay 9592
1000000 hay 78498
10000000 hay 664579
Buscando numeros perfectos...
6 es un numero perfecto
28 es un numero perfecto
496 es un numero perfecto
8,128 es un numero perfecto
33,550,336 es un numero perfecto
Hay 5 numeros perfectos <= 35.000.000
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}}==
<
import "fmt"
Line 375 ⟶ 2,221:
}
fmt.Println("There are", count, "perfect numbers <= 35,000,000")
}</
{{out}}
Line 431 ⟶ 2,277:
There are 5 perfect numbers <= 35,000,000
</pre>
=={{header|Groovy}}==
{{trans|Kotlin}}
<syntaxhighlight lang="groovy">class Chowla {
static int chowla(int n) {
if (n < 1) throw new RuntimeException("argument must be a positive integer")
int sum = 0
int i = 2
while (i * i <= n) {
if (n % i == 0) {
int j = (int) (n / i)
sum += (i == j) ? i : i + j
}
i++
}
return sum
}
static boolean[] sieve(int limit) {
// True denotes composite, false denotes prime.
// Only interested in odd numbers >= 3
boolean[] c = new boolean[limit]
for (int i = 3; i < limit / 3; i += 2) {
if (!c[i] && chowla(i) == 0) {
for (int j = 3 * i; j < limit; j += 2 * i) {
c[j] = true
}
}
}
return c
}
static void main(String[] args) {
for (int i = 1; i <= 37; i++) {
printf("chowla(%2d) = %d\n", i, chowla(i))
}
println()
int count = 1
int limit = 10_000_000
boolean[] c = sieve(limit)
int power = 100
for (int i = 3; i < limit; i += 2) {
if (!c[i]) {
count++
}
if (i == power - 1) {
printf("Count of primes up to %,10d = %,7d\n", power, count)
power *= 10
}
}
println()
count = 0
limit = 35_000_000
int i = 2
while (true) {
int p = (1 << (i - 1)) * ((1 << i) - 1) // perfect numbers must be of this form
if (p > limit) break
if (chowla(p) == p - 1) {
printf("%,d is a perfect number\n", p)
count++
}
i++
}
printf("There are %,d perfect numbers <= %,d\n", count, limit)
}
}</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 1,000 = 168
Count of primes up to 10,000 = 1,229
Count of primes up to 100,000 = 9,592
Count of primes up to 1,000,000 = 78,498
Count of primes up to 10,000,000 = 664,579
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|Haskell}}==
Uses arithmoi Library: https://hackage.haskell.org/package/arithmoi-0.11.0.0
compiled with "-O2 -threaded -rtsopts"<br/>
<syntaxhighlight lang="haskell">import Control.Concurrent (setNumCapabilities)
import Control.Monad.Par (runPar, get, spawnP)
import Control.Monad (join, (>=>))
import Data.List.Split (chunksOf)
import Data.List (intercalate, mapAccumL, genericTake, genericDrop)
import Data.Bifunctor (bimap)
import GHC.Conc (getNumProcessors)
import Math.NumberTheory.Primes (factorise, unPrime)
import Text.Printf (printf)
chowla :: Word -> Word
chowla 1 = 0
chowla n = f n
where
f = (-) =<< pred . product . fmap sumFactor . factorise
sumFactor (n, e) = foldr (\p s -> s + unPrime n^p) 1 [1..e]
chowlas :: [Word] -> [(Word, Word)]
chowlas [] = []
chowlas xs = runPar $ join <$>
(mapM (spawnP . fmap ((,) <*> chowla)) >=> mapM get) (chunksOf (10^6) xs)
chowlaPrimes :: [(Word, Word)] -> (Word, Word) -> (Word, Word)
chowlaPrimes chowlas range = (count chowlas, snd range)
where
isPrime (1, n) = False
isPrime (_, n) = n == 0
count = fromIntegral . length . filter isPrime . between range
between (min, max) = genericTake (max - pred min) . genericDrop (pred min)
chowlaPerfects :: [(Word, Word)] -> [Word]
chowlaPerfects = fmap fst . filter isPerfect
where
isPerfect (1, _) = False
isPerfect (n, c) = c == pred n
commas :: (Show a, Integral a) => a -> String
commas = reverse . intercalate "," . chunksOf 3 . reverse . show
main :: IO ()
main = do
cores <- getNumProcessors
setNumCapabilities cores
printf "Using %d cores\n" cores
mapM_ (uncurry (printf "chowla(%2d) = %d\n")) $ take 37 allChowlas
mapM_ (uncurry (printf "There are %8s primes < %10s\n"))
(chowlaP
[ (1, 10^2)
, (succ $ 10^2, 10^3)
, (succ $ 10^3, 10^4)
, (succ $ 10^4, 10^5)
, (succ $ 10^5, 10^6)
, (succ $ 10^6, 10^7) ])
mapM_ (printf "%10s is a perfect number.\n" . commas) perfects
printf "There are %2d perfect numbers < 35,000,000\n" $ length perfects
where
chowlaP = fmap (bimap commas commas) . snd
. mapAccumL (\total (count, max) -> (total + count, (total + count, max))) 0
. fmap (chowlaPrimes $ take (10^7) allChowlas)
perfects = chowlaPerfects allChowlas
allChowlas = chowlas [1..35*10^6]</syntaxhighlight>
{{out}}
<pre>Using 4 cores
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|J}}==
'''Solution:'''
<syntaxhighlight lang="j">chowla=: >: -~ >:@#.~/.~&.q: NB. sum of factors - (n + 1)
intsbelow=: (2 }. i.)"0
countPrimesbelow=: +/@(0 = chowla)@intsbelow
findPerfectsbelow=: (#~ <: = chowla)@intsbelow</syntaxhighlight>
'''Tasks:'''
<syntaxhighlight lang="j"> (] ,. chowla) >: i. 37 NB. chowla numbers 1-37
1 0
2 0
3 0
4 2
5 0
6 5
7 0
8 6
9 3
10 7
11 0
12 15
13 0
14 9
15 8
16 14
17 0
18 20
19 0
20 21
21 10
22 13
23 0
24 35
25 5
26 15
27 12
28 27
29 0
30 41
31 0
32 30
33 14
34 19
35 12
36 54
37 0
countPrimesbelow 100 1000 10000 100000 1000000 10000000
25 168 1229 9592 78498 664579
findPerfectsbelow 35000000
6 28 496 8128 33550336</syntaxhighlight>
=={{header|Java}}==
{{trans|C}}
<syntaxhighlight lang="java">
public class Chowla {
public static void main(String[] args) {
int[] chowlaNumbers = findChowlaNumbers(37);
for (int i = 0; i < chowlaNumbers.length; i++) {
System.out.printf("chowla(%d) = %d%n", (i+1), chowlaNumbers[i]);
}
System.out.println();
int[][] primes = countPrimes(100, 10_000_000);
for (int i = 0; i < primes.length; i++) {
System.out.printf(Locale.US, "There is %,d primes up to %,d%n", primes[i][1], primes[i][0]);
}
System.out.println();
int[] perfectNumbers = findPerfectNumbers(35_000_000);
for (int i = 0; i < perfectNumbers.length; i++) {
System.out.printf("%d is a perfect number%n", perfectNumbers[i]);
}
System.out.printf(Locale.US, "There are %d perfect numbers < %,d%n", perfectNumbers.length, 35_000_000);
}
public static int chowla(int n) {
if (n < 0) throw new IllegalArgumentException("n is not positive");
int sum = 0;
for (int i = 2, j; i * i <= n; i++)
if (n % i == 0) sum += i + (i == (j = n / i) ? 0 : j);
return sum;
}
protected static int[][] countPrimes(int power, int limit) {
int count = 0;
int[][] num = new int[countMultiplicity(limit, power)][2];
for (int n = 2, i=0; n <= limit; n++) {
if (chowla(n) == 0) count++;
if (n % power == 0) {
num[i][0] = power;
num[i][1] = count;
i++;
power *= 10;
}
}
return num;
}
protected static int countMultiplicity(int limit, int start) {
int count = 0;
int cur = limit;
while(cur >= start) {
count++;
cur = cur/10;
}
return count;
}
protected static int[] findChowlaNumbers(int limit) {
int[] num = new int[limit];
for (int i = 0; i < limit; i++) {
num[i] = chowla(i+1);
}
return num;
}
protected static int[] findPerfectNumbers(int limit) {
int count = 0;
int[] num = new int[count];
int k = 2, kk = 3, p;
while ((p = k * kk) < limit) {
if (chowla(p) == p - 1) {
num = increaseArr(num);
num[count++] = p;
}
k = kk + 1;
kk += k;
}
return num;
}
private static int[] increaseArr(int[] arr) {
int[] tmp = new int[arr.length + 1];
System.arraycopy(arr, 0, tmp, 0, arr.length);
return tmp;
}
}
</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 is 25 primes up to 100
There is 168 primes up to 1,000
There is 1,229 primes up to 10,000
There is 9,592 primes up to 100,000
There is 78,498 primes up to 1,000,000
There is 664,579 primes up to 10,000,000
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 < 35,000,000
</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
The "brute-force" computation of the perfect number beyond 8,128 took many hours.
<syntaxhighlight lang="jq">def add(stream): reduce stream as $x (0; . + $x);
# input should be an integer
def commatize:
def digits: tostring | explode | reverse;
if . == null then ""
elif . < 0 then "-" + ((- .) | commatize)
else [foreach digits[] as $d (-1; .+1;
# "," is 44
(select(. > 0 and . % 3 == 0)|44), $d)]
| reverse
| implode
end;
def count(stream): reduce stream as $i (0; . + 1);
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
# To take advantage of gojq's arbitrary-precision integer arithmetic:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
# unordered
def proper_divisors:
. as $n
| if $n > 1 then 1,
( range(2; 1 + (sqrt|floor)) as $i
| if ($n % $i) == 0 then $i,
(($n / $i) | if . == $i then empty else . end)
else empty
end)
else empty
end;
def chowla:
if . == 1 then 0
else add(proper_divisors) - 1
end;
# Input: a positive integer
def is_chowla_prime:
. > 1 and chowla == 0;
# In the interests of green(er) computing ...
def chowla_primes($n):
2, range(3; $n; 2) | select(is_chowla_prime);
def report_chowla_primes:
reduce range(2; 10000000) as $i (null;
if $i | is_chowla_prime
then if $i < 10000000 then .[7] += 1 else . end
| if $i < 1000000 then .[6] += 1 else . end
| if $i < 100000 then .[5] += 1 else . end
| if $i < 10000 then .[4] += 1 else . end
| if $i < 1000 then .[3] += 1 else . end
| if $i < 100 then .[2] += 1 else . end
else . end)
| (range(2;8) as $i
| "10 ^ \($i) \(.[$i]|commatize|lpad(16))") ;
def is_chowla_perfect:
(. > 1) and (chowla == . - 1);
def task:
" n\("chowla"|lpad(16))",
(range(1;38) | "\(lpad(3)): \(chowla|lpad(10))"),
"\n n \("Primes < n"|lpad(10))",
report_chowla_primes,
# "\nPerfect numbers up to 35e6",
# (range(1; 35e6) | select(is_chowla_perfect) | commatize)
""
;
task</syntaxhighlight>
{{out}}
<pre>
n chowla
1: 0
2: 0
3: 0
4: 2
5: 0
6: 5
7: 0
8: 6
9: 3
10: 7
11: 0
12: 15
13: 0
14: 9
15: 8
16: 14
17: 0
18: 20
19: 0
20: 21
21: 10
22: 13
23: 0
24: 35
25: 5
26: 15
27: 12
28: 27
29: 0
30: 41
31: 0
32: 30
33: 14
34: 19
35: 12
36: 54
37: 0
n Primes < n
10 ^ 2 25
10 ^ 3 168
10 ^ 4 1,229
10 ^ 5 9,592
10 ^ 6 78,498
10 ^ 7 664,579
Perfect numbers up to 35e6
6
28
496
8,128
33,550,336
</pre>
=={{header|Julia}}==
<
function chowla(n)
Line 473 ⟶ 2,881:
testchowla()
</
<pre>
The first 37 chowla numbers are:
Line 526 ⟶ 2,934:
The count of perfect numbers up to 35,000,000 is 5.
</pre>
=={{header|Kotlin}}==
{{trans|Go}}
<syntaxhighlight lang="scala">// Version 1.3.21
fun chowla(n: Int): Int {
if (n < 1) throw RuntimeException("argument must be a positive integer")
var sum = 0
var i = 2
while (i * i <= n) {
if (n % i == 0) {
val j = n / i
sum += if (i == j) i else i + j
}
i++
}
return sum
}
fun sieve(limit: Int): BooleanArray {
// True denotes composite, false denotes prime.
// Only interested in odd numbers >= 3
val c = BooleanArray(limit)
for (i in 3 until limit / 3 step 2) {
if (!c[i] && chowla(i) == 0) {
for (j in 3 * i until limit step 2 * i) c[j] = true
}
}
return c
}
fun main() {
for (i in 1..37) {
System.out.printf("chowla(%2d) = %d\n", i, chowla(i))
}
println()
var count = 1
var limit = 10_000_000
val c = sieve(limit)
var
for (i in 3
if (i == power - 1) {
System.out.printf("Count of primes up to %,-10d = %,d\n", power, count)
power *= 10
}
}
println()
count = 0
limit = 35_000_000
var i = 2
while (true) {
val p = (1 shl (i - 1)) * ((1 shl i) - 1) // perfect numbers must be of this form
if (p > limit) break
if (chowla(p) == p - 1) {
System.out.printf("%,d is a perfect number\n", p)
count++
}
i++
}
println("There are $count perfect numbers <= 35,000,000")
}</syntaxhighlight>
{{output}}
<pre>
Same as Go example.
</pre>
=={{header|Lua}}==
{{trans|D}}
<syntaxhighlight lang="lua">function chowla(n)
local sum = 0
local i = 2
local j = 0
while i * i <= n do
if n % i == 0 then
j = math.floor(n / i)
sum = sum + i
if i ~= j then
sum = sum + j
end
end
i = i + 1
end
return sum
end
function sieve(limit)
-- True denotes composite, false denotes prime.
-- Only interested in odd numbers >= 3
local c = {}
local i = 3
while i * 3 < limit do
if not c[i] and (chowla(i) == 0) then
local j = 3 * i
while j < limit do
c[j] = true
j = j + 2 * i
end
end
i = i + 2
end
return c
end
function main()
for i = 1, 37 do
print(string.format("chowla(%d) = %d", i, chowla(i)))
end
local count = 1
local limit = math.floor(1e7)
local power = 100
local c = sieve(limit)
local i = 3
while i < limit do
if not c[i] then
count = count + 1
end
if i == power - 1 then
print(string.format("Count of primes up to %10d = %d", power, count))
power = power * 10
end
i = i + 2
end
count = 0
limit = 350000000
local k = 2
local kk = 3
local p = 0
i = 2
while true do
p = k * kk
if p > limit then
break
end
if chowla(p) == p - 1 then
print(string.format("%10d is a number that is perfect", p))
count = count + 1
end
k = kk + 1
kk = kk + k
i = i + 1
end
print(string.format("There are %d perfect numbers <= 35,000,000", count))
end
main()</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|MAD}}==
{{trans|C}}
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER
INTERNAL FUNCTION(N)
ENTRY TO CHOWLA.
SUM = 0
THROUGH LOOP, FOR I=2, 1, I*I.G.N
J = N/I
WHENEVER J*I.E.N
SUM = SUM + I
WHENEVER I.NE.J, SUM = SUM + J
END OF CONDITIONAL
LOOP CONTINUE
FUNCTION RETURN SUM
END OF FUNCTION
VECTOR VALUES CHWFMT = $7HCHOWLA(,I2,4H) = ,I2*$
THROUGH CH37, FOR CH=1, 1, CH.G.37
CH37 PRINT FORMAT CHWFMT, CH, CHOWLA.(CH)
VECTOR VALUES PRIMES =
0 $10HTHERE ARE ,I6,S1,13HPRIMES BELOW ,I8*$
POWER = 100
COUNT = 0
THROUGH PRM, FOR CH=2, 1, CH.G.10000000
WHENEVER CHOWLA.(CH).E.0, COUNT = COUNT + 1
WHENEVER (CH/POWER)*POWER.E.CH
PRINT FORMAT PRIMES, COUNT, POWER
POWER = POWER * 10
PRM END OF CONDITIONAL
COUNT = 0
LIMIT = 35000000
VECTOR VALUES PERFCT = $I8,S1,20HIS A PERFECT NUMBER.*$
VECTOR VALUES PRFCNT =
0 $10HTHERE ARE ,I1,S1,22HPERFECT NUMBERS BELOW ,I8*$
K = 2
KK = 3
LOOP CH = K * KK
WHENEVER CH.G.LIMIT, TRANSFER TO DONE
WHENEVER CHOWLA.(CH).E.CH-1
PRINT FORMAT PERFCT, CH
COUNT = COUNT + 1
END OF CONDITIONAL
K = KK + 1
KK = KK + K
TRANSFER TO LOOP
DONE PRINT FORMAT PRFCNT, COUNT, LIMIT
END OF PROGRAM</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 BELOW 100
THERE ARE 168 PRIMES BELOW 1000
THERE ARE 1229 PRIMES BELOW 10000
THERE ARE 9592 PRIMES BELOW 100000
THERE ARE 78498 PRIMES BELOW 1000000
THERE ARE 664579 PRIMES BELOW 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 BELOW 35000000</pre>
=={{header|Maple}}==
{{incorrect|Maple| <br><br> The output for Chowla(1) is incorrect. <br><br> }}
<syntaxhighlight lang="maple">ChowlaFunction := n -> NumberTheory:-SumOfDivisors(n) - n - 1;
PrintChowla := proc(n::posint) local i;
printf("Integer : Chowla Number\n");
for i to n do
printf("%d : %d\n", i, ChowlaFunction(i));
end do;
end proc:
countPrimes := n -> nops([ListTools[SearchAll](0, map(ChowlaFunction, [seq(1 .. n)]))]);
findPerfect := proc(n::posint) local to_check, found, k;
to_check := map(ChowlaFunction, [seq(1 .. n)]);
found := [];
for k to n do
if to_check(k) = k - 1 then
found := [found, k];
end if;
end do;
end proc:
PrintChowla(37);
countPrimes(100);
countPrimes(1000);
countPrimes(10000);
countPrimes(100000);
countPrimes(1000000);
countPrimes(10000000);
findPerfect(35000000)</syntaxhighlight>
{{Out}}
<pre>
Integer : Chowla Number
1 : -1
2 : 0
3 : 0
4 : 2
5 : 0
6 : 5
7 : 0
8 : 6
9 : 3
10 : 7
11 : 0
12 : 15
13 : 0
14 : 9
15 : 8
16 : 14
17 : 0
18 : 20
19 : 0
20 : 21
21 : 10
22 : 13
23 : 0
24 : 35
25 : 5
26 : 15
27 : 12
28 : 27
29 : 0
30 : 41
31 : 0
32 : 30
33 : 14
34 : 19
35 : 12
36 : 54
37 : 0
25
168
1229
9592
78498
664579
[6, 28, 496, 8128, 33550336]</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[Chowla]
Chowla[0 | 1] := 0
Chowla[n_] := DivisorSigma[1, n] - 1 - n
Table[{i, Chowla[i]}, {i, 37}] // Grid
PrintTemporary[Dynamic[n]];
i = 1; Do[If[Chowla[n] == 0, i++], {n, 3, 100, 2}]; i
i = 1; Do[If[Chowla[n] == 0, i++], {n, 3, 1000, 2}]; i
i = 1; Do[If[Chowla[n] == 0, i++], {n, 3, 10000, 2}]; i
i = 1; Do[If[Chowla[n] == 0, i++], {n, 3, 100000, 2}]; i
i = 1; Do[If[Chowla[n] == 0, i++], {n, 3, 1000000, 2}]; i
i = 1; Do[If[Chowla[n] == 0, i++], {n, 3, 10000000, 2}]; i
Reap[Do[If[Chowla[n] == n - 1, Sow[n]], {n, 1, 35 10^6}]][[2, 1]]</syntaxhighlight>
{{out}}
<pre>25
168
1229
9592
78498
664579
{1, 6, 28, 496, 8128, 33550336}</pre>
=={{header|Nim}}==
{{trans|C}}
<syntaxhighlight lang="nim">import strformat
import strutils
func chowla(n: uint64): uint64 =
var sum = 0u64
var i = 2u64
var j: uint64
while i * i <= n:
if n mod i == 0:
j = n div i
sum += i
if i != j:
sum += j
inc i
sum
for n in 1u64..37:
echo &"chowla({n}) = {chowla(n)}"
var count = 0
var power = 100u64
for n in 2u64..10_000_000:
if chowla(n) == 0:
inc count
if n mod power == 0:
echo &"There are {insertSep($count, ','):>7} primes < {insertSep($power, ','):>10}"
power *= 10
count = 0
const limit = 350_000_000u64
var k = 2u64
var kk = 3u64
var p: uint64
while true:
p = k * kk
if p > limit:
break
if chowla(p) == p - 1:
echo &"{insertSep($p, ','):>10} is a perfect number"
inc count
k = kk + 1
kk += k
echo &"There are {count} perfect numbers < {insertSep($limit, ',')}"</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 < 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 < 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}}
{{works with|Delphi}}
{{trans|Go}} but not using a sieve, cause a sieve doesn't need precalculated small primes.<BR>
So runtime is as bad as trial division.
<syntaxhighlight lang="pascal">program Chowla_numbers;
{$IFDEF FPC}
{$MODE Delphi}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
SysUtils
{$IFDEF FPC}
,StrUtils{for Numb2USA}
{$ENDIF}
;
{$IFNDEF FPC}
function Numb2USA(const S: string): string;
var
I, NA: Integer;
begin
I := Length(S);
Result := S;
NA := 0;
while (I > 0) do
begin
if ((Length(Result) - I + 1 - NA) mod 3 = 0) and (I <> 1) then
begin
Insert(',', Result, I);
Inc(NA);
end;
Dec(I);
end;
end;
{$ENDIF}
function Chowla(n: NativeUint): NativeUint;
var
Divisor, Quotient: NativeUint;
begin
result := 0;
Divisor := 2;
while sqr(Divisor) < n do
begin
Quotient := n div Divisor;
if Quotient * Divisor = n then
inc(result, Divisor + Quotient);
inc(Divisor);
end;
if sqr(Divisor) = n then
inc(result, Divisor);
end;
procedure Count10Primes(Limit: NativeUInt);
var
n, i, cnt: integer;
begin
writeln;
writeln(' primes til | count');
i := 100;
n := 2;
cnt := 0;
repeat
repeat
// Ord (true) = 1 ,Ord (false) = 0
inc(cnt, ORD(chowla(n) = 0));
inc(n);
until n > i;
writeln(Numb2USA(IntToStr(i)): 12, '|', Numb2USA(IntToStr(cnt)): 10);
i := i * 10;
until i > Limit;
end;
procedure CheckPerf;
var
k, kk, p, cnt, limit: NativeInt;
begin
writeln;
writeln(' number that is perfect');
cnt := 0;
limit := 35000000;
k := 2;
kk := 3;
repeat
p := k * kk;
if p > limit then
BREAK;
if chowla(p) = (p - 1) then
begin
writeln(Numb2USA(IntToStr(p)): 12);
inc(cnt);
end;
k := kk + 1;
inc(kk, k);
until false;
end;
var
I: integer;
begin
for I := 2 to 37 do
writeln('chowla(', I: 2, ') =', chowla(I): 3);
Count10Primes(10 * 1000 * 1000);
CheckPerf;
end.</syntaxhighlight>
{{Out}}
<pre>
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
primes til | count
100| 25
1,000| 168
10,000| 1,229
100,000| 9,592
1,000,000| 78,498
10,000,000| 664,579
number that is perfect
6
28
496
8,128
33,550,336
real 1m54,534s
</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl">use strict;
use warnings;
use ntheory 'divisor_sum';
sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
sub chowla {
my($n) = @_;
$n < 2 ? 0 : divisor_sum($n) - ($n + 1);
}
sub prime_cnt {
my($n) = @_;
my $cnt = 1;
for (3..$n) {
$cnt++ if $_%2 and chowla($_) == 0
}
$cnt;
}
sub perfect {
my($n) = @_;
my @p;
for my $i (1..$n) {
push @p, $i if $i > 1 and chowla($i) == $i-1;
}
# map { push @p, $_ if $_ > 1 and chowla($_) == $_-1 } 1..$n; # speed penalty
@p;
}
printf "chowla(%2d) = %2d\n", $_, chowla($_) for 1..37;
print "\nCount of primes up to:\n";
printf "%10s %s\n", comma(10**$_), comma(prime_cnt(10**$_)) for 2..7;
my @perfect = perfect(my $limit = 35_000_000);
printf "\nThere are %d perfect numbers up to %s: %s\n",
1+$#perfect, comma($limit), join(' ', map { comma($_) } @perfect);</syntaxhighlight>
{{out}}
<pre>chowla( 1) = 0
chowla( 2) = 0
chowla( 3) = 0
chowla( 4) =
chowla( 5) = 0
chowla( 6) = 5
Line 600 ⟶ 3,764:
chowla(37) = 0
Count of primes up to
100 25
10,000,000 664,579
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">chowla</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">sieve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- True denotes composite, false denotes prime.
-- Only interested in odd numbers >= 3</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">/</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- if not c[i] and chowla(i)==0 then</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (see note below)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span><span style="color: #0000FF;">*</span><span style="color: #000000;">i</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">i</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">c</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pow10</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">37</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">chowla</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"chowla[1..37]: %V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sieve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">==</span><span style="color: #000000;">pow10</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Count of primes up to %,d = %,d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">pow10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">pow10</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">10</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">32</span><span style="color: #0000FF;">?</span><span style="color: #000000;">1.4e11</span><span style="color: #0000FF;">:</span><span style="color: #000000;">2.4e18</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--limit = power(2,iff(machine_bits()=32?53:64)) -- (see note below)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)*(</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- perfect numbers must be of this form</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">></span><span style="color: #000000;">limit</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">chowla</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)==</span><span style="color: #000000;">p</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%,d is a perfect number\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"There are %d perfect numbers <= %,d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">})</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
The use of chowla() in sieve() does not actually achieve anything other than slow it down, so I took it out.
{{out}}
<pre>
chowla[1..37]: {0,0,0,2,0,5,0,6,3,7,0,15,0,9,8,14,0,20,0,21,10,13,0,35,5,15,12,27,0,41,0,30,14,19,12,54,0}
Count of primes up to 100 = 25
Count of primes up to 1,000 = 168
Count of primes up to 10,000 = 1,229
Count of primes up to 100,000 = 9,592
Count of primes up to 1,000,000 = 78,498
Count of primes up to 10,000,000 = 664,579
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
8,589,869,056 is a perfect number
137,438,691,328 is a perfect number
2,305,843,008,139,952,128 is a perfect number
There are 8 perfect numbers <= 9,223,372,036,854,775,808
</pre>
Note that 32-bit only finds the first 7 perfect numbers, but does so in 0.4s, whereas 64-bit
takes just under 45s to find the 8th one. Using the theoretical (power 2) limits, those times
become 4s and 90s respectively, without finding anything else. Obviously 1.4e11 and 2.4e18
were picked to minimise the run times.
=={{header|Picat}}==
{{trans|Prolog}}
{{works with|Picat}}
<syntaxhighlight lang="picat">
table
chowla(1) = 0.
chowla(2) = 0.
chowla(3) = 0.
chowla(N) = C, N>3 =>
Max = floor(sqrt(N)),
Sum = 0,
foreach (X in 2..Max, N mod X == 0)
Y := N div X,
Sum := Sum + X + Y
end,
if (N == Max * Max) then
Sum := Sum - Max
end,
C = Sum.
main =>
foreach (I in 1..37)
printf("chowla(%d) = %d\n", I, chowla(I))
end,
Ranges = {100, 1000, 10000, 100000, 1000000, 10000000},
foreach (Range in Ranges)
Count = 0,
foreach (I in 2..Range)
if (chowla(I) == 0) then
Count := Count + 1
end
end,
printf("There are %d primes less than %d.\n", Count, Range)
end,
Limit = 35000000,
Count = 0,
foreach (I in 2..Limit)
if (chowla(I) == I-1) then
printf("%d is a perfect number\n", I),
Count := Count + 1
end
end,
printf("There are %d perfect numbers less than %d.\n", Count, Limit).
</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 less than 100.
There are 168 primes less than 1000.
There are 1229 primes less than 10000.
There are 9592 primes less than 100000.
There are 78498 primes less than 1000000.
There are 664579 primes less than 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 less than 35000000.
</pre>
=={{header|PicoLisp}}==
<syntaxhighlight lang="picolisp">(de accu1 (Var Key)
(if (assoc Key (val Var))
(con @ (inc (cdr @)))
(push Var (cons Key 1)) )
Key )
(de factor (N)
(let
(R NIL
D 2
L (1 2 2 . (4 2 4 2 4 6 2 6 .))
M (sqrt N) )
(while (>= M D)
(if (=0 (% N D))
(setq M
(sqrt (setq N (/ N (accu1 'R D)))) )
(inc 'D (pop 'L)) ) )
(accu1 'R N)
(mapcar
'((L)
(make
(for N (cdr L)
(link (** (car L) N)) ) ) )
R ) ) )
(de chowla (N)
(let F (factor N)
(-
(sum
prog
(make
(link 1)
(mapc
'((A)
(chain
(mapcan
'((B)
(mapcar '((C) (* C B)) (made)) )
A ) ) )
F ) ) )
N
1 ) ) )
(de prime (N)
(and (> N 1) (=0 (chowla N))) )
(de perfect (N)
(and
(> N 1)
(= (chowla N) (dec N))) )
(de countP (N)
(let C 0
(for I N
(and (prime I) (inc 'C)) )
C ) )
(de listP (N)
(make
(for I N
(and (perfect I) (link I)) ) ) )
(for I 37
(prinl "chowla(" I ") = " (chowla I)) )
(prinl "Count of primes up to 100 = " (countP 100))
(prinl "Count of primes up to 1000 = " (countP 1000))
(prinl "Count of primes up to 10000 = " (countP 10000))
(prinl "Count of primes up to 100000 = " (countP 100000))
(prinl "Count of primes up to 1000000 = " (countP 1000000))
(prinl "Count of primes up to 10000000 = " (countP 10000000))
(println (listP 35000000))</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 28 496 8128 33550336)
</pre>
=={{header|PowerBASIC}}==
{{incorrect|PowerBASIC| <br><br> The 8<sup>th</sup> perfect number is off by '''2''' (it is too high), <br> it should end in ... 952,128}}
{{trans|Visual Basic .NET}}
<syntaxhighlight lang="powerbasic">#COMPILE EXE
#DIM ALL
#COMPILER PBCC 6
FUNCTION chowla(BYVAL n AS LONG) AS LONG
REGISTER i AS LONG, j AS LONG
LOCAL r AS LONG
i = 2
DO WHILE i * i <= n
j = n \ i
IF n MOD i = 0 THEN
r += i
IF i <> j THEN
r += j
END IF
END IF
INCR i
LOOP
FUNCTION = r
END FUNCTION
FUNCTION chowla1(BYVAL n AS QUAD) AS QUAD
LOCAL i, j, r AS QUAD
i = 2
DO WHILE i * i <= n
j = n \ i
IF n MOD i = 0 THEN
r += i
IF i <> j THEN
r += j
END IF
END IF
INCR i
LOOP
FUNCTION = r
END FUNCTION
SUB sieve(BYVAL limit AS LONG, BYREF c() AS INTEGER)
LOCAL i, j AS LONG
REDIM c(limit - 1)
i = 3
DO WHILE i * 3 < limit
IF NOT c(i) THEN
IF chowla(i) = 0 THEN
j = 3 * i
DO WHILE j < limit
c(j) = -1
j += 2 * i
LOOP
END IF
END IF
i += 2
LOOP
END SUB
FUNCTION PBMAIN () AS LONG
LOCAL i, count, limit, power AS LONG
LOCAL c() AS INTEGER
LOCAL s AS STRING
LOCAL s30 AS STRING * 30
LOCAL p, k, kk, r, ql AS QUAD
FOR i = 1 TO 37
s = "chowla(" & TRIM$(STR$(i)) & ") = " & TRIM$(STR$(chowla(i)))
CON.PRINT s
NEXT i
count = 1
limit = 10000000
power = 100
CALL sieve(limit, c())
FOR i = 3 TO limit - 1 STEP 2
IF ISFALSE c(i) THEN count += 1
IF i = power - 1 THEN
RSET s30 = FORMAT$(power, "#,##0")
s = "Count of primes up to " & s30 & " =" & STR$(count)
CON.PRINT s
power *= 10
END IF
NEXT i
ql = 2 ^ 61
k = 2: kk = 3
RESET count
DO
p = k * kk : IF p > ql THEN EXIT DO
IF chowla1(p) = p - 1 THEN
RSET s30 = FORMAT$(p, "#,##0")
s = s30 & " is a number that is perfect"
CON.PRINT s
count += 1
END IF
k = kk + 1 : kk += k
LOOP
s = "There are" & STR$(count) & " perfect numbers <= " & FORMAT$(ql, "#,##0")
CON.PRINT s
CON.PRINT "press any key to exit program"
CON.WAITKEY$
END FUNCTION</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 1,000 = 168
Count of primes up to 10,000 = 1229
Count of primes up to 100,000 = 9592
Count of primes up to 1,000,000 = 78498
Count of primes up to 10,000,000 = 664579
6 is a number that is perfect
28 is a number that is perfect
496 is a number that is perfect
8,128 is a number that is perfect
33,550,336 is a number that is perfect
8,589,869,056 is a number that is perfect
137,438,691,328 is a number that is perfect
2,305,843,008,139,952,130 is a number that is perfect
There are 8 perfect numbers <= 2,305,843,009,213,693,950
press any key to exit program</pre>
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<syntaxhighlight lang="prolog">
chowla(1, 0).
chowla(2, 0).
chowla(N, C) :-
N > 2,
Max is floor(sqrt(N)),
findall(X, (between(2, Max, X), N mod X =:= 0), Xs),
findall(Y, (member(X1, Xs), Y is N div X1, Y \= Max), Ys),
!,
sum_list(Xs, S1),
sum_list(Ys, S2),
C is S1 + S2.
prime_count(Upper, Upper, Count, Count) :-
!.
prime_count(Lower, Upper, Add, Count) :-
chowla(Lower, 0),
!,
Lower1 is Lower + 1,
Add1 is Add + 1,
prime_count(Lower1, Upper, Add1, Count).
prime_count(Lower, Upper, Add, Count) :-
Lower1 is Lower + 1,
prime_count(Lower1, Upper, Add, Count).
perfect_numbers(Upper, Upper, AccNums, Nums) :-
!,
reverse(AccNums, Nums).
perfect_numbers(Lower, Upper, AccNums, Nums) :-
Perfect is Lower - 1,
chowla(Lower, Perfect),
!,
Lower1 is Lower + 1,
AccNums1 = [Lower|AccNums],
perfect_numbers(Lower1, Upper, AccNums1, Nums).
perfect_numbers(Lower, Upper, AccNums, Nums) :-
Lower1 is Lower + 1,
perfect_numbers(Lower1, Upper, AccNums, Nums).
main :-
% Chowla numbers
forall(between(1, 37, N), (
chowla(N, C),
format('chowla(~D) = ~D\n', [N, C])
)),
% Prime numbers
Ranges = [100, 1000, 10000, 100000, 1000000, 10000000],
forall(member(Range, Ranges), (
prime_count(2, Range, 0, PrimeCount),
format('There are ~D primes less than ~D.\n', [PrimeCount, Range])
)),
% Perfect numbers
Limit = 35000000,
perfect_numbers(2, Limit, [], Nums),
forall(member(Perfect, Nums), (
format('~D is a perfect number.\n', [Perfect])
)),
length(Nums, PerfectCount),
format('There are ~D perfect numbers < ~D.\n', [PerfectCount, Limit]).
</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 less than 100.
There are 168 primes less than 1,000.
There are 1,229 primes less than 10,000.
There are 9,592 primes less than 100,000.
There are 78,498 primes less than 1,000,000.
There are 664,579 primes less than 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|Python}}==
Uses [https://www.python.org/dev/peps/pep-0515/ underscores to separate digits] in numbers, and th [https://www.sympy.org/en/index.htm sympy library] to aid calculations.
<
from sympy import divisors
Line 649 ⟶ 4,369:
for i in range(6, 8):
print(f"primes_to({10**i:_}) == {primes_to(10**i):_}")
perfect_between(1_000_000, 35_000_000)</
{{out}}
Line 715 ⟶ 4,435:
* Splitting one function for the jit compiler to digest.
<
# https://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.factor_.divisors
Line 748 ⟶ 4,468:
print(f" {i:_}")
c += 1
print(f"Found {c} Perfect numbers between [{n:_}, {m:_})")</
{{out}}
Line 754 ⟶ 4,474:
Speedup - not much, subjectively...
=={{header|Racket}}==
<syntaxhighlight lang="racket">#lang racket
(require racket/fixnum)
(define cache-size 35000000)
(define chowla-cache (make-fxvector cache-size -1))
(define (chowla/uncached n)
(for/sum ((i (sequence-filter (λ (x) (zero? (modulo n x))) (in-range 2 (add1 (quotient n 2)))))) i))
(define (chowla n)
(if (> n cache-size)
(chowla/uncached n)
(let ((idx (sub1 n)))
(if (negative? (fxvector-ref chowla-cache idx))
(let ((c (chowla/uncached n))) (fxvector-set! chowla-cache idx c) c)
(fxvector-ref chowla-cache idx)))))
(define (prime?/chowla n)
(and (> n 1)
(zero? (chowla n))))
(define (perfect?/chowla n)
(and (> n 1)
(= n (add1 (chowla n)))))
(define (make-chowla-sieve n)
(let ((v (make-vector n 0)))
(for* ((i (in-range 2 n)) (j (in-range (* 2 i) n i))) (vector-set! v j (+ i (vector-ref v j))))
(for ((i (in-range 1 n))) (fxvector-set! chowla-cache (sub1 i) (vector-ref v i)))))
(module+
main
(define (count-and-report-primes limit)
(printf "Primes < ~a: ~a~%" limit (for/sum ((i (sequence-filter prime?/chowla (in-range 2 (add1 limit))))) 1)))
(for ((i (in-range 1 (add1 37)))) (printf "(chowla ~a) = ~a~%" i (chowla i)))
(make-chowla-sieve cache-size)
(for-each count-and-report-primes '(1000 10000 100000 1000000 10000000))
(let ((ns (for/list ((n (sequence-filter perfect?/chowla (in-range 2 35000000)))) n)))
(printf "There are ~a perfect numbers <= 35000000: ~a~%" (length ns) ns)))</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
cpu time: 23937 real time: 23711 gc time: 151
Primes < 1000: 168
Primes < 10000: 1229
Primes < 100000: 9592
Primes < 1000000: 78498
Primes < 10000000: 664579
There are 5 perfect numbers <= 35000000: (6 28 496 8128 33550336)</pre>
=={{header|Raku}}==
(formerly Perl 6)
Much like in the [[Totient_function|Totient function]] task, we are using a thing poorly suited to finding prime numbers, to find large quantities of prime numbers.
::: (From the task's author): the object is not in the ''finding'' of prime numbers, but in ''verifying'' that the Chowla function operates correctly (and '''can be''' used for such a purpose, whatever the efficacy). These types of comments belong in the ''discussion'' page. Whether or not this function is poorly suited for finding prime numbers (or anything else) is not part of this task's purpose or objective.
(For a more reasonable test, reduce the orders-of-magnitude range in the "Primes count" line from 2..7 to 2..5)
<syntaxhighlight lang="raku" line>sub comma { $^i.flip.comb(3).join(',').flip }
sub schnitzel (\Radda, \radDA = 0) {
Radda.is-prime ?? !Radda !! ?radDA ?? Radda
!! sum flat (2 .. Radda.sqrt.floor).map: -> \RAdda {
my \RADDA = Radda div RAdda;
next if RADDA * RAdda !== Radda;
RAdda !== RADDA ?? (RAdda, RADDA) !! RADDA
}
}
my \chowder = cache (1..Inf).hyper(:8degree).grep( !*.&schnitzel: 'panini' );
my \mung-daal = lazy gather for chowder -> \panini {
my \gazpacho = 2**panini - 1;
take gazpacho * 2**(panini - 1) unless schnitzel gazpacho, panini;
}
printf "chowla(%2d) = %2d\n", $_, .&schnitzel for 1..37;
say '';
printf "Count of primes up to %10s: %s\n", comma(10**$_),
comma chowder.first( * > 10**$_, :k) for 2..7;
say "\nPerfect numbers less than 35,000,000";
.&comma.say for mung-daal[^5];</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 1,000: 168
Count of primes up to 10,000: 1,229
Count of primes up to 100,000: 9,592
Count of primes up to 1,000,000: 78,498
Count of primes up to 10,000,000: 664,579
Perfect numbers less than 35,000,000
6
28
496
8,128
33,550,336
</pre>
=={{header|REXX}}==
<
parse arg LO HI . /*obtain optional arguments from the CL*/
if LO=='' | LO=="," then LO= 1 /*Not specified? Then use the default.*/
Line 784 ⟶ 4,687:
return s /*return " " " " " */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg _; do k=length(_)-3 to 1 by -3; _= insert(',', _, k); end; return _</
{{out|output|text= when using the input of: <tt> 1 37 </tt>}}
<pre>
Line 829 ⟶ 4,732:
number of primes found for the range 1 to 100 (inclusive) is: 25
</pre>
{{out|output|text= when using the input of: <tt> 1 -
<pre>
number of primes found for the range 1 to 1,000 (inclusive) is: 168
</pre>
{{out|output|text= when using the input of: <tt> 1 -
<pre>
number of primes found for the range 1 to 10,000 (inclusive) is: 1,229
</pre>
{{out|output|text= when using the input of: <tt> 1 -
<pre>
number of primes found for the range 1 to 100,000 (inclusive) is: 9,592
</pre>
{{out|output|text= when using the input of: <tt> 1 -
<pre>
number of primes found for the range 1 to 1,000,000 (inclusive) is: 78.498
</pre>
{{out|output|text= when using the input of: <tt> 1 -
<pre>
number of primes found for the range 1 to 10,000,000 (inclusive) is: 664,579
</pre>
{{out|output|text= when using the input of: <tt>
<pre>
number of primes found for the range 1 to 100,000,000 (inclusive) is: 5,761,455
</pre>
{{out|output|text= when using the input of: <tt> -1 35000000 </tt>}}
<pre>
6 is a perfect number.
Line 857 ⟶ 4,764:
33,550,336 is a perfect number.
</pre>
=={{header|Ruby}}==
{{trans|C}}
<syntaxhighlight lang="ruby">def chowla(n)
sum = 0
i = 2
while i * i <= n do
if n % i == 0 then
sum = sum + i
j = n / i
if i != j then
sum = sum + j
end
end
i = i + 1
end
return sum
end
def main
for n in 1 .. 37 do
puts "chowla(%d) = %d" % [n, chowla(n)]
end
count = 0
power = 100
for n in 2 .. 10000000 do
if chowla(n) == 0 then
count = count + 1
end
if n % power == 0 then
puts "There are %d primes < %d" % [count, power]
power = power * 10
end
end
count = 0
limit = 350000000
k = 2
kk = 3
loop do
p = k * kk
if p > limit then
break
end
if chowla(p) == p - 1 then
puts "%d is a perfect number" % [p]
count = count + 1
end
k = kk + 1
kk = kk + k
end
puts "There are %d perfect numbers < %d" % [count, limit]
end
main()</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 < 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.
<syntaxhighlight lang="scala">object ChowlaNumbers {
def main(args: Array[String]): Unit = {
println("Chowla Numbers...")
for(n <- 1 to 37){println(s"$n: ${chowlaNum(n)}")}
println("\nPrime Counts...")
for(i <- (2 to 7).map(math.pow(10, _).toInt)){println(f"$i%,d: ${primesPar(i).size}%,d")}
println("\nPerfect Numbers...")
print(perfectsPar(35000000).toVector.sorted.zipWithIndex.map{case (n, i) => f"${i + 1}%,d: $n%,d"}.mkString("\n"))
}
def primesPar(num: Int): ParVector[Int] = ParVector.range(2, num + 1).filter(n => chowlaNum(n) == 0)
def perfectsPar(num: Int): ParVector[Int] = ParVector.range(6, num + 1).filter(n => chowlaNum(n) + 1 == n)
def chowlaNum(num: Int): Int = Iterator.range(2, math.sqrt(num).toInt + 1).filter(n => num%n == 0).foldLeft(0){case (s, n) => if(n*n == num) s + n else s + n + (num/n)}
}</syntaxhighlight>
{{out}}
<pre>Chowla Numbers...
1: 0
2: 0
3: 0
4: 2
5: 0
6: 5
7: 0
8: 6
9: 3
10: 7
11: 0
12: 15
13: 0
14: 9
15: 8
16: 14
17: 0
18: 20
19: 0
20: 21
21: 10
22: 13
23: 0
24: 35
25: 5
26: 15
27: 12
28: 27
29: 0
30: 41
31: 0
32: 30
33: 14
34: 19
35: 12
36: 54
37: 0
Prime Counts...
100: 25
1,000: 168
10,000: 1,229
100,000: 9,592
1,000,000: 78,498
10,000,000: 664,579
Perfect Numbers...
1: 6
2: 28
3: 496
4: 8,128
5: 33,550,336</pre>
=={{header|Swift}}==
Uses Grand Central Dispatch to perform concurrent prime counting and perfect number searching
<syntaxhighlight lang="swift">import Foundation
@inlinable
public func chowla<T: BinaryInteger>(n: T) -> T {
stride(from: 2, to: T(Double(n).squareRoot()+1), by: 1)
.lazy
.filter({ n % $0 == 0 })
.reduce(0, {(s: T, m: T) in
m*m == n ? s + m : s + m + (n / m)
})
}
extension Dictionary where Key == ClosedRange<Int> {
subscript(n: Int) -> Value {
get {
guard let key = keys.first(where: { $0.contains(n) }) else {
fatalError("dict does not contain range for \(n)")
}
return self[key]!
}
set {
guard let key = keys.first(where: { $0.contains(n) }) else {
fatalError("dict does not contain range for \(n)")
}
self[key] = newValue
}
}
}
let lock = DispatchSemaphore(value: 1)
var perfect = [Int]()
var primeCounts = [
1...100: 0,
101...1_000: 0,
1_001...10_000: 0,
10_001...100_000: 0,
100_001...1_000_000: 0,
1_000_001...10_000_000: 0
]
for i in 1...37 {
print("chowla(\(i)) = \(chowla(n: i))")
}
DispatchQueue.concurrentPerform(iterations: 35_000_000) {i in
let chowled = chowla(n: i)
if chowled == 0 && i > 1 && i < 10_000_000 {
lock.wait()
primeCounts[i] += 1
lock.signal()
}
if chowled == i - 1 && i > 1 {
lock.wait()
perfect.append(i)
lock.signal()
}
}
let numPrimes = primeCounts
.sorted(by: { $0.key.lowerBound < $1.key.lowerBound })
.reduce(into: [(Int, Int)](), {counts, oneCount in
guard !counts.isEmpty else {
counts.append((oneCount.key.upperBound, oneCount.value))
return
}
counts.append((oneCount.key.upperBound, counts.last!.1 + oneCount.value))
})
for (upper, count) in numPrimes {
print("Number of primes < \(upper) = \(count)")
}
for p in perfect {
print("\(p) is a perfect number")
}
</syntaxhighlight>
{{out}}
<pre style="height: 20em; overflow: scroll">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
Number of primes < 100 = 25
Number of primes < 1000 = 168
Number of primes < 10000 = 1229
Number of primes < 100000 = 9592
Number of primes < 1000000 = 78498
Number of primes < 10000000 = 664579
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</pre>
=={{header|Visual Basic}}==
{{works with|Visual Basic|6}}
{{trans|Visual Basic .NET}}
<syntaxhighlight lang="vb">Option Explicit
Private Declare Function AllocConsole Lib "kernel32.dll" () As Long
Private Declare Function FreeConsole Lib "kernel32.dll" () As Long
Dim mStdOut As Scripting.TextStream
Function chowla(ByVal n As Long) As Long
Dim j As Long, i As Long
i = 2
Do While i * i <= n
j = n \ i
If n Mod i = 0 Then
chowla = chowla + i
If i <> j Then
chowla = chowla + j
End If
End If
i = i + 1
Loop
End Function
Function sieve(ByVal limit As Long) As Boolean()
Dim c() As Boolean
Dim i As Long
Dim j As Long
i = 3
ReDim c(limit - 1)
Do While i * 3 < limit
If Not c(i) Then
If (chowla(i) = 0) Then
j = 3 * i
Do While j < limit
c(j) = True
j = j + 2 * i
Loop
End If
End If
i = i + 2
Loop
sieve = c()
End Function
Sub Display(ByVal s As String)
Debug.Print s
mStdOut.Write s & vbNewLine
End Sub
Sub Main()
Dim i As Long
Dim count As Long
Dim limit As Long
Dim power As Long
Dim c() As Boolean
Dim p As Long
Dim k As Long
Dim kk As Long
Dim s As String * 30
Dim mFSO As Scripting.FileSystemObject
Dim mStdIn As Scripting.TextStream
AllocConsole
Set mFSO = New Scripting.FileSystemObject
Set mStdIn = mFSO.GetStandardStream(StdIn)
Set mStdOut = mFSO.GetStandardStream(StdOut)
For i = 1 To 37
Display "chowla(" & i & ")=" & chowla(i)
Next i
count = 1
limit = 10000000
power = 100
c = sieve(limit)
For i = 3 To limit - 1 Step 2
If Not c(i) Then
count = count + 1
End If
If i = power - 1 Then
RSet s = FormatNumber(power, 0, vbUseDefault, vbUseDefault, True)
Display "Count of primes up to " & s & " = " & FormatNumber(count, 0, vbUseDefault, vbUseDefault, True)
power = power * 10
End If
Next i
count = 0: limit = 35000000
k = 2: kk = 3
Do
p = k * kk
If p > limit Then
Exit Do
End If
If chowla(p) = p - 1 Then
RSet s = FormatNumber(p, 0, vbUseDefault, vbUseDefault, True)
Display s & " is a number that is perfect"
count = count + 1
End If
k = kk + 1
kk = kk + k
Loop
Display "There are " & CStr(count) & " perfect numbers <= 35.000.000"
mStdOut.Write "press enter to quit program."
mStdIn.Read 1
FreeConsole
End Sub</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 1.000 = 168
Count of primes up to 10.000 = 1.229
Count of primes up to 100.000 = 9.592
Count of primes up to 1.000.000 = 78.498
Count of primes up to 10.000.000 = 664.579
6 is a number that is perfect
28 is a number that is perfect
496 is a number that is perfect
8.128 is a number that is perfect
33.550.336 is a number that is perfect
There are 5 perfect numbers <= 35.000.000
press enter to quit program.</pre>
=={{header|Visual Basic .NET}}==
{{trans|Go}}
<
Module Program
Line 908 ⟶ 5,423:
If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey()
End Sub
End Module</
{{out}}
<pre>chowla(1) = 0
Line 958 ⟶ 5,473:
8,128 is a number that is perfect
33,550,336 is a number that is perfect
There are 5 perfect numbers <= 35,000,000
</pre>
===More Cowbell===
{{libheader|System.Numerics}}One can get a little further, but that 8th perfect number takes nearly a minute to verify. The 9th takes longer than I have patience. If you care to see the 9th and 10th perfect numbers, change the 31 to 61 or 89 where indicated by the comment.
<syntaxhighlight lang="vbnet">Imports System.Numerics
Module Program
Function chowla(n As Integer) As Integer
chowla = 0 : Dim j As Integer, i As Integer = 2
While i * i <= n
If n Mod i = 0 Then j = n / i : chowla += i : If i <> j Then chowla += j
i += 1
End While
End Function
Function chowla1(ByRef n As BigInteger, x As Integer) As BigInteger
chowla1 = 1 : Dim j As BigInteger, lim As BigInteger = BigInteger.Pow(2, x - 1)
For i As BigInteger = 2 To lim
If n Mod i = 0 Then j = n / i : chowla1 += i : If i <> j Then chowla1 += j
Next
End Function
Function sieve(ByVal limit As Integer) As Boolean()
Dim c As Boolean() = New Boolean(limit - 1) {}, i As Integer = 3
While i * 3 < limit
If Not c(i) AndAlso (chowla(i) = 0) Then
Dim j As Integer = 3 * i
While j < limit : c(j) = True : j += 2 * i : End While
End If : i += 2
End While
Return c
End Function
Sub Main(args As String())
For i As Integer = 1 To 37
Console.WriteLine("chowla({0}) = {1}", i, chowla(i))
Next
Dim count As Integer = 1, limit As Integer = CInt((10000000.0)), power As Integer = 100,
c As Boolean() = sieve(limit)
For i As Integer = 3 To limit - 1 Step 2
If Not c(i) Then count += 1
If i = power - 1 Then
Console.WriteLine("Count of primes up to {0,10:n0} = {1:n0}", power, count)
power = power * 10
End If
Next
count = 0
Dim p As BigInteger, k As BigInteger = 2, kk As BigInteger = 3
For i As Integer = 2 To 31 ' if you dare, change the 31 to 61 or 89
If {2, 3, 5, 7, 13, 17, 19, 31, 61, 89}.Contains(i) Then
p = k * kk
If chowla1(p, i) = p Then
Console.WriteLine("{0,25:n0} is a number that is perfect", p)
st = DateTime.Now
count += 1
End If
End If
k = kk + 1 : kk += k
Next
Console.WriteLine("There are {0} perfect numbers <= {1:n0}", count, 25 * BigInteger.Pow(10, 18))
If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey()
End Sub
End Module</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 1,000 = 168
Count of primes up to 10,000 = 1,229
Count of primes up to 100,000 = 9,592
Count of primes up to 1,000,000 = 78,498
Count of primes up to 10,000,000 = 664,579
6 is a number that is perfect
28 is a number that is perfect
496 is a number that is perfect
8,128 is a number that is perfect
33,550,336 is a number that is perfect
8,589,869,056 is a number that is perfect
137,438,691,328 is a number that is perfect
2,305,843,008,139,952,128 is a number that is perfect
There are 8 perfect numbers <= 25,000,000,000,000,000,000</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">fn chowla(n int) int {
if n < 1 {
panic("argument must be a positive integer")
}
mut sum := 0
for i := 2; i*i <= n; i++ {
if n%i == 0 {
j := n / i
if i == j {
sum += i
} else {
sum += i + j
}
}
}
return sum
}
fn sieve(limit int) []bool {
// True denotes composite, false denotes prime.
// Only interested in odd numbers >= 3
mut c := []bool{len: limit}
for i := 3; i*3 < limit; i += 2 {
if !c[i] && chowla(i) == 0 {
for j := 3 * i; j < limit; j += 2 * i {
c[j] = true
}
}
}
return c
}
fn main() {
for i := 1; i <= 37; i++ {
println("chowla(${i:2}) = ${chowla(i)}")
}
println('')
mut count := 1
mut limit := int(1e7)
c := sieve(limit)
mut power := 100
for i := 3; i < limit; i += 2 {
if !c[i] {
count++
}
if i == power-1 {
println("Count of primes up to ${power:-10} = $count")
power *= 10
}
}
println('')
count = 0
limit = 35000000
for i := 2; ; i++ {
p := (1 << (i -1)) * ((1<<i) - 1)
if p > limit {
break
}
if chowla(p) == p-1 {
println("$p is a perfect number")
count++
}
}
println("There are $count perfect numbers <= 35,000,000")
}</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 1,000 = 168
Count of primes up to 10,000 = 1,229
Count of primes up to 100,000 = 9,592
Count of primes up to 1,000,000 = 78,498
Count of primes up to 10,000,000 = 664,579
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 <= 35,000,000
</pre>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
import "./math" for Int, Nums
var chowla = Fn.new { |n| (n > 1) ? Nums.sum(Int.properDivisors(n)) - 1 : 0 }
for (i in 1..37) Fmt.print("chowla($2d) = $d", i, chowla.call(i))
System.print()
var count = 1
var limit = 1e7
var c = Int.primeSieve(limit, false)
var power = 100
var i = 3
while (i < limit) {
if (!c[i]) count = count + 1
if (i == power - 1) {
Fmt.print("Count of primes up to $,-10d = $,d", power, count)
power = power * 10
}
i = i + 2
}
System.print()
count = 0
limit = 35 * 1e6
i = 2
while (true) {
var p = (1 << (i -1)) * ((1<<i) - 1) // perfect numbers must be of this form
if (p > limit) break
if (chowla.call(p) == p-1) {
Fmt.print("$,d is a perfect number", p)
count = count + 1
}
i = i + 1
}
System.print("There are %(count) perfect numbers <= 35,000,000")</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 1,000 = 168
Count of primes up to 10,000 = 1,229
Count of primes up to 100,000 = 9,592
Count of primes up to 1,000,000 = 78,498
Count of primes up to 10,000,000 = 664,579
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|XPL0}}==
<syntaxhighlight lang="xpl0">func Chowla(N); \Return sum of divisors
int N, Div, Sum, Quot;
[Div:= 2; Sum:= 0;
loop [Quot:= N/Div;
if Quot < Div then quit;
if Quot = Div and rem(0) = 0 then \N is a square
[Sum:= Sum+Quot; quit];
if rem(0) = 0 then
Sum:= Sum + Div + Quot;
Div:= Div+1;
];
return Sum;
];
int N, C, P;
[for N:= 1 to 37 do
[IntOut(0, N); Text(0, ": ");
IntOut(0, Chowla(N)); CrLf(0);
];
C:= 1; \count 2 as prime
N:= 3; \only check odd numbers
repeat if Chowla(N) = 0 then \N is prime
C:= C+1;
case N+1 of 100, 1000, 10_000, 100_000, 1_000_000, 10_000_000:
[Text(0, "There are "); IntOut(0, C); Text(0, " primes < ");
IntOut(0, N+1); CrLf(0)]
other [];
N:= N+2;
until N >= 10_000_000;
P:= 1; \perfect numbers are of form: 2^(P-1) * (2^P - 1)
loop [P:= P*2;
N:= P*(P*2-1);
if N > 35_000_000 then quit;
if Chowla(N) = N-1 then \N is perfect
[IntOut(0, N); CrLf(0)];
];
]</syntaxhighlight>
{{out}}
<pre>
1: 0
2: 0
3: 0
4: 2
5: 0
6: 5
7: 0
8: 6
9: 3
10: 7
11: 0
12: 15
13: 0
14: 9
15: 8
16: 14
17: 0
18: 20
19: 0
20: 21
21: 10
22: 13
23: 0
24: 35
25: 5
26: 15
27: 12
28: 27
29: 0
30: 41
31: 0
32: 30
33: 14
34: 19
35: 12
36: 54
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
28
496
8128
33550336
</pre>
=={{header|zkl}}==
{{trans|Go}}
<syntaxhighlight lang="zkl">fcn chowla(n){
if(n<1)
throw(Exception.ValueError("Chowla function argument must be positive"));
sum:=0;
foreach i in ([2..n.toFloat().sqrt()]){
if(n%i == 0){
j:=n/i;
if(i==j) sum+=i;
else sum+=i+j;
}
}
sum
}
fcn chowlaSieve(limit){
// True denotes composite, false denotes prime.
// Only interested in odd numbers >= 3
c:=Data(limit+100).fill(0); # slop at the end (for reverse wrap around)
foreach i in ([3..limit/3,2]){
if(not c[i] and chowla(i)==0)
{ foreach j in ([3*i..limit,2*i]){ c[j]=True } }
}
c
}</syntaxhighlight>
<syntaxhighlight lang="zkl">fcn testChowla{
println("The first 37 Chowla numbers:\n",
[1..37].apply(chowla).concat(" ","[","]"), "\n");
count,limit,power := 1, (1e7).toInt(), 100;
c:=chowlaSieve(limit);
foreach i in ([3..limit-1,2]){
if(not c[i]) count+=1;
if(i == power - 1){
println("The count of the primes up to %10,d is %8,d".fmt(power,count));
power*=10;
}
}
println();
count, limit = 0, 35_000_000;
foreach i in ([2..]){
p:=(1).shiftLeft(i - 1) * ((1).shiftLeft(i)-1); // perfect numbers must be of this form
if(p>limit) break;
if(p-1 == chowla(p)){
println("%,d is a perfect number".fmt(p));
count+=1;
}
}
println("There are %,d perfect numbers <= %,d".fmt(count,limit));
}();</syntaxhighlight>
{{out}}
<pre>
The first 37 Chowla numbers:
[0 0 0 2 0 5 0 6 3 7 0 15 0 9 8 14 0 20 0 21 10 13 0 35 5 15 12 27 0 41 0 30 14 19 12 54 0]
The count of the primes up to 100 is 25
The count of the primes up to 1,000 is 168
The count of the primes up to 10,000 is 1,229
The count of the primes up to 100,000 is 9,592
The count of the primes up to 1,000,000 is 78,498
The count of the primes up to 10,000,000 is 664,579
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>
| |||