Repunit primes: Difference between revisions
(Added a Scheme implementation.) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 52: | Line 52: | ||
{{libheader|GMP}} |
{{libheader|GMP}} |
||
{{libheader|Primesieve}} |
{{libheader|Primesieve}} |
||
< |
<syntaxhighlight lang="cpp">#include <future> |
||
#include <iomanip> |
#include <iomanip> |
||
#include <iostream> |
#include <iostream> |
||
Line 86: | Line 86: | ||
std::cout << '\n'; |
std::cout << '\n'; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 131: | Line 131: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (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 |
// 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 |
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 "") |
[2..16]|>List.iter(fun n->printf $"Base %d{n}: "; rUnitP(n)|>Seq.iter(printf "%d "); printfn "") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 160: | Line 160: | ||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
Took 11 minutes 25 seconds which is much the same as Wren's GMP wrapper. |
Took 11 minutes 25 seconds which is much the same as Wren's GMP wrapper. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 183: | Line 183: | ||
fmt.Printf("Base %2d: %v\n", b, rPrimes) |
fmt.Printf("Base %2d: %v\n", b, rPrimes) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 225: | Line 225: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
repunitprimeinbase(n, base) = isprime(evalpoly(BigInt(base), [1 for _ in 1:n])) |
repunitprimeinbase(n, base) = isprime(evalpoly(BigInt(base), [1 for _ in 1:n])) |
||
Line 232: | Line 232: | ||
println(rpad("Base $b:", 9), filter(n -> repunitprimeinbase(n, b), 1:2700)) |
println(rpad("Base $b:", 9), filter(n -> repunitprimeinbase(n, b), 1:2700)) |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Base 2: [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281] |
Base 2: [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281] |
||
Line 276: | Line 276: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[RepUnitPrimeQ] |
||
RepUnitPrimeQ[b_][n_] := PrimeQ[FromDigits[ConstantArray[1, n], b]] |
RepUnitPrimeQ[b_][n_] := PrimeQ[FromDigits[ConstantArray[1, n], b]] |
||
ClearAll[RepUnitPrimeQ] |
ClearAll[RepUnitPrimeQ] |
||
Line 285: | Line 285: | ||
{b, 2, 16} |
{b, 2, 16} |
||
] |
] |
||
</syntaxhighlight> |
|||
</lang> |
|||
Searching bases 2–16 for repunits of size 2700: |
Searching bases 2–16 for repunits of size 2700: |
||
{{out}} |
{{out}} |
||
Line 306: | Line 306: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use ntheory <is_prime fromdigits>; |
use ntheory <is_prime fromdigits>; |
||
Line 316: | Line 316: | ||
for my $base (2..16) { |
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 |
printf "Base %2d: %s\n", $base, join ' ', grep { is_prime $_ and is_prime fromdigits(('1'x$_), $base) and " $_" } 1..$limit |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Repunit prime digits (up to 1000) in: |
<pre>Repunit prime digits (up to 1000) in: |
||
Line 336: | Line 336: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
||
Line 367: | Line 367: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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> |
<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}} |
{{out}} |
||
Note the first half (base<=16) is from a {2700,16} run and the rest (base>16) from a {1000,36} run. |
Note the first half (base<=16) is from a {2700,16} run and the rest (base>16) from a {1000,36} run. |
||
Line 409: | Line 409: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">from sympy import isprime |
||
for b in range(2, 17): |
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))])</ |
print(b, [n for n in range(2, 1001) if isprime(n) and isprime(int('1'*n, base=b))])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>2 [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607] |
<pre>2 [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607] |
||
Line 431: | Line 431: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>my $limit = 2700; |
||
say "Repunit prime digits (up to $limit) in:"; |
say "Repunit prime digits (up to $limit) in:"; |
||
Line 437: | Line 437: | ||
.put for (2..16).hyper(:1batch).map: -> $base { |
.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 ) |
$base.fmt("Base %2d: ") ~ (1..$limit).grep(&is-prime).grep( (1 x *).parse-base($base).is-prime ) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Repunit prime digits (up to 2700) in: |
<pre>Repunit prime digits (up to 2700) in: |
||
Line 485: | Line 485: | ||
<br /> |
<br /> |
||
'''Primality Test''' |
'''Primality Test''' |
||
< |
<syntaxhighlight lang="scheme">; Test whether any integer is a probable prime. |
||
(define prime<probably>? |
(define prime<probably>? |
||
(lambda (n) |
(lambda (n) |
||
Line 526: | Line 526: | ||
(or (= n 2) |
(or (= n 2) |
||
(and (odd? n) |
(and (odd? n) |
||
(pseudoprime? n 50))))))</ |
(pseudoprime? n 50))))))</syntaxhighlight> |
||
'''The Task''' |
'''The Task''' |
||
< |
<syntaxhighlight lang="scheme">; Return list of the Repunit Primes in the given base up to the given limit. |
||
(define repunit_primes |
(define repunit_primes |
||
(lambda (base limit) |
(lambda (base limit) |
||
Line 546: | Line 546: | ||
(do ((base 2 (1+ base))) |
(do ((base 2 (1+ base))) |
||
((> base max-base)) |
((> base max-base)) |
||
(printf "Base ~2d: ~a~%" base (repunit_primes base max-digits))))</ |
(printf "Base ~2d: ~a~%" base (repunit_primes base max-digits))))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 568: | Line 568: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">var limit = 1000 |
||
say "Repunit prime digits (up to #{limit}) in:" |
say "Repunit prime digits (up to #{limit}) in:" |
||
Line 575: | Line 575: | ||
printf("Base %2d: %s\n", n, |
printf("Base %2d: %s\n", n, |
||
{|k| is_prime((n**k - 1) / (n-1)) }.grep(1..limit)) |
{|k| is_prime((n**k - 1) / (n-1)) }.grep(1..limit)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 607: | Line 607: | ||
Still takes a while - 11 minutes 20 seconds to get up to base 36 with a limit of 2700. |
Still takes a while - 11 minutes 20 seconds to get up to base 36 with a limit of 2700. |
||
< |
<syntaxhighlight lang="ecmascript">/* repunit_primes.wren */ |
||
import "./gmp" for Mpz |
import "./gmp" for Mpz |
||
Line 624: | Line 624: | ||
} |
} |
||
Fmt.print("Base $2d: $n", b, rPrimes) |
Fmt.print("Base $2d: $n", b, rPrimes) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
Revision as of 12:35, 28 August 2022
You are encouraged to solve this task according to the task description, using any language you may know.
Repunit is a 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 Mersenne primes.)
In base three: 111, 1111111, 1111111111111, etc.
Repunit primes, by definition, are also circular primes.
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.
Rather than expanding the repunit out as a giant list of 1s or converting to base 10, it is common to just list the number of 1s 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, though they aren't specifically listed as "repunit prime digits" sequences.
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.
- Task
- For bases 2 through 16, Find and show, here on this page, the repunit primes as digit counts, up to a limit of 1000.
- Stretch
- Increase the limit to 2700 (or as high as you have patience for.)
- See also
- Wikipedia: Repunit primes
- 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 - Numbers k such that (3^k - 1)/2 is prime (base 3)
- OEIS:A004061 - Numbers n such that (5^n - 1)/4 is prime (base 5)
- OEIS:A004062 - Numbers n such that (6^n - 1)/5 is prime (base 6)
- OEIS:A004063 - Numbers k such that (7^k - 1)/6 is prime (base 7)
- OEIS:A004023 - Indices of prime repunits: numbers n such that 11...111 (with n 1's) = (10^n - 1)/9 is prime (base 10)
- OEIS:A005808 - Numbers k such that (11^k - 1)/10 is prime (base 11)
- OEIS:A004064 - Numbers n such that (12^n - 1)/11 is prime (base 12)
- OEIS:A016054 - Numbers n such that (13^n - 1)/12 is prime (base 13)
- OEIS:A006032 - Numbers k such that (14^k - 1)/13 is prime (base 14)
- OEIS:A006033 - Numbers n such that (15^n - 1)/14 is prime (base 15)
- Related task: Circular primes
C++
#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';
}
}
- Output:
This takes about 4 minutes 12 seconds (3.2GHz Quad-Core Intel Core i5).
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
F#
This task uses Extensible Prime Generator (F#)
// 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 "")
- Output:
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
Go
Took 11 minutes 25 seconds which is much the same as Wren's GMP wrapper.
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)
}
}
- Output:
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]
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
- Output:
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]
Mathematica/Wolfram Language
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}
]
Searching bases 2–16 for repunits of size 2700:
- Output:
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}
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
}
- Output:
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
Phix
with javascript_semantics include mpfr.e procedure repunit(mpz z, integer n, base=10) mpz_set_si(z,0) for i=1 to n do mpz_mul_si(z,z,base) mpz_add_si(z,z,1) end for end procedure atom t0 = time() constant {limit,blimit} = iff(platform()=JS?{400,16} -- 8.8s :{1000,16}) -- 50.3s -- :{1000,36}) -- 4 min 20s -- :{2700,16}) -- 28 min 35s -- :{2700,36}) -- >patience sequence primes = get_primes_le(limit) mpz z = mpz_init() for base=2 to blimit do sequence rprimes = {} for i=1 to length(primes) do integer p = primes[i] repunit(z,p,base) if mpz_prime(z) then rprimes = append(rprimes,sprint(p)) end if end for printf(1,"Base %2d: %s\n", {base, join(rprimes)}) end for ?elapsed(time()-t0)
- Output:
Note the first half (base<=16) is from a {2700,16} run and the rest (base>16) from a {1000,36} run.
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
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))])
- Output:
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]
Raku
my $limit = 2700;
say "Repunit prime digits (up to $limit) in:";
.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 )
}
- Output:
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
And for my own amusement, also tested up to 2700.
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
Scheme
This uses
Miller–Rabin primality test (Scheme)
, renamed, restructured, with a minor fix.
Took about 59 minutes to run.
Primality Test
; 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))))))
The Task
; 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))))
- Output:
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)
Sidef
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))
}
- Output:
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]
Wren
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.
/* 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)
}
- Output:
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]