How to resolve the algorithm Blum integer step by step in the Perl programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Blum integer step by step in the Perl programming language

Table of Contents

Problem Statement

A positive integer n is a Blum integer if n = p x q is a semi-prime for which p and q are distinct primes congruent to 3 mod 4. In other words, p and q must be of the form 4t + 3 where t is some non-negative integer.

21 is a Blum integer because it has two prime factors: 3 (= 4 x 0 + 3) and 7 (= 4 x 1 + 3). Find and show on this page the first 50 Blum integers. Also show the 26,828th.

Find and show the 100,000th, 200,000th, 300,000th and 400,000th Blum integers. For the first 400,000 Blum integers, show the percentage distribution by final decimal digit (to 3 decimal places). Clearly, such integers can only end in 1, 3, 7 or 9.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Blum integer step by step in the Perl programming language

Source code in the perl programming language

use v5.36;
use enum <false true>;
use ntheory <is_prime gcd>;

sub comma { reverse ((reverse shift) =~ s/.{3}\K/,/gr) =~ s/^,//r }
sub table ($c, @V) { my $t = $c * (my $w = 5); ( sprintf( ('%'.$w.'d')x@V, @V) ) =~ s/.{1,$t}\K/\n/gr }

sub is_blum ($n) {
    return false if $n < 2 or is_prime $n;
    my $factor = find_factor($n);
    my $div = int($n / $factor);
    return true if is_prime($factor) && is_prime($div) && ($div != $factor) && ($factor%4 == 3) && ($div%4 == 3);
    false;
}

sub find_factor ($n, $constant = 1) {
    my($x, $rho, $factor) = (2, 1, 1);
    while ($factor == 1) {
        $rho *= 2;
        my $fixed = $x;
        for (0..$rho) {
            $x = ( $x * $x + $constant ) % $n;
            $factor = gcd(($x-$fixed), $n);
            last if 1 < $factor;
        }
    }
    $factor = find_factor($n, $constant+1) if $n == $factor;
    $factor;
}

my($i, @blum, %C);
my @nth = (26828, 1e5, 2e5, 3e5, 4e5);

while (++$i) {
    push @blum, $i if is_blum $i;
    last if $nth[-1] == scalar @blum;
}
$C{substr $_, -1, 1}++ for @blum;

say "The first fifty Blum integers:\n" . table 10, @blum[0..49];
printf "The %7sth Blum integer: %9s\n", comma($_), comma $blum[$_-1] for @nth;
say '';
printf "$_: %6d (%.3f%%)\n", $C{$_}, 100*$C{$_}/scalar @blum for <1 3 7 9>;


  

You may also check:How to resolve the algorithm Guess the number/With feedback step by step in the Lambdatalk programming language
You may also check:How to resolve the algorithm Generate random chess position step by step in the Typescript programming language
You may also check:How to resolve the algorithm Check that file exists step by step in the Pop11 programming language
You may also check:How to resolve the algorithm Roman numerals/Encode step by step in the C programming language
You may also check:How to resolve the algorithm Pascal matrix generation step by step in the Fortran programming language