An Abundance of Numbers
with Raku and Perl

by Arne Sommer

An Abundance of Numbers with Raku and Perl

[188] Published 19. June 2022.

This is my response to The Weekly Challenge #169.

Challenge #169.1: Brilliant Numbers

Write a script to generate first 20 Brilliant Numbers.

Brilliant numbers are numbers with two prime factors of the same length.

The number should have exactly two prime factors, i.e. it’s the product of two primes of the same length.

For example: 
24287 = 149 x 163
24289 = 107 x 227

Therefore 24287 and 24289 are 2-brilliant numbers.
These two brilliant numbers happen to be consecutive as there are no
  even brilliant numbers greater than 14.
Output: 
4, 6, 9, 10, 14, 15, 21, 25, 35, 49, 121, 143, 169, 187, 209, 221, 247,
  253, 289, 299

My «factors» procedure, introduced in Centenary Sequences with Raku - Part 5: Divisors and Factors, and used in numerous challenges after that, comes is handy yet again:

File: brilliant-numbers 
#! /usr/bin/env raku

unit sub MAIN (Int :c(:$count) where $count > 0 = 20);         # [1]

my $bn := (1 .. Inf).grep( *.&is-brilliant );                  # [2]

say $bn[^$count].join(", ");                                   # [3]

sub factors ($number is copy)                                  # [4]
{
  return (1)       if $number == 1;
  return ($number) if $number.is-prime;

  my @factors;

  for (2 .. $number div 2).grep( *.is-prime) -> $candidate
  {
    while $number %% $candidate
    {
      @factors.push: $candidate;
      $number /= $candidate;
    }
  }
    
  return @factors;
}

sub is-brilliant ($number)                                     # [2a]
{
  my @factors = factors($number);                              # [4]
  return False unless @factors.elems == 2;                     # [5]
  return False unless @factors[0].chars == @factors[1].chars;  # [6]
  return True;                                                 # [7]
}

[1] The number of values to print, with 20 as the default.

[2] Use the «is-brilliant» procedure to filter out the correct values, with grep. Note the special .& calling syntax allowing us to pretend that a procedure is a method. Also note that we can use the special colon syntax instead of the parens: grep: *.&is-brilliant (but I have not done so).

See docs.raku.org/language/operators#methodop_.& for more information about the special procedure invocation syntax .&.

[3] Print the required number of values from the sequence.

[4] Get the factors.

[5] The number of factors must be 2.

[6] The two factors must have the same number of digits.

[7] If we have not failed yet, it is brilliant.

Running it: 

$ ./brilliant-numbers
4, 6, 9, 10, 14, 15, 21, 25, 35, 49, 121, 143, 169, 187, 209, 221, 247, \
  253, 289, 299

$ ./brilliant-numbers -c=30
4, 6, 9, 10, 14, 15, 21, 25, 35, 49, 121, 143, 169, 187, 209, 221, 247, \
  253, 289, 299, 319, 323, 341, 361, 377, 391, 403, 407, 437, 451

Looking good.

A Perl Version

This is straight forward translation of the Raku version.

File: brilliant-numbers-perl 
#! /usr/bin/env perl

use strict;
use warnings;
use feature 'say';
use feature 'signatures';
no warnings 'experimental::signatures';

use Math::Prime::Util 'is_prime';

my $count = shift(@ARGV) || 20;

die "Please specify a positive integer" unless $count =~ /^[1-9]\d*$/;

my @bn = ();

my $candidate = 0;

while (@bn != $count)
{
  $candidate++;

  push(@bn, $candidate) if is_brilliant($candidate);
}

say join(", ", @bn);

sub factors ($number)
{
  return (1)       if $number == 1;
  return ($number) if is_prime($number);

  my @factors;

  for my $candidate (grep { is_prime($_) } 2 .. $number / 2)
  {
    while ($number % $candidate == 0)
    {
      push(@factors, $candidate);
      $number /= $candidate;
    }
  }
    
  return @factors;
}

sub is_brilliant ($number)
{
  my @factors = factors($number);
  return 0 unless @factors == 2;
  return 0 unless length($factors[0]) == length($factors[1]);
  return 1;
}

Running it gives the same result as the Raku version: 

$ ./brilliant-numbers-perl
4, 6, 9, 10, 14, 15, 21, 25, 35, 49, 121, 143, 169, 187, 209, 221, 247, \
  253, 289, 299

$ ./brilliant-numbers-perl 30
4, 6, 9, 10, 14, 15, 21, 25, 35, 49, 121, 143, 169, 187, 209, 221, 247, \
  253, 289, 299, 319, 323, 341, 361, 377, 391, 403, 407, 437, 451

