Perl Weekly Challenge 169: primes, primes and more primes!
It is sad that, after more than two years of me doing Raku, I still don’t have any production code project to work on. Therefore, in order to keep my coding and Raku-ing (is that a term?) knowdledge, I try to solve every Perl Weekly Challenge tasks.In the following, the assigned tasks for Challenge 169.
and for the sake of some Perl 5, let’s do some stuff also in PostgreSQL Pl/Perl:
Last, the solutions in PostgreSQL PL/PgSQL:
PWC 169 - Task 1
Compute first twenty brilliant numbers, those with exactly two factors of the very same length:sub is-brilliant( $num ) {
my $number = $num;
# get all the factors
my @factors;
for 2 ..^ $number {
next if ! $_.is-prime;
while ( $number %% $_ ) {
@factors.push: $_;
$number /= $_;
}
}
return False if @factors.elems != 2;
return False if @factors[0] == @factors[1];
return True if @factors[0].Str.chars == @factors[1].Str.chars;
}
sub MAIN( Int $limit where { $limit > 0 } = 20 ) {
my @brilliant = lazy gather {
take $_ if is-brilliant( $_ ) for 1 .. Inf;
};
@brilliant[ 0 .. $limit ].join( "\n" ).say;
}
The
is-brilliant function does all the work. Given a number, it extracts its factors, and then checks if the number has exactly two factors with the same character length.
The
MAIN does use a lazy gather to extract the values.
PWC 169 - Task 2
Compute Achille’s numbers, those that are powerful but imperfect.sub compute-factors( $num ) {
my $number = $num;
my @factors;
for 2 ..^ $number {
next if ! $_.is-prime;
while ( $number %% $_ ) {
@factors.push: $_;
$number /= $_;
}
}
return @factors;
}
sub is-achille( $num )
{
my Bag $bag = Bag.new: compute-factors( $num );
return False if $bag.keys.elems <= 1;
return $bag.values.min >= 2 && ( [gcd] $bag.values ) == 1;
}
sub MAIN( Int $limit where { $limit > 0 } = 20 ) {
my @achille = lazy gather {
take $_ if is-achille( $_ ) for 1 .. Inf;
};
@achille[ 0 .. $limit ].join( "\n" ).say;
}
I used a
Bag, to store the factors of a given number and its occurrencies. Thanks to the presence of the gcd list operator, it becomes really easy to implement the is-achille function.
The
MAIN uses a lazy gather to extract all the values.
PWC 169 - Task 1 in PostgreSQL PL/Perl
A translation of the Raku implementation. The boring part is that all the pieces have to be provided as anoymous code blocks to check if a number is prime and to get the factors:CREATE OR REPLACE FUNCTION
pwc169.task1_plperl( int )
RETURNS SETOF int
AS $CODE$
my ($limit) = @_;
my $is_prime = sub {
my ($value) = @_;
for ( 2 .. $value - 1 ) {
return 0 if $value % $_ == 0;
}
return 1;
};
my $compute_factors = sub {
my ($value) = @_;
my @factors;
for ( 2 .. $value - 1 ) {
next if ! $is_prime->( $_ );
while ( $value % $_ == 0 ) {
push @factors, $_;
$value /= $_;
}
}
return @factors;
};
for ( 1 .. 9999999 ) {
my @factors = $compute_factors->( $_ );
elog( DEBUG, "Number $_ with factors " . join(',', @factors) );
next if ( @factors != 2 );
next if $factors[ 0 ] == $factors[ 1 ];
if ( length( $factors[ 0 ] ) == length( $factors[ 1 ] ) ) {
$limit--;
return_next( $_ );
}
last if ! $limit;
}
return undef;
$CODE$
LANGUAGE plperl;
PWC 169 - Task 2 in PostgreSQL PL/Perl
Again, a translation of the Raku solution. This time however, I decided to use a module to take advantage ofgcd for a list, so the language has changed to plperlu to allow the system to load the Math::BigInt module:
CREATE OR REPLACE FUNCTION
pwc169.task2_plperl( int )
RETURNS SETOF int
AS $CODE$
use Math::BigInt;
my ($limit) = @_;
my $is_prime = sub {
my ($value) = @_;
for ( 2 .. $value - 1 ) {
return 0 if $value % $_ == 0;
}
return 1;
};
my $compute_factors = sub {
my ($value) = @_;
my @factors;
for ( 2 .. $value - 1 ) {
next if ! $is_prime->( $_ );
while ( $value % $_ == 0 ) {
push @factors, $_;
$value /= $_;
}
}
return @factors;
};
my $min = sub {
my $found = shift @_;
for ( @_ ) {
$found = $_ if $_ < $found;
}
return $found;
};
my $is_achille = sub {
my ($number) = @_;
my $bag = {};
for ( $compute_factors->( $number ) ) {
$bag->{ $_ }++;
}
return $min->( values( %$bag ) ) >= 2 && Math::BigInt::bgcd( values( %$bag ) )->numify == 1;
};
for ( 1 .. 999999 ) {
if ( $is_achille->( $_ ) ) {
$limit--;
return_next( $_ );
}
last if ! $limit;
}
return undef;
$CODE$
LANGUAGE plperlu;
I could have used other modules to get prime numbers and factors, but I preferred to keep as simpler as possible the solution.
Here implementing the
Bag class behavior is easy thanks to autovivification!
PWC 169 - Task 1 in PostgreSQL PL/PgSQL
Here I split the solution into different functions, that can provide theis_prime and compute_factors capabilities:
CREATE OR REPLACE FUNCTION
pwc169.compute_factors( n int )
RETURNS SETOF INT
AS $CODE$
DECLARE
i int;
BEGIN
FOR i IN 2 .. ( n - 1 ) LOOP
IF NOT pwc169.is_prime( i ) THEN
CONTINUE;
END IF;
WHILE n % i = 0 LOOP
RETURN NEXT i;
n = n / i;
END LOOP;
END LOOP;
RETURN;
END
$CODE$
LANGUAGE plpgsql;
CREATE OR REPLACE FUNCTION
pwc169.task1_plpgsql( n int DEFAULT 20 )
RETURNS SETOF INT
AS $CODE$
DECLARE
i int;
f int;
current_length int := 0;
current_count int := 0;
ok bool := false;
previous_f int := 0;
BEGIN
FOR i IN 2 .. 100000 LOOP
current_length := 0;
current_count := 0;
ok := true;
previous_f := 0;
FOR f IN SELECT * FROM pwc169.compute_factors( i ) ORDER BY 1 LOOP
current_count := current_count + 1;
IF current_length = 0 THEN
current_length := length( f::text );
END IF;
IF length( f::text ) <> current_length OR current_count > 2 OR f = previous_f THEN
ok := false;
EXIT;
END IF;
previous_f := f;
END LOOP;
IF ok AND previous_f <> 0 THEN
RETURN NEXT i;
IF n = 0 THEN
RETURN;
END IF;
n := n - 1;
END IF;
END LOOP;
RETURN;
END
$CODE$
LANGUAGE plpgsql;
The main loop within the
task1_plpgsql() function iterates over all numbers, and then inner-interates on factors. For each factor I see if I’ve reached more than two factors, or if the same factor is present, so that I can quickly exit. Otherwise, if the text representation of the numbers has the same length, I can spurt the number appending it to the result set.
PWC 169 - Task 2 in PostgreSQL PL/PgSQL
Exploiting the sameis_prime and compute_factors functions from the previous task, and the PostgreSQL inner gcd (that works on a couple of numbers at a time), the code can be implemented as follows:
CREATE OR REPLACE FUNCTION
pwc169.task2_plpgsql( n int DEFAULT 20 )
RETURNS SETOF INT
AS $CODE$
DECLARE
i int;
current_min int;
current_gcd int;
previous_gcd int;
BEGIN
FOR i IN 1 .. 999999 LOOP
WITH bag AS (
SELECT f, count(*) AS counter
FROM pwc169.compute_factors( i ) f
GROUP BY f
)
SELECT min( counter )
INTO current_min
FROM bag
;
IF current_min < 2 THEN
CONTINUE;
END IF;
previous_gcd := -1;
FOR current_gcd IN SELECT count(f) FROM pwc169.compute_factors( i ) f GROUP BY f LOOP
IF previous_gcd < 0 THEN
previous_gcd := current_gcd;
CONTINUE;
END IF;
previous_gcd := gcd( previous_gcd, current_gcd );
END LOOP;
IF previous_gcd = 1 THEN
RETURN NEXT i;
IF n = 0 THEN
RETURN;
END IF;
n := n - 1;
END IF;
END LOOP;
RETURN;
END
$CODE$
LANGUAGE plpgsql;
Note the inner query that exploits a CTE named
bag in honor of the same Bag class used in the Raku solution.