# Perl Weekly Challenge 109: Chowla Numbers

by Abigail

## Challenge

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


### Output

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


## Discussion

Another glorified Hello, World! program!

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

1. Just print the 20 required numbers, as given in the challenge.
2. Fetch the right sequence from the OEIS, extract the first 20 numbers, and print those.
3. 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.

## Solutions

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.

### Perl

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.

### AWK

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.

### Bash

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.

### C

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.

### Lua

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.

### Node.js

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.

### Python

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.

### Ruby

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.

### Other languages

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.

Please leave any comments as a GitHub issue.