Month: April 2021

Wherein we break things apart and add them up again, sometimes alone and other times fitting into the context of what we share with others.

THE WEEKLY CHALLENGE – PERL & RAKU #109

---

episode one:
“Break it Apart and View the Big Picture”

---

Task 1

Chowla Numbers

Submitted by: Mohammad S Anwar

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

Method

When tasked to create the sum of a bunch of divisors we first need to create a list of divisors and then sum them.

With that brilliant piece of tautological insight behind us, let’s move forward to a more specific question: how do we create this list of divisors we need? Not including either 1 or the value, of course. Well, we can always pick a number and see whether it evenly divides into our target. A factor must, by its nature, be smaller than the target, so there’s our potential range: numbers smaller than the target.

The easiest way to determine whether one number evenly divides another is to use the modulo operator and see whether there is any remainder to the division. Because in Perl, 0 is a logical false, this can be used in a conditional to decide whether or not to add in the factor to the sum.

Ok, so all the numbers less than our target then? Well, no. Theoretically we explicitly aren’t using the target so we don’t need to test that value, and on the other side we’re excluding 1 so that’s out too. The the big end the largest factor we could possibly have is the target over 2, or the next smaller integer, if our target is odd. In any case anything greater than that times 2 would be too much so it’s out. So we’ve narrowed the list to starting from 2 and working upwards to one-half the number we’re factoring.

That all makes sense and frankly works quite well, if the numbers factored remain small. The first twenty, as we’re being asked, for example, will require, let’s see,

0 + 0 + 0 + 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 + 7 + 8 + 8 + 9 = 71

checks. Certainly doable.

But what of 12 factorial? That number,

12 × 11 × 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 479,001,600

has a lot of factors surely. Sounds like an interesting target. So let’s take some initiative and expand our horizons beyond the twenty results we’ve been immediately asked for. We don’t work for the challenge. Let’s let the challenge work for us.

If we iterate through half the value for 12!, we need to loop

479,001,600 / 2 = 239,500,800

times. That’s a lot of checking.

How can we speed things up? One thing though — every time we find a factor, we really find two, the factor and the number it multiplies by to produce the target. If we note that down the first time through we won’t need to test that value if we run into it again. So what is the relationship between the numbers?

As it works out, the fulcrum between the two factors is the square root. For every factor found below the square root there will be exactly one complementary factor above it that when multiplied will produce the target value. And vice-versa, it stands to reason. If there was a factor above it would have a complement below. So all we really need to do is search numbers up to the square root of the target, then, and, if we find a factor, add its complement to the sum as we go.

Oh, right: unless it is the square root, that is. In that case the complement is itself, and we will have already noticed the value as the factor once, and should not give it special treatment and notice it twice. Numbers are very egalitarian that way. All numbers are interesting, and all have value, and none do not have value.

Oh, right: except 0, zero has no value, but is every bit as interesting as any of its compatriots. Love zero.

PERL 5 SOLUTION

C(1)  = 0
C(2)  = 0
C(3)  = 0
C(4)  = 2
C(5)  = 0
C(6)  = 5
C(7)  = 0
C(8)  = 6
C(9)  = 3
C(10) = 7
C(11) = 0
C(12) = 15
C(13) = 0
C(14) = 9
C(15) = 8
C(16) = 14
C(17) = 0
C(18) = 20
C(19) = 0
C(20) = 21
C(479001600)      = 1738439807

We first set up a loop from two to the square root. In Perl if an element in a range is real, integer truncation of the whole part is automatically done, and furthermore, if the range goes nowhere, say from 1 to 0, then nothing will happen, rather than complaining. We sometimes call this “Do What I Want” behavior. Don’t crash, just figure it out.

But back to the code: then we compound our sum, unless the division has a remainder. If the complement to the factor found is equal to factor we only add the factor to the sum, otherwise we add both the factor and the complement. We could have saved out the square root to a variable and used it again here, but, you know, whatever.

We get a little fancy in the printf statement with a variable-length field specified for the space — this way the single-digit values have (3 – 1), or 2 characters for the space, and the two-digit numbers have (3 – 2), or only the single space. Of course this cleverness breaks down for Chowla(12!), but that was a later addition and you can’t have everything.

use warnings;
use strict;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

for (1..20, 479001600) {
     printf "C(%d)%*s= %d\n", $_,  3-length, ' ', sum_divisors($_);
}

sub sum_divisors ($n) {
    my $out = 0;
    for (2..sqrt $n) {
        unless ($n % $_) {
            $out += ($n/$_ == $_ ? $_ : $_ + $n/$_) ;
        }
    }
    return $out;
}

raku solution

In Raku wee can easily process everything functionally, as lists handed from one operation to the next. We first take a list of values from 2 to the square root, then filter it for only values that evenly divide, using the super-handy %% operator. Then each list value is mapped to either itself or itself plus its complement factor according to a conditional, and finally the mapped list is summed with the reduction metaoperator to yield the result. I think this is the prettiest solution.

