Perl Weekly Challenge 109: Chowla Numbers

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.

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;

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

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