Super-Poulet numbers: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (Remove draft tag. Draft for over a year, multiple implementations, little controversy) |
(New post.) |
||
Line 162: | Line 162: | ||
Task example:<syntaxhighlight lang="j"> 20{. (#~ is_super_poulet) 1+i.1e5 |
Task example:<syntaxhighlight lang="j"> 20{. (#~ is_super_poulet) 1+i.1e5 |
||
341 1387 2047 2701 3277 4033 4369 4681 5461 7957 8321 10261 13747 14491 15709 18721 19951 23377 31417 31609</syntaxhighlight> |
341 1387 2047 2701 3277 4033 4369 4681 5461 7957 8321 10261 13747 14491 15709 18721 19951 23377 31417 31609</syntaxhighlight> |
||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java"> |
|||
import java.util.Set; |
|||
import java.util.TreeSet; |
|||
public final class SuperPouletNumbers { |
|||
public static void main(String[] args) { |
|||
int n = 2; |
|||
int count = 0; |
|||
boolean searching = true; |
|||
while ( searching ) { |
|||
if ( isSuperPouletNumber(n) ) { |
|||
count += 1; |
|||
if ( count <= 20 ) { |
|||
System.out.print(String.format("%6d%s", n, ( count % 5 == 0 ? "\n" : " " ))); |
|||
} else if ( n > 1_000_000 ) { |
|||
System.out.println(System.lineSeparator() + |
|||
"The first super-Poulet number greater than one million is " + n + " at index " + count); |
|||
searching = false; |
|||
} |
|||
} |
|||
n += 1; |
|||
} |
|||
} |
|||
private static boolean isSuperPouletNumber(int number) { |
|||
if ( isPrime(number) || modulusPower(2, number - 1, number) != 1 ) { |
|||
return false; |
|||
} |
|||
for ( int divisor : divisors(number) ) { |
|||
if ( modulusPower(2, divisor, divisor) != 2 ) { |
|||
return false; |
|||
} |
|||
} |
|||
return true; |
|||
} |
|||
// Return the divisors of the given number, excluding 1 |
|||
private static Set<Integer> divisors(int number) { |
|||
Set<Integer> result = new TreeSet<Integer>(); |
|||
for ( int d = 2; d * d <= number; d++ ) { |
|||
if ( number % d == 0 ) { |
|||
result.add(d); |
|||
result.add(number / d); |
|||
} |
|||
} |
|||
result.add(number); |
|||
return result; |
|||
} |
|||
private static long modulusPower(long base, long exponent, long modulus) { |
|||
if ( modulus == 1 ) { |
|||
return 0; |
|||
} |
|||
base %= modulus; |
|||
long result = 1; |
|||
while ( exponent > 0 ) { |
|||
if ( ( exponent & 1 ) == 1 ) { |
|||
result = ( result * base ) % modulus; |
|||
} |
|||
base = ( base * base ) % modulus; |
|||
exponent >>= 1; |
|||
} |
|||
return result; |
|||
} |
|||
private static boolean isPrime(int number) { |
|||
if ( number < 2 ) { |
|||
return false; |
|||
} |
|||
if ( number % 2 == 0 ) { |
|||
return number == 2; |
|||
} |
|||
if ( number % 3 == 0 ) { |
|||
return number == 3; |
|||
} |
|||
int delta = 2; |
|||
int k = 5; |
|||
while ( k * k <= number ) { |
|||
if ( number % k == 0 ) { |
|||
return false; |
|||
} |
|||
k += delta; |
|||
delta = 6 - delta; |
|||
} |
|||
return true; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
341 1387 2047 2701 3277 |
|||
4033 4369 4681 5461 7957 |
|||
8321 10261 13747 14491 15709 |
|||
18721 19951 23377 31417 31609 |
|||
The first super-Poulet number greater than one million is 1016801 at index 109 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |