Chowla numbers

Chowla numbers are also known as:

Task
Chowla numbers
You are encouraged to solve this task according to the task description, using any language you may know.
  •   Chowla's function
  •   chowla numbers
  •   the chowla function
  •   the chowla number
  •   the chowla sequence



The chowla number of   n   is   (as defined by Chowla's function):

  •   the sum of the divisors of   n     excluding unity and   n
  •   where   n   is a positive integer


The sequence is named after   Sarvadaman D. S. Chowla,   (22 October 1907 ──► 10 December 1995),
a London born Indian American mathematician specializing in number theory.


German mathematician Carl Friedrich Gauss (1777─1855) said:

   "Mathematics is the queen of the sciences ─ and number theory is the queen of mathematics".


Definitions

Chowla numbers can also be expressed as:

   
   chowla(n) = sum of divisors of  n  excluding unity and  n
   chowla(n) = sum(       divisors(n))   - 1  -  n 
   chowla(n) = sum( properDivisors(n))   - 1       
   chowla(n) = sum(aliquotDivisors(n))   - 1        
   chowla(n) = aliquot(n)                - 1       
   chowla(n) = sigma(n)                  - 1  -  n 
   chowla(n) = sigmaProperDivisiors(n)   - 1       
 
   chowla(a*b) =  a + b,    if  a  and  b  are distinct primes
   if  chowla(n) =  0,       and n > 1,  then   n   is prime
   if  chowla(n) =  n - 1,  and n > 1,  then   n   is a perfect number
    
Task
  •   create a   chowla   function that returns the   chowla number   for a positive integer   n
  •   Find and display   (1 per line)   for the 1st   37   integers:
  •   the integer   (the index)
  •   the chowla number for that integer
  •   For finding primes, use the   chowla   function to find values of zero
  •   Find and display the   count   of the primes up to              100
  •   Find and display the   count   of the primes up to           1,000
  •   Find and display the   count   of the primes up to         10,000
  •   Find and display the   count   of the primes up to       100,000
  •   Find and display the   count   of the primes up to    1,000,000
  •   Find and display the   count   of the primes up to  10,000,000
  •   For finding perfect numbers, use the   chowla   function to find values of   n - 1
  •   Find and display all   perfect numbers   up to   35,000,000
  •   use commas within appropriate numbers
  •   show all output here



Related tasks


See also



11lEdit

Translation of: C
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)
Output:
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

AdaEdit

Translation of: C
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;
Output:
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

ALGOL 68Edit

Translation of: C
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
Output:
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

ArturoEdit

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
]
Output:
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

AWKEdit

# 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
        }
      }
    }
}
Output:
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

CEdit

#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;
}
Output:
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

C#Edit

Translation of: Go
using System;

namespace chowla_cs
{
    class Program
    {
        static int chowla(int n)
        {
            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;
        }

        static bool[] sieve(int limit)
        {
            // True denotes composite, false denotes prime.
            // Only interested in odd numbers >= 3
            bool[] 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;
        }

        static void Main(string[] args)
        {
            for (int i = 1; i <= 37; i++)
                Console.WriteLine("chowla({0}) = {1}", i, chowla(i));
            int count = 1, limit = (int)(1e7), power = 100;
            bool[] c = sieve(limit);
            for (int i = 3; i < limit; i += 2)
            {
                if (!c[i]) count++;
                if (i == power - 1)
                {
                    Console.WriteLine("Count of primes up to {0,10:n0} = {1:n0}", power, count);
                    power *= 10;
                }
            }

            count = 0; limit = 35000000;
            int k = 2, kk = 3, p;
            for (int i = 2; ; i++)
            {
                if ((p = k * kk) > limit) break;
                if (chowla(p) == p - 1)
                {
                    Console.WriteLine("{0,10:n0} is a number that is perfect", p);
                    count++;
                }
                k = kk + 1; kk += k;
            }
            Console.WriteLine("There are {0} perfect numbers <= 35,000,000", count);
            if (System.Diagnostics.Debugger.IsAttached) Console.ReadKey();
        }
    }
}
Output:
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

C++Edit

Translation of: Go
#include <vector>
#include <iostream>

using namespace std;

int chowla(int n)
{
	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;
}

