Peter
Peter Campbell Smith

Brilliant and Achilles numbers

Weekly challenge 169 — 13 June 2022

Week 169 - 13 Jun 2022

Task 1

Task — Brilliant numbers

Write a script to generate first 20 Brilliant Numbers. Brilliant numbers are numbers with exactly two prime factors with the same number of digits.

Examples


Example 1:
24287 = 149 x 163

Example 2:
24289 = 107 x 227

Analysis

The criteria for brilliant numbers sound easy to met. For example, there are 21 2-digit prime numbers, yielding 231 brilliant numbers ranging from 441 to 9409, so they're not rare.

The ever-helpful Math::Prime::Util has a function factor($n) which returns a list of prime factors of its argument, so the algorithm looks like this:

  • Loop $test from 1 to something big until we've found 20 brilliant numbers
  • Get the prime factors (pf) of $test
  • Skip to the next $test unless pf contains exactly 2 same-length members
  • Else $test is brilliant

That generates the desired 20 numbers in microseconds, 2000 in under a second and 20 000 in under 15 seconds on my lowly Raspberry Pi. The 20 000th brilliant number is 2733299, which is 1117 x 2447.

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-06-13
# PWC 169 task 1

use v5.28;
use strict;
use warnings;
use utf8;
use Math::Prime::Util qw[factor];

my ($test, @pf, @result, $count, $j, $j_max);

# loop till done
$j = 0;
for ($test = 1, $count = 0; $count < 20; $test ++) {
    @pf = factor($test);
    
    # test for brilliance
    next unless (scalar @pf == 2 and length($pf[0]) == length($pf[1]));
    
    # accumulate answers
    $result[$j ++] = $test;
    $count ++;
}

# tell the world
for ($j = 0; $j < @result; $j ++) {
    print $result[$j];
    print ', ' unless $j == @result - 1;
    say '' if $j % 10 == 9;
}   

Output


4, 6, 9, 10, 14, 15, 21, 25, 35, 49, 
121, 143, 169, 187, 209, 221, 247, 253, 289, 299

The content of this website which has been created by
Peter Campbell Smith is hereby placed in the public domain