Duffinian numbers: Difference between revisions
Content added Content deleted
No edit summary |
(New post.) |
||
Line 730: | Line 730: | ||
6399 6400 6401 |
6399 6400 6401 |
||
8449 8450 8451</syntaxhighlight> |
8449 8450 8451</syntaxhighlight> |
||
=={{header|Java}}== |
|||
<syntaxhighlight lang="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 sums 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); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
The first 50 Duffinian numbers: |
|||
4 8 9 16 21 25 27 32 35 36 39 49 50 55 57 63 64 65 75 77 81 85 93 98 100 |
|||
111 115 119 121 125 128 129 133 143 144 155 161 169 171 175 183 185 187 189 201 203 205 209 215 217 |
|||
The first 16 Duffinian triplets: |
|||
(63, 64, 65) (323, 324, 325) (511, 512, 513) (721, 722, 723) |
|||
(899, 900, 901) (1443, 1444, 1445) (2303, 2304, 2305) (2449, 2450, 2451) |
|||
(3599, 3600, 3601) (3871, 3872, 3873) (5183, 5184, 5185) (5617, 5618, 5619) |
|||
(6049, 6050, 6051) (6399, 6400, 6401) (8449, 8450, 8451) (10081, 10082, 10083) |
|||
</pre> |
|||
=={{header|jq}}== |
=={{header|jq}}== |