Twenty-Two Brilliant Numbers

Wherein we discover a diamond can be a painful thing if stuck inside your shoe…

THE WEEKLY CHALLENGE – PERL & RAKU #169 — Task 1

---

“I cannot pretend to be impartial about the colours. I rejoice with the brilliant ones, and am genuinely sorry for the poor browns.“

— Winston Churchill

---

Brilliant Numbers

Submitted by: Mohammad S Anwar

Write a script to generate first 20 Brilliant Numbers.

Brilliant numbers are numbers with two prime factors of the same length.

The number should have exactly two prime factors, i.e. it’s the product of two primes of the same length.

For example,

24287 = 149 x 163
24289 = 107 x 227

Therefore 24287 and 24289 are 2-brilliant numbers.
These two brilliant numbers happen to be consecutive as there are no even brilliant numbers greater than 14.

Output

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

Discussion

Well, right off the bat we seem to have a problem, brought to light by a puzzling statement in the example, that “24287 and 24289 are 2-brilliant numbers”. Wait, what are 2-brilliant numbers? Does this refer to the 2 required factors, and if so, does the definition allow of 3- or more briliiant numbers as well?

Well, to cut to the chase, yes it does refer to the factor count, and as for whether other orders exist, well sort of. The answer has to do with why these numbers are useful. The quick answer is that the 2-factor brilliant numbers are the most useful, but others orders can exists, sure, and have their utility too.

This then is the definition for a set of brilliant numbers, and there can be, should we decide to define them, others, with different numbers of equally-long factors. But the basic definition is for 2 factors, and without further qualification this can be assumed. It appears, then, that the request is for the first 20 brilliant numbers as defined, which would mean 2-factor brilliant numbers only. ¹

So what even is a brilliant number, and why do they matter? Despite their simple definition, this is less clear. Although the rationale is still rooted in number theory, this sequence does not appear in the end to be in itself a number-theoretical pursuit. They’re composite numbers. There’s a lot of those. Rather, it’s that these numbers are used in other number-theoretical processes.

To explain: a number with two factors is by definition composite, which of course means it is not prime. And the restriction that the two factors have the same number of digits means they can only vary from another by a factor of nine times the largest largest digit place, which may sound large, but the two values will also hover around square root of the number factored, one above and one below. So compared to the size of the target, this range is quite constricted; one factor cannot be very small and the other many orders of magnitude larger.

What all this means is that the numbers are not prime, yet of all the composite numbers available to chose from, these numbers will have close to the largest equally-large pair of factors making them up. The brilliant numbers, consequently, will be those most difficult to factor using trial division. Or whatever factoring process you happen to be using, probably.

Which in turn brings us to why these numbers are useful: to provide maximally difficult targets for factoring algorithms.

---

¹ If, on the other hand, we were to want the first 20 n-brilliant numbers, selected from any order, then the problem becomes much weirder and trickier. It’s unclear why we would actually want to do this. Especially so as brilliant numbers are most useful when they are big, rather than small. The reasons for this will become clear.

---

METHOD

The nature of prime factoring — indeed the Fundamental Theorem of Arithmetic — says to our specific problem that every prime with a given number of digits, times any prime of the same length, inclusive, produces its own unique brilliant number. This much is settled law. Cross-multiplying the sets of primes of a given length will produce all of the brilliant numbers for that length.

So the only question remaining is ordering these products to determine the lowest 20 values. I propose we calculate an excess, say those for each of the one and two digit primes, and sort the results. We will then select the first twenty values from this sorted list.

Of note we can definitively conclude, by counting digits, that the list of brilliant numbers created as each new digit is allowed is complete: the largest two-digit multiple is smaller than the smallest three-digit multiple, and this relationship holds for all such increases. So the strategy is sound: by adding the new numbers from a larger factor size we expand our list of brilliant numbers without overlapping the ordering of those already created. As long as we compute all of the numbers from a given length we won’t need to worry about some yet-to-be computed interstitial combination interfering with our selection. There are ways to address these concerns and compute the values in order, but those are needlessly complex for the task.

PERL 5 SOLUTION

The most complicated part of the gathering is selecting the ranges one digit at a time, so as to only create cross products from combinations of the same length values. this is done using powers of ten and reselecting the prime sets for each new digit added.

The primes themselves are produced using the primes() function from Math::Prime::Util, aka ntheory.

To select the first twenty items, we use and array slice instead of a loop, because it’s fundamentally cooler.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

use ntheory qw( primes );

my @orders = (1,2);
my @bns;

for my $o ( @orders ) {
    my @p = primes( 1 * 10**($o-1), 10**$o - 1 )->@*;
    
    for my $i ( 0..@p-1 ) {
        for my $j ( $i..@p-1 ) {
            push @bns, $p[$i] * $p[$j];
        }
    }
}

@bns = sort {$a<=>$b} @bns;

say "@bns[0..19]";