Write a script to generate first 20 Chowla Numbers, named after, Sarvadaman D. S. Chowla, a London born Indian American mathematician. It is defined as:

`C(n) = sum of divisors of n except 1 and n`

`0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21`

Another glorified `Hello, World!`

program!

Just like in last weeks challenge, we have three options to solve this:

- Just print the 20 required numbers, as given in the challenge.
- Fetch the right sequence from the OEIS, extract the first 20 numbers, and print those.
- Calculate the numbers.

In all the languages we provide solutions in, we at least implement the first strategy. For Perl, we also implement the second strategy. And for a handful of languages, we also implement the last strategy.

The solutions implementing multiple strategies take command line
argument, indiciting which strategy to use. This argument is one
off: `plain`

(for the first strategy), `fetch`

(for the second
strategy), or `compute`

(for the third). If no argument is given,
an argument which isn't recognized, or one which isn't implemented,
the solution falls back to the first strategy.

We will only discuss solutions implementing the third strategy; that is, actually computing the numbers.

Summing the divisors of a number \(N\) is at least as hard as factorizing \(N\), which is a hard problem.

For non-quantum computers, as of this writing, the best know algorithm takes

\[ \exp\left( \left(\sqrt[3]{\frac{64}{9}} + \mathcal{o} (1)\right) (\ln N)^{\frac{1}{3}}(\ln \ln N)^{\frac{2}{3}}\right) \]

time to factor a number \(N\), using a general number field sieve.

(For quantum computers, Shor's algorithm can factor a number \(N\) in \(\mathcal{O} \left((\ln N)^3\right)\) time, using \(\mathcal{O} \left((\ln N)^2(\ln \ln N)(\ln \ln \ln N)\right)\) quantum gates.)

Luckily, we don't have to do anything hard. No deep math, nor a quantum computer. After all, we don't have to solve the general case, we only have compute the Chowla Number for a handful of tiny integers.

So, for a number \(N\), we just check all numbers \(k: 1 < k \leq \frac{N}{2}\) to see if they evenly divide \(N\), and sum those that do. That's only 81 modulo operations.

In most, but not all, solutions, we create a method called
`divisor_sum`

, which takes a single argument, and returns the
sum of the proper divisors (except `1`

and the number itselfs)
of the passed in number.

```
my $COUNT = 20;
use List::Util qw [sum0];
$, = ", ";
say map {my $n = $_; sum0 grep {!($n % $_)} 2 .. $_ / 2} 1 .. $COUNT;
```

Here the `map`

takes each number from `1`

to `20`

, and calculates
the Chowla Number for it. To do so, given a number `$n`

, we `grep`

the
numbers which evenly divide `$n`

(by checking if the modulo is 0).
The `grep`

returns a, possibly empty, list, which we sum using `sum0`

from the `List::Util`

module. `sum0`

returns `0`

when summing
an empty list.

Find the full program on GitHub.

The `divisor_sum`

method:

```
function divisor_sum (n, i) {
sum = 0
for (i = 2; i <= n / 2; i ++) {
if (n % i == 0) {
sum += i
}
}
return (sum)
}
```

The second argument, `i`

, is not used; that is, when we call the
method we only pass in a single argument. But this is AWKs way of
creating a lexical variable in the body of the method.

We then call `divisor_sum`

20 times, and print the results,
separated by commas:

```
COUNT = 20
for (i = 1; i <= COUNT; i ++) {
if (i > 1) {
printf ", ";
}
printf "%d", divisor_sum(i)
}
printf "\n";
```

Find the full program on GitHub.

The `divisor_sum`

method:

```
function divisor_sum () {
local n=$1
sum=0
local i
for ((i = 2; i <= n / 2; i ++))
do if ((n % i == 0))
then ((sum += i))
fi
done
}
```

Note that in Bash, function arguments are available in the function
as `$1`

, `$2`

, ... etc. The result is passed back using the global
variable `$sum`

.

Calling `divisor_sum`

20 times, and printing the results, separated
by commas:

```
COUNT=20
for ((n = 1; n <= COUNT; n ++))
do if ((n > 1))
then printf ", "
fi
divisor_sum $n
printf $sum
done
echo ""
```

Find the full program on GitHub.

For once, our C solution is hardly larger than solutions in other
language: we don't have to `malloc`

memory.

The `divisor_sum`

method:

```
typedef int number;
number divisor_sum (number n) {
number sum = 0;
for (number i = 2; i <= n / 2; i ++) {
if (!(n % i)) {
sum += i;
}
}
return (sum);
}
```

We're using a `typedef`

to create a type `number`

. If we would ever need
to expand this to deal with larger numbers, we can change the typedef
so `number`

is an alias for a `long`

or `long long`

. We would only have
to make the change in one location.

Calling `divisor_sum`

and printing the results:

```
# define COUNT 20
# define fmt "%d" /* Change if the typedef changes */
for (number i = 1; i <= COUNT; i ++) {
if (i != 1) {
printf (", ");
}
printf (fmt, divisor_sum (i));
}
printf ("\n");
```

Find the full program on GitHub.

No `+=`

in Lua. Other than that, it's pretty straightforward:

```
function divisor_sum (n)
local sum = 0
for i = 2, n / 2 do
if n % i == 0
then sum = sum + i
end
end
return (sum)
end
```

Main loop:

```
local COUNT = 20
for n = 1, COUNT do
if n > 1
then io . write (", ")
end
io . write (divisor_sum (n))
end
io . write ("\n")
```

Find the full program on GitHub.

In Node.js, we need to explicitly round the division, otherwise, we get a type error. Other than that, the method is very similar to solutions in the other languages.

```
function divisor_sum (n) {
let sum = 0
for (let i = 2; i <= Math . floor (n / 2); i ++) {
if (n % i == 0) {
sum += i
}
}
return (sum)
}
```

Calling the method and printing the results:

```
let COUNT = 20
for (let i = 1; i <= COUNT; i ++) {
if (i > 1) {
process . stdout . write (", ")
}
process . stdout . write (divisor_sum (i) . toString ())
}
process . stdout . write ("\n")
```

Find the full program on GitHub.

Pythons whitespace rules make for more compact code:

```
def divisor_sum (n):
sum = 0
for i in range (2, n / 2 + 1):
if n % i == 0:
sum = sum + i
return (sum)
```

Main loop:

```
COUNT = 20
for n in range (1, COUNT + 1):
if n > 1:
print (", ", end = '')
print (divisor_sum (n), end = '')
print ("")
```

Find the full program on GitHub.

```
def divisor_sum (n)
sum = 0
for i in 2 .. n / 2
if n % i == 0
then sum += i
end
end
return sum
end
```

Main loop:

```
for n in 1 .. COUNT
if n > 1
then print (", ")
end
print divisor_sum (n)
end
puts ("")
```

Find the full program on GitHub.

We also have simple solutions for BASIC, bc, Befunge-93, Cobol, Csh, Erlang, Forth, Fortran, Go, Java, m4, OCaml, Pascal, PHP, PostScript, R, Rexx, Scheme, sed, SQL, and Tcl.