Brilliant and Achilles
A brilliant number has exactly two prime factors, and they both have the same number of digits.
That sounds like an easily met pair of criteria. 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 which returns a list of prime factors of its argument. so the algorithm looks like this:
loop over 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
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 2 733 299, which is 1117 x 2447.
Write a script to generate first 20 Achilles Numbers: numbers that are powerful but imperfect. A positive integer n is a powerful number if, for every prime factor p of n, p^2 is also a divisor. A number is imperfect if it has at least two distinct prime factors.
So, my algorithm looks like this:
loop over test from 1 to something big until we've found 20 Achilles numbers
# check for powerful
for each prime factor (p) of test
if test isn't a multiple of p^2 -- no good
while we're here, count how many times (seen(f)) p is a factor f
# check for imperfection
if any seen(f) < 2 -- no good
# check for not being a perfect power
find the least frequently occurring prime factor: say it occurs m times
check that all the values in seen are *not* multiples of m
... and if that is the case, test is an Achilles number
The 'not a perfect power' criterion is quite tricky, although for the current exercise it could be done simply by calculating all the squares, cubes etc less than the number under test. To see why my way works, consider a number n with prime factors:
n = a^z * b^y * c^x * d^w
where a, b, c etc are primes, and they are ordered such that z <= y <= x <= w. Let's suppose that y, x and w are all multiples of z, so that:
n = a^z * b^2z * c^6z * d^8z
n = (a * b^z * c^3z * d^4z) ^2
and n is therefore a perfect square. Similarly, if z = 3 and y, x, w etc are all multiples of 3, then n is a perfect cube. And so on.
So the 'not a perfect power' rule boils down to any of the coefficients - ie the number of times each prime factor occurs - not being a multiple of the number of times the least frequent factor occurs.
Having worked all that out, the algorithm is quite fast, yielding 1000 Achilles numbers in under 10 seconds. The 1000th is 1 151 064, which is 2^3 * 3^3 * 73^2.