Repunit primes

Repunit primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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++

Library: GMP

Library: Primesieve

<lang cpp>#include <future>

1. include <iomanip>
2. include <iostream>
3. include <vector>

1. include <gmpxx.h>
2. include <primesieve.hpp>

std::vector<uint64_t> repunit_primes(uint32_t base, uint64_t limit,

                                    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(
           [base, &primes] { return repunit_primes(base, limit, 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';
   }

}</lang>

Output:

This takes about 4 minutes 24 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#) <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 "") </lang>

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

Julia

<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

</lang>

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]

Perl

Library: ntheory

<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

}</lang>

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

Raku

<lang perl6>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 )

}</lang>

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

Wren

Library: Wren-gmp

Library: Wren-math

Library: Wren-fmt

Library: 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. <lang ecmascript>/* 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)

}</lang>

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]