Perl Weekly Challenge 109: Chowla Numbers and Four Square Puzzle
These are some answers to the Week 109 of the Perl Weekly Challenge organized by Mohammad S. Anwar.
Spoiler Alert: This weekly challenge deadline is due in a few days (April 25, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.
Task 1: Chowla Numbers
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
Originally, the task requested us to generate the first 37 Chowla numbers and I wrote implementations in 12 different languages based on that requirement. This requirement has now been amended to the first 20 Chowla numbers. I’ll fix the program and output for some implementations, but will leave some as they were developed.
Chowla Numbers in Raku
For each number $n between 1 and 20, we print 0 if the number is less than 2 or if it is prime. Otherwise, we look for divisors of that number between 2 and $n / 2 (thereby excluding 1 and the number $n itself) and compute the sum of the divisors.
use v6;
sub chowla (Int $n) {
return 0 if $n < 2 or $n.is-prime;
return (2..$n div 2).grep({$n %% $_}).sum;
}
say "$_\t", chowla $_ for 1..20;
Note that for the first implementation of this task, I decided to print the source number and the Chowla number over two columns to make result checking easier. All other implementations will be printed over a single line for brevity. So this is our output over two columns:
$ raku ./chowla.raku
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
Chowla Numbers in Perl
Perl doesn’t have a built-in sum method as Raku, so I’ll compute the sums by hand (I know that there are modules doing that, but, as I have pointed out many times already, I do not want to use external libraries as I consider this would go against the true spirit of a coding challenge).
use strict;
use warnings;
use feature "say";
sub chowla {
my $n = shift;
return 0 if $n <= 2;
my @divisors = grep {$n % $_== 0} 2..($n / 2);
my $sum = 0;
$sum += $_ for @divisors;
return $sum;
}
say join ", ", map { chowla $_} 1..20;
This displays the following output.
$ perl chowla.pl
0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21
Chowla Numbers in Other Languages
Note that I don’t consider the example output provided with the task description to be part of the requirement. In some cases, I’ll output the values separated by commas, in others simply by a space. And since I do not want to test again all the programs below (for some, I would have to go on another computer), I’ll stick to the original requirement of the first 37 Chowla numbers for some of the programs below.
Chowla Numbers in Scala
Rather than storing the divisors in an array as I did in Perl, I just accumulate them into a sum variable. Note that in Scala, to get all integers between 1 and 20, you need to use 1 until 21, since the upper bound is not included in the range.
object chowla extends App {
def chowla(n: Int): Int = {
if (n <= 2) return 0
var sum = 0;
for (i <- 2 until n/2 + 1) {
if (n % i == 0) sum += i
}
return sum
}
println((1 until 21).map(chowla(_)).mkString(", "))
}
Output:
0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21
Chowla Numbers in C
#include <stdio.h>
int chowla(int n) {
int sum = 0;
for (int i = 2; i <= n/2; i++) {
if (n % i == 0) {
sum += i;
}
}
return sum;
}
int main() {
for (int n = 1; n <= 37; n++) {
printf("%i ", chowla(n));
}
printf("\n");
}
Output:
$ ./a.out
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
Chowla Numbers in Python
Here again (as in Scala), to get all integers between 1 and 20, you need to use range(1, 21), since the upper bound is not included in the range.
def chowla(n):
sum = 0
for i in range(2, int(n/2) +1):
if n % i == 0:
sum += i
return sum
chowla_nums = []
for m in range (1, 21):
chowla_nums.append (chowla(m))
print(chowla_nums)
Output:
[0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21]
Chowla Numbers in Awk
Very straight forward. Here, we are printing the 20th Chowla number separately to print a new line and avoid terminating the line with a comma.
function chowla(num) {
sum = 0
for (i = 2; i <= n/2; i++) {
if (n % i == 0) {
sum += i;
}
}
return sum;
}
BEGIN {
for (n = 1; n <= 19; n++) {
printf("%i, ", chowla(n));
}
printf("%i\n", chowla(20));
}
Output:
$ awk -f chowla.awk
0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21
Chowla in Julia
An interesting feature of Julia is that you can use Unicode letters in identifiers for variables or functions. Here we use capital Greek letter ∑ for our sum variable:
function chowla(n)
∑ = 0
for i = 2:(trunc(Int, n/2))
if (n % i == 0) ∑ += i end
end
return ∑
end
for n = 1:37 print(chowla(n), " ") end
Output:
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
Chowla in Rust
fn chowla(n : i32) -> i32 {
let mut sum = 0;
for i in 2..=n/2 {
if n % i == 0 {
sum += i
}
}
return sum
}
fn main() {
for n in 1..20 {
print!("{}, ", chowla(n));
}
println!("{} ", chowla(20));
}
Output:
0, 0, 0, 2, 0, 5, 0, 6, 3, 7, 0, 15, 0, 9, 8, 14, 0, 20, 0, 21
Chowla in Go
package main
import "fmt"
func chowla(n int) int {
var sum int = 0
for i := 2; i <= n/2; i++ {
if (n % i == 0) {
sum += i;
}
}
return sum;
}
func main() {
const MAX int = 37
for i := 1; i <= MAX; i++ {
fmt.Print(chowla(i), " ")
}
}
Output:
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
Chowla in Pascal
program chowla;
const
max = 37;
var
j, res : integer;
function chowla(n: integer): integer;
var
i, sum, rounded_half: integer;
begin
sum := 0;
rounded_half := round(n/2);
for i := 2 to rounded_half do
begin
if (n mod i = 0) then
sum := sum + i
end;
chowla := sum;
end;
begin
for j := 1 to max do
begin
write(chowla(j), ' ');
end;
writeln(' ');
end.
Output:
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
Chowla in D
import std.stdio;
int chowla(int n) {
int sum = 0;
for (int i = 2; i <= n-1; i++) {
if (n % i == 0) {
sum += i;
}
}
return sum;
}
void main() {
for (int n = 1; n <= 37; n++) {
writef("%d ", chowla(n));
}
writeln("");
}
Output:
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
Chowla in Ruby
def chowla (n)
sum = 0
for i in 2..n/2
if n % i == 0
sum += i
end
end
return sum;
end
max = 37
results = []
for n in 1..max
results[n-1] = chowla(n)
end
puts "The #{max} first Chowla numbers are: #{results.join(" ")}"
Output:
The 37 first Chowla numbers are: 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
Task 2: Four Squares Puzzle
You are given four squares as below with numbers named a,b,c,d,e,f,g.
(1) (3)
╔══════════════╗ ╔══════════════╗
║ ║ ║ ║
║ a ║ ║ e ║
║ ║ (2) ║ ║ (4)
║ ┌───╫──────╫───┐ ┌───╫─────────┐
║ │ ║ ║ │ │ ║ │
║ │ b ║ ║ d │ │ f ║ │
║ │ ║ ║ │ │ ║ │
║ │ ║ ║ │ │ ║ │
╚══════════╪═══╝ ╚═══╪══════╪═══╝ │
│ c │ │ g │
│ │ │ │
│ │ │ │
└──────────────┘ └─────────────┘
Write a script to place the given unique numbers in the square box so that sum of numbers in each box is the same.
Example:
Input: 1,2,3,4,5,6,7
Output:
a = 6
b = 4
c = 1
d = 5
e = 2
f = 3
g = 7
Box 1: a + b = 6 + 4 = 10
Box 2: b + c + d = 4 + 1 + 5 = 10
Box 3: d + e + f = 5 + 2 + 3 = 10
Box 4: f + g = 3 + 7 = 10
The example in the task description provides only one solution to the puzzle, but there may be several solutions (most solutions will have a symmetrical one, because of the symmetry of the figure with the squares). In my original implementation in Raku, I stopped the algorithm as soon as one solution was found, but I then changed my mind and decided to list all solutions.
If I were solving the puzzle by hand, I would first notice that, since all squares have the same sum, then, the sum a + 2b + c + 2d + e + 2f + g must be a multiple of 4. Since the sum of the input numbers in the example is 28, we can try to see how, when adding three of the input numbers, we can get to a multiple of 4. The possible total sums are therefore 36, 40 and 44, so that the individual square sums are 9, 10 or 11. We can then add equations to the story: for example, we must have a = c + d, b + c = e + f, and g = e + d. We also have a + b = b + c + c = d + e + f = f + g. And so on. From there, we can use substitutions and eliminations in these equations and eventually get to a fairly limited number of possibilities that we can then explore one by one. In other words, we are still likely to have to conduct some form of exhaustive search in the final phase.
This is one case where you probably don’t want to let your computer do it the same way a human being would do it. Since we probably need an exhaustive search in the end, let’s do everything with an exhaustive search, i.e. a brute force approach. After all, computers are much better than us, humans, at doing that. So, basically, we will examine all permutations of the seven input integers. There are 7! = 5040 such permutations, really no big deal for a computer. Some of the programs below run in less than 0.1 seconds. I had some performance optimizations in mind (like eliminating early entire sub-trees of permutations that could not lead to solutions), but it turns out that it isn’t even necessary.
Four Squares Puzzle in Raku
As explained above, we just use the built-in permutations method and test all permutations of the input numbers
use v6;
sub check-squares (@in) {
my $flag = False;
for @in.permutations -> @perm {
my $sum1 = [+] @perm[0, 1];
next if $sum1 != [+] @perm[1..3] or
$sum1 != [+] @perm[3..5] or
$sum1 != [+] @perm[5, 6];
say @perm and $flag = True
}
return $flag;
}
say "No solution" unless check-squares(1..7)
This leads to 8 solutions:
$ raku ./four-squares.raku
(3 7 2 1 5 4 6)
(4 5 3 1 6 2 7)
(4 7 1 3 2 6 5)
(5 6 2 3 1 7 4)
(6 4 1 5 2 3 7)
(6 4 5 1 2 7 3)
(7 2 6 1 3 5 4)
(7 3 2 5 1 4 6)
Each solution is the symmetry of another one (for example (3 7 2 1 5 4 6) is the symmetry of (6 4 5 1 2 7 3)), which reflects the symmetry of the figure with the four squares. Also notice that the individual square sums are 9, 10 and 11, which confirms the original manual analysis of the problem made above.
Note that we can make the check-squares subroutine slightly more concise and perhaps a bit simpler using chained numeric equality operators:
use v6;
sub check-squares (@in) {
my $flag = False;
for @in.permutations -> @p {
say @p and $flag = True if
@p[0,1].sum == @p[1..3].sum ==
@p[3..5].sum == @p[5, 6].sum;
}
return $flag;
}
say "No solution" unless check-squares(1..7)
This amended version displays the same output.
Four Squares Puzzle in Raku
Perl doesn’t have a built-in permutations subroutine. There are some CPAN modules, such as ntheory or Algorithm::Permute, providing a permutation functionality, but I explained above why I eschew using external libraries for a coding challenge. So, I’ll write my own little recursive permute subroutine:
use strict;
use warnings;
use feature "say";
sub add {
my $sum = 0;
$sum += $_ for @_;
return $sum;
}
sub check_squares {
my @in = @{$_[0]};
my $sum = add @in[0, 1];
return ($sum == add @in[1..3] and
$sum == add @in[3..5] and
$sum == add @in[5, 6] );
}
sub permute {
my ($perm_ref, $inref) = @_;
my @in = @$inref;
if (scalar @in == 0) {
say "@$perm_ref" if check_squares $perm_ref;
return;
}
permute([@$perm_ref, $in[$_]], [ @in[0..$_-1, $_+1..$#in] ]) for 0..$#in;
}
my @input = 1..7;
permute [], \@input;
And we obtain the same output:
$ perl four-squares.pl
3 7 2 1 5 4 6
4 5 3 1 6 2 7
4 7 1 3 2 6 5
5 6 2 3 1 7 4
6 4 1 5 2 3 7
6 4 5 1 2 7 3
7 2 6 1 3 5 4
7 3 2 5 1 4 6
Four Squares Puzzle in Other Programming Languages
In some languages, we’ll use a built-in permutation routine, in others, we will roll out our own, either recursive or iterative, permutation function.
Four Squares in Scala
Scala has a built-in permutation method. So we generate all permutations and print out those satisfying the requirement:
object fourSquares extends App {
val in = (1 to 7).toList
for (perm <- in.permutations) {
val sum = perm.slice(0, 2).sum;
// In Scala, slice(0, 2) returns items 0 and 1
if (
perm.slice(1, 4).sum == sum &&
perm.slice(3, 6).sum == sum &&
perm.slice(5, 7).sum == sum
) {
println(perm.mkString(" "))
}
}
}
Output:
3 7 2 1 5 4 6
4 5 3 1 6 2 7
4 7 1 3 2 6 5
5 6 2 3 1 7 4
6 4 1 5 2 3 7
6 4 5 1 2 7 3
7 2 6 1 3 5 4
7 3 2 5 1 4 6
Four Squares in Python
We use the permutations method provided by itertools core library. Our Python implementation can use chained equality operators, similarly to our second Raku implementation:
import itertools
input = range(1, 8) # 1 to 7
for p in itertools.permutations(input):
if sum(p[0:2]) == sum(p[1:4]) == sum(p[3:6]) == sum(p[5:7]):
print (perm)
Output:
(3, 7, 2, 1, 5, 4, 6)
(4, 5, 3, 1, 6, 2, 7)
(4, 7, 1, 3, 2, 6, 5)
(5, 6, 2, 3, 1, 7, 4)
(6, 4, 1, 5, 2, 3, 7)
(6, 4, 5, 1, 2, 7, 3)
(7, 2, 6, 1, 3, 5, 4)
(7, 3, 2, 5, 1, 4, 6)
Four Squares in Julia
Julia has the Combinatorics external library that provides a permutations function, but, as mentioned above, I tend to avoid using external libraries for a coding challenge. So we will roll out our own permute function, based on this Wikipedia Page on Heap’s algorithm. Note that the algorithm described on Wikipedia is for zero-based array indices, I had to change the details significantly for Julia’s one-based array indices.
function check_squares(p)
∑ = p[1] + p[2]
return (p[2] + p[3] + p[4] == ∑ &&
p[4] + p[5] + p[6] == ∑ &&
p[6] + p[7] == ∑)
end
function permute(k, in) # Heap's algorithm
if (k == 1)
if (check_squares(in)) println(in) end
# println(in)
else
permute(k - 1, in)
for i = 1:(k-1)
if (k % 2 == 0)
in[i], in[k] = in[k], in[i]
else
in[1], in[k] = in[k], in[1]
end
permute(k - 1, in)
end
end
end
permute(7, [1, 2, 3, 4, 5, 6, 7])
Output:
$ julia four_squares.jl
[4, 5, 3, 1, 6, 2, 7]
[6, 4, 1, 5, 2, 3, 7]
[7, 2, 6, 1, 3, 5, 4]
[5, 6, 2, 3, 1, 7, 4]
[6, 4, 5, 1, 2, 7, 3]
[4, 7, 1, 3, 2, 6, 5]
[7, 3, 2, 5, 1, 4, 6]
[3, 7, 2, 1, 5, 4, 6]
Four Squares in C
C language is relatively low-level and, as you can imagine, doesn’t have a built-in permutation function. So it will be rolled out in the main function.
#include <stdio.h>
int check_squares (int p[]) {
int sum = p[0] + p[1];
return ( p[1] + p[2] + p[3] == sum &&
p[3] + p[4] + p[5] == sum &&
p[5] + p[6] == sum);
}
void swap (int a[], int m, int n) {
int temp = a[m];
a[m] = a[n];
a[n] = temp;
}
int main() {
int in[7] = {7, 6, 5, 4, 3, 2, 1}; # values must be in descending order
int i, j;
int fact = 5040; //factorial 7
while (fact--) {
if (check_squares(in)) {
for (int i = 0; i < 6; i++) printf("%d ", in[i]);
printf("%d\n", in[6]);
}
i = 1;
while (in[i] > in[i-1]) i++;
j = 0;
while (in[j] < in[i]) j++;
swap(in, i, j);
i--;
for (j = 0; j < i; i--, j++) swap(in, i, j);
}
}
Output:
6 4 5 1 2 7 3
7 2 6 1 3 5 4
5 6 2 3 1 7 4
4 7 1 3 2 6 5
7 3 2 5 1 4 6
3 7 2 1 5 4 6
4 5 3 1 6 2 7
6 4 1 5 2 3 7
Four Squares in Lua
Lua doesn’t have a built-in permutation function (AFAIK), so we will roll out our own recursive permute function:
local function check_square (p)
sum = p[1] + p[2]
return p[2] + p[3] + p[4] == sum and
p[4] + p[5] + p[6] == sum and
p[6] + p[7] == sum
end
local function permute(perm, n)
if n == 0 and check_square(perm) then
print( table.concat(perm, ' ') )
else
for i = 1, n do
perm[i], perm[n] = perm[n], perm[i]
permute(perm, n - 1)
perm[i], perm[n] = perm[n], perm[i]
end
end
end
permute({1,2,3,4,5,6,7}, 7)
Output:
6 4 5 1 2 7 3
5 6 2 3 1 7 4
7 2 6 1 3 5 4
4 7 1 3 2 6 5
7 3 2 5 1 4 6
3 7 2 1 5 4 6
4 5 3 1 6 2 7
6 4 1 5 2 3 7
Four Squares in D
The D programming language has a couple of permutation methods in its std.algorithm core library. We will use nextPermutation, which acts as an iterator:
bool check_squares (int [] p) {
int sum = p[0] + p[1];
return ( p[1] + p[2] + p[3] == sum &&
p[3] + p[4] + p[5] == sum &&
p[5] + p[6] == sum);
}
void main() {
import std.stdio, std.algorithm;
auto items = [1, 2, 3, 4, 5, 6, 7];
do
if (check_squares(items)) items.writeln;
while (items.nextPermutation);
}
Output:
[3, 7, 2, 1, 5, 4, 6]
[4, 5, 3, 1, 6, 2, 7]
[4, 7, 1, 3, 2, 6, 5]
[5, 6, 2, 3, 1, 7, 4]
[6, 4, 1, 5, 2, 3, 7]
[6, 4, 5, 1, 2, 7, 3]
[7, 2, 6, 1, 3, 5, 4]
[7, 3, 2, 5, 1, 4, 6]
Four Squares in Nim
Remember that Nim supports indentation-based syntax like Python, except that it is possible to break a line after a binary operator (after the and in the code below). We use the nextPermutation method of the core algorithm library, which also acts as an iterator.
import algorithm
proc check_squares (p: array[0..6, int]) : bool =
var sum = p[0] + p[1]
return ( p[1] + p[2] + p[3] == sum and
p[3] + p[4] + p[5] == sum and p[5] + p[6] == sum )
var input = [1, 2, 3, 4, 5, 6, 7] # List has to start sorted
while input.nextPermutation():
if check_squares(input):
echo input
Output:
[3, 7, 2, 1, 5, 4, 6]
[4, 5, 3, 1, 6, 2, 7]
[4, 7, 1, 3, 2, 6, 5]
[5, 6, 2, 3, 1, 7, 4]
[6, 4, 1, 5, 2, 3, 7]
[6, 4, 5, 1, 2, 7, 3]
[7, 2, 6, 1, 3, 5, 4]
[7, 3, 2, 5, 1, 4, 6]
Four Squares in Ruby
We use the built-in permutation method of Ruby and print out the permutations matching the requirements:
input = [1, 2, 3, 4, 5, 6, 7]
for p in input.permutation
sum = p[0] + p[1]
if p[1] + p[2] + p[3] == sum and
p[3] + p[4] + p[5] == sum and
p[5] + p[6] == sum then
puts p.join(" ")
end
end
Output:
3 7 2 1 5 4 6
4 5 3 1 6 2 7
4 7 1 3 2 6 5
5 6 2 3 1 7 4
6 4 1 5 2 3 7
6 4 5 1 2 7 3
7 2 6 1 3 5 4
7 3 2 5 1 4 6
Four Squares in Kotlin
I did not write the permute function used in the program below, but found it on the Internet.
fun <T> permute(input: List<T>): List<List<T>> {
if (input.size == 1) return listOf(input)
val perms = mutableListOf<List<T>>()
val toInsert = input[0]
for (perm in permute(input.drop(1))) {
for (i in 0..perm.size) {
val newPerm = perm.toMutableList()
newPerm.add(i, toInsert)
perms.add(newPerm)
}
}
return perms
}
fun check_squares(p: List<Int>): Boolean {
val sum = p[0] + p[1]
return ( p[1] + p[2] + p[3] == sum &&
p[3] + p[4] + p[5] == sum &&
p[5] + p[6] == sum )
}
fun main(args: Array<String>) {
val input = listOf(1, 2, 3, 4, 5, 6, 7)
val perms = permute(input)
for (perm in perms) {
if (check_squares(perm)) println(perm)
}
}
Output:
[4, 5, 3, 1, 6, 2, 7]
[5, 6, 2, 3, 1, 7, 4]
[6, 4, 1, 5, 2, 3, 7]
[6, 4, 5, 1, 2, 7, 3]
[3, 7, 2, 1, 5, 4, 6]
[7, 3, 2, 5, 1, 4, 6]
[4, 7, 1, 3, 2, 6, 5]
[7, 2, 6, 1, 3, 5, 4]
Four Squares in Go
package main
import "fmt"
func check_squares ( p[] int) bool {
var sum = p[0] + p[1]
return ( p[1] + p[2] + p[3] == sum &&
p[3] + p[4] + p[5] == sum &&
p[5] + p[6] == sum)
}
func main() {
var in = []int{1, 2, 3, 4, 5, 6, 7}
var max = len(in) - 1
var i, j int
for c := 1; c < 5040; c++ { // 7! = 5040
i = max - 1
j = max
for in[i] > in[i+1] {
i--
}
for in[j] < in[i] {
j--
}
in[i], in[j] = in[j], in[i]
j = max
i += 1
for i < j {
in[i], in[j] = in[j], in[i]
i++
j--
}
if check_squares(in) {
fmt.Println(in)
}
}
}
Output:
[3 7 2 1 5 4 6]
[4 5 3 1 6 2 7]
[4 7 1 3 2 6 5]
[5 6 2 3 1 7 4]
[6 4 1 5 2 3 7]
[6 4 5 1 2 7 3]
[7 2 6 1 3 5 4]
[7 3 2 5 1 4 6]
Wrapping up
The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, May 2, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.
I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.
Leave a comment