Day 25 – Calling Numbers Names

This school semester I took my first proof-based class titled “Intro to Mathematical Proof Workshop”. After having taken other math classes (Calculus, Matrix Algebra, etc.), I felt that I didn’t have that much of a mathematical foundation and up to this point, all I had been doing was purely computational mathematics sprinkled with some proofs here and there. Looking back, I found the class quite enjoyable and learning about different theorems and their proofs, mostly from number theory, has given me a new perspective of mathematics.

“How is this related to Perl 6?”, you might be asking. As I mentioned, most of the proofs that were discussed either in class or left for homework were related to number theory. If there’s one thing Perl 6 and number theory have in common is their accessibility. Similar to how the content of the elementary theory of numbers can be tangible and familiar, Perl 6 can be quite approachable to beginners. In fact, beginners are encouraged to write what’s known as “baby Perl”.

Another thing they seem to share is their vastness. For example, in Perl 6 one can find many operators while in number theory one can find a plethora of different types of numbers from even numbers to cute numbers. For most purposes, these numbers are easy to understand and if one has the definition of a number, then it’s quite easy to check if a given integer follows in that category. For example, a prime number is formally defined as follows:

An integer p > 1 is called a prime number, or simply a prime, if its only positive divisors are 1 and p. Otherwise, the integer p is termed composite.

By using this definition, we can quite simply figure out if a certain number is a prime. For example, among the first ten positive integers, 2, 3, 5 and 7 are primes. This is quite trivial for small numbers but doing it by hand with larger numbers would become tedious in no time. This is where Perl 6 comes into the picture. Perl 6 offers many constructs/features that even if they don’t make the job easy, they certainly simplify it. For instance, with the definition of a prime in mind, we could easily implement an algorithm that tests for primality in Perl 6:

sub isPrime( $number ) {
    return $number > 1 if $number ≤ 3;

    loop (my $i = 2; $i² ≤ $number; $i++) {
        return False if $number %% $i;
    }

    return True;
}

Please bear in mind that this is not about writing performant code. If the code turns down that way, then it would be excellent but it is not the goal. My aim is to showcase the easiness with which a beginner can express mathematical constructs in Perl 6. It’s worth mentioning that Perl 6 already includes the subroutine (or method) is-prime that tests for primality. However, although this is true for prime numbers, it might not be the case for another type of number you might come across such as a factorial, a factorion or even a Catalan number. And in cases like this, Perl 6 will be helpful.

After learning about different types of numbers, I set out to look for some peculiar numbers and see how I could implement them using Perl 6. In the process, I found this useful website that lists a bunch of numbers, their definitions and some examples. From all of these, I’ve chosen four types of numbers that aren’t stupidly difficult to implement (I still write baby Perl 😅) while being enough to illustrate some Perl 6 constructs. On the other hand, I’ve avoided those which might be too straightforward.

Let us start with…

Amicable numbers

Amicable numbers are pairs of numbers, also known as friendly numbers, each of whose aliquot parts add to give the other number.

sub aliquot-parts( $number ) {
   (^$number).grep: $number %% *; 
}

sub infix:<amic>( $m, $n ) {
    $m == aliquot-parts($n).sum &&
    $n == aliquot-parts($m).sum;
}

say 12 amic 28;   # False, 12 and 28 aren't amicables.
say 220 amic 284; # True, 220 and 284 are though.

A number’s aliquot parts are its factors excluding the number itself. To find the aliquot parts of a number, I’ve a created the subroutine aliquot-parts which uses 1..^$number to create a list of numbers from 1 up to $numbers (exclusive). This list is subsequently grepped to find out those numbers in the list that evenly divide $number. In this snippet it’s achieved by using the infix operator %% which returns True if a first operand is divisible by a second operand. Otherwise, it returns False. The second operand stands for any number in the list aforementioned so I’ve used *, which in this context is known as the whatever star and creates a closure over the expression $number %% *. Thus the whole expression in the subroutine is equivalent to (^$number).grep: { $number %% $_ };. At the end, the subroutine returns a list of factors of $number excluding $number itself.

To find out if two numbers are amicable, we could have used just a subroutine. However, Perl 6 allows for the creation of new operators, which are just subroutines with funny names themselves, and I’ve done just that. I created the infix operator (meaning between two operands) amic that returns True if two numbers are amicable. Otherwise, False. As you can see, the syntax to create a new operator is straightforward: the keyword sub, followed by the type of the operator (prefix, infix, postfix, etc.), the name of the operator inside quoting constructs, the expected parameters and a code block.

Factorion

A factorion is a natural number that equals the sum of the factorials of its digits in a given base.