vector<bool> sieve(int limit)
{
	// True denotes composite, false denotes prime.
	// Only interested in odd numbers >= 3
	vector<bool> c(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;
}

int main()
{
	cout.imbue(locale(""));
	for (int i = 1; i <= 37; i++)
		cout << "chowla(" << i << ") = " << chowla(i) << "\n";
	int count = 1, limit = (int)(1e7), power = 100;
	vector<bool> c = sieve(limit);
	for (int i = 3; i < limit; i += 2)
	{
		if (!c[i]) count++;
		if (i == power - 1)
		{
			cout << "Count of primes up to " << power << " = "<< count <<"\n";
			power *= 10;
		}
	}

	count = 0; limit = 35000000;
	int k = 2, kk = 3, p;
	for (int i = 2; ; i++)
	{
		if ((p = k * kk) > limit) break;
		if (chowla(p) == p - 1)
		{
			cout << p << " is a number that is perfect\n";
			count++;
		}
		k = kk + 1; kk += k;
	}
	cout << "There are " << count << " perfect numbers <= 35,000,000\n";
	return 0;
}
Output:
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

CLUEdit

% 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
Output:
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.

CowgolEdit

Translation of: C
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();
Output:
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

DEdit

Translation of: C#
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);
}
Output:
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

DelphiEdit

See #Pascal.

DyalectEdit

Translation of: C#
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")
Output:
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

EasyLangEdit

Translation of: Go
func chowla n . sum .
  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
  .
.
func sieve . c[] .
  i = 3
  while i * 3 <= len c[]
    if c[i] = 0
      call chowla i h
      if h = 0
        j = 3 * i
        while j <= len c[]
          c[j] = 1
          j += 2 * i
        .
      .
    .
    i += 2
  .
.
func 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
  call chowla i h
  print "  " & i & ": " & h
.
func main . .
  print ""
  len c[] 10000000
  count = 1
  call sieve c[]
  power = 100
  i = 3
  while i <= len c[]
    if c[i] = 0
      count += 1
    .
    if i = power - 1
      call commatize power p$
      call 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
    call chowla p h
    if h = p - 1
      call commatize p s$
      print s$ & " is a perfect number"
      count += 1
    .
    k = kk + 1
    kk += k
    i += 1
  .
  call commatize limit s$
  print "There are " & count & " perfect mumbers up to " & s$
.
call main
Output:
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

FactorEdit

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
Output:
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

FreeBASICEdit

Translation of: Visual Basic
' 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
Output:
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

GoEdit

package main

import "fmt"

func chowla(n int) int {
    if n < 1 {
        panic("argument must be a positive integer")
    }
    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
}

func sieve(limit int) []bool {
    // True denotes composite, false denotes prime.
    // Only interested in odd numbers >= 3
    c := make([]bool, 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
}

func commatize(n int) string {
    s := fmt.Sprintf("%d", n)
    le := len(s)
    for i := le - 3; i >= 1; i -= 3 {
        s = s[0:i] + "," + s[i:]
    }
    return s
}

func main() {
    for i := 1; i <= 37; i++ {
        fmt.Printf("chowla(%2d) = %d\n", i, chowla(i))
    }
    fmt.Println()

    count := 1
    limit := int(1e7)
    c := sieve(limit)
    power := 100
    for i := 3; i < limit; i += 2 {
        if !c[i] {
            count++
        }
        if i == power-1 {
            fmt.Printf("Count of primes up to %-10s = %s\n", commatize(power), commatize(count))
            power *= 10
        }
    }

    fmt.Println()
    count = 0
    limit = 35000000
    for i := uint(2); ; i++ {
        p := 1 << (i - 1) * (1<<i - 1) // perfect numbers must be of this form
        if p > limit {
            break
        }
        if chowla(p) == p-1 {
            fmt.Printf("%s is a perfect number\n", commatize(p))
            count++
        }
    }
    fmt.Println("There are", count, "perfect numbers <= 35,000,000")
}
Output:
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

GroovyEdit

Translation of: Kotlin
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)
    }
}
Output:
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

HaskellEdit

Uses arithmoi Library: https://hackage.haskell.org/package/arithmoi-0.11.0.0 compiled with "-O2 -threaded -rtsopts"

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]
Output:
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

