62 lines
1.5 KiB
Java
62 lines
1.5 KiB
Java
import java.util.Arrays;
|
|
|
|
public final class DuffianNumbers {
|
|
|
|
public static void main(String[] aArgs) {
|
|
int[] duffians = createDuffians(11_000);
|
|
|
|
System.out.println("The first 50 Duffinian numbers:");
|
|
int count = 0;
|
|
int n = 1;
|
|
while ( count < 50 ) {
|
|
if ( duffians[n] > 0 ) {
|
|
System.out.print(String.format("%4d%s", n, ( ++count % 25 == 0 ? "\n" : "" )));
|
|
}
|
|
n += 1;
|
|
}
|
|
System.out.println();
|
|
|
|
System.out.println("The first 16 Duffinian triplets:");
|
|
count = 0;
|
|
n = 3;
|
|
while( count < 16 ) {
|
|
if ( duffians[n - 2] > 0 && duffians[n - 1] > 0 && duffians[n] > 0 ) {
|
|
System.out.print(String.format("%22s%s",
|
|
"(" + ( n - 2 ) + ", " + ( n - 1 ) + ", " + n + ")", ( ++count % 4 == 0 ? "\n" : "" )));
|
|
}
|
|
n += 1;
|
|
}
|
|
System.out.println();
|
|
}
|
|
|
|
private static int[] createDuffians(int aLimit) {
|
|
// Create a list where list[i] is the divisor sum of i.
|
|
int[] result = new int[aLimit];
|
|
Arrays.fill(result, 1);
|
|
for ( int i = 2; i < aLimit; i++ ) {
|
|
for ( int j = i; j < aLimit; j += i ) {
|
|
result[j] += i;
|
|
}
|
|
}
|
|
|
|
// Set the divisor sum of non-Duffinian numbers to 0.
|
|
result[1] = 0; // 1 is not a Duffinian number.
|
|
for ( int n = 2; n < aLimit; n++ ) {
|
|
int resultN = result[n];
|
|
if ( resultN == n + 1 || gcd(n, resultN) != 1 ) {
|
|
// n is prime, or it is not relatively prime to its divisor sum.
|
|
result[n] = 0;
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
private static int gcd(int aOne, int aTwo) {
|
|
if ( aTwo == 0 ) {
|
|
return aOne;
|
|
}
|
|
return gcd(aTwo, aOne % aTwo);
|
|
}
|
|
|
|
}
|