Challenge #169.2: Achilles Numbers

Write a script to generate first 20 Achilles Numbers. Please checkout wikipedia for more information.

An Achilles number is a number that is powerful but imperfect (not a perfect power). Named after Achilles, a hero of the Trojan war, who was also powerful but imperfect.

A positive integer n is a powerful number if, for every prime factor p of n, p^2 is also a divisor.

A number is a perfect power if it has any integer roots (square root, cube root, etc.).

For example 36 factors to (2, 2, 3, 3) - every prime factor (2, 3) also has its square as a divisor (4, 9). But 36 has an integer square root, 6, so the number is a perfect power.

But 72 factors to (2, 2, 2, 3, 3); it similarly has 4 and 9 as divisors, but it has no integer roots. This is an Achilles number.

Output: 
72, 108,  200,  288,  392,  432,  500,  648,  675,  800,  864, 968, 972,
  1125, 1152, 1323, 1352, 1372, 1568, 1800

Let us do the three sequences (Powerful Numbers, Perfect Powers and Achilles Numbers) separately.

Powerful Numbers:

File: achilles-numbers (partial) 
#! /usr/bin/env raku

unit sub MAIN (Int :c(:$count) where $count > 0 = 20, :$powerful, :$perfect);
                                                 # [1]
my $bn;

if ($powerful && ! $perfect)                     # [2]
{
  $bn := (1 .. Inf).grep( *.&is-powerful );      # [2a]
}
elsif ($perfect && !$powerful)                   # [3]
{
  $bn := (1 .. Inf).grep( *.&is-perfect );       # [3a]
}
else                                             # [4]
{
  $bn := (1 .. Inf).grep( *.&is-achilles );      # [4a]
}

say $bn[^$count].join(", ");                     # [5]

sub factors ($number is copy)                    # [6]
{
  …
}

sub is-powerful ($number)                        # [7]
{
  return True if $number == 1;                   # [8]

  my @factors = factors($number);                # [9]

  my $b = @factors.Bag;                          # [10]

  return all($b.values) > 1;                     # [11]
}

[1] Note the named arguments «powerful» and «perfect» that can be used to get that sequence instead of the default Achilles one.

[2] The Powerful Number sequence. Note that if we ask for both, we get Achilles in [4].

[3] The Perfect Power sequence - to be described later.

[4] The Achilles sequence, if none (or both) of the above has been specified. Also subject for later description.

[5] Print the required number of values from the sequence.

[6] See the first part of the challenge for the actual code - or the source code of this program.

[7] Is the number powerful?

[8] «1» is not detected by the code in [11], so we special case it.

[9] Get the factors.

[10] Turn the factors into a Bag, a hash like structure where the (in this case) prime factors are the keys, and the frequencies are the values.

See docs.raku.org/routine/flat for more information about flat.

See docs.raku.org/type/Bag for more information about the Bag type.

[11] «A positive integer n is a powerful number if, for every prime factor p of n, p^2 is also a divisor» means that all the prime factors must occur more than once (i.e. at least twice; giving p^2). We check for that with an all junction.

See docs.raku.org/routine/all for more information about the all Junction.

Running it: 

$ ./achilles-numbers -powerful
1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72, 81, 100, 108, 121, 125, 128, \
  144, 169

$ ./achilles-numbers -powerful -c=30
1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72, 81, 100, 108, 121, 125, 128, \
  144, 169, 196, 200, 216, 225, 243, 256, 288, 289, 324, 343

We got the same result as Wikipedia.

Perfect Powers:

File: achilles-numbers (partial) 
sub is-perfect ($number)
{
  return True if $number <= 1;                            # [1]
			   
  my @divisors = divisors($number, :not-self, :not-one);  # [2]

  return False unless @divisors.elems;                    # [3]

  for @divisors -> $divisor                               # [4]
  {
    my $current = $divisor;                               # [5]

    $current *= $divisor while $current < $number;        # [5a]

    return True if $current == $number;                   # [6]
  }

  return False;                                           # [8]
}

sub divisors ($number, :$not-self, :$not-one)             # [2a]
{
  my @divisors;
  
  for ($not-one ?? 2 !! 1) .. $number/2 -> $candidate
  {
    @divisors.push: $candidate if $number %% $candidate;
  }
  
  @divisors.push: $number unless $not-self;
  
  return @divisors;
}

[1] We can choose to include 0 and 1 in the sequence or not, as explained in the wikipedia article, but we need 1 as the challenge gives us 1 as the first Achilles Number.