JEdit

Solution:

chowla=: >: -~ >:@#.~/.~&.q:     NB. sum of factors - (n + 1)

intsbelow=: (2 }. i.)"0
countPrimesbelow=: +/@(0 = chowla)@intsbelow
findPerfectsbelow=: (#~ <: = chowla)@intsbelow

Tasks:

   (] ,. 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

JavaEdit

Translation of: C
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;
    }
}
Output:
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

jqEdit

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.

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
Output:
  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

JuliaEdit

using Primes, Formatting

function chowla(n)
    if n < 1
        throw("Chowla function argument must be positive")
    elseif n < 4
        return zero(n)
    else
        f = [one(n)]
        for (p,e) in factor(n)
            f = reduce(vcat, [f*p^j for j in 1:e], init=f)
        end
        return sum(f) - one(n) - n
    end
end

function countchowlas(n, asperfect=false, verbose=false)
    count = 0
    for i in 2:n  # 1 is not prime or perfect so skip
        chow = chowla(i)
        if (asperfect && chow == i - 1) || (!asperfect && chow == 0)
            count += 1
            verbose && println("The number $(format(i, commas=true)) is ", asperfect ? "perfect." : "prime.")
        end
    end
    count
end

function testchowla()
    println("The first 37 chowla numbers are:")
    for i in 1:37
        println("Chowla($i) is ", chowla(i))
    end
    for i in [100, 1000, 10000, 100000, 1000000, 10000000]
        println("The count of the primes up to $(format(i, commas=true)) is $(format(countchowlas(i), commas=true))")
    end
    println("The count of perfect numbers up to 35,000,000 is $(countchowlas(35000000, true, true)).")
end

testchowla()
Output:
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 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
The number 6 is perfect.
The number 28 is perfect.
The number 496 is perfect.
The number 8,128 is perfect.
The number 33,550,336 is perfect.
The count of perfect numbers up to 35,000,000 is 5.

KotlinEdit

Translation of: Go
// 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 power = 100
    for (i in 3 until limit step 2) {
        if (!c[i]) count++
        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")
}
Output:
Same as Go example.

LuaEdit

Translation of: D
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()
Output:
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

MADEdit

Translation of: C
            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
Output:
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

MapleEdit

This example is incorrect. Please fix the code and remove this message.
Details:

The output for Chowla(1) is incorrect.

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)
Output:
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]

Mathematica / Wolfram LanguageEdit

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]]
Output:
25
168
1229
9592
78498
664579
{1, 6, 28, 496, 8128, 33550336}

NimEdit

Translation of: C
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, ',')}"
Output:
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

PascalEdit

Works with: Free Pascal
Works with: Delphi
Translation of: Go
but not using a sieve, cause a sieve doesn't need precalculated small primes.

So runtime is as bad as trial division.

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.
Output:
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

PerlEdit

Library: ntheory
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);
Output:
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

There are 5 perfect numbers up to 35,000,000: 6 28 496 8,128 33,550,336

PhixEdit

function chowla(atom n)
    return sum(factors(n))
end function
 
function sieve(integer limit)
    -- True denotes composite, false denotes prime.
    -- Only interested in odd numbers >= 3
    sequence c = repeat(false,limit)
    for i=3 to floor(limit/3) by 2 do
--      if not c[i] and chowla(i)==0 then
        if not c[i] then -- (see note below)
            for j=3*i to limit by 2*i do
                c[j] = true
            end for
        end if
    end for
    return c
end function
 
atom limit = 1e7, count = 1, pow10 = 100, t0 = time()
sequence s = {}
for i=1 to 37 do
    s &= chowla(i)
end for
printf(1,"chowla[1..37]: %V\n",{s})
s = sieve(limit)
for i=3 to limit by 2 do
    if not s[i] then count += 1 end if
    if i==pow10-1 then
        printf(1,"Count of primes up to %,d = %,d\n", {pow10, count})
        pow10 *= 10
    end if
end for
 
