How to resolve the algorithm Brilliant numbers step by step in the Perl programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Brilliant numbers step by step in the Perl programming language

Table of Contents

Problem Statement

Brilliant numbers are a subset of semiprime numbers. Specifically, they are numbers that are the product of exactly two prime numbers that both have the same number of digits when expressed in base 10. Brilliant numbers are useful in cryptography and when testing prime factoring algorithms.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Brilliant numbers step by step in the Perl programming language

Source code in the perl programming language

use strict;
use warnings;
use feature 'say';
use List::AllUtils <max head firstidx uniqint>;
use ntheory <primes is_semiprime forsetproduct>;

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

my(@B,@Br);
for my $oom (1..5) {
    my @P = grep { $oom == length } @{primes(10**$oom)};
    forsetproduct { is_semiprime($_[0] * $_[1]) and push @B, $_[0] * $_[1] } \@P, \@P;
    @Br = uniqint sort { $a <=> $b } @Br, @B;
}

say "First 100 brilliant numbers:\n" . table 10, head 100, @Br;

for my $oom (1..9) {
    my $key = firstidx { $_ > 10**$oom } @Br;
    printf "First >= %13s is position %9s in the series: %13s\n", comma(10**$oom), comma($key), comma $Br[$key];
}


use 5.020;
use strict;
use warnings;

use ntheory qw(:all);
use experimental qw(signatures);

sub is_briliant_number ($n) {
    is_semiprime($n) || return;
    my @f = factor($n);
    length($f[0]) == length($f[1]);
}

sub next_brilliant_number ($n) {
    ++$n while not is_briliant_number($n);
    $n;
}

sub brilliant_numbers_count ($n) {

    use integer;

    my $count = 0;
    my $len   = length(sqrtint($n));

    foreach my $k (1 .. $len - 1) {
        my $pi = prime_count(10**($k - 1), 10**$k - 1);
        $count += binomial($pi, 2) + $pi;
    }

    my $min = 10**($len - 1);
    my $max = 10**$len - 1;

    my $pi_min = prime_count($min);
    my $pi_max = prime_count($max);

    my $j  = -1;

    forprimes {
        if ($_*$_ <= $n) {
            $count += (($max <= $n/$_) ? $pi_max : prime_count($n/$_)) - $pi_min - ++$j;
        }
        else {
            lastfor;
        }
    } $min, $max;

    return $count;
}

say "First 100 brilliant numbers:";

my @nums;

for (my $k = 1 ; scalar(@nums) < 100 ; ++$k) {
    push(@nums, $k) if is_briliant_number($k);
}

while (@nums) {
    my @slice = splice(@nums, 0, 10);
    say join ' ', map { sprintf("%4s", $_) } @slice;
}

say '';

foreach my $n (1 .. 13) {
    my $v = next_brilliant_number(vecprod((10) x $n));
    printf("First brilliant number >= 10^%d is %s", $n, $v);
    printf(" at position %s\n", brilliant_numbers_count($v));
}


  

You may also check:How to resolve the algorithm Substring step by step in the Maple programming language
You may also check:How to resolve the algorithm Memory layout of a data structure step by step in the ALGOL 68 programming language
You may also check:How to resolve the algorithm Stair-climbing puzzle step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Sorting Algorithms/Circle Sort step by step in the Nim programming language
You may also check:How to resolve the algorithm Munchausen numbers step by step in the Kotlin programming language