Brilliant and Achilles numbers

Weekly challenge 169 — 13 June 2022

Week 169 - 13 Jun 2022

Task 2

Write a script to generate the first 20 Achilles Numbers. An Achilles number is a number that is powerful but imperfect (not a perfect power).

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 a perfect power if it has any integer roots (square root, cube root, etc).

These numbers are named after Achilles, a hero of the Trojan war, who was also powerful but imperfect, and are described further in Wikipedia.

Example 1: 36 factors to (2, 2, 3, 3) - every prime factor (2, 3) also has its square as a divisor (4, 9). But 36 has an integer square root, 6, so the number is a perfect power and therefore not an Achilles number.Example 2: 72 factors to (2, 2, 2, 3, 3); it similarly has 4 and 9 as divisors, but it has no integer roots. This is an Achilles number.

My algorithm looks like this:

- Loop
`$test`

from 1 to something big until we've found 20 Achilles numbers - Check for powerfulness:
- 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
`$p`

is a factor`$f`

and store that in`$seen[$f]`

- For each prime factor
- Check for imperfection:
- if any
`$seen[$f] < 2`

-- no good

- if any
- 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`

- Find the least frequently occurring prime factor: say it occurs
- ... and if all those checks pass,
`$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

We have already checked n for imperfection, so z must be at least 2. But if z is 2, then:

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 1151064, which is 2^3 * 3^3 * 73^2.

#!/usr/bin/perl # Peter Campbell Smith - 2022-06-13 # PWC 169 task 2 use v5.28; use strict; use warnings; use utf8; use Math::Prime::Util qw[factor]; my ($test, @pf, $f, @result, $count, $dpf, %seen, $p, $rarest_factor, $good, $j); # loop from 1 up until done TEST: for ($test = 1, $count = 0; $count < 20; $test ++) { # get prime factors @pf = factor($test); # test for powerfulness $dpf = 0; %seen = (); for $f (@pf) { # discard unless $test is a multiple of prime factor $f squared next TEST unless $test % ($f ** 2) == 0; # count distinct prime factors and their frequency $dpf ++ unless $seen{$f}; $seen{$f} ++; } # test for imperfection next unless $dpf >= 2; # test for not a perfect power: first find the least frequently repeating prime factor $rarest_factor = ~0; for $f (keys %seen) { last if $seen{$f} == 1; $rarest_factor = $seen{$f} if $seen{$f} < $rarest_factor; } # then check that at least one other pf repeats a non-multiple of time the least frequent $good = 0; for $f (keys %seen) { $good = 1 if $seen{$f} % $rarest_factor != 0; } next TEST unless $good; # 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; }

72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125, 1152, 1323, 1352, 1372, 1568, 1800

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain