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 of gcd 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 the is_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 same is_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.

The article Perl Weekly Challenge 169: primes, primes, and more primes! has been posted by Luca Ferrari on June 13, 2022