How to resolve the algorithm Achilles numbers step by step in the XPL0 programming language

Published on 12 May 2024 09:40 PM
#Xpl0

How to resolve the algorithm Achilles numbers step by step in the XPL0 programming language

Table of Contents

Problem Statement

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.

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.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Achilles numbers step by step in the XPL0 programming language

Source code in the xpl0 programming language

func GCD(N, D);         \Return the greatest common divisor of N and D
int  N, D;              \numerator and denominator
int  R;
[if D > N then
    [R:= D;  D:= N;  N:= R];    \swap D and N
while D > 0 do
    [R:= rem(N/D);
    N:= D;
    D:= R;
    ];
return N;
];      \GCD

func Totient(N);        \Return the totient of N
int  N, Phi, M;
[Phi:= 0;
for M:= 1 to N do
    if GCD(M, N) = 1 then Phi:= Phi+1;
return Phi;
];

func Powerful(N0);      \Return 'true' if N0 is a powerful number
int  N0, N, F, Q, L;
[if N0 <= 1 then return false;
N:= N0;  F:= 2;
L:= sqrt(N0);
loop    [Q:= N/F;
        if rem(0) = 0 then      \found a factor
                [if rem(N0/(F*F)) then return false;
                N:= Q;
                if F>N then quit;
                ]
        else    [F:= F+1;
                if F > L then
                    [if rem(N0/(N*N)) then return false;
                    quit;
                    ];
                ];
        ];
return true;
];

func Achilles(N);       \Return 'true' if N is an Achilles number
int  N, M, A;
[if not Powerful(N) then return false;
M:= 2;
A:= M*M;
repeat  loop    [if A = N then return false;
                if A > N then quit;
                A:= A*M;
                ];
        M:= M+1;
        A:= M*M;
until   A > N;
return true;
];

int Cnt, N, Pwr, Start;
[Cnt:= 0;
N:= 1;
loop    [if Achilles(N) then
            [IntOut(0, N);
            Cnt:= Cnt+1;
            if Cnt >= 50 then quit;
            if rem(Cnt/10) then ChOut(0, 9) else CrLf(0);
            ];
        N:= N+1;
        ];
CrLf(0);  CrLf(0);
Cnt:= 0;
N:= 1;
loop    [if Achilles(N) then
            if Achilles(Totient(N)) then
                [IntOut(0, N);
                Cnt:= Cnt+1;
                if Cnt >= 20 then quit;
                if rem(Cnt/10) then ChOut(0, 9) else CrLf(0);
                ];
        N:= N+1;
        ];
CrLf(0);  CrLf(0);
for Pwr:= 1 to 6 do
    [IntOut(0, Pwr);  Text(0, ": ");
    Start:= fix(Pow(10.0, float(Pwr-1)));
    Cnt:= 0;
    for N:= Start to Start*10-1 do
        if Achilles(N) then Cnt:= Cnt+1;
    IntOut(0, Cnt);  CrLf(0);
    ];
]

You may also check:How to resolve the algorithm Zig-zag matrix step by step in the Icon and Unicon programming language
You may also check:How to resolve the algorithm Bitcoin/address validation step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Anonymous recursion step by step in the Io programming language
You may also check:How to resolve the algorithm Damm algorithm step by step in the Factor programming language
You may also check:How to resolve the algorithm Permutation test step by step in the GAP programming language