using System;

using System.Collections.Generic;

using System.Linq;

​

public class AchillesNumbers

{

    public static void Main(string[] args)

    {

        var perfectPowers = PerfectPowers(500000);

        var achilles = Achilles(1, 250000, perfectPowers);

        var totients = Totients(250000);

​

        Console.WriteLine("First 50 Achilles numbers:");

        for (int i = 0; i < 50; i++)

        {

            Console.Write($"{achilles[i],4}{((i + 1) % 10 == 0 ? "\n" : " ")}");

        }

        Console.WriteLine();

​

        Console.WriteLine("First 50 strong Achilles numbers:");

        for (int i = 0, count = 0; count < 50; i++)

        {

            if (achilles.Contains(totients[achilles[i]]))

            {

                Console.Write($"{achilles[i],6}{(++count % 10 == 0 ? "\n" : " ")}");

            }

        }

        Console.WriteLine();

​

        Console.WriteLine("Number of Achilles numbers with:");

        for (int i = 100; i < 1000000; i *= 10)

        {

            int digits = i.ToString().Length - 1;

            Console.WriteLine($"    {digits} digits: {Achilles(i / 10, i - 1, perfectPowers).Count}");

        }

    }

​

    private static List<int> Achilles(int from, int to, HashSet<int> perfectPowers)

    {

        var result = new SortedSet<int>();

        int cubeRoot = (int)Math.Cbrt(to / 4);

        int squareRoot = (int)Math.Sqrt(to / 8);

​

        for (int b = 2; b <= cubeRoot; b++)

        {

            int bCubed = b * b * b;

            for (int a = 2; a <= squareRoot; a++)

            {

                int achilles = bCubed * a * a;

                if (achilles >= to) break;

                if (achilles >= from && !perfectPowers.Contains(achilles))

                {

                    result.Add(achilles);

                }

            }

        }

        return result.ToList();

    }

​

    private static HashSet<int> PerfectPowers(int n)

    {

        var result = new HashSet<int>();

        for (int i = 2, root = (int)Math.Sqrt(n); i <= root; i++)

        {

            for (int perfect = i * i; perfect < n; perfect *= i)

            {

                result.Add(perfect);

            }

        }

        return result;

    }

​

    private static List<int> Totients(int n)

    {

        var result = Enumerable.Range(0, n + 1).ToList();

        for (int i = 2; i <= n; i++)

        {

            if (result[i] == i)

            {

                result[i] = i - 1;

                for (int j = i * 2; j <= n; j += i)

                {

                    result[j] = (result[j] / i) * (i - 1);

                }

            }

        }

        return result;

    }

}

​