count = 0
limit = iff(machine_bits()=32?1.4e11:2.4e18)
--limit = power(2,iff(machine_bits()=32?53:64)) -- (see note below)
integer i=2
while true do
    atom p = power(2,i-1)*(power(2,i)-1) -- perfect numbers must be of this form
    if p>limit then exit end if
    if chowla(p)==p-1 then
        printf(1,"%,d is a perfect number\n", p)
        count += 1
    end if
    i += 1
end while
printf(1,"There are %d perfect numbers <= %,d\n",{count,limit})
?elapsed(time()-t0)

The use of chowla() in sieve() does not actually achieve anything other than slow it down, so I took it out.

Output:
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

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.

PicatEdit

Translation of: Prolog
Works with: 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).
Output:
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.

PicoLispEdit

(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))
Output:
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)

PowerBASICEdit

This example is incorrect. Please fix the code and remove this message.
Details:

The 8th perfect number is off by 2   (it is too high),
it should end in   ... 952,128
Translation of: Visual Basic .NET
#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
Output:
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

PrologEdit

Works with: SWI 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]).
Output:
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.

PythonEdit

Uses underscores to separate digits in numbers, and th sympy library to aid calculations.

# https://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.factor_.divisors
from sympy import divisors

def chowla(n):
    return 0 if n < 2 else sum(divisors(n, generator=True)) - 1 -n

def is_prime(n):
    return chowla(n) == 0

def primes_to(n):
    return sum(chowla(i) == 0 for i in range(2, n))

def perfect_between(n, m):
    c = 0
    print(f"\nPerfect numbers between [{n:_}, {m:_})")
    for i in range(n, m):
        if i > 1 and chowla(i) == i - 1:
            print(f"  {i:_}")
            c += 1
    print(f"Found {c} Perfect numbers between [{n:_}, {m:_})")
    

if __name__ == '__main__':
    for i in range(1, 38):
        print(f"chowla({i:2}) == {chowla(i)}")
    for i in range(2, 6):
        print(f"primes_to({10**i:_}) == {primes_to(10**i):_}")
    perfect_between(1, 1_000_000)
    print()
    for i in range(6, 8):
        print(f"primes_to({10**i:_}) == {primes_to(10**i):_}")
    perfect_between(1_000_000, 35_000_000)
Output:
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
primes_to(100) == 25
primes_to(1_000) == 168
primes_to(10_000) == 1_229
primes_to(100_000) == 9_592

Perfect numbers between [1, 1_000_000)
  6
  28
  496
  8_128
Found 4 Perfect numbers between [1, 1_000_000)

primes_to(1_000_000) == 78_498
primes_to(10_000_000) == 664_579

Perfect numbers between [1_000_000, 35_000_000)
  33_550_336
Found 1 Perfect numbers between [1_000_000, 35_000_000)

Python: NumbaEdit

(Elementary) use of the numba library needs

  • library install and import
  • use of `@jit` decorator on some functions
  • Rewrite to remove use of `sum()`
  • Splitting one function for the jit compiler to digest.
from numba import jit

# https://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.factor_.divisors
from sympy import divisors

@jit
def chowla(n):
    return 0 if n < 2 else sum(divisors(n, generator=True)) - 1 -n

@jit
def is_prime(n):
    return chowla(n) == 0

@jit
def primes_to(n):
    acc = 0
    for i in range(2, n):
        if chowla(i) == 0:
            acc += 1
    return acc

@jit
def _perfect_between(n, m):
    for i in range(n, m):
        if i > 1 and chowla(i) == i - 1:
            yield i

def perfect_between(n, m):
    c = 0
    print(f"\nPerfect numbers between [{n:_}, {m:_})")
    for i in _perfect_between(n, m):
        print(f"  {i:_}")
        c += 1
    print(f"Found {c} Perfect numbers between [{n:_}, {m:_})")
Output:

Same as above for use of same __main__ block.

Speedup - not much, subjectively...

RacketEdit

#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)))
Output:
(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)

RakuEdit

(formerly Perl 6) Much like in the 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)

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];
Output:
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

REXXEdit

