Achilles numbers: Difference between revisions
Content added Content deleted
(→{{header|C#}}: fix typo) |
(→{{header|Java}}: update java code, correct result of "Number of Achilles numbers with" from up to 5 digits to up to 8 digits) |
||
Line 2,392: | Line 2,392: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
<syntaxhighlight lang="java"> |
<syntaxhighlight lang="java"> |
||
import java.util.ArrayList; |
import java.util.ArrayList; |
||
import java.util.Collections; |
|||
import java.util.HashMap; |
|||
import java.util.List; |
import java.util.List; |
||
import java.util. |
import java.util.Map; |
||
import java.util.TreeSet; |
|||
import java.util.stream.Collectors; |
|||
import java.util.stream.IntStream; |
|||
public |
public class AchillesNumbers { |
||
private Map<Integer, Boolean> pps = new HashMap<>(); |
|||
public static void main(String[] aArgs) { |
|||
Set<Integer> perfectPowers = perfectPowers(500_000); |
|||
List<Integer> achilles = achilles(1, 250_000, perfectPowers); |
|||
List<Integer> totients = totients(250_000); |
|||
public int totient(int n) { |
|||
System.out.println("First 50 Achilles numbers:"); |
|||
int tot = n; |
|||
int i = 2; |
|||
System.out.print(String.format("%4d%s", achilles.get(i), ( ( i + 1 ) % 10 == 0 ) ? "\n" : " ")); |
|||
while (i * i <= n) { |
|||
} |
|||
if (n % i == 0) { |
|||
System.out.println(); |
|||
while (n % i == 0) { |
|||
n /= i; |
|||
System.out.println("First 50 strong Achilles numbers:"); |
|||
} |
|||
tot -= tot / i; |
|||
if ( achilles.contains(totients.get(achilles.get(i))) ) { |
|||
} |
|||
System.out.print(String.format("%6d%s", achilles.get(i), ( ++count % 10 == 0 ) ? "\n" : " ")); |
|||
if (i == 2) { |
|||
} |
|||
i = 1; |
|||
} |
|||
} |
|||
System.out.println(); |
|||
i += 2; |
|||
} |
|||
System.out.println("Number of Achilles numbers with:"); |
|||
if (n > 1) { |
|||
tot -= tot / n; |
|||
final int digits = String.valueOf(i).length() - 1; |
|||
} |
|||
System.out.println(" " + digits + " digits: " + achilles(i / 10, i - 1, perfectPowers).size()); |
|||
return tot; |
|||
} |
|||
} |
|||
} |
|||
private static List<Integer> achilles(int aFrom, int aTo, Set<Integer> aPerfectPowers) { |
|||
Set<Integer> result = new TreeSet<Integer>(); |
|||
final int cubeRoot = (int) Math.cbrt(aTo / 4); |
|||
final int squareRoot = (int) Math.sqrt(aTo / 8); |
|||
for ( int b = 2; b <= cubeRoot; b++ ) { |
|||
final int bCubed = b * b * b; |
|||
for ( int a = 2; a <= squareRoot; a++ ) { |
|||
int achilles = bCubed * a * a; |
|||
if ( achilles >= aTo ) { |
|||
break; |
|||
} |
|||
if ( achilles >= aFrom && ! aPerfectPowers.contains(achilles) ) { |
|||
result.add(achilles); |
|||
} |
|||
} |
|||
} |
|||
return new ArrayList<Integer>(result); |
|||
} |
|||
private static Set<Integer> perfectPowers(int aN) { |
|||
Set<Integer> result = new TreeSet<Integer>(); |
|||
for ( int i = 2, root = (int) Math.sqrt(aN); i <= root; i++ ) { |
|||
for ( int perfect = i * i; perfect < aN; perfect *= i ) { |
|||
result.add(perfect); |
|||
} |
|||
} |
|||
return result; |
|||
} |
|||
private static List<Integer> totients(int aN) { |
|||
List<Integer> result = IntStream.rangeClosed(0, aN).boxed().collect(Collectors.toList());; |
|||
for ( int i = 2; i <= aN; i++ ) { |
|||
if ( result.get(i) == i ) { |
|||
result.set(i, i - 1); |
|||
for ( int j = i * 2; j <= aN; j = j + i ) { |
|||
result.set(j, ( result.get(j) / i ) * ( i - 1 )); |
|||
} |
|||
} |
|||
} |
|||
return result; |
|||
} |
|||
public void getPerfectPowers(int maxExp) { |
|||
double upper = Math.pow(10, maxExp); |
|||
for (int i = 2; i <= Math.sqrt(upper); i++) { |
|||
double fi = i; |
|||
double p = fi; |
|||
while (true) { |
|||
p *= fi; |
|||
if (p >= upper) { |
|||
break; |
|||
} |
|||
pps.put((int) p, true); |
|||
} |
|||
} |
|||
} |
|||
public Map<Integer, Boolean> getAchilles(int minExp, int maxExp) { |
|||
double lower = Math.pow(10, minExp); |
|||
double upper = Math.pow(10, maxExp); |
|||
Map<Integer, Boolean> achilles = new HashMap<>(); |
|||
for (int b = 1; b <= (int) Math.cbrt(upper); b++) { |
|||
int b3 = b * b * b; |
|||
for (int a = 1; a <= (int) Math.sqrt(upper); a++) { |
|||
int p = b3 * a * a; |
|||
if (p >= (int) upper) { |
|||
break; |
|||
} |
|||
if (p >= (int) lower) { |
|||
if (!pps.containsKey(p)) { |
|||
achilles.put(p, true); |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return achilles; |
|||
} |
|||
public static void main(String[] args) { |
|||
AchillesNumbers an = new AchillesNumbers(); |
|||
int maxDigits = 8; |
|||
an.getPerfectPowers(maxDigits); |
|||
Map<Integer, Boolean> achillesSet = an.getAchilles(1, 5); |
|||
List<Integer> achilles = new ArrayList<>(achillesSet.keySet()); |
|||
Collections.sort(achilles); |
|||
System.out.println("First 50 Achilles numbers:"); |
|||
for (int i = 0; i < 50; i++) { |
|||
System.out.printf("%4d ", achilles.get(i)); |
|||
if ((i + 1) % 10 == 0) { |
|||
System.out.println(); |
|||
} |
|||
} |
|||
System.out.println("\nFirst 30 strong Achilles numbers:"); |
|||
List<Integer> strongAchilles = new ArrayList<>(); |
|||
int count = 0; |
|||
for (int n = 0; count < 30; n++) { |
|||
int tot = an.totient(achilles.get(n)); |
|||
if (achillesSet.containsKey(tot)) { |
|||
strongAchilles.add(achilles.get(n)); |
|||
count++; |
|||
} |
|||
} |
|||
for (int i = 0; i < 30; i++) { |
|||
System.out.printf("%5d ", strongAchilles.get(i)); |
|||
if ((i + 1) % 10 == 0) { |
|||
System.out.println(); |
|||
} |
|||
} |
|||
System.out.println("\nNumber of Achilles numbers with:"); |
|||
for (int d = 2; d <= maxDigits; d++) { |
|||
int ac = an.getAchilles(d - 1, d).size(); |
|||
System.out.printf("%2d digits: %d\n", d, ac); |
|||
} |
|||
} |
|||
} |
} |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
Line 2,475: | Line 2,504: | ||
<pre> |
<pre> |
||
First 50 Achilles numbers: |
First 50 Achilles numbers: |
||
72 108 200 288 392 432 500 648 675 800 |
72 108 200 288 392 432 500 648 675 800 |
||
864 968 972 1125 1152 1323 1352 1372 1568 1800 |
864 968 972 1125 1152 1323 1352 1372 1568 1800 |
||
1944 2000 2312 2592 2700 2888 3087 3200 3267 3456 |
1944 2000 2312 2592 2700 2888 3087 3200 3267 3456 |
||
3528 3872 3888 4000 4232 4500 4563 4608 5000 5292 |
3528 3872 3888 4000 4232 4500 4563 4608 5000 5292 |
||
5324 5400 5408 5488 6075 6125 6272 6728 6912 7200 |
5324 5400 5408 5488 6075 6125 6272 6728 6912 7200 |
||
First |
First 30 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: |
Number of Achilles numbers with: |
||
2 digits: 1 |
|||
3 digits: 12 |
|||
4 digits: 47 |
|||
5 digits: 192 |
|||
6 digits: 664 |
|||
7 digits: 2242 |
|||
8 digits: 7395 |
|||
</pre> |
</pre> |
||