

 This page uses content from Wikipedia. The original article was at Achilles number. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



An Achilles number is a number that is powerful but imperfect. 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, p2 is also a divisor.

In other words, every prime factor appears at least squared in the factorization.

All Achilles numbers are powerful. However, not all powerful numbers are Achilles numbers: only those that cannot be represented as mk, where m and k are positive integers greater than 1.



A strong Achilles number is an Achilles number whose Euler totient (𝜑) is also an Achilles number.



E.G.
108 is a powerful number. Its prime factorization is 22 × 33, and thus its prime factors are 2 and 3. Both 22 = 4 and 32 = 9 are divisors of 108. However, 108 cannot be represented as mk, where m and k are positive integers greater than 1, so 108 is an Achilles number.

360 is not an Achilles number because it is not powerful. One of its prime factors is 5 but 360 is not divisible by 52 = 25.

Finally, 784 is not an Achilles number. It is a powerful number, because not only are 2 and 7 its only prime factors, but also 22 = 4 and 72 = 49 are divisors of it. Nonetheless, it is a perfect power; its square root is an even integer, so it is not an Achilles number.


500 = 22 × 53 is a strong Achilles number as its Euler totient, 𝜑(500), is 200 = 23 × 52 which is also an Achilles number.



Task
 Find and show the first 50 Achilles numbers.
 Find and show at least the first 20 strong Achilles numbers.
 For at least 2 through 5, show the count of Achilles numbers with that many digits.


See also
 Wikipedia: Achilles number
 OEIS:A052486 - Achilles numbers - powerful but imperfect numbers
 OEIS:A194085 - Strong Achilles numbers: Achilles numbers m such that phi(m) is also an Achilles number
 Related task: Powerful numbers
 Related task: Totient function


Function GCD(n As Uinteger, d As Uinteger) As Uinteger
    Return Iif(d = 0, n, GCD(d, n Mod d))
End Function
 
Function Totient(n As Integer) As Integer
    Dim As Integer m, tot = 0
    For m = 1 To n
        If GCD(m, n) = 1 Then tot += 1
    Next m
    Return tot
End Function
 
Function isPowerful(m As Integer) As Boolean
    Dim As Integer n = m, f = 2, q, l = Sqr(m)
 
    If m <= 1 Then Return false
    Do
        q = n/f
        If (n Mod f) = 0 Then
            If (m Mod(f*f)) Then Return false
            n = q
            If f > n Then Exit Do
        Else    
            f += 1
            If f > l Then
                If (m Mod (n*n)) Then Return false
                Exit Do
            End If
        End If
    Loop
    Return true
End Function
 
Function isAchilles(n As Integer) As Boolean
    If Not isPowerful(n) Then Return false
    Dim As Integer m = 2, a = m*m
    Do
        Do
            If a = n Then Return false
            If a > n Then Exit Do
            a *= m
        Loop
        m += 1
        a = m*m
    Loop Until a > n
    Return true
End Function
 
Dim As Integer num, n, i
Dim As Single inicio
Dim As Double t0 = Timer
 
Print "First 50 Achilles numbers:"
num = 0
n = 1
Do
    If isAchilles(n) Then
        Print Using "#####"; n;
        num += 1
        If num >= 50 Then Exit Do
        If (num Mod 10) Then Print Space(3); Else Print
    End If
    n += 1
Loop
 
Print !"\n\nFirst 20 strong Achilles numbers:"
num = 0
n = 1
Do
    If isAchilles(n) And isAchilles(Totient(n)) Then
        Print Using "#####"; n;
        num += 1
        If num >= 20 Then Exit Do
        If (num Mod 10) Then Print Space(3); Else Print
    End If
    n += 1
Loop
 
Print !"\n\nNumber of Achilles numbers with:"
For i = 2 To 6
    inicio = Fix(10.0 ^ (i-1))
    num = 0
    For n = inicio To inicio*10-1
        If isAchilles(n) Then num += 1
    Next n
    Print i; " digits:"; num
Next i
Sleep