Super-Poulet numbers: Difference between revisions
Add Mathematica/Wolfram Language implementation
Thundergnat (talk | contribs) m (Remove draft tag. Draft for over a year, multiple implementations, little controversy) |
(Add Mathematica/Wolfram Language implementation) |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 162:
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>
=={{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}}==
Line 185 ⟶ 289:
The first super-Poulet number over 10 million is the 317th one, which is 10031653
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
{{trans|Python}}
<syntaxhighlight lang="Mathematica">
(*Define the super-Poulet number test*)
IsSuperPoulet[n_Integer] :=
Module[{divisors, condition1, condition2}, divisors = Divisors[n];
condition1 = Not[PrimeQ[n]] && Mod[2^(n - 1), n] == 1;
condition2 = AllTrue[Most@divisors, Mod[2^# - 2, #] == 0 &];
condition1 && condition2];
(*Generate super-Poulet numbers up to 1,100,000*)
superPoulets = Select[Range[2, 1100000], IsSuperPoulet];
(*Print the first 20 super-Poulet numbers*)
Print["The first 20 super-Poulet numbers are: ",
superPoulets[[1 ;; 20]]];
(*Find and print the first super-Poulet number over 1 million*)
firstOverOneMillion = First@Select[superPoulets, # > 1000000 &];
idx1m = Position[superPoulets, firstOverOneMillion][[1, 1]];
Print["The first super-Poulet number over 1 million is the ", idx1m,
"th one, which is ", firstOverOneMillion];
</syntaxhighlight>
{{out}}
<pre>
The first 20 super-Poulet numbers are: {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 over 1 million is the 109th one, which is 1016801
</pre>
=={{header|Nim}}==
Line 556 ⟶ 690:
{{libheader|Wren-gmp}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./gmp" for Mpz
import "./fmt" for Fmt
| |||