unit sub MAIN () ;

for 1..20 {
     printf "C(%d)%*s= %s\n", $_,  3 - $_.chars, ' ', sum_divisors($_);  
}

sub sum_divisors ($n) {
    [+] (2..sqrt $n).grep({$n %% $_})
                    .map({$n/$_ == $_ ?? $_
                                      !! $_ + $n/$_})

Python Solution

In python we can condense a little of the math using the divmod function to perform integer division, returning the whole quotient and remainder in a tuple.

import math

def sum_divisors (n):
    out = 0
    for d in range( 2, int(math.sqrt(n))+1 ):
        id = divmod(n,d)
        if id[1] == 0:
            out += d 
            if id[0] != d:
                out += id[0]
    return out


for n in range(1,21):
    print(f"C({n}) = ", sum_divisors(n))

---

episode two:
“Learning to Share”

---

task 2

Four Squares Puzzle

Submitted by: Mohammad S Anwar

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

Method

I have to admit I spent a lot of time on this puzzle, working is over, massaging the equations, looking at the underlying structure tying together the various equations that describe the interrelationships between the variables:

[1]	a + b = n
[2]	b + c + d = n
[3]	d + e + f = n
[4]	f + g = n
[1.1]	a = n – b
[1.2]	b = n – a
[2.1]	b = n – c – d
[2.2]	c = n – b – d
[2.3]	d = n – b – c
[3.1]	d = n – e – f
[3.2]	e = n – d – f
[3.3]	f = n – d – e
[4.1]	f = n – g
[4.2]	g = n – f
[1]	a = n – b
	= n – (n – c – d)
	= n – (n – c – (n – e – f))
	= n – (n – c – (n – e – (n – g)))
[5]	a = c + g – e
[5.1]	a = c + g – e
[5.2]	c = a + e – g
[5.3]	e = c + g – a
[5.4]	g = a + e – c
[2.1]	b = n – c – d
	= n – c – (n – e – f)
	= n – c – n + e + f
[6]	b = e + f – c
[7]	f = b + c – e
[3.1]	d = n – e – f
	= n – (c + g – a) – (n – g)
	= n – c – g + a – n + g
[8]	d = a – c
[2.3]	d = n – b – c
	= n – (n – a) – (a + e – g)
	= n – n + a – a – e + g
[9]	d = g – e

It all ends up circular after that.

What does it all mean? It means that we don’t have nearly enough information to make any of the 8 variables: a, b, c, d, e, f, g and n, the constant sum, go away. They can be defined amongst themselves due to their interdependencies, but we can’t just “solve” this. There are classes of solutions, and it’s not clear how to specifically derive which ones will work.

It is pretty in there, though. It reminded me of the Seven Bridges of Königsberg problem after a while, counting the ns to try and get d in terms of n. There are some very interesting symmetries to be found. Especially around d — everything cancels out right in the middle.

None of that did much to solve our problem, though. Or really, to even fully explain what it was we were sent here to do. Given a list of random numbers see if they can be fitted? Doesn’t sound likely. Rather it sounds like a whole bunch of misses looking for a hit somewhere.

So I decided to take a different tangent. For a given set of values there are only 7!, or 5040, permutations to fit, so why not try them all? It’s not a very big number.

A bit surprisingly, for the given example of 1 through 7, there are 8 solutions. Obviously, because the whole arrangement can be rotated 180° to map to itself there will be pairs of solutions of the form

(a, b, c, d, e, f, g) ⟺ (g, f, e, d, c, b, a)

but I did not expect there to be 4 such sets, for a total of 8. And I do think that because we have explicitly labeled the squares the rotated pairs should be considered distinct. There’s an order to it all.

I set up a loop to offset the starting value to further explore the solution space, and found that once the mean value drifts too far from 0 the difference between adding three values and two to make a constant becomes too much and there are no solutions. In the other direction, the maximum for a set of values with a delta of 1, like in our example, was 18 solutions for the lists -4 to 2 and -2 to 4. These have a mean value of -1 and 1 respectively, but the symmetrical list of (-3, -2, -1, 0, 1, 2, 3), centered around and with a mean of 0, has no solutions at all.

Isomorphic sets, with all elements multiplied by a constant, predictably produce the same number of solutions.

PERL 5 SOLUTION

We’ve divided the logic into three phases: fitting possible outcomes, validating the solutions, and reporting the results. To fit we use the Algorithm::Combinatorics routine permutations to generate a list of 5040 lists for us, which we try one at time. As we are looking for all solutions we will try them all. To validate we will use the four equations at the start of our table above, comparing areas a + b, b + c + d, d+ e + f and f + g to each other. Should any comparison fail the test short-circuits and stops evaluation immediately.

zip is a welcome addition to the core module List::Util as of version 1.56.

use warnings;
use strict;
use feature ":5.26";
use feature qw(signatures);
no  warnings 'experimental::signatures';

use Algorithm::Combinatorics qw(permutations);
use List::Util 1.56 qw(sum zip);   ## need 1.56 for zip

if (@ARGV == 7) {
    my @sol = find_solutions(\@ARGV);
    say "Input list: @ARGV";
    say scalar @sol, " solutions found.\n";
    if (@sol) {
        report($_) for @sol; 
    }
}
else {
    for my $s (-10..10) {
        my @list = ($s..$s+6);

        my @sol = find_solutions(\@list);
        next if not @sol;

        say "+++++++++++++++++++++++++++++\n";
        say "Input list: @list";
        say scalar @sol, " solutions found.\n";
        report($_) for @sol;
    }
}

sub find_solutions ($list) {
    my @out;    
    for my $candidate ( permutations($list) ) {
        my $n = validate($candidate);
        push @out, [$candidate, $n] if defined $n;
    }

    return @out;
}

sub validate ($r) {
    my $n = $r->[0] + $r->[1];
    return $n if     $n 
                 ==  $r->[1] + $r->[2] + $r->[3] 
                 ==  $r->[3] + $r->[4] + $r->[5] 
                 ==  $r->[5] + $r->[6] ; 
    return undef;
}   

sub report ($sol) {
    my ($list, $num) = $sol->@*;
    
    say<<~"HEAD";
        ===============================
        Solution:
            Sum:    $num for all squares
            Values:
    HEAD
    
    my @lets = zip ['a'..'g'], $list;
    for (@lets) {
        say "\t\t$_->[0] = $_->[1]";
    }
        
    say<<~"TAIL";
    
        ===============================
    TAIL
}

If given a list of seven numbers the script will try and fit them, but as a default it runs the tests centered around 0:

Input list: -2 -1 0 1 2 3 4
18 solutions found.

    ===============================
    Solution:
        Sum:    2 for all squares
        Values:

		a = -1
		b = 3
		c = 1
		d = -2
		e = 4
		f = 0
		g = 2

    ===============================

    ===============================
    Solution:
        Sum:    3 for all squares
        Values:

		a = -1
		b = 4
		c = -2
		d = 1
		e = 2
		f = 0
		g = 3

    ===============================

    . . . etc

Raku Solution

Assigning the output elements to their respective area labels is a little cleaner in Raku, using the infix Z operator and a list of string literals with our decontainerized list.

multi sub MAIN () {
    for 1..1 -> $s {
        my @list = ($s..$s+6);
    
        my @sol = find_solutions(@list);
        next if not @sol.elems;
    
        say "+++++++++++++++++++++++++++++\n";
        say "Input list: ", @list;
        say @sol.elems, " solutions found.\n";
        report($_) for @sol;
    }
}

multi sub MAIN (*@list where { @list.elems == 7 }) {
    my @sol = find_solutions(@list);
    say "Input list: ", @list.sort;
    say @sol.elems, " solutions found";
    if (@sol.elems) {
        report($_) for @sol; 
    }
}

multi sub MAIN (*@list) {
    say "please enter 7 numbers";
}

sub find_solutions (@list) {
    my @out;    
    my @pm = @list.permutations;

    for @pm -> $candidate {
        my $n = validate($candidate);
        push @out, ($candidate, $n) if defined $n;
    }

    return @out;
}

sub validate (@list) {
    my $n = @list[0] + @list[1];
    $n == @list[1] + @list[2] + @list[3] 
       == @list[3] + @list[4] + @list[5] 
       == @list[5] + @list[6] ?? $n
                              !! Nil
}   

sub report ($sol) {

    my ($list, $num) = |$sol;
    say "list  ", $list;
    say "total ", $num;
    
    
    say qq:to/HEAD/;
    
        ===============================
        Solution:
            Sum:    $num for all squares
            Values:
    HEAD
    
    my @pairs =  <a b c d e f g> Z $list.list;
 
    say "\t\t $_[0] = $_[1]" for @pairs;
        
    say qq:to/TAIL/;
    
        ===============================
    TAIL
}

Python Solution

from itertools import permutations



def find_solutions ( lst ):
    out = []
    for candidate in list( permutations(lst) ):
        (v, n) = validate( candidate )
        if v: 
            out.append( [candidate, n] )
    return out

def validate ( lst ):
    n = lst[0] + lst[1]
    return ( (n == lst[1] + lst[2] + lst[3] 
                == lst[3] + lst[4] + lst[5] 
                == lst[5] + lst[6]), n )

def report ( tup ):
    (list, n) = tup
    
    print(f'''
    ===============================
    solution    
        sum is {n}
        values:
    ''')

    letter_values = zip( ['a','b','c','d','e','f','g'] , list )
    for lv in letter_values:
        print(f"\t\t{lv[0]} = {lv[1]}")
        
    print(f'''
    ===============================
    ''')

input    = [1,2,3,4,5,6,7]
solution = find_solutions(input)
if len(solution) > 0:
    for sol in solution:
        report(sol)