/*REXX program computes/displays chowla numbers (and may count primes & perfect numbers.*/
parse arg LO HI .                                /*obtain optional arguments from the CL*/
if LO=='' | LO==","  then LO=  1                 /*Not specified?  Then use the default.*/
perf= LO<0;               LO= abs(LO)            /*Negative?  Then determine if perfect.*/
if HI=='' | HI==","  then HI= LO                 /*Not specified?  Then use the default.*/
prim= HI<0;               HI= abs(HI)            /*Negative?  Then determine if a prime.*/
numeric digits max(9, length(HI) + 1 )           /*use enough decimal digits for   //   */
w= length( commas(HI) )                          /*W:   used in aligning output numbers.*/
tell= \(prim | perf)                             /*set boolean value for showing chowlas*/
p= 0                                             /*the number of primes found  (so far).*/
     do j=LO  to HI;       #= chowla(j)          /*compute the  cholwa number  for  J.  */
     if tell  then say right('chowla('commas(j)")", w+9)    ' = '    right( commas(#), w)
              else if #==0  then if j>1  then p= p+1
     if perf  then if j-1==# & j>1  then say right(commas(j), w)   ' is a perfect number.'
     end   /*j*/

if prim & \perf  then say 'number of primes found for the range '   commas(LO)    " to " ,
                           commas(HI)        " (inclusive)  is: "   commas(p)
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
chowla: procedure; parse arg x;         if x<2  then return 0;          odd= x // 2
        s=0                                      /* [↓]  use EVEN or ODD integers.   ___*/
            do k=2+odd  by 1+odd  while k*k<x    /*divide by all the integers up to √ X */
            if x//k==0  then  s=s + k + x%k      /*add the two divisors to the sum.     */
            end   /*k*/                          /* [↓]  adkust for square.          ___*/
        if k*k==x  then  s=s + k                 /*Was  X  a square?    If so, add  √ X */
        return s                                 /*return     "     "    "      "     " */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg _;  do k=length(_)-3  to 1  by -3; _= insert(',', _, k); end;   return _
output   when using the input of:     1     37
  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
output   when using the input of:     1     -100
number of primes found for the range  1  to  100  (inclusive)  is:  25
output   when using the input of:     1     -1000
number of primes found for the range  1  to  1,000  (inclusive)  is:  168
output   when using the input of:     1     -10000
number of primes found for the range  1  to  10,000  (inclusive)  is:  1,229
output   when using the input of:     1     -100000
number of primes found for the range  1  to  100,000  (inclusive)  is:  9,592
output   when using the input of:     1     -1000000
number of primes found for the range  1  to  1,000,000  (inclusive)  is:  78.498
output   when using the input of:     1     -10000000
number of primes found for the range  1  to  10,000,000  (inclusive)  is:  664,579
output   when using the input of:     1     -100000000
number of primes found for the range  1  to  100,000,000  (inclusive)  is:  5,761,455
output   when using the input of:     -1     35000000
         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.

RubyEdit

Translation of: C
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()
Output:
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

ScalaEdit

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.

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)}
}
Output:
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

SwiftEdit

Uses Grand Central Dispatch to perform concurrent prime counting and perfect number searching

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")
}
Output:
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

Visual BasicEdit

Works with: Visual Basic version 6
Translation of: Visual Basic .NET
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
Output:
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.

Visual Basic .NETEdit

Translation of: Go
Imports System

Module Program
    Function chowla(ByVal n As Integer) As Integer
        chowla = 0 : Dim j As Integer, i As Integer = 2
        While i * i <= n
            j = n / i : If n Mod i = 0 Then chowla += i + (If(i = j, 0, j))
            i += 1
        End While
    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 : limit = 35000000
        Dim p As Integer, k As Integer = 2, kk As Integer = 3
        While True
            p = k * kk : If p > limit Then Exit While
            If chowla(p) = p - 1 Then
                Console.WriteLine("{0,10:n0} is a number that is perfect", p)
                count += 1
            End If
            k = kk + 1 : kk += k
        End While
        Console.WriteLine("There are {0} perfect numbers <= 35,000,000", count)
        If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey()
    End Sub
End Module
Output:
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

More CowbellEdit

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.
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
Output:
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

V (Vlang)Edit

Translation of: Go
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")
}
Output:
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

WrenEdit

Library: Wren-fmt
Library: Wren-math
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")
Output:
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

XPL0Edit

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)];
        ];
]
Output:
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

zklEdit

Translation of: Go
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
}
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));
}();
Output:
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