[2] Get the divisors this time (compared with the factors for the Powerful Numbers). This procedure [2a] was also introduced in Centenary Sequences with Raku - Part 5: Divisors and Factors. We do not want «1» and the number itself.

[3] It is not perfect if it does not have any divisors (i.e. it is a prime number).

[4] Iterate over all the divisors.

[5] Start counting at the current divisor, and add it repeatedly until we have reached or passed the initial number [5a].

[6] We have a perfect number if we have reached it (the number). If not, iterate over the next divisor [4].

[7] We have tried all the divisors, without luck. Then it is not a Perfect Number.

Why Divisors?

We are looking for an integer square root, cubic root, and any higher order root. If any such root exist, we have a Perfect Number. We cannot start with the (prime) factors, as e.g. 400 is a Perfect Number (as it is the same as 20 ** 2), and 20 is not a factor. But it is a divisor. (A divisor is a number that the original number is divisible with - integer wise.)

Another example is 8. This does not have an integer root, but the cubic root is 2 (i.e. 2 ** 3 == 8). In this case 2 is a divisor.

Thus we consider each and every divisor, adding them to each other until we have reached (or passed) the original number.

Running it: 

$ ./achilles-numbers -perfect
1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, \
  196, 216

$ ./achilles-numbers -perfect -c=30
1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, \
  196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484

We got the same result as Wikipedia, again.

And finally, the Achilles sequence:

File: achilles-numbers (the rest) 
sub is-achilles ($number)
{
  return False unless $number.&is-powerful; # [1]
  return False if     $number.&is-perfect;  # [2]
  return True;                              # [3]
}

For a number to be an Achilles Number [3], it must be Powerful [1], but not Perfect [2]. Note the negations due to the return False statements.

Running it: 

$ ./achilles-numbers
72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125, 1152, \
  1323, 1352, 1372, 1568, 1800

$ ./achilles-numbers -c=30
72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125, 1152, \
  1323, 1352, 1372, 1568, 1800, 1944, 2000, 2312, 2592, 2700, 2888, 3087, \
  3200, 3267, 3456

Perl

This is a straight forward translation of the Raku version, without support for the internal sequences (Powerful Numbers, Perfect Powers):

File: achilles-numbers-perl 
#! /usr/bin/env perl

use strict;
use warnings;
use feature 'say';
use feature 'signatures';
no warnings 'experimental::signatures';

use Math::Prime::Util 'is_prime';

my $count = shift(@ARGV) || 20;

die "Please specify a positive integer" unless $count =~ /^[1-9]\d*$/;

my @achilles = ();

my $candidate = 0;

while (@achilles != $count)
{
  $candidate++;

  push(@achilles, $candidate) if is_achilles($candidate);
}

say join(", ", @achilles);

sub factors ($number)
{
  return (1)       if $number == 1;
  return ($number) if is_prime($number);

  my @factors;

  for my $candidate (grep { is_prime($_) } 2 .. $number / 2)
  {
    while ($number % $candidate == 0)
    {
      push(@factors, $candidate);
      $number /= $candidate;
    }
  }
    
  return @factors;
}

sub divisors ($number)
{
  my @divisors;
  
  for my $candidate (2 .. $number/2)
  {
    push(@divisors, $candidate) if $number % $candidate == 0;
  }
  
  return @divisors;
}

sub is_powerful ($number)
{
  return 1 if $number == 1;

  my @factors = factors($number);

  my %values;

  for my $val (@factors)
  {
    $values{$val}++;
  }
  
  for my $count (values %values)
  {
    return 0 if $count == 1;
  }

  return 1;
}

sub is_perfect ($number)
{
  return 1 if $number <= 1;

  my @divisors = divisors($number);

  return 0 unless @divisors;

  for my $divisor (@divisors)
  {
    my $current = $divisor;

    $current *= $divisor while $current < $number;

    return 1 if $current == $number;
  }

  return 0;
}

sub is_achilles ($number)
{
  return 0 unless is_powerful($number);
  return 0 if     is_perfect($number);
  return 1;
}

Running it gives the same result as the Raku version: 

$ ./achilles-numbers-perl
72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125, 1152, \
  1323, 1352, 1372, 1568, 1800

$ ./achilles-numbers-perl 30
72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125, 1152, \
  1323, 1352, 1372, 1568, 1800, 1944, 2000, 2312, 2592, 2700, 2888, 3087, \
  3200, 3267, 3456

And that's it.

Links
 About me
 Keyword Index
Raku Courses
 Beginning Raku (book)
 RSS Feed
 Code (zip)
Reddit Comments