Super-Poulet numbers: Difference between revisions
Add Mathematica/Wolfram Language implementation
(→{{header|Ruby}}: Add Ruby) |
(Add Mathematica/Wolfram Language implementation) |
||
| (5 intermediate revisions by 5 users not shown) | |||
Line 1:
{{
A [[wp:Super-Poulet_number|super-Poulet number]] is a [[wp:Fermat_pseudoprime|Poulet number]] (or Fermat pseudoprime to base 2) whose every divisor '''''d''''' evenly divides '''''2<sup>d</sup> − 2'''''.
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 184 ⟶ 288:
The first super-Poulet number over 1 million is the 109th one, which is 1016801
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}}==
<syntaxhighlight lang="Nim">import std/[strformat, strutils]
proc powMod*(a, n, m: int): int =
## Return "a^n mod m".
var a = a mod m
var n = n
if a > 0:
result = 1
while n > 0:
if (n and 1) != 0:
result = (result * a) mod m
n = n shr 1
a = (a * a) mod m
func isPrime(n: Natural): bool =
## Return true if "n" is prime.
if n < 2: return false
if (n and 1) == 0: return n == 2
if n mod 3 == 0: return n == 3
var k = 5
var delta = 2
while k * k <= n:
if n mod k == 0: return false
inc k, delta
delta = 6 - delta
result = true
iterator divisors(n: Positive): int =
## Yield the divisors of "n", except 1.
yield n
var d = 2
while d * d <= n:
if n mod d == 0:
let q = n div d
yield d
if q != d:
yield q
inc d
func isSuperPouletNumber(n: int): bool =
## Return true is "x" is a Fermat pseudoprime to base "a".
if n.isPrime or powMod(2, n - 1, n) != 1: return false
for d in n.divisors:
if powMod(2, d, d) != 2:
return false
result = true
var n = 2
var count = 0
while true:
if n.isSuperPouletNumber:
inc count
if count <= 20:
stdout.write &"{n:5}"
stdout.write if count mod 5 == 0: '\n' else: ' '
if count == 20: echo()
elif n > 1_000_000:
echo &"First super-Poulet number greater than one million is {insertSep($n)} at index {count}."
break
inc n
</syntaxhighlight>
{{out}}
<pre> 341 1387 2047 2701 3277
4033 4369 4681 5461 7957
8321 10261 13747 14491 15709
18721 19951 23377 31417 31609
First super-Poulet number greater than one million is 1_016_801 at index 109.
</pre>
Line 341 ⟶ 547:
341, 1387, 2047, 2701, 3277, 4033, 4369, 4681, 5461, 7957, 8321, 10261, 13747, 14491, 15709, 18721, 19951, 23377, 31417, 31609
Value and index of first super-Poulet number greater than 1000000:
1016801 is #109
Value and index of first super-Poulet number greater than 10000000:
10031653 is #317
</pre>
=={{header|Swift}}==
{{trans|C++}}
Line 483 ⟶ 690:
{{libheader|Wren-gmp}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./gmp" for Mpz
import "./fmt" for Fmt
| |||