with Raku and Perl

This is my response to The Weekly Challenge #169.

Write a script to generate first

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:

`20 Brilliant Numbers`

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

The number should have

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.

#! /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

Write a script to generate first `20 Achilles Numbers`

. Please checkout
wikipedia for more information.

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.

`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

#! /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.