subset Whole of Int where * ≥ 0;

sub postfix:<!>( Whole $N --> Whole ) {
    [*] 1..$N;
}

sub is-factorion( Whole $number --> Bool ) {
    $number == $number.comb.map({ Int($_)! }).sum 
}

say is-factorion(25);  # False
say is-factorion(145); # True

Recall that a factorial of a number N, which is usually denoted by N!, is the product 1 x 2 x ... x N. For example, 3! = 1 x 2 x 3 = 6. In the code snippet, I created the postfix operator ! to return the factorial of an integer operand. Thus say 3!; will work just fine in the code snippet and prints 6. How the factorial is calculated is straightforward: The range 1..$N creates a list of numbers from 1 to $N (inclusive) and then I use [...], which is known as the reduction meta-operator, with the operator * to reduce the created list to 1 x 2 x ... $N which effectively gives me the factorial of $N. There are many operators in Perl 6 and the meta-operator [...] can work with many of them.

As for the factorion, I want to know if a number is a factorion so I created a subroutine that takes an integer and returns a Boolean. Perl 6 is gradually typed so it allows to type variables explicitly, specify the return type of a sub, etc. I’ve decided to type the subroutines’ parameters and the subroutine’s return type.

In the section about the amicable numbers, I was quite liberal regarding the subroutines’ arguments. However, here I’ve decided to comply with the definition of a factorial and only allow for whole numbers, hence the definition and use of the Whole type. In Perl 6, the operator subset declares a new type using a base type. However if I hadn’t used the where clause, I’d have ended up with just another name for the Int type which would be redundant. So I used the where clause to constraint the type of any assignment to the desired input. In this case, the assignment to a variable of type Whole.

With the is-factorion sub, I used the method comb to break up $number into its digits and then use map to find their respective factorials and sum them up. The sub returns True if $number is equal to the sum of the factorials of its digits. It returns False otherwise.

Cyclic Numbers

A cyclic number is a number with N digits, which, when multiplied by 1, 2, 3, ..., N produces the same digits in a different order.

sub is-cyclic( Int $n --> Bool ) {
    for 1..$n.chars -> $d {
        return False if $n.comb.Bag != ($n * $d).comb.Bag;
    }
    return True;
}

say is-cyclic(142857); # True
say is-cyclic(95678);  # False

Here I created the subroutine is-cyclic that takes an integer and returns a Boolean value. I use a for loop to iterate over the places of the number’s digits (1st, 2nd, etc.) and use them to multiply the number in each iteration. Afterward I use the previously seen comb method followed by the Bag method. In Perl 6, a Bag is an immutable collection of distinct elements in no particular order where each element is weighted by the number of copies in the collection. This is the kind of structure I need since only the number’s digits and their amounts are important, not their order and a Bag accomplishes exactly this. The subroutine returns False if the bags don’t have the same numbers or have the same numbers but are weighted differently. Otherwise, True is returned indicating the number’s cyclic-ness.

Happy numbers

A happy number is defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits in base-ten, and repeat the process until the number either equals 1 (where it will stay), or it loops endlessly in a cycle that does not include 1.

sub is-happy( $n is copy ) {
    my $seen-numbers = :{};
    while $n > 1 {
        return False if $n ∈ $seen-numbers;
        $seen-numbers{$n} = True;
        $n = $n.comb.map(*²).sum
    }
    return True;
}

say is-happy(7);     # True
say is-happy(2018);  # False

After going through the process described in the definition, a happy number ends being equal to 1. On the other hand, a non-happy number follows a sequence that reaches the cycle 4, 16, 37, 58, 89, 145, 42, 20, 4,… which excludes 1. Armed with this fact, I created the hash $seen-numbers to keep track of such numbers. As illustrated by the while loop, the process is repeated over and over while $n is greater than 1 or until a number has been seen. Here the line that stands out is the one containing the symbol ∈. In set theory, if an element p is a member (or element) of a set A, then it’s denoted by p ∈ A and this exactly what’s being tested here. If the number $n is an element of the hash, then the sub returns False. Otherwise, it returns True which indicates the number’s happiness.

Summary

In this post, I slightly went over gradual typing, how to define a new operator, sub-classing by using the subset keyword and the set and bag data structures. As you may have realized, Perl 6 offers many constructs that facilitate many different tasks. In this instance, it was my desire to express definitions of numbers in a more programmatic way. Yours could be totally different but you can rest assured that Perl 6 is there to make the job easier and immensely more enjoyable.

Well…that’s all folks! Happy Christmas and a wonder-ofun New Year!

4 thoughts on “Day 25 – Calling Numbers Names

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.