109 lines
3.1 KiB
Java
109 lines
3.1 KiB
Java
import java.util.ArrayList;
|
|
import java.util.Collections;
|
|
import java.util.HashMap;
|
|
import java.util.List;
|
|
import java.util.Map;
|
|
|
|
public class AchillesNumbers {
|
|
|
|
private Map<Integer, Boolean> pps = new HashMap<>();
|
|
|
|
public int totient(int n) {
|
|
int tot = n;
|
|
int i = 2;
|
|
while (i * i <= n) {
|
|
if (n % i == 0) {
|
|
while (n % i == 0) {
|
|
n /= i;
|
|
}
|
|
tot -= tot / i;
|
|
}
|
|
if (i == 2) {
|
|
i = 1;
|
|
}
|
|
i += 2;
|
|
}
|
|
if (n > 1) {
|
|
tot -= tot / n;
|
|
}
|
|
return tot;
|
|
}
|
|
|
|
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);
|
|
}
|
|
}
|
|
}
|