Repunit primes: Difference between revisions
Add PARI/GP implementation
Thundergnat (talk | contribs) (New draft task and Raku example) |
(Add PARI/GP implementation) |
||
| (40 intermediate revisions by 19 users not shown) | |||
Line 1:
{{
[[wp:Repunit|Repunit]] is a [[wp:Portmanteau|portmanteau]] of the words "repetition" and "unit", with unit being "unit value"... or in laymans terms, '''1'''. So 1, 11, 111, 1111 & 11111 are all repunits.
Every standard integer base has repunits since every base has the digit 1. This task involves finding the repunits in different bases that are prime.
In base two, the repunits 11, 111, 11111, 1111111, etc. are prime. (These correspond to the [[wp:Mersenne_prime|
In base three: 111, 1111111, 1111111111111, etc.
''
Any repunit in any base having a composite number of digits is necessarily composite. Only repunits (in any base) having a prime number of digits ''might'' be prime.
Line 16:
Rather than expanding the repunit out as a giant list of '''1'''s or converting to base 10, it is common to just list the ''number'' of '''1'''s in the repunit; effectively the digit count. The base two repunit primes listed above would be represented as: 2, 3, 5, 7, etc.
Many of these sequences exist on [[oeis:|OEIS]], though they aren't specifically listed as
Some bases have very few repunit primes. Bases 4, 8, and likely 16 have only one. Base 9 has none at all. Bases above 16 may have repunit primes as well... but this task is getting large enough already.
Line 33:
;See also
;* [[wp:Repunit#Repunit_primes|Wikipedia: Repunit primes]]
;* [[oeis:A000043|OEIS:A000043 - Mersenne exponents: primes p such that 2^p - 1 is prime. Then 2^p - 1 is called a Mersenne prime]] (base 2)
;* [[oeis:A028491|OEIS:A028491 - Numbers k such that (3^k - 1)/2 is prime]] (base 3)
Line 45:
;* [[oeis:A006032|OEIS:A006032 - Numbers k such that (14^k - 1)/13 is prime]] (base 14)
;* [[oeis:A006033|OEIS:A006033 - Numbers n such that (15^n - 1)/14 is prime]] (base 15)
;* [[Circular primes|Related task: Circular primes]]
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
{{libheader|ALGOL 68-primes}}
<syntaxhighlight lang="algol68">
BEGIN # find repunit (all digits are 1 ) primes in various bases #
INT max base = 16;
INT max repunit digits = 1000;
PR precision 3000 PR # set precision of LONG LONG INT #
# 16^1000 has ~1200 digits but the primality test needs more #
PR read "primes.incl.a68" PR # include prime utilities #
[]BOOL prime = PRIMESIEVE max repunit digits;
FOR base FROM 2 TO max base DO
LONG LONG INT repunit := 1;
print( ( whole( base, -2 ), ":" ) );
FOR digits TO max repunit digits DO
IF prime[ digits ] THEN
IF is probably prime( repunit ) THEN
# found a prime repunit in the current base #
print( ( " ", whole( digits, 0 ) ) )
FI
FI;
repunit *:= base +:= 1
OD;
print( ( newline ) )
OD
END
</syntaxhighlight>
{{out}}
<pre>
2: 2 3 5 7 13 17 19 31 61 89 107 127 521 607
3: 3 7 13 71 103 541
4: 2
5: 3 7 11 13 47 127 149 181 619 929
6: 2 3 7 29 71 127 271 509
7: 5 13 131 149
8: 3
9:
10: 2 19 23 317
11: 17 19 73 139 907
12: 2 3 5 19 97 109 317 353 701
13: 5 7 137 283 883 991
14: 3 7 19 31 41
15: 3 43 73 487
16: 2
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">getRepunit: function [n,b][
result: 1
loop 1..dec n 'z ->
result: result + b^z
return result
]
loop 2..16 'base [
print [
pad (to :string base) ++ ":" 4
join.with:", " to [:string] select 2..1001 'x ->
and? -> prime? x
-> prime? getRepunit x base
]
]</syntaxhighlight>
{{out}}
<pre> 2: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607
3: 3, 7, 13, 71, 103, 541
4: 2
5: 3, 7, 11, 13, 47, 127, 149, 181, 619, 929
6: 2, 3, 7, 29, 71, 127, 271, 509
7: 5, 13, 131, 149
8: 3
9:
10: 2, 19, 23, 317
11: 17, 19, 73, 139, 907
12: 2, 3, 5, 19, 97, 109, 317, 353, 701
13: 5, 7, 137, 283, 883, 991
14: 3, 7, 19, 31, 41
15: 3, 43, 73, 487
16: 2</pre>
=={{header|C++}}==
{{libheader|GMP}}
{{libheader|Primesieve}}
<syntaxhighlight lang="cpp">#include <future>
#include <iomanip>
#include <iostream>
#include <vector>
#include <gmpxx.h>
#include <primesieve.hpp>
std::vector<uint64_t> repunit_primes(uint32_t base,
const std::vector<uint64_t>& primes) {
std::vector<uint64_t> result;
for (uint64_t prime : primes) {
mpz_class repunit(std::string(prime, '1'), base);
if (mpz_probab_prime_p(repunit.get_mpz_t(), 25) != 0)
result.push_back(prime);
}
return result;
}
int main() {
std::vector<uint64_t> primes;
const uint64_t limit = 2700;
primesieve::generate_primes(limit, &primes);
std::vector<std::future<std::vector<uint64_t>>> futures;
for (uint32_t base = 2; base <= 36; ++base) {
futures.push_back(std::async(repunit_primes, base, primes));
}
std::cout << "Repunit prime digits (up to " << limit << ") in:\n";
for (uint32_t base = 2, i = 0; base <= 36; ++base, ++i) {
std::cout << "Base " << std::setw(2) << base << ':';
for (auto digits : futures[i].get())
std::cout << ' ' << digits;
std::cout << '\n';
}
}</syntaxhighlight>
{{out}}
This takes about 4 minutes 12 seconds (3.2GHz Quad-Core Intel Core i5).
<pre>
Repunit prime digits (up to 2700) in:
Base 2: 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281
Base 3: 3 7 13 71 103 541 1091 1367 1627
Base 4: 2
Base 5: 3 7 11 13 47 127 149 181 619 929
Base 6: 2 3 7 29 71 127 271 509 1049
Base 7: 5 13 131 149 1699
Base 8: 3
Base 9:
Base 10: 2 19 23 317 1031
Base 11: 17 19 73 139 907 1907 2029
Base 12: 2 3 5 19 97 109 317 353 701
Base 13: 5 7 137 283 883 991 1021 1193
Base 14: 3 7 19 31 41 2687
Base 15: 3 43 73 487 2579
Base 16: 2
Base 17: 3 5 7 11 47 71 419
Base 18: 2
Base 19: 19 31 47 59 61 107 337 1061
Base 20: 3 11 17 1487
Base 21: 3 11 17 43 271
Base 22: 2 5 79 101 359 857
Base 23: 5
Base 24: 3 5 19 53 71 653 661
Base 25:
Base 26: 7 43 347
Base 27: 3
Base 28: 2 5 17 457 1423
Base 29: 5 151
Base 30: 2 5 11 163 569 1789
Base 31: 7 17 31
Base 32:
Base 33: 3 197
Base 34: 13 1493
Base 35: 313 1297
Base 36: 2
</pre>
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<syntaxhighlight lang="fsharp">
// Repunit primes. Nigel Galloway: January 24th., 2022
let rUnitP(b:int)=let b=bigint b in primes32()|>Seq.takeWhile((>)1000)|>Seq.map(fun n->(n,((b**n)-1I)/(b-1I)))|>Seq.filter(fun(_,n)->Open.Numeric.Primes.MillerRabin.IsProbablePrime &n)|>Seq.map fst
[2..16]|>List.iter(fun n->printf $"Base %d{n}: "; rUnitP(n)|>Seq.iter(printf "%d "); printfn "")
</syntaxhighlight>
{{out}}
<pre>
Base 2: 2 3 5 7 13 17 19 31 61 89 107 127 521 607
Base 3: 3 7 13 71 103 541
Base 4: 2
Base 5: 3 7 11 13 47 127 149 181 619 929
Base 6: 2 3 7 29 71 127 271 509
Base 7: 5 13 131 149
Base 8: 3
Base 9:
Base 10: 2 19 23 317
Base 11: 17 19 73 139 907
Base 12: 2 3 5 19 97 109 317 353 701
Base 13: 5 7 137 283 883 991
Base 14: 3 7 19 31 41
Base 15: 3 43 73 487
Base 16: 2
</pre>
=={{header|Go}}==
{{trans|Wren}}
{{libheader|GMP(Go wrapper)}}
{{libheader|Go-rcu}}
Took 11 minutes 25 seconds which is much the same as Wren's GMP wrapper.
<syntaxhighlight lang="go">package main
import (
"fmt"
big "github.com/ncw/gmp"
"rcu"
"strings"
)
func main() {
limit := 2700
primes := rcu.Primes(limit)
s := new(big.Int)
for b := 2; b <= 36; b++ {
var rPrimes []int
for _, p := range primes {
s.SetString(strings.Repeat("1", p), b)
if s.ProbablyPrime(15) {
rPrimes = append(rPrimes, p)
}
}
fmt.Printf("Base %2d: %v\n", b, rPrimes)
}
}</syntaxhighlight>
{{out}}
<pre>
Base 2: [2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281]
Base 3: [3 7 13 71 103 541 1091 1367 1627]
Base 4: [2]
Base 5: [3 7 11 13 47 127 149 181 619 929]
Base 6: [2 3 7 29 71 127 271 509 1049]
Base 7: [5 13 131 149 1699]
Base 8: [3]
Base 9: []
Base 10: [2 19 23 317 1031]
Base 11: [17 19 73 139 907 1907 2029]
Base 12: [2 3 5 19 97 109 317 353 701]
Base 13: [5 7 137 283 883 991 1021 1193]
Base 14: [3 7 19 31 41 2687]
Base 15: [3 43 73 487 2579]
Base 16: [2]
Base 17: [3 5 7 11 47 71 419]
Base 18: [2]
Base 19: [19 31 47 59 61 107 337 1061]
Base 20: [3 11 17 1487]
Base 21: [3 11 17 43 271]
Base 22: [2 5 79 101 359 857]
Base 23: [5]
Base 24: [3 5 19 53 71 653 661]
Base 25: []
Base 26: [7 43 347]
Base 27: [3]
Base 28: [2 5 17 457 1423]
Base 29: [5 151]
Base 30: [2 5 11 163 569 1789]
Base 31: [7 17 31]
Base 32: []
Base 33: [3 197]
Base 34: [13 1493]
Base 35: [313 1297]
Base 36: [2]
</pre>
=={{header|J}}==
Slow (runs a few minutes):
<syntaxhighlight lang="j">repunitp=. 1 p: ^&x: %&<: [
(2 + i. 15) ([ ;"0 repunitp"0/ <@# ]) i.&.(p:inv) 1000</syntaxhighlight>
{{out}}
<pre>
┌──┬─────────────────────────────────────────┐
│2 │2 3 5 7 13 17 19 31 61 89 107 127 521 607│
├──┼─────────────────────────────────────────┤
│3 │3 7 13 71 103 541 │
├──┼─────────────────────────────────────────┤
│4 │2 │
├──┼─────────────────────────────────────────┤
│5 │3 7 11 13 47 127 149 181 619 929 │
├──┼─────────────────────────────────────────┤
│6 │2 3 7 29 71 127 271 509 │
├──┼─────────────────────────────────────────┤
│7 │5 13 131 149 │
├──┼─────────────────────────────────────────┤
│8 │3 │
├──┼─────────────────────────────────────────┤
│9 │ │
├──┼─────────────────────────────────────────┤
│10│2 19 23 317 │
├──┼─────────────────────────────────────────┤
│11│17 19 73 139 907 │
├──┼─────────────────────────────────────────┤
│12│2 3 5 19 97 109 317 353 701 │
├──┼─────────────────────────────────────────┤
│13│5 7 137 283 883 991 │
├──┼─────────────────────────────────────────┤
│14│3 7 19 31 41 │
├──┼─────────────────────────────────────────┤
│15│3 43 73 487 │
├──┼─────────────────────────────────────────┤
│16│2 │
└──┴─────────────────────────────────────────┘
</pre>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
public final class RepunitPrimes {
public static void main(String[] aArgs) {
final int limit = 2_700;
System.out.println("Repunit primes, up to " + limit + " digits, in:");
for ( int base = 2; base <= 16; base++ ) {
System.out.print(String.format("%s%2s%s", "Base ", base, ": "));
String repunit = "";
while ( repunit.length() < limit ) {
repunit += "1";
if ( BigInteger.valueOf(repunit.length()).isProbablePrime(CERTAINTY_LEVEL) ) {
BigInteger value = new BigInteger(repunit, base);
if ( value.isProbablePrime(CERTAINTY_LEVEL) ) {
System.out.print(repunit.length() + " ");
}
}
}
System.out.println();
}
}
private static final int CERTAINTY_LEVEL = 20;
}
</syntaxhighlight>
{{ out }}
<pre>
Repunit primes, up to 2700 digits, in:
Base 2: 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281
Base 3: 3 7 13 71 103 541 1091 1367 1627
Base 4: 2
Base 5: 3 7 11 13 47 127 149 181 619 929
Base 6: 2 3 7 29 71 127 271 509 1049
Base 7: 5 13 131 149 1699
Base 8: 3
Base 9:
Base 10: 2 19 23 317 1031
Base 11: 17 19 73 139 907 1907 2029
Base 12: 2 3 5 19 97 109 317 353 701
Base 13: 5 7 137 283 883 991 1021 1193
Base 14: 3 7 19 31 41 2687
Base 15: 3 43 73 487 2579
Base 16: 2
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">using Primes
repunitprimeinbase(n, base) = isprime(evalpoly(BigInt(base), [1 for _ in 1:n]))
for b in 2:40
println(rpad("Base $b:", 9), filter(n -> repunitprimeinbase(n, b), 1:2700))
end
</syntaxhighlight>{{out}}
<pre>
Base 2: [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281]
Base 3: [3, 7, 13, 71, 103, 541, 1091, 1367, 1627]
Base 4: [2]
Base 5: [3, 7, 11, 13, 47, 127, 149, 181, 619, 929]
Base 6: [2, 3, 7, 29, 71, 127, 271, 509, 1049]
Base 7: [5, 13, 131, 149, 1699]
Base 8: [3]
Base 9: Int64[]
Base 10: [2, 19, 23, 317, 1031]
Base 11: [17, 19, 73, 139, 907, 1907, 2029]
Base 12: [2, 3, 5, 19, 97, 109, 317, 353, 701]
Base 13: [5, 7, 137, 283, 883, 991, 1021, 1193]
Base 14: [3, 7, 19, 31, 41, 2687]
Base 15: [3, 43, 73, 487, 2579]
Base 16: [2]
Base 17: [3, 5, 7, 11, 47, 71, 419]
Base 18: [2]
Base 19: [19, 31, 47, 59, 61, 107, 337, 1061]
Base 20: [3, 11, 17, 1487]
Base 21: [3, 11, 17, 43, 271]
Base 22: [2, 5, 79, 101, 359, 857]
Base 23: [5]
Base 24: [3, 5, 19, 53, 71, 653, 661]
Base 25: Int64[]
Base 26: [7, 43, 347]
Base 27: [3]
Base 28: [2, 5, 17, 457, 1423]
Base 29: [5, 151]
Base 30: [2, 5, 11, 163, 569, 1789]
Base 31: [7, 17, 31]
Base 32: Int64[]
Base 33: [3, 197]
Base 34: [13, 1493]
Base 35: [313, 1297]
Base 36: [2]
Base 37: [13, 71, 181, 251, 463, 521]
Base 38: [3, 7, 401, 449]
Base 39: [349, 631]
Base 40: [2, 5, 7, 19, 23, 29, 541, 751, 1277]
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[RepUnitPrimeQ]
RepUnitPrimeQ[b_][n_] := PrimeQ[FromDigits[ConstantArray[1, n], b]]
ClearAll[RepUnitPrimeQ]
RepUnitPrimeQ[b_][n_] := PrimeQ[FromDigits[ConstantArray[1, n], b]]
Do[
Print["Base ", b, ": ", Select[Range[2700], RepUnitPrimeQ[b]]]
,
{b, 2, 16}
]
</syntaxhighlight>
Searching bases 2–16 for repunits of size 2700:
{{out}}
<pre>Base 2: {2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281}
Base 3: {3,7,13,71,103,541,1091,1367,1627}
Base 4: {2}
Base 5: {3,7,11,13,47,127,149,181,619,929}
Base 6: {2,3,7,29,71,127,271,509,1049}
Base 7: {5,13,131,149,1699}
Base 8: {3}
Base 9: {}
Base 10: {2,19,23,317,1031}
Base 11: {17,19,73,139,907,1907,2029}
Base 12: {2,3,5,19,97,109,317,353,701}
Base 13: {5,7,137,283,883,991,1021,1193}
Base 14: {3,7,19,31,41,2687}
Base 15: {3,43,73,487,2579}
Base 16: {2}</pre>
=={{header|Nim}}==
{{libheader|Nim-Integers}}
<syntaxhighlight lang="Nim">
import std/strformat
import integers
for base in 2..16:
stdout.write &"{base:>2}:"
var rep = ""
while true:
rep.add '1'
if rep.len > 2700: break
if not rep.len.isPrime: continue
let val = newInteger(rep, base)
if val.isPrime():
stdout.write ' ', rep.len
echo()
</syntaxhighlight>
{{out}}
<pre> 2: 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281
3: 3 7 13 71 103 541 1091 1367 1627
4: 2
5: 3 7 11 13 47 127 149 181 619 929
6: 2 3 7 29 71 127 271 509 1049
7: 5 13 131 149 1699
8: 3
9:
10: 2 19 23 317 1031
11: 17 19 73 139 907 1907 2029
12: 2 3 5 19 97 109 317 353 701
13: 5 7 137 283 883 991 1021 1193
14: 3 7 19 31 41 2687
15: 3 43 73 487 2579
16: 2
</pre>
=={{header|PARI/GP}}==
{{trans|Julia}}
<syntaxhighlight lang="PARI/GP">
default(parisizemax, "128M")
default(parisize, "64M");
repunitprimeinbase(n, base) = {
repunit = sum(i=0, n-1, base^i); /* Construct the repunit */
return(isprime(repunit)); /* Check if it's prime */
}
{
for(b=2, 40,
print("Base ", b, ": ");
for(n=1, 2700,
if(repunitprimeinbase(n, b), print1(n, " "))
);
print(""); /* Print a newline */
)
}
</syntaxhighlight>
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl">use strict;
use warnings;
use ntheory <is_prime fromdigits>;
my $limit = 1000;
print "Repunit prime digits (up to $limit) in:\n";
for my $base (2..16) {
printf "Base %2d: %s\n", $base, join ' ', grep { is_prime $_ and is_prime fromdigits(('1'x$_), $base) and " $_" } 1..$limit
}</syntaxhighlight>
{{out}}
<pre>Repunit prime digits (up to 1000) in:
Base 2: 2 3 5 7 13 17 19 31 61 89 107 127 521 607
Base 3: 3 7 13 71 103 541
Base 4: 2
Base 5: 3 7 11 13 47 127 149 181 619 929
Base 6: 2 3 7 29 71 127 271 509
Base 7: 5 13 131 149
Base 8: 3
Base 9:
Base 10: 2 19 23 317
Base 11: 17 19 73 139 907
Base 12: 2 3 5 19 97 109 317 353 701
Base 13: 5 7 137 283 883 991
Base 14: 3 7 19 31 41
Base 15: 3 43 73 487
Base 16: 2</pre>
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">repunit</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">z</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">=</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_add_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">constant</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">blimit</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?{</span><span style="color: #000000;">400</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- 8.8s</span>
<span style="color: #0000FF;">:{</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- 50.3s
-- :{1000,36}) -- 4 min 20s
-- :{2700,16}) -- 28 min 35s
-- :{2700,36}) -- >patience</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">blimit</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rprimes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">repunit</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">rprimes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rprimes</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Base %2d: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rprimes</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
Note the first half (base<=16) is from a {2700,16} run and the rest (base>16) from a {1000,36} run.
<pre>
Base 2: 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281
Base 3: 3 7 13 71 103 541 1091 1367 1627
Base 4: 2
Base 5: 3 7 11 13 47 127 149 181 619 929
Base 6: 2 3 7 29 71 127 271 509 1049
Base 7: 5 13 131 149 1699
Base 8: 3
Base 9:
Base 10: 2 19 23 317 1031
Base 11: 17 19 73 139 907 1907 2029
Base 12: 2 3 5 19 97 109 317 353 701
Base 13: 5 7 137 283 883 991 1021 1193
Base 14: 3 7 19 31 41 2687
Base 15: 3 43 73 487 2579
Base 16: 2
Base 17: 3 5 7 11 47 71 419
Base 18: 2
Base 19: 19 31 47 59 61 107 337
Base 20: 3 11 17
Base 21: 3 11 17 43 271
Base 22: 2 5 79 101 359 857
Base 23: 5
Base 24: 3 5 19 53 71 653 661
Base 25:
Base 26: 7 43 347
Base 27: 3
Base 28: 2 5 17 457
Base 29: 5 151
Base 30: 2 5 11 163 569
Base 31: 7 17 31
Base 32:
Base 33: 3 197
Base 34: 13
Base 35: 313
Base 36: 2
</pre>
=={{header|Python}}==
<syntaxhighlight lang="python">from sympy import isprime
for b in range(2, 17):
print(b, [n for n in range(2, 1001) if isprime(n) and isprime(int('1'*n, base=b))])</syntaxhighlight>
{{out}}
<pre>2 [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607]
3 [3, 7, 13, 71, 103, 541]
4 [2]
5 [3, 7, 11, 13, 47, 127, 149, 181, 619, 929]
6 [2, 3, 7, 29, 71, 127, 271, 509]
7 [5, 13, 131, 149]
8 [3]
9 []
10 [2, 19, 23, 317]
11 [17, 19, 73, 139, 907]
12 [2, 3, 5, 19, 97, 109, 317, 353, 701]
13 [5, 7, 137, 283, 883, 991]
14 [3, 7, 19, 31, 41]
15 [3, 43, 73, 487]
16 [2]</pre>
=={{header|Quackery}}==
<code>prime</code> is defined at [[Miller–Rabin primality test#Quackery]].
<syntaxhighlight lang="Quackery"> [ base put
1 temp put
[] 1 1000 times
[ temp share prime if
[ dup prime if
[ dip [ i^ 1+ join ] ] ]
base share * 1+
1 temp tally ]
drop
temp release
base release ] is repunitprimes ( n --> [ )
15 times
[ i^ 2 +
dup 10 < if sp
dup echo
say ": "
repunitprimes echo
cr ]</syntaxhighlight>
{{out}}
<pre> 2: [ 2 3 5 7 13 17 19 31 61 89 107 127 521 607 ]
3: [ 3 7 13 71 103 541 ]
4: [ 2 ]
5: [ 3 7 11 13 47 127 149 181 619 929 ]
6: [ 2 3 7 29 71 127 271 509 ]
7: [ 5 13 131 149 ]
8: [ 3 ]
9: [ ]
10: [ 2 19 23 317 ]
11: [ 17 19 73 139 907 ]
12: [ 2 3 5 19 97 109 317 353 701 ]
13: [ 5 7 137 283 883 991 ]
14: [ 3 7 19 31 41 ]
15: [ 3 43 73 487 ]
16: [ 2 ]</pre>
=={{header|Raku}}==
<syntaxhighlight lang="raku"
say "Repunit prime digits (up to $limit) in:";
Line 57 ⟶ 710:
.put for (2..16).hyper(:1batch).map: -> $base {
$base.fmt("Base %2d: ") ~ (1..$limit).grep(&is-prime).grep( (1 x *).parse-base($base).is-prime )
}</
{{out}}
<pre>Repunit prime digits (up to 2700) in:
Line 75 ⟶ 728:
Base 15: 3 43 73 487 2579
Base 16: 2</pre>
''And for my own amusement, also tested up to 2700.''
<pre>Base 17: 3 5 7 11 47 71 419
Base 18: 2
Base 19: 19 31 47 59 61 107 337 1061
Base 20: 3 11 17 1487
Base 21: 3 11 17 43 271
Base 22: 2 5 79 101 359 857
Base 23: 5
Base 24: 3 5 19 53 71 653 661
Base 25:
Base 26: 7 43 347
Base 27: 3
Base 28: 2 5 17 457 1423
Base 29: 5 151
Base 30: 2 5 11 163 569 1789
Base 31: 7 17 31
Base 32:
Base 33: 3 197
Base 34: 13 1493
Base 35: 313 1297
Base 36: 2</pre>
=={{header|RPL}}==
{{works with|HP|49}}
≪ 0 1 4 ROLL '''START''' OVER * 1 + '''NEXT''' NIP
≫ '<span style="color:blue">REPUB</span>' STO <span style="color:grey">@ ( n b → Rb(n) )</span>
≪ 16 2 '''FOR''' b
{ }
2 1000 '''FOR''' n
'''IF''' n b <span style="color:blue">REPUB</span> ISPRIME? '''THEN''' n + '''END'''
'''NEXT'''
-1 '''STEP'''
"Done."
≫ '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
16: {2}
15: {3 43 73 487}
14: {3 7 19 31 41}
13: {5 7 137 283 883 991}
12: {2 3 5 19 97 109 317 353 701}
11: {17 19 73 139 907}
10: {2 19 23 317}
9: { }
8: {3}
7: {5 13 131 149}
6: {2 3 7 29 71 127 271 509}
5: {3 7 11 13 47 127 149 181 619 929}
4: {2}
3: {3 7 13 71 103 541}
2: {2 3 5 7 13 17 19 31 61 89 107 127 521 607}
1: "Done."
</pre>
=={{header|Ruby}}==
Ruby's standard lib 'Prime' is boring slow for this. GMP to the rescue. GMP bindings is a gem, not in std lib.
<syntaxhighlight lang="ruby">require 'prime'
require 'gmp'
(2..16).each do |base|
res = Prime.each(1000).select {|n| GMP::Z(("1" * n).to_i(base)).probab_prime? > 0}
puts "Base #{base}: #{res.join(" ")}"
end
</syntaxhighlight>
{{out}}
<pre>Base 2: 2 3 5 7 13 17 19 31 61 89 107 127 521 607
Base 3: 3 7 13 71 103 541
Base 4: 2
Base 5: 3 7 11 13 47 127 149 181 619 929
Base 6: 2 3 7 29 71 127 271 509
Base 7: 5 13 131 149
Base 8: 3
Base 9:
Base 10: 2 19 23 317
Base 11: 17 19 73 139 907
Base 12: 2 3 5 19 97 109 317 353 701
Base 13: 5 7 137 283 883 991
Base 14: 3 7 19 31 41
Base 15: 3 43 73 487
Base 16: 2
</pre>
=={{header|Scheme}}==
{{works with|Chez Scheme}}
This uses
[http://www.rosettacode.org/wiki/Miller-Rabin_primality_test#Scheme Miller–Rabin primality test (Scheme)]
, renamed, restructured, with a minor fix.
<br />
Took about 59 minutes to run.
<br />
'''Primality Test'''
<syntaxhighlight lang="scheme">; Test whether any integer is a probable prime.
(define prime<probably>?
(lambda (n)
; Fast modular exponentiation.
(define modexpt
(lambda (b e m)
(cond
((zero? e) 1)
((even? e) (modexpt (mod (* b b) m) (div e 2) m))
((odd? e) (mod (* b (modexpt b (- e 1) m)) m)))))
; Return multiple values s, d such that d is odd and 2^s * d = n.
(define split
(lambda (n)
(let recur ((s 0) (d n))
(if (odd? d)
(values s d)
(recur (+ s 1) (div d 2))))))
; Test whether the number a proves that n is composite.
(define composite-witness?
(lambda (n a)
(let*-values (((s d) (split (- n 1)))
((x) (modexpt a d n)))
(and (not (= x 1))
(not (= x (- n 1)))
(let try ((r (- s 1)))
(set! x (modexpt x 2 n))
(or (zero? r)
(= x 1)
(and (not (= x (- n 1)))
(try (- r 1)))))))))
; Test whether n > 2 is a Miller-Rabin pseudoprime, k trials.
(define pseudoprime?
(lambda (n k)
(or (zero? k)
(let ((a (+ 2 (random (- n 2)))))
(and (not (composite-witness? n a))
(pseudoprime? n (- k 1)))))))
; Compute and return Probable Primality using the Miller-Rabin algorithm.
(and (> n 1)
(or (= n 2)
(and (odd? n)
(pseudoprime? n 50))))))</syntaxhighlight>
'''The Task'''
<syntaxhighlight lang="scheme">; Return list of the Repunit Primes in the given base up to the given limit.
(define repunit_primes
(lambda (base limit)
(let loop ((count 2)
(value (1+ base)))
(cond ((> count limit)
'())
((and (prime<probably>? count) (prime<probably>? value))
(cons count (loop (1+ count) (+ value (expt base count)))))
(else
(loop (1+ count) (+ value (expt base count))))))))
; Show all the Repunit Primes up to 2700 digits for bases 2 through 16.
(let ((max-base 16)
(max-digits 2700))
(printf "~%Repunit Primes up to ~d digits for bases 2 through ~d:~%" max-digits max-base)
(do ((base 2 (1+ base)))
((> base max-base))
(printf "Base ~2d: ~a~%" base (repunit_primes base max-digits))))</syntaxhighlight>
{{out}}
<pre>
Repunit Primes up to 2700 digits for bases 2 through 16:
Base 2: (2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281)
Base 3: (3 7 13 71 103 541 1091 1367 1627)
Base 4: (2)
Base 5: (3 7 11 13 47 127 149 181 619 929)
Base 6: (2 3 7 29 71 127 271 509 1049)
Base 7: (5 13 131 149 1699)
Base 8: (3)
Base 9: ()
Base 10: (2 19 23 317 1031)
Base 11: (17 19 73 139 907 1907 2029)
Base 12: (2 3 5 19 97 109 317 353 701)
Base 13: (5 7 137 283 883 991 1021 1193)
Base 14: (3 7 19 31 41 2687)
Base 15: (3 43 73 487 2579)
Base 16: (2)
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">var limit = 1000
say "Repunit prime digits (up to #{limit}) in:"
for n in (2..20) {
printf("Base %2d: %s\n", n,
{|k| is_prime((n**k - 1) / (n-1)) }.grep(1..limit))
}</syntaxhighlight>
{{out}}
<pre>
Base 2: [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607]
Base 3: [3, 7, 13, 71, 103, 541]
Base 4: [2]
Base 5: [3, 7, 11, 13, 47, 127, 149, 181, 619, 929]
Base 6: [2, 3, 7, 29, 71, 127, 271, 509]
Base 7: [5, 13, 131, 149]
Base 8: [3]
Base 9: []
Base 10: [2, 19, 23, 317]
Base 11: [17, 19, 73, 139, 907]
Base 12: [2, 3, 5, 19, 97, 109, 317, 353, 701]
Base 13: [5, 7, 137, 283, 883, 991]
Base 14: [3, 7, 19, 31, 41]
Base 15: [3, 43, 73, 487]
Base 16: [2]
Base 17: [3, 5, 7, 11, 47, 71, 419]
Base 18: [2]
Base 19: [19, 31, 47, 59, 61, 107, 337]
Base 20: [3, 11, 17]
</pre>
=={{header|Wren}}==
{{libheader|Wren-gmp}}
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
{{libheader|Wren-str}}
An embedded program so we can use GMP as I know from experience that Wren-CLI (using BigInt) will not be able to complete this task in a reasonable time.
Still takes a while - 11 minutes 20 seconds to get up to base 36 with a limit of 2700.
<syntaxhighlight lang="wren">/* Repunit_primes.wren */
import "./gmp" for Mpz
import "./math" for Int
import "./fmt" for Fmt
import "./str" for Str
var limit = 2700
var primes = Int.primeSieve(limit)
for (b in 2..36) {
var rPrimes = []
for (p in primes) {
var s = Mpz.fromStr(Str.repeat("1", p), b)
if (s.probPrime(15) > 0) rPrimes.add(p)
}
Fmt.print("Base $2d: $n", b, rPrimes)
}</syntaxhighlight>
{{out}}
<pre>
Base 2: [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281]
Base 3: [3, 7, 13, 71, 103, 541, 1091, 1367, 1627]
Base 4: [2]
Base 5: [3, 7, 11, 13, 47, 127, 149, 181, 619, 929]
Base 6: [2, 3, 7, 29, 71, 127, 271, 509, 1049]
Base 7: [5, 13, 131, 149, 1699]
Base 8: [3]
Base 9: []
Base 10: [2, 19, 23, 317, 1031]
Base 11: [17, 19, 73, 139, 907, 1907, 2029]
Base 12: [2, 3, 5, 19, 97, 109, 317, 353, 701]
Base 13: [5, 7, 137, 283, 883, 991, 1021, 1193]
Base 14: [3, 7, 19, 31, 41, 2687]
Base 15: [3, 43, 73, 487, 2579]
Base 16: [2]
Base 17: [3, 5, 7, 11, 47, 71, 419]
Base 18: [2]
Base 19: [19, 31, 47, 59, 61, 107, 337, 1061]
Base 20: [3, 11, 17, 1487]
Base 21: [3, 11, 17, 43, 271]
Base 22: [2, 5, 79, 101, 359, 857]
Base 23: [5]
Base 24: [3, 5, 19, 53, 71, 653, 661]
Base 25: []
Base 26: [7, 43, 347]
Base 27: [3]
Base 28: [2, 5, 17, 457, 1423]
Base 29: [5, 151]
Base 30: [2, 5, 11, 163, 569, 1789]
Base 31: [7, 17, 31]
Base 32: []
Base 33: [3, 197]
Base 34: [13, 1493]
Base 35: [313, 1297]
Base 36: [2]
</pre>
| |||