A Tendon-ous Task

Wherein we find our fatal flaw…

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

---

“I don’t get a sense of American pride. I just get a sense that everyone is here, battling the same thing – that around the world everybody’s after the same thing, just some minor piece of happiness each day.”

— Paul Thomas Anderson

---

Achilles Numbers

Submitted by: Mohammad S Anwar

Write a script to generate first 20 Achilles Numbers. Please checkout wikipedia for more information.

An Achilles number is a number that is powerful but imperfect (not a perfect power). Named after Achilles, a hero of the Trojan war, who was also 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 a perfect power if it has any integer roots (square root, cube root, etc.).

For example, 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.

But 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.

Output

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

Discussion

One unexpected delight in the past year’s excursions into number theory has been the amount of wordplay involved. One probably wouldn’t expect that from a mathematical crowd, but then again play is play, and people who like to play have a tendency to play with whatever they have around them — numbers, words, game tokens, often wrapped in stories and fictional flights of fancy.

Enter Achilleus, in the Ancient Greek Ἀχιλλεύς, a demigod who fought for Athens in the Trojan Wars. Achilleus, known in English more often as Achilles, was the progeny of a god and a nymph. Although this union produced a mortal man, Achilleus did retain some of the powers of the his father, and as fighter was commonly characterized as being invincible in battle. He was Athen’s greatest warrior in the fight against Troy.

Achilleus was a proud man, and he himself stated that he was driven in his successes by his pride. Excessive pride, ὕβρις or hubris, was frowned upon by the gods as unbecoming, taken to be a sign of man upsetting his station in the world, improperly venturing into the territory of the gods. When Achilleus refuses to fight for his side because of a perceived slight this pridefulness comes to a head. His friend, unable to sway his stubborn judgement, goes to the battlefield to lead his men in his stead and is killed. Enraged by this personal loss, Achilleus rejoins the battle and in his ruthless valor looks to single-handedly tip the scales back to Athens and win the war.

However it was not fated that Achilleus should take such a role, and with this the gods took notice. He was already on watch for his hubris. Achilleus had fought for himself, his pride, not his people, and when he had first reacted to a slight had started a chain of events that produced first the death of his friend and now was threatening the divine role of the fates themselves.

This would not do. Achilleus’ essential hubris became his ἁμαρτία, or hamartíā: his fatal flaw. — his undoing. And the Greek gods were known for violent and disproportionate justice when correcting transgressions of the natural order.

against the inconsequence of mere mortals. Although his prowness on the battlefield made him seem untouchable in a fight, Apollo personally guided an arrow into his heart, killing him.

So Achilleus is the most powerful warrior in the Athenian army, but for all that power had a fatal flaw, hamartíā, that led to his downfall.

---

The wordplay in the labeling this particular sequence as Achilles Numbers is layered like an onion. Numbers whose prime factors are all raised to at least the power of 2 are known as powerful numbers. Because, you know, they are full of powers. Then we have numbers that are the product of an exponential term, such as a value being squared or cubed, or raised to a higher power. As a group, these are known as perfect powers: perfect squares, perfect cubes, and so on.

So a powerful number that is also is imperfect, which is to say it is powerful but not a perfect power, is like Achilles.

METHOD

For a number to be powerful, it must have all of its prime factors at least doubled.

For a number to be a perfect power, then the count of all of its prime factors must be at least two, and furthermore the count of each prime must have a single common divisor greater than one. That is, that a common exponent must be able to be wholly isolated to be the integer root power.

324 = 2 x 2 x 3 x 3 x 3 x 3 = 2² x 3⁴ = (2¹ x 3²)² = (2 x 3²)² = 18²,

so 18 is the integral square root. The frequencies of the individual prime factors don’t need to be equal, or even a whole fraction of each other, as long as they share a greatest common divisor of at least 2.

So we’re going to count primes among the factors. If the count of each prime is greater than 1, but the counts have a GCD of only 1 , then we have found an Achilles Number.

PERL 5 SOLUTION

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

use ntheory qw( factor gcd );
use constant { QUANTITY => 20 };

my @achilles;
my $candidate = 1;

while ( $candidate++ ) {
    my @f = factor( $candidate );
    my %freq;
    $freq{$_}++ for @f;
    
    my @values = sort {$a<=>$b} values %freq;
            
    next if $values[0]     == 1;    ## not powerful
    next if gcd( @values ) >  1;    ## is perfect power

    push @achilles, $candidate;
    last if @achilles == QUANTITY;
}

say "@achilles";