Achilles numbers: Difference between revisions
Content added Content deleted
(Added Sidef) |
(Add C# implementation) |
||
Line 1,651: | Line 1,651: | ||
print i; " digits:"; num |
print i; " digits:"; num |
||
next i</syntaxhighlight> |
next i</syntaxhighlight> |
||
=={{header|C#}}== |
|||
{{trans|Java}} |
|||
{{works with| .NET 8}} |
|||
<syntaxhighlight lang="C#"> |
|||
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; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First 50 Achilles numbers: |
|||
72 108 200 288 392 432 500 648 675 800 |
|||
864 968 972 1125 1152 1323 1352 1372 1568 1800 |
|||
1944 2000 2312 2592 2700 2888 3087 3200 3267 3456 |
|||
3528 3872 3888 4000 4232 4500 4563 4608 5000 5292 |
|||
5324 5400 5408 5488 6075 6125 6272 6728 6912 7200 |
|||
First 50 strong Achilles numbers: |
|||
500 864 1944 2000 2592 3456 5000 10125 10368 12348 |
|||
12500 16875 19652 19773 30375 31104 32000 33275 37044 40500 |
|||
49392 50000 52488 55296 61731 64827 67500 69984 78608 80000 |
|||
81000 83349 84375 93312 108000 111132 124416 128000 135000 148176 |
|||
151875 158184 162000 165888 172872 177957 197568 200000 202612 209952 |
|||
Number of Achilles numbers with: |
|||
2 digits: 1 |
|||
3 digits: 12 |
|||
4 digits: 47 |
|||
5 digits: 192 |
|||
</pre> |
|||
[[https://dotnetfiddle.net/TCD2WC You may run it online!]] |
|||
=={{header|C++}}== |
=={{header|C++}}== |