Zsigmondy numbers: Difference between revisions
New post.
Thundergnat (talk | contribs) m (Remove draft tag. Draft for over a year, multiple implementations, little controversy) |
(New post.) |
||
Line 187:
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133 5689910849522509 3949201</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public final class ZsigmondyNumbers {
public static void main(String[] args) {
record Pair(int a, int b) {}
List<Pair> pairs = List.of( new Pair(2, 1), new Pair(3, 1), new Pair(4, 1), new Pair(5, 1),
new Pair(6, 1), new Pair(7, 1), new Pair(3, 2), new Pair(5, 3), new Pair(7, 3), new Pair(7, 5) );
for ( Pair pair : pairs ) {
System.out.println("Zsigmondy(n, " + pair.a + ", " + pair.b + ")");
for ( int n = 1; n <= 18; n++ ) {
System.out.print(zsigmondyNumber(n, pair.a, pair.b) + " ");
}
System.out.println(System.lineSeparator());
}
}
private static long zsigmondyNumber(int n, int a, int b) {
final long dn = (long) ( Math.pow(a, n) - Math.pow(b, n) );
if ( isPrime(dn) ) {
return dn;
}
List<Long> divisors = divisors(dn);
for ( int m = 1; m < n; m++ ) {
long dm = (long) ( Math.pow(a, m) - Math.pow(b, m) );
divisors.removeIf( d -> gcd(dm, d) > 1 );
}
return divisors.get(divisors.size() - 1);
}
private static List<Long> divisors(long number) {
List<Long> result = new ArrayList<Long>();
for ( long d = 1; d * d <= number; d++ ) {
if ( number % d == 0 ) {
result.add(d);
if ( d * d < number ) {
result.add(number / d);
}
}
}
Collections.sort(result);
return result;
}
private static boolean isPrime(long number) {
if ( number < 2 ) {
return false;
}
if ( number % 2 == 0 ) {
return number == 2;
}
if ( number % 3 == 0 ) {
return number == 3;
}
int delta = 2;
long k = 5;
while ( k * k <= number ) {
if ( number % k == 0 ) {
return false;
}
k += delta;
delta = 6 - delta;
}
return true;
}
private static long gcd(long a, long b) {
while ( b != 0 ) {
long temp = a; a = b; b = temp % b;
}
return a;
}
}
</syntaxhighlight>
{{ out }}
<pre>
Zsigmondy(n, 2, 1)
1 3 7 5 31 1 127 17 73 11 2047 13 8191 43 151 257 131071 19
Zsigmondy(n, 3, 1)
2 1 13 5 121 7 1093 41 757 61 88573 73 797161 547 4561 3281 64570081 703
Zsigmondy(n, 4, 1)
3 5 7 17 341 13 5461 257 1387 41 1398101 241 22369621 3277 49981 65537 5726623061 4033
Zsigmondy(n, 5, 1)
4 3 31 13 781 7 19531 313 15751 521 12207031 601 305175781 13021 315121 195313 190734863281 5167
Zsigmondy(n, 6, 1)
5 7 43 37 311 31 55987 1297 46873 1111 72559411 1261 2612138803 5713 1406371 1679617 3385331888947 46441
Zsigmondy(n, 7, 1)
6 1 19 25 2801 43 137257 1201 39331 2101 329554457 2353 16148168401 102943 4956001 2882401 38771752331201 117307
Zsigmondy(n, 3, 2)
1 5 19 13 211 7 2059 97 1009 11 175099 61 1586131 463 3571 6817 129009091 577
Zsigmondy(n, 5, 3)
2 1 49 17 1441 19 37969 353 19729 421 24325489 481 609554401 10039 216001 198593 381405156481 12979
Zsigmondy(n, 7, 3)
4 5 79 29 4141 37 205339 1241 127639 341 494287399 2041 24221854021 82573 3628081 2885681 58157596211761 109117
Zsigmondy(n, 7, 5)
2 3 109 37 6841 13 372709 1513 176149 1661 964249309 1801 47834153641 75139 3162961 3077713 115933787267041 30133
</pre>
=={{header|jq}}==
| |||