Multi-base primes
You are encouraged to solve this task according to the task description, using any language you may know.
Prime numbers are prime no matter what base they are represented in.
A prime number in a base other than 10 may not look prime at first glance.
For instance: 19 base 10 is 25 in base 7.
Several different prime numbers may be expressed as the "same" string when converted to a different base.
- 107 base 10 converted to base 6 == 255
- 173 base 10 converted to base 8 == 255
- 353 base 10 converted to base 12 == 255
- 467 base 10 converted to base 14 == 255
- 743 base 10 converted to base 18 == 255
- 1277 base 10 converted to base 24 == 255
- 1487 base 10 converted to base 26 == 255
- 2213 base 10 converted to base 32 == 255
- Task
Restricted to bases 2 through 36; find the strings that have the most different bases that evaluate to that string when converting prime numbers to a base.
Find the conversion string, the amount of bases that evaluate a prime to that string and the enumeration of bases that evaluate a prime to that string.
Display here, on this page, the string, the count and the list for all of the: 1 character, 2 character, 3 character, and 4 character strings that have the maximum base count that evaluate to that string.
Should be no surprise, the string '2' has the largest base count for single character strings.
- Stretch goal
Do the same for the maximum 5 character string.
C++
Originally translated from Wren with ideas borrowed from other solutions. The maximum base and number of characters can be specified as command line arguments.
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <primesieve.hpp>
class prime_sieve {
public:
explicit prime_sieve(uint64_t limit);
bool is_prime(uint64_t n) const {
return n == 2 || ((n & 1) == 1 && sieve[n >> 1]);
}
private:
std::vector<bool> sieve;
};
prime_sieve::prime_sieve(uint64_t limit) : sieve((limit + 1) / 2, false) {
primesieve::iterator iter;
uint64_t prime = iter.next_prime(); // consume 2
while ((prime = iter.next_prime()) <= limit) {
sieve[prime >> 1] = true;
}
}
template <typename T> void print(std::ostream& out, const std::vector<T>& v) {
if (!v.empty()) {
out << '[';
auto i = v.begin();
out << *i++;
for (; i != v.end(); ++i)
out << ", " << *i;
out << ']';
}
}
std::string to_string(const std::vector<unsigned int>& v) {
static constexpr char digits[] =
"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
std::string str;
for (auto i : v)
str += digits[i];
return str;
}
bool increment(std::vector<unsigned int>& digits, unsigned int max_base) {
for (auto i = digits.rbegin(); i != digits.rend(); ++i) {
if (*i + 1 != max_base) {
++*i;
return true;
}
*i = 0;
}
return false;
}
void multi_base_primes(unsigned int max_base, unsigned int max_length) {
prime_sieve sieve(static_cast<uint64_t>(std::pow(max_base, max_length)));
for (unsigned int length = 1; length <= max_length; ++length) {
std::cout << length
<< "-character strings which are prime in most bases: ";
unsigned int most_bases = 0;
std::vector<
std::pair<std::vector<unsigned int>, std::vector<unsigned int>>>
max_strings;
std::vector<unsigned int> digits(length, 0);
digits[0] = 1;
std::vector<unsigned int> bases;
do {
auto max = std::max_element(digits.begin(), digits.end());
unsigned int min_base = 2;
if (max != digits.end())
min_base = std::max(min_base, *max + 1);
if (most_bases > max_base - min_base + 1)
continue;
bases.clear();
for (unsigned int b = min_base; b <= max_base; ++b) {
if (max_base - b + 1 + bases.size() < most_bases)
break;
uint64_t n = 0;
for (auto d : digits)
n = n * b + d;
if (sieve.is_prime(n))
bases.push_back(b);
}
if (bases.size() > most_bases) {
most_bases = bases.size();
max_strings.clear();
}
if (bases.size() == most_bases)
max_strings.emplace_back(digits, bases);
} while (increment(digits, max_base));
std::cout << most_bases << '\n';
for (const auto& m : max_strings) {
std::cout << to_string(m.first) << " -> ";
print(std::cout, m.second);
std::cout << '\n';
}
std::cout << '\n';
}
}
int main(int argc, char** argv) {
unsigned int max_base = 36;
unsigned int max_length = 4;
for (int arg = 1; arg + 1 < argc; ++arg) {
if (strcmp(argv[arg], "-max_base") == 0)
max_base = strtoul(argv[++arg], nullptr, 10);
else if (strcmp(argv[arg], "-max_length") == 0)
max_length = strtoul(argv[++arg], nullptr, 10);
}
if (max_base > 62) {
std::cerr << "Max base cannot be greater than 62.\n";
return EXIT_FAILURE;
}
if (max_base < 2) {
std::cerr << "Max base cannot be less than 2.\n";
return EXIT_FAILURE;
}
multi_base_primes(max_base, max_length);
return EXIT_SUCCESS;
}
- Output:
Maximum base 36 and maximum length 6. This takes 0.41 seconds to process up to 5 character strings and 15 seconds to process up to 6 characters (3.2GHz Intel Core i5-4570).
1-character strings which are prime in most bases: 34 2 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] 2-character strings which are prime in most bases: 18 21 -> [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36] 3-character strings which are prime in most bases: 18 131 -> [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34] 551 -> [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36] 737 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36] 4-character strings which are prime in most bases: 19 1727 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36] 5347 -> [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36] 5-character strings which are prime in most bases: 18 30271 -> [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36] 6-character strings which are prime in most bases: 18 441431 -> [5, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 23, 26, 28, 30, 31, 32, 33]
Maximum base 62 and maximum length 5. This takes 0.15 seconds to process up to 4 character strings and 6.4 seconds to process up to 5 characters (3.2GHz Intel Core i5-4570).
1-character strings which are prime in most bases: 60 2 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62] 2-character strings which are prime in most bases: 31 65 -> [7, 8, 9, 11, 13, 14, 16, 17, 18, 21, 22, 24, 27, 28, 29, 31, 32, 37, 38, 39, 41, 42, 43, 44, 46, 48, 51, 52, 57, 58, 59] 3-character strings which are prime in most bases: 33 1l1 -> [22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 51, 52, 53, 54, 57, 58, 59, 60, 61, 62] b9b -> [13, 14, 15, 16, 17, 19, 20, 21, 23, 24, 26, 27, 28, 30, 31, 34, 36, 39, 40, 42, 45, 47, 49, 50, 52, 53, 54, 57, 58, 59, 60, 61, 62] 4-character strings which are prime in most bases: 32 1727 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36, 37, 38, 39, 41, 45, 46, 48, 50, 51, 57, 58, 60, 61] 417b -> [12, 13, 15, 16, 17, 18, 19, 21, 23, 25, 28, 30, 32, 34, 35, 37, 38, 39, 41, 45, 48, 49, 50, 51, 52, 54, 56, 57, 58, 59, 61, 62] 5-character strings which are prime in most bases: 30 50161 -> [7, 8, 9, 13, 17, 18, 19, 20, 25, 28, 29, 30, 31, 33, 35, 36, 38, 39, 41, 42, 43, 44, 47, 48, 52, 55, 56, 59, 60, 62]
F#
This task uses Extensible Prime Generator (F#)
// Multi-base primes. Nigel Galloway: July 4th., 2021
let digits="0123456789abcdefghijklmnopqrstuvwxyz"
let fG n g=let rec fN g=function i when i<n->i::g |i->fN((i%n)::g)(i/n) in primes32()|>Seq.skipWhile((>)(pown n (g-1)))|>Seq.takeWhile((>)(pown n g))|>Seq.map(fun g->(n,fN [] g))
let fN g={2..36}|>Seq.collect(fun n->fG n g)|>Seq.groupBy snd|>Seq.groupBy(snd>>(Seq.length))|>Seq.maxBy fst
{1..4}|>Seq.iter(fun g->let n,i=fN g in printfn "The following strings of length %d represent primes in the maximum number of bases(%d):" g n
i|>Seq.iter(fun(n,g)->printf " %s->" (n|>List.map(fun n->digits.[n])|>Array.ofList|>System.String)
g|>Seq.iter(fun(g,_)->printf "%d " g); printfn ""); printfn "")
- Output:
The following strings of length 1 represent primes in the maximum number of bases(34): 2->3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 The following strings of length 2 represent primes in the maximum number of bases(18): 21->3 5 6 8 9 11 14 15 18 20 21 23 26 29 30 33 35 36 The following strings of length 3 represent primes in the maximum number of bases(18): 131->4 5 7 8 9 10 12 14 15 18 19 20 23 25 27 29 30 34 551->6 7 11 13 14 15 16 17 19 21 22 24 25 26 30 32 35 36 737->8 9 11 12 13 15 16 17 19 22 23 24 25 26 29 30 31 36 The following strings of length 4 represent primes in the maximum number of bases(19): 1727->8 9 11 12 13 15 16 17 19 20 22 23 24 26 27 29 31 33 36 5347->8 9 10 11 12 13 16 18 19 22 24 25 26 30 31 32 33 34 36
Factor
USING: assocs assocs.extras formatting io kernel math
math.functions math.parser math.primes math.ranges present
sequences ;
: prime?* ( n -- ? ) [ prime? ] [ f ] if* ; inline
: (bases) ( n -- range quot )
present 2 36 [a,b] [ base> prime?* ] with ; inline
: <digits> ( n -- range ) [ 1 - ] keep [ 10^ ] bi@ [a,b) ;
: multibase ( n -- assoc )
<digits> [ (bases) count ] zip-with assoc-invert
expand-keys-push-at >alist [ first ] supremum-by ;
: multibase. ( n -- )
dup multibase first2
[ "%d-digit numbers that are prime in the most bases: %d\n" printf ] dip
[ dup (bases) filter "%d => %[%d, %]\n" printf ] each ;
4 [1,b] [ multibase. nl ] each
- Output:
1-digit numbers that are prime in the most bases: 34
2 => { 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36 }
2-digit numbers that are prime in the most bases: 18
21 => { 3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36 }
3-digit numbers that are prime in the most bases: 18
131 => { 4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34 }
551 => { 6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36 }
737 => { 8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36 }
4-digit numbers that are prime in the most bases: 19
1727 => { 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36 }
5347 => { 8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36 }
FreeBASIC
Const maxBase = 36 ' o 62
Function isPrime(Byval ValorEval As Integer) As Boolean
If ValorEval < 2 Then Return False
If ValorEval Mod 2 = 0 Then Return ValorEval = 2
If ValorEval Mod 3 = 0 Then Return ValorEval = 3
Dim d As Integer = 5
While d * d <= ValorEval
If ValorEval Mod d = 0 Then Return False Else d += 2
Wend
Return True
End Function
Function maxval(arr() As Integer) As Integer
Dim As Integer max_value = arr(0)
For i As Integer = 1 To Ubound(arr)
If arr(i) > max_value Then max_value = arr(i)
Next
Return max_value
End Function
Function join(arr() As Integer, delimiter As String) As String
Dim As String result = ""
For i As Integer = 0 To Ubound(arr)
result &= Str(arr(i))
If i < Ubound(arr) Then result &= delimiter
Next
Return result
End Function
Function evalPoly(x As Integer, p() As Integer) As Integer
Dim result As Integer = 0
For y As Integer = 0 To Ubound(p)
result = result * x + p(y)
Next
Return result
End Function
Function stringify(digits() As Integer) As String
Dim res As String
For i As Integer = 0 To Ubound(digits)
Dim di As Integer = digits(i)
res &= Chr(Iif(di <= 9, di + Asc("0"), Iif(di < 36, di + Asc("A") - 10, di + Asc("a") - 36)))
Next
Return res
End Function
Sub maxPrimeVases(ndig As Integer, maxVase As Integer)
Dim As Double t0 = Timer
Dim As String maxPrimeBases()
Dim As Integer digits(ndig - 1)
Dim As Integer maxlen = 0
Dim As Integer limit = 10 ^ ndig
Dim As Integer maxDigit = maxBase
If ndig > 1 Then digits(0) = 1
Do
For i As Integer = Ubound(digits) To 0 Step -1
Dim As Integer di = digits(i) + 1
If di < maxDigit Then
digits(i) = di
Exit For
Else
digits(i) = 0
End If
Next
Dim As Integer minBase = maxval(digits()) + 1
Dim As Integer maxPoss = maxBase - minBase + 1
If minBase = 1 Then Exit Do
Dim As Integer bases()
For base_ As Integer = minBase To maxBase
If isPrime(evalPoly(base_, digits())) Then
Redim Preserve bases(Ubound(bases) + 1)
bases(Ubound(bases)) = base_
Else
maxPoss -= 1
If maxPoss < maxlen Then Exit For
End If
Next
Dim As Integer l = Ubound(bases) + 1
If l > maxlen Then
maxlen = l
maxDigit = maxBase - maxlen
Redim maxPrimeBases(0)
End If
If l = maxlen Then
Redim Preserve maxPrimeBases(Ubound(maxPrimeBases) + 1)
maxPrimeBases(Ubound(maxPrimeBases)) = Chr(10) & stringify(digits()) & " => " & join(bases(), ", ")
End If
Loop
Print Using "# character strings which are prime in most bases: ## (#.##s):"; ndig; maxlen; Timer - t0;
For i As Integer = 0 To Ubound(maxPrimeBases)
Print maxPrimeBases(i);
Next
Print Chr(10)
End Sub
For n As Integer = 1 To Iif(maxBase > 36, 4, 6)
maxPrimeVases(n, maxBase)
Next n
Sleep
- Output:
1 character strings which are prime in most bases: 34 (0.00s): 2 => 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36 2 character strings which are prime in most bases: 18 (0.00s): 21 => 3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36 3 character strings which are prime in most bases: 18 (0.01s): 131 => 4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34 551 => 6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36 737 => 8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36 4 character strings which are prime in most bases: 19 (0.08s): 1727 => 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36 5347 => 8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36 5 character strings which are prime in most bases: 18 (4.31s): 30271 => 8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36 6 character strings which are prime in most bases: 18 (238.32s): 441431 => 5, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 23, 26, 28, 30, 31, 32, 33
If we set maxBase to 62:
1 character strings which are prime in most bases: 60 (0.00s): 2 => 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62 2 character strings which are prime in most bases: 31 (0.00s): 65 => 7, 8, 9, 11, 13, 14, 16, 17, 18, 21, 22, 24, 27, 28, 29, 31, 32, 37, 38, 39, 41, 42, 43, 44, 46, 48, 51, 52, 57, 58, 59 3 character strings which are prime in most bases: 33 (0.03s): 1L1 => 22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 51, 52, 53, 54, 57, 58, 59, 60, 61, 62 B9B => 13, 14, 15, 16, 17, 19, 20, 21, 23, 24, 26, 27, 28, 30, 31, 34, 36, 39, 40, 42, 45, 47, 49, 50, 52, 53, 54, 57, 58, 59, 60, 61, 62 4 character strings which are prime in most bases: 32 (2.04s): 1727 => 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36, 37, 38, 39, 41, 45, 46, 48, 50, 51, 57, 58, 60, 61 417B => 12, 13, 15, 16, 17, 18, 19, 21, 23, 25, 28, 30, 32, 34, 35, 37, 38, 39, 41, 45, 48, 49, 50, 51, 52, 54, 56, 57, 58, 59, 61, 62
Go
This takes about 1.2 seconds and 31.3 seconds to process up to 5 and 6 character strings, respectively.
package main
import (
"fmt"
"math"
"rcu"
)
var maxDepth = 6
var maxBase = 36
var c = rcu.PrimeSieve(int(math.Pow(float64(maxBase), float64(maxDepth))), true)
var digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
var maxStrings [][][]int
var mostBases = -1
func maxSlice(a []int) int {
max := 0
for _, e := range a {
if e > max {
max = e
}
}
return max
}
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
func process(indices []int) {
minBase := maxInt(2, maxSlice(indices)+1)
if maxBase - minBase + 1 < mostBases {
return // can't affect results so return
}
var bases []int
for b := minBase; b <= maxBase; b++ {
n := 0
for _, i := range indices {
n = n*b + i
}
if !c[n] {
bases = append(bases, b)
}
}
count := len(bases)
if count > mostBases {
mostBases = count
indices2 := make([]int, len(indices))
copy(indices2, indices)
maxStrings = [][][]int{[][]int{indices2, bases}}
} else if count == mostBases {
indices2 := make([]int, len(indices))
copy(indices2, indices)
maxStrings = append(maxStrings, [][]int{indices2, bases})
}
}
func printResults() {
fmt.Printf("%d\n", len(maxStrings[0][1]))
for _, m := range maxStrings {
s := ""
for _, i := range m[0] {
s = s + string(digits[i])
}
fmt.Printf("%s -> %v\n", s, m[1])
}
}
func nestedFor(indices []int, length, level int) {
if level == len(indices) {
process(indices)
} else {
indices[level] = 0
if level == 0 {
indices[level] = 1
}
for indices[level] < length {
nestedFor(indices, length, level+1)
indices[level]++
}
}
}
func main() {
for depth := 1; depth <= maxDepth; depth++ {
fmt.Print(depth, " character strings which are prime in most bases: ")
maxStrings = maxStrings[:0]
mostBases = -1
indices := make([]int, depth)
nestedFor(indices, maxBase, 0)
printResults()
fmt.Println()
}
}
- Output:
1 character strings which are prime in most bases: 34 2 -> [3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36] 2 character strings which are prime in most bases: 18 21 -> [3 5 6 8 9 11 14 15 18 20 21 23 26 29 30 33 35 36] 3 character strings which are prime in most bases: 18 131 -> [4 5 7 8 9 10 12 14 15 18 19 20 23 25 27 29 30 34] 551 -> [6 7 11 13 14 15 16 17 19 21 22 24 25 26 30 32 35 36] 737 -> [8 9 11 12 13 15 16 17 19 22 23 24 25 26 29 30 31 36] 4 character strings which are prime in most bases: 19 1727 -> [8 9 11 12 13 15 16 17 19 20 22 23 24 26 27 29 31 33 36] 5347 -> [8 9 10 11 12 13 16 18 19 22 24 25 26 30 31 32 33 34 36] 5 character strings which are prime in most bases: 18 30271 -> [8 10 12 13 16 17 18 20 21 23 24 25 31 32 33 34 35 36] 6 character strings which are prime in most bases: 18 441431 -> [5 8 9 11 12 14 16 17 19 21 22 23 26 28 30 31 32 33]
If we change maxBase to 62 and maxDepth to 5 in the above code, then the following results are reached in 0.5 and 19.2 seconds for 4 and 5 digit character strings, respectively:
1 character strings which are prime in most bases: 60 2 -> [3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62] 2 character strings which are prime in most bases: 31 65 -> [7 8 9 11 13 14 16 17 18 21 22 24 27 28 29 31 32 37 38 39 41 42 43 44 46 48 51 52 57 58 59] 3 character strings which are prime in most bases: 33 1l1 -> [22 23 25 26 27 28 29 30 31 32 33 34 36 38 39 40 41 42 43 44 45 46 48 51 52 53 54 57 58 59 60 61 62] b9b -> [13 14 15 16 17 19 20 21 23 24 26 27 28 30 31 34 36 39 40 42 45 47 49 50 52 53 54 57 58 59 60 61 62] 4 character strings which are prime in most bases: 32 1727 -> [8 9 11 12 13 15 16 17 19 20 22 23 24 26 27 29 31 33 36 37 38 39 41 45 46 48 50 51 57 58 60 61] 417b -> [12 13 15 16 17 18 19 21 23 25 28 30 32 34 35 37 38 39 41 45 48 49 50 51 52 54 56 57 58 59 61 62] 5 character strings which are prime in most bases: 30 50161 -> [7 8 9 13 17 18 19 20 25 28 29 30 31 33 35 36 38 39 41 42 43 44 47 48 52 55 56 59 60 62]
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public final class MultibasePrimes {
public static void main(String[] aArgs) {
final int maxBase = 36;
final int maxLength = 5;
fillPrimes(maxBase, maxLength);
multibasePrimes(maxBase, maxLength);
}
private static void multibasePrimes(int aMaxBase, int aMaxLength) {
for ( int length = 1; length <= aMaxLength; length++ ) {
int maxBasesCount = 0;
List<Tuple> maxStrings = new ArrayList<Tuple>();
List<Integer> digits = new ArrayList<Integer>(Collections.nCopies(length, 0));
digits.set(0, 1);
List<Integer> bases = new ArrayList<Integer>();
do {
final int maxDigit = digits.stream().max(Integer::compare).get();
final int minBase = Math.max(2, maxDigit + 1);
if ( maxBasesCount > aMaxBase - minBase + 1 ) {
continue;
}
bases.clear();
for ( int base = minBase; base <= aMaxBase; base++ ) {
if ( aMaxBase - base + 1 + bases.size() < maxBasesCount ) {
break;
}
int number = 0;
for ( int digit : digits ) {
number = number * base + digit;
}
if ( primes[number] ) {
bases.add(base);
}
}
if ( bases.size() > maxBasesCount ) {
maxBasesCount = bases.size();
maxStrings.clear();
}
if ( bases.size() == maxBasesCount ) {
maxStrings.add( new Tuple( new ArrayList<Integer>(digits), new ArrayList<Integer>(bases) ) );
}
} while ( increment(digits, aMaxBase) );
System.out.println(length + "-character strings which are prime in the most bases: " + maxBasesCount);
for ( Tuple tuple : maxStrings ) {
System.out.println(numberBase(tuple.first) + " -> " + tuple.second);
}
System.out.println();
}
}
private static boolean increment(List<Integer> aDigits, int aMaxBase) {
for ( int i = aDigits.size() - 1; i >= 0; i-- ) {
if ( aDigits.get(i) + 1 != aMaxBase ) {
aDigits.set(i, aDigits.get(i) + 1);
return true;
}
aDigits.set(i, 0);
}
return false;
}
private static String numberBase(List<Integer> aList) {
final String digits = "0123456789abcdefghijklmnopqrstuvwxyz";
StringBuilder result = new StringBuilder();
for ( int number : aList ) {
result.append(digits.charAt(number));
}
return result.toString();
}
private static void fillPrimes(int aMaxBase, int aMaxLength) {
final int limit = (int) Math.pow(aMaxBase, aMaxLength);
primes = new boolean[limit + 1];
Arrays.fill(primes, true);
primes[0] = false;
primes[1] = false;
for ( int i = 2; i < Math.sqrt(limit); i++ ) {
if ( primes[i] ) {
int j = i * i;
while ( j <= limit ) {
primes[j] = false;
j += i;
}
}
}
}
private static class Tuple {
public Tuple(List<Integer> aFirst, List<Integer> aSecond) {
first = aFirst; second = aSecond;
}
private List<Integer> first, second;
}
private static boolean[] primes;
}
- Output:
1-character strings which are prime in the most bases: 34 2 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] 2-character strings which are prime in the most bases: 18 21 -> [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36] 3-character strings which are prime in the most bases: 18 131 -> [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34] 551 -> [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36] 737 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36] 4-character strings which are prime in the most bases: 19 1727 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36] 5347 -> [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36] 5-character strings which are prime in the most bases: 18 30271 -> [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36]
Julia
using Primes
function maxprimebases(ndig, maxbase)
maxprimebases = [Int[]]
nwithbases = [0]
maxprime = 10^(ndig) - 1
for p in div(maxprime + 1, 10):maxprime
dig = digits(p)
bases = [b for b in 2:maxbase if (isprime(evalpoly(b, dig)) && all(i -> i < b, dig))]
if length(bases) > length(first(maxprimebases))
maxprimebases = [bases]
nwithbases = [p]
elseif length(bases) == length(first(maxprimebases))
push!(maxprimebases, bases)
push!(nwithbases, p)
end
end
alen, vlen = length(first(maxprimebases)), length(maxprimebases)
println("\nThe maximum number of prime valued bases for base 10 numeric strings of length ",
ndig, " is $alen. The base 10 value list of ", vlen > 1 ? "these" : "this", " is:")
for i in eachindex(maxprimebases)
println(nwithbases[i], " => ", maxprimebases[i])
end
end
@time for n in 1:6
maxprimebases(n, 36)
end
- Output:
The maximum number of prime valued bases for base 10 numeric strings of length 1 is 34. The base 10 value list of this is: 2 => [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The maximum number of prime valued bases for base 10 numeric strings of length 2 is 18. The base 10 value list of this is: 21 => [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36] The maximum number of prime valued bases for base 10 numeric strings of length 3 is 18. The base 10 value list of these is: 131 => [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34] 551 => [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36] 737 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36] The maximum number of prime valued bases for base 10 numeric strings of length 4 is 19. The base 10 value list of these is: 1727 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36] 5347 => [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36] The maximum number of prime valued bases for base 10 numeric strings of length 5 is 18. The base 10 value list of this is: 30271 => [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36] The maximum number of prime valued bases for base 10 numeric strings of length 6 is 18. The base 10 value list of this is: 441431 => [5, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 23, 26, 28, 30, 31, 32, 33] 4.808196 seconds (8.58 M allocations: 357.983 MiB, 0.75% gc time)
Up to base 62
using Primes
function maxprimebases(ndig, maxbase)
maxprimebases = [Int[]]
nwithbases = ["0"]
for tup in Iterators.product([0:maxbase-1 for _ in 1:ndig - 1]..., 1:maxbase-1)
dig = collect(tup)
foundbases = Int[]
for b in maximum(dig)+1:maxbase
if isprime(evalpoly(b, dig))
push!(foundbases, b)
end
maxbase - b + length(foundbases) < length(maxprimebases) && break # shortcut if hopeless
end
if length(foundbases) > length(first(maxprimebases))
maxprimebases = [foundbases]
nwithbases = [prod(string.(reverse(dig), base = any(x -> x > 9, dig) ? 32 : 10))]
elseif length(foundbases) == length(first(maxprimebases))
push!(maxprimebases, foundbases)
push!(nwithbases, prod(string.(reverse(dig), base = any(x -> x > 9, dig) ? 32 : 10)))
end
end
alen, vlen = length(first(maxprimebases)), length(maxprimebases)
println("\nThe maximum number of prime valued bases for base up to $maxbase numeric strings of length ",
ndig, " is $alen. The value list of ", vlen > 1 ? "these" : "this", " is:")
for i in eachindex(maxprimebases)
println(nwithbases[i], maxprimebases[i][1] > 10 ? "(base 32)" : "", " => ", maxprimebases[i])
end
end
for n in 1:5
maxprimebases(n, 36)
maxprimebases(n, 62)
end
- Output:
The maximum number of prime valued bases for base up to 36 numeric strings of length 1 is 34. The value list of this is: 2 => [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The maximum number of prime valued bases for base up to 62 numeric strings of length 1 is 60. The value list of this is: 2 => [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62] The maximum number of prime valued bases for base up to 36 numeric strings of length 2 is 18. The value list of this is: 21 => [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36] The maximum number of prime valued bases for base up to 62 numeric strings of length 2 is 31. The value list of this is: 65 => [7, 8, 9, 11, 13, 14, 16, 17, 18, 21, 22, 24, 27, 28, 29, 31, 32, 37, 38, 39, 41, 42, 43, 44, 46, 48, 51, 52, 57, 58, 59] The maximum number of prime valued bases for base up to 36 numeric strings of length 3 is 18. The value list of these is: 131 => [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34] 551 => [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36] 737 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36] The maximum number of prime valued bases for base up to 62 numeric strings of length 3 is 33. The value list of these is: 1l1(base 32) => [22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 51, 52, 53, 54, 57, 58, 59, 60, 61, 62] b9b(base 32) => [13, 14, 15, 16, 17, 19, 20, 21, 23, 24, 26, 27, 28, 30, 31, 34, 36, 39, 40, 42, 45, 47, 49, 50, 52, 53, 54, 57, 58, 59, 60, 61, 62] The maximum number of prime valued bases for base up to 36 numeric strings of length 4 is 19. The value list of these is: 1727 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36] 5347 => [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36] The maximum number of prime valued bases for base up to 62 numeric strings of length 4 is 32. The value list of these is: 1727 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36, 37, 38, 39, 41, 45, 46, 48, 50, 51, 57, 58, 60, 61] 417b(base 32) => [12, 13, 15, 16, 17, 18, 19, 21, 23, 25, 28, 30, 32, 34, 35, 37, 38, 39, 41, 45, 48, 49, 50, 51, 52, 54, 56, 57, 58, 59, 61, 62] The maximum number of prime valued bases for base up to 36 numeric strings of length 5 is 18. The value list of this is: 30271 => [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36] The maximum number of prime valued bases for base up to 62 numeric strings of length 5 is 30. The value list of this is: 50161 => [7, 8, 9, 13, 17, 18, 19, 20, 25, 28, 29, 30, 31, 33, 35, 36, 38, 39, 41, 42, 43, 44, 47, 48, 52, 55, 56, 59, 60, 62]
Mathematica /Wolfram Language
ClearAll[OtherBasePrimes, OtherBasePrimesPower]
OtherBasePrimes[n_Integer] := Module[{digs, minbase, bases},
digs = IntegerDigits[n];
minbase = Max[digs] + 1;
bases = Range[minbase, 36];
Pick[bases, PrimeQ[FromDigits[digs, #] & /@ bases], True]
]
OtherBasePrimesPower[p_] := Module[{min, max, out, maxlen},
min = 10^p;
max = 10^(p + 1) - 1;
out = {#, OtherBasePrimes[#]} & /@ Range[min, max];
maxlen = Max[Length /@ out[[All, 2]]];
Select[out, Last /* Length /* EqualTo[maxlen]]
]
OtherBasePrimesPower[0] // Column
OtherBasePrimesPower[1] // Column
OtherBasePrimesPower[2] // Column
OtherBasePrimesPower[3] // Column
OtherBasePrimesPower[4] // Column
OtherBasePrimesPower[5] // Column
- Output:
{2,{3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36}}
{21,{3,5,6,8,9,11,14,15,18,20,21,23,26,29,30,33,35,36}}
{131,{4,5,7,8,9,10,12,14,15,18,19,20,23,25,27,29,30,34}}
{551,{6,7,11,13,14,15,16,17,19,21,22,24,25,26,30,32,35,36}}
{737,{8,9,11,12,13,15,16,17,19,22,23,24,25,26,29,30,31,36}}
{1727,{8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36}}
{5347,{8,9,10,11,12,13,16,18,19,22,24,25,26,30,31,32,33,34,36}}
{30271,{8,10,12,13,16,17,18,20,21,23,24,25,31,32,33,34,35,36}}
{441431,{5,8,9,11,12,14,16,17,19,21,22,23,26,28,30,31,32,33}}
Nim
Compiled via C++ with full optimizations and runtime checks deactivated, the program takes 1 second to process up to 5 character strings and 34 seconds to process up to 6 characters (i5-8250U CPU @ 1.60GHz). Curiously, compiled via C it is slower (1.1 s and 38 seconds).
import math, sequtils, strutils
const
MaxDepth = 6
Max = 36^MaxDepth - 1 # Max value for MaxDepth digits in base 36.
Digits = "0123456789abcdefghijklmnopqrstuvwxyz"
# Sieve of Erathostenes.
var composite: array[1..(Max div 2), bool] # Only odd numbers.
for i in 1..composite.high:
let n = 2 * i + 1
let n2 = n * n
if n2 > Max: break
if not composite[i]:
for k in countup(n2, Max, 2 * n):
composite[k shr 1] = true
template isPrime(n: int): bool =
if n <= 1: false
elif (n and 1) == 0: n == 2
else: not composite[n shr 1]
type Context = object
indices: seq[int]
mostBases: int
maxStrings: seq[tuple[indices, bases: seq[int]]]
func initContext(depth: int): Context =
result.indices.setLen(depth)
result.mostBases = -1
proc process(ctx: var Context) =
let minBase = max(2, max(ctx.indices) + 1)
if 37 - minBase < ctx.mostBases: return
var bases: seq[int]
for b in minBase..36:
var n = 0
for i in ctx.indices:
n = n * b + i
if n.isPrime: bases.add b
var count = bases.len
if count > ctx.mostBases:
ctx.mostBases = count
ctx.maxStrings = @{ctx.indices: bases}
elif count == ctx.mostBases:
ctx.maxStrings.add (ctx.indices, bases)
proc nestedFor(ctx: var Context; length, level: int) =
if level == ctx.indices.len:
ctx.process()
else:
ctx.indices[level] = if level == 0: 1 else: 0
while ctx.indices[level] < length:
ctx.nestedFor(length, level + 1)
inc ctx.indices[level]
for depth in 1..MaxDepth:
var ctx = initContext(depth)
ctx.nestedFor(Digits.len, 0)
echo depth, " character strings which are prime in most bases: ", ctx.maxStrings[0].bases.len
for m in ctx.maxStrings:
echo m.indices.mapIt(Digits[it]).join(), " → ", m[1].join(" ")
echo()
- Output:
1 character strings which are prime in most bases: 34 2 → 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 2 character strings which are prime in most bases: 18 21 → 3 5 6 8 9 11 14 15 18 20 21 23 26 29 30 33 35 36 3 character strings which are prime in most bases: 18 131 → 4 5 7 8 9 10 12 14 15 18 19 20 23 25 27 29 30 34 551 → 6 7 11 13 14 15 16 17 19 21 22 24 25 26 30 32 35 36 737 → 8 9 11 12 13 15 16 17 19 22 23 24 25 26 29 30 31 36 4 character strings which are prime in most bases: 19 1727 → 8 9 11 12 13 15 16 17 19 20 22 23 24 26 27 29 31 33 36 5347 → 8 9 10 11 12 13 16 18 19 22 24 25 26 30 31 32 33 34 36 5 character strings which are prime in most bases: 18 30271 → 8 10 12 13 16 17 18 20 21 23 24 25 31 32 33 34 35 36 6 character strings which are prime in most bases: 18 441431 → 5 8 9 11 12 14 16 17 19 21 22 23 26 28 30 31 32 33
Pascal
First counting the bases that convert a MAXBASE string of n into a prime number.
Afterwards only checking the maxcount for the used bases.
program MAXBaseStringIsPrimeInBase;
{$IFDEF FPC}
{$MODE DELPHI}
{$OPTIMIZATION ON,ALL}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils;
const
CharOfBase= '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
MINBASE = 2;
MAXBASE = 62;//36;//62;
MAXDIGITCOUNT = 5;//6;
type
tdigits = packed record
dgtDgts : array [0..13] of byte;
dgtMaxIdx,
dgtMaxDgtVal :byte;
dgtNum : Uint64;
end;
tSol = array of Uint64;
var
BoolPrimes: array of boolean;
function BuildWheel(primeLimit:Int64):NativeUint;
var
myPrimes : pBoolean;
wheelprimes :array[0..31] of byte;
wheelSize,wpno,
pr,pw,i, k: NativeUint;
begin
myPrimes := @BoolPrimes[0];
pr := 1;
myPrimes[1]:= true;
WheelSize := 1;
wpno := 0;
repeat
inc(pr);
pw := pr;
if pw > wheelsize then
dec(pw,wheelsize);
If myPrimes[pw] then
begin
k := WheelSize+1;
for i := 1 to pr-1 do
begin
inc(k,WheelSize);
if k<primeLimit then
move(myPrimes[1],myPrimes[k-WheelSize],WheelSize)
else
begin
move(myPrimes[1],myPrimes[k-WheelSize],PrimeLimit-WheelSize*i);
break;
end;
end;
dec(k);
IF k > primeLimit then
k := primeLimit;
wheelPrimes[wpno] := pr;
myPrimes[pr] := false;
inc(wpno);
WheelSize := k;
i:= pr;
i := i*i;
while i <= k do
begin
myPrimes[i] := false;
inc(i,pr);
end;
end;
until WheelSize >= PrimeLimit;
while wpno > 0 do
begin
dec(wpno);
myPrimes[wheelPrimes[wpno]] := true;
end;
myPrimes[0] := false;
myPrimes[1] := false;
BuildWheel := pr+1;
end;
procedure Sieve(PrimeLimit:Uint64);
var
myPrimes : pBoolean;
sieveprime,
fakt : NativeUint;
begin
setlength(BoolPrimes,PrimeLimit+1);
myPrimes := @BoolPrimes[0];
sieveprime := BuildWheel(PrimeLimit);
repeat
if myPrimes[sieveprime] then
begin
fakt := PrimeLimit DIV sieveprime;
IF fakt < sieveprime then
BREAK;
repeat
myPrimes[sieveprime*fakt] := false;
repeat
dec(fakt);
until myPrimes[fakt];
until fakt < sieveprime;
end;
inc(sieveprime);
until false;
myPrimes[1] := false;
end;
procedure CnvtoBASE(var dgt:tDigits;n:Uint64;base:NativeUint);
var
q,r: Uint64;
i : Int32;
Begin
i := 0;
with dgt do
Begin
fillchar(dgtDgts,SizeOf(dgtDgts),#0);
dgtNum:= n;
repeat
r := n;
q := n div base;
r -= q*base;
n := q;
dgtDgts[i] := r;
inc(i);
until (q = 0);
dec(i);
dgtMaxIdx := i;
r := 1;
repeat
q := dgtDgts[i];
if r < q then
r := q;
dec(i);
until i <0 ;
dgtMaxDgtVal := r;
end;
end;
function CnvDgtAsInBase(const dgt:tDigits;base:NativeUint):Uint64;
var
tmpDgt,i: NativeInt;
Begin
result := 0;
with dgt do
Begin
i:= dgtMaxIdx;
repeat
tmpDgt := dgtDgts[i];
result *= base;
dec(i);
result +=tmpDgt;
until (i< 0);
end;
end;
procedure IncInBaseDigits(var dgt:tDigits;base:NativeInt);
var
i,q,tmp :NativeInt;
Begin
with dgt do
Begin
tmp := dgtMaxIdx;
i := 0;
repeat
q := dgtDgts[i]+1;
q -= (-ORD(q >=base) AND base);
dgtDgts[i] := q;
inc(i);
until q <> 0;
dec(i);
if tmp < i then
begin
tmp := i;
dgtMaxIdx := i;
end;
i := tmp;
repeat
tmp := dgtDgts[i];
if q< tmp then
q := tmp;
dec(i);
until i <0;
inc(dgtNum);
dgtMaxDgtVal := q;
end;
end;
function CntPrimeInBases(var Digits :tdigits;max:Int32):Uint32;
var
pr : Uint64;
base: Uint32;
begin
result := 0;
IncInBaseDigits(Digits,MAXBASE);
base := Digits.dgtMaxDgtVal+1;
//divisible by every base
IF Digits.dgtDgts[0] = 0 then
EXIT;
IF base < MINBASE then base := MINBASE;
// if (MAXBASE - Base) <= (max-result) then BREAK;
max := (max+Base-MAXBASE);
if (max>=0) then
EXIT;
for base := base TO MAXBASE do
begin
pr := CnvDgtAsInBase(Digits,base);
inc(result,Ord(boolprimes[pr]));
//no chance to reach max then exit
if result<max then
break;
inc(max);
end;
end;
function GetMaxBaseCnt(var dgt:tDigits;MinLmt,MaxLmt:Uint32):tSol;
var
i : Uint32;
baseCnt,max,Idx: Int32;
Begin
setlength(result,0);
max :=-1;
Idx:= 0;
For i := MinLmt to MaxLmt do
Begin
baseCnt := CntPrimeInBases(dgt,max);
if baseCnt = 0 then
continue;
if max<=baseCnt then
begin
if max = baseCnt then
begin
inc(Idx);
if Idx > High(result) then
setlength(result,Idx);
result[idx-1] := i;
end
else
begin
Idx:= 1;
setlength(result,1);
result[0] := i;
max := baseCnt;
end;
end;
end;
end;
function Out_String(n:Uint64;var s: AnsiString):Uint32;
//out-sourced for debugging purpose
var
dgt:tDigits;
sl : string[15];
base,i: Int32;
Begin
result := 0;
CnvtoBASE(dgt,n,MaxBase);
sl := '';
with dgt do
begin
base:= dgtMaxDgtVal+1;
IF base < MINBASE then
base := MINBASE;
i := dgtMaxIdx;
while (i>=0)do
Begin
sl += CharOfBase[dgtDgts[i]+1];
dec(i);
end;
s := sl+' -> [';
end;
For base := base to MAXBASE do
if boolprimes[CnvDgtAsInBase(dgt,base)] then
begin
inc(result);
str(base,sl);
s := s+sl+',';
end;
s[length(s)] := ']';
end;
procedure Out_Sol(sol:tSol);
var
s : AnsiString;
i,cnt : Int32;
begin
if length(Sol) = 0 then
EXIT;
for i := 0 to High(Sol) do
begin
cnt := Out_String(sol[i],s);
if i = 0 then
writeln(cnt);
writeln(s);
end;
writeln;
setlength(Sol,0);
end;
var
dgt:tDigits;
T0 : Int64;
i : NativeInt;
lmt,minLmt : UInt64;
begin
T0 := GetTickCount64;
lmt := 0;
//maxvalue in Maxbase
for i := 1 to MAXDIGITCOUNT do
lmt :=lmt*MAXBASE+MAXBASE-1;
writeln('max prime limit ',lmt);
Sieve(lmt);
writeln('Prime sieving ',(GetTickCount64-T0)/1000:6:3,' s');
T0 := GetTickCount64;
CnvtoBASE(dgt,0,MAXBASE);
i := 1;
minLmt := 1;
repeat
write(i:2,' character strings which are prime in count bases = ');
Out_Sol(GetMaxBaseCnt(dgt,minLmt,MAXBASE*minLmt-1));
minLmt *= MAXBASE;
inc(i);
until i>MAXDIGITCOUNT;
writeln(' Converting ',(GetTickCount64-T0)/1000:6:3,' s');
{$IFDEF WINDOWS} readln; {$ENDIF}
end.
- Output:
TIO.RUN// extreme volatile timings for sieving primes max prime limit 916132831 Prime sieving 3.788 s 1 character strings which are prime in count bases = 60 2 -> [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62] 2 character strings which are prime in count bases = 31 65 -> [7,8,9,11,13,14,16,17,18,21,22,24,27,28,29,31,32,37,38,39,41,42,43,44,46,48,51,52,57,58,59] 3 character strings which are prime in count bases = 33 1L1 -> [22,23,25,26,27,28,29,30,31,32,33,34,36,38,39,40,41,42,43,44,45,46,48,51,52,53,54,57,58,59,60,61,62] B9B -> [13,14,15,16,17,19,20,21,23,24,26,27,28,30,31,34,36,39,40,42,45,47,49,50,52,53,54,57,58,59,60,61,62] 4 character strings which are prime in count bases = 32 1727 -> [8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36,37,38,39,41,45,46,48,50,51,57,58,60,61] 417B -> [12,13,15,16,17,18,19,21,23,25,28,30,32,34,35,37,38,39,41,45,48,49,50,51,52,54,56,57,58,59,61,62] 5 character strings which are prime in count bases = 30 50161 -> [7,8,9,13,17,18,19,20,25,28,29,30,31,33,35,36,38,39,41,42,43,44,47,48,52,55,56,59,60,62] Converting 12.738 s Real time: 16.768 s User time: 16.128 s Sys. time: 0.488 s CPU share: 99.09 % //at home AMD 2200G Linux fpc 3.2.2 real 0m8,609s user 0m8,378s sys 0m0,220s max prime limit 916132831 Prime sieving 1.734 s Converting 6.842 s //base = 36 maxcharacters = 6 max prime limit 2176782335 Prime sieving 4.986 s 1 character strings which are prime in count bases = 34 2 -> [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36] 2 character strings which are prime in count bases = 18 21 -> [3,5,6,8,9,11,14,15,18,20,21,23,26,29,30,33,35,36] 3 character strings which are prime in count bases = 18 131 -> [4,5,7,8,9,10,12,14,15,18,19,20,23,25,27,29,30,34] 551 -> [6,7,11,13,14,15,16,17,19,21,22,24,25,26,30,32,35,36] 737 -> [8,9,11,12,13,15,16,17,19,22,23,24,25,26,29,30,31,36] 4 character strings which are prime in count bases = 19 1727 -> [8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36] 5347 -> [8,9,10,11,12,13,16,18,19,22,24,25,26,30,31,32,33,34,36] 5 character strings which are prime in count bases = 18 30271 -> [8,10,12,13,16,17,18,20,21,23,24,25,31,32,33,34,35,36] 6 character strings which are prime in count bases = 18 441431 -> [5,8,9,11,12,14,16,17,19,21,22,23,26,28,30,31,32,33] Converting 15.507 s// 24.3s before real 0m20,566s
Perl
use strict;
use warnings;
use feature 'say';
use List::AllUtils <firstidx max>;
use ntheory qw/fromdigits todigitstring primes/;
my(%prime_base, %max_bases, $l);
my $chars = 5;
my $upto = fromdigits( '1' . 'Z' x $chars, 36);
my @primes = @{primes( $upto )};
for my $base (2..36) {
my $n = todigitstring($base-1, $base) x $chars;
my $threshold = fromdigits($n, $base);
my $i = firstidx { $_ > $threshold } @primes;
map { push @{$prime_base{ todigitstring($primes[$_],$base) }}, $base } 0..$i-1;
}
$l = length and $max_bases{$l} = max( $#{$prime_base{$_}}, $max_bases{$l} // 0 ) for keys %prime_base;
for my $m (1 .. $chars) {
say "$m character strings that are prime in maximum bases: ", 1+$max_bases{$m};
for (sort grep { length($_) == $m } keys %prime_base) {
my @bases = @{($prime_base{$_})[0]};
say "$_: " . join ' ', @bases if $max_bases{$m} eq $#bases;
}
say ''
}
- Output:
1 character strings that are prime in maximum bases: 34 2: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 2 character strings that are prime in maximum bases: 18 21: 3 5 6 8 9 11 14 15 18 20 21 23 26 29 30 33 35 36 3 character strings that are prime in maximum bases: 18 131: 4 5 7 8 9 10 12 14 15 18 19 20 23 25 27 29 30 34 551: 6 7 11 13 14 15 16 17 19 21 22 24 25 26 30 32 35 36 737: 8 9 11 12 13 15 16 17 19 22 23 24 25 26 29 30 31 36 4 character strings that are prime in maximum bases: 19 1727: 8 9 11 12 13 15 16 17 19 20 22 23 24 26 27 29 31 33 36 5347: 8 9 10 11 12 13 16 18 19 22 24 25 26 30 31 32 33 34 36 5 character strings that are prime in maximum bases: 18 30271: 8 10 12 13 16 17 18 20 21 23 24 25 31 32 33 34 35 36
Phix
Originally translated from Rust, but changed to a much fuller range of digits, as per talk page.
with javascript_semantics constant maxbase=36 -- or 62 function evalpoly(integer x, sequence p) integer result = 0 for y=1 to length(p) do result = result*x + p[y] end for return result end function function stringify(sequence digits) string res = repeat('0',length(digits)) for i=1 to length(digits) do integer di = digits[i] res[i] = di + iff(di<=9?'0':iff(di<36?'A'-10:'a'-36)) end for return res end function procedure max_prime_bases(integer ndig, maxbase) atom t0 = time(), t1 = time()+1 sequence maxprimebases = {}, digits = repeat(0,ndig) integer maxlen = 0, limit = power(10,ndig), maxdigit = maxbase if ndig>1 then digits[1] = 1 end if while true do for i=length(digits) to 1 by -1 do integer di = digits[i]+1 if di<maxdigit then -- (or 9, see below) digits[i] = di exit else di = 0 digits[i] = 0 end if end for integer minbase = max(digits)+1, maxposs = maxbase-minbase+1 if minbase=1 then exit end if -- (ie we just wrapped round to all 0s) sequence bases = {} for base=minbase to maxbase do if is_prime(evalpoly(base,digits)) then bases &= base else maxposs -= 1 if maxposs<maxlen then exit end if -- (a 5-fold speedup) end if end for integer l = length(bases) if l>maxlen then maxlen = l maxdigit = maxbase-maxlen -- (around 20-fold speedup) maxprimebases = {} end if if l=maxlen then maxprimebases &= {{stringify(digits), bases}} end if if platform()!=JS and time()>t1 then progress("%V\r",{digits}) t1 = time()+1 end if end while string e = elapsed(time()-t0) printf(1,"%d character numeric strings that are prime in %d bases (%s):\n",{ndig,maxlen,e}) for i=1 to length(maxprimebases) do printf(1," %s => %V\n", maxprimebases[i]) end for printf(1,"\n") end procedure for n=1 to iff(platform()=JS or maxbase>36?4:6) do max_prime_bases(n, maxbase) end for
- Output:
1 character numeric strings that are prime in 34 bases (0s):
2 => {3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36}
2 character numeric strings that are prime in 18 bases (0s):
21 => {3,5,6,8,9,11,14,15,18,20,21,23,26,29,30,33,35,36}
3 character numeric strings that are prime in 18 bases (0.0s):
131 => {4,5,7,8,9,10,12,14,15,18,19,20,23,25,27,29,30,34}
551 => {6,7,11,13,14,15,16,17,19,21,22,24,25,26,30,32,35,36}
737 => {8,9,11,12,13,15,16,17,19,22,23,24,25,26,29,30,31,36}
4 character numeric strings that are prime in 19 bases (0.6s):
1727 => {8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36}
5347 => {8,9,10,11,12,13,16,18,19,22,24,25,26,30,31,32,33,34,36}
5 character numeric strings that are prime in 18 bases (18.6s):
30271 => {8,10,12,13,16,17,18,20,21,23,24,25,31,32,33,34,35,36}
6 character numeric strings that are prime in 18 bases (11 minutes and 17s):
441431 => {5,8,9,11,12,14,16,17,19,21,22,23,26,28,30,31,32,33}
As usual we skip the last couple of entries under pwa/p2js to avoid staring at a blank screen for ages
If we "cheat" and only check digits 0..9 we get the same results much faster:
4 character numeric strings that are prime in 19 bases (0.1s): 5 character numeric strings that are prime in 18 bases (1.0s): 6 character numeric strings that are prime in 18 bases (16.8s):
If we set maxbase to 62:
1 character numeric strings that are prime in 60 bases (0s):
2 => {3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62}
2 character numeric strings that are prime in 31 bases (0.0s):
65 => {7,8,9,11,13,14,16,17,18,21,22,24,27,28,29,31,32,37,38,39,41,42,43,44,46,48,51,52,57,58,59}
3 character numeric strings that are prime in 33 bases (0.2s):
1L1 => {22,23,25,26,27,28,29,30,31,32,33,34,36,38,39,40,41,42,43,44,45,46,48,51,52,53,54,57,58,59,60,61,62}
B9B => {13,14,15,16,17,19,20,21,23,24,26,27,28,30,31,34,36,39,40,42,45,47,49,50,52,53,54,57,58,59,60,61,62}
4 character numeric strings that are prime in 32 bases (9.6s):
1727 => {8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36,37,38,39,41,45,46,48,50,51,57,58,60,61}
417B => {12,13,15,16,17,18,19,21,23,25,28,30,32,34,35,37,38,39,41,45,48,49,50,51,52,54,56,57,58,59,61,62}
Raku
Up to 4 character strings finish fairly quickly. 5 character strings take a while.
All your base are belong to us. You have no chance to survive make your prime.
use Math::Primesieve;
my $sieve = Math::Primesieve.new;
my %prime-base;
my $chars = 4; # for demonstration purposes. Change to 5 for the whole shmegegge.
my $threshold = ('1' ~ 'Z' x $chars).parse-base(36);
my @primes = $sieve.primes($threshold);
%prime-base.push: $_ for (2..36).map: -> $base {
$threshold = (($base - 1).base($base) x $chars).parse-base($base);
@primes[^(@primes.first: * > $threshold, :k)].race.map: { .base($base) => $base }
}
%prime-base.=grep: +*.value.elems > 10;
for 1 .. $chars -> $m {
say "$m character strings that are prime in maximum bases: " ~ (my $e = ((%prime-base.grep( *.key.chars == $m )).max: +*.value.elems).value.elems);
.say for %prime-base.grep( +*.value.elems == $e ).grep(*.key.chars == $m).sort: *.key;
say '';
}
- Output:
1 character strings that are prime in maximum bases: 34 2 => [3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36] 2 character strings that are prime in maximum bases: 18 21 => [3 5 6 8 9 11 14 15 18 20 21 23 26 29 30 33 35 36] 3 character strings that are prime in maximum bases: 18 131 => [4 5 7 8 9 10 12 14 15 18 19 20 23 25 27 29 30 34] 551 => [6 7 11 13 14 15 16 17 19 21 22 24 25 26 30 32 35 36] 737 => [8 9 11 12 13 15 16 17 19 22 23 24 25 26 29 30 31 36] 4 character strings that are prime in maximum bases: 19 1727 => [8 9 11 12 13 15 16 17 19 20 22 23 24 26 27 29 31 33 36] 5347 => [8 9 10 11 12 13 16 18 19 22 24 25 26 30 31 32 33 34 36] 5 character strings that are prime in maximum bases: 18 30271 => [8 10 12 13 16 17 18 20 21 23 24 25 31 32 33 34 35 36]
You can't really assume that the maximum string will be all numeric digits. It is just an accident that they happen to work out that way with a upper limit of base 36. If we do the same filtering using a maximum of base 62, we end up with several that contain alphabetics.
use Math::Primesieve;
use Base::Any;
my $chars = 4;
my $check-base = 62;
my $threshold = $check-base ** $chars + 20;
my $sieve = Math::Primesieve.new;
my @primes = $sieve.primes($threshold);
my %prime-base;
%prime-base.push: $_ for (2..$check-base).map: -> $base {
$threshold = (($base - 1).&to-base($base) x $chars).&from-base($base);
@primes[^(@primes.first: * > $threshold, :k)].race.map: { .&to-base($base) => $base }
}
%prime-base.=grep: +*.value.elems > 10;
for 1 .. $chars -> $m {
say "$m character strings that are prime in maximum bases: " ~ (my $e = ((%prime-base.grep( *.key.chars == $m )).max: +*.value.elems).value.elems);
.say for %prime-base.grep( +*.value.elems == $e ).grep(*.key.chars == $m).sort: *.key;
say '';
}
- Yields:
1 character strings that are prime in maximum bases: 60 2 => [3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62] 2 character strings that are prime in maximum bases: 31 65 => [7 8 9 11 13 14 16 17 18 21 22 24 27 28 29 31 32 37 38 39 41 42 43 44 46 48 51 52 57 58 59] 3 character strings that are prime in maximum bases: 33 1L1 => [22 23 25 26 27 28 29 30 31 32 33 34 36 38 39 40 41 42 43 44 45 46 48 51 52 53 54 57 58 59 60 61 62] B9B => [13 14 15 16 17 19 20 21 23 24 26 27 28 30 31 34 36 39 40 42 45 47 49 50 52 53 54 57 58 59 60 61 62] 4 character strings that are prime in maximum bases: 32 1727 => [8 9 11 12 13 15 16 17 19 20 22 23 24 26 27 29 31 33 36 37 38 39 41 45 46 48 50 51 57 58 60 61] 417B => [12 13 15 16 17 18 19 21 23 25 28 30 32 34 35 37 38 39 41 45 48 49 50 51 52 54 56 57 58 59 61 62]
REXX
/*REXX pgm finds primes whose values in other bases (2──►36) have the most diff. bases. */
parse arg widths . /*obtain optional argument from the CL.*/
if widths=='' | widths=="," then widths= 5 /*Not specified? Then use the default.*/
call genP /*build array of semaphores for primes.*/
names= 'one two three four five six seven eight' /*names for some low decimal numbers. */
$.=
do j=1 for # /*only use primes that are within range*/
do b=36 by -1 for 35; n= base(@.j, b) /*use different bases for each prime. */
L= length(n); if L>widths then iterate /*obtain length; Length too big? Skip.*/
if L==1 then $.L.n= b $.L.n /*Length = unity? Prepend the base.*/
else $.L.n= $.L.n b /* " ¬= " Append " " */
end /*b*/
end /*j*/
/*display info for each of the widths. */
do w=1 for widths; cnt= 0 /*show for each width: cnt,number,bases*/
bot= left(1, w, 0); top= left(9, w, 9) /*calculate range for DO. */
do n=bot to top; y= words($.w.n) /*find the sets of numbers for a width.*/
if y>cnt then do; mxn=n; cnt= max(cnt, y); end /*found a max? Remember it*/
end /*n*/
say
say; say center(' 'word(names, w)"─character numbers that are" ,
'prime in the most bases: ('cnt "bases) ", 101, '─')
do n=bot to top; y= words($.w.n) /*search again for maximums.*/
if y==cnt then say n '──►' strip($.w.n) /*display ───a─── maximum. */
end /*n*/
end /*w*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
base: procedure; parse arg x,r,,z; @= '0123456789abcdefghijklmnopqrsruvwxyz'
do j=1; _= r**j; if _>x then leave
end /*j*/
do k=j-1 to 1 by -1; _= r**k; z= z || substr(@, (x % _) + 1, 1); x= x // _
end /*k*/; return z || substr(@, x+1, 1)
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
#= 5; sq.#= @.# ** 2 /*number primes so far; prime squared.*/
do j=@.#+2 by 2 to 2 * 36 * 10**widths /*find odd primes from here on. */
parse var j '' -1 _; if _==5 then iterate /*J is ÷ by 5? (right dig).*/
if j//3==0 then iterate; if j//7==0 then iterate /*" " " " 3?; ÷ by 7? */
do k=5 while sq.k<=j /* [↓] divide by the known odd primes.*/
if j//@.k==0 then iterate j /*Is J ÷ X? Then not prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= # + 1; @.#= j; sq.#= j*j /*bump # Ps; assign next P; P squared.*/
end /*j*/; return
- output when using the default input:
──────────────── one─character numbers that are prime in the most bases: (34 bases) ───────────────── 2 ──► 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 ──────────────── two─character numbers that are prime in the most bases: (18 bases) ───────────────── 21 ──► 3 5 6 8 9 11 14 15 18 20 21 23 26 29 30 33 35 36 ─────────────── three─character numbers that are prime in the most bases: (18 bases) ──────────────── 131 ──► 4 5 7 8 9 10 12 14 15 18 19 20 23 25 27 29 30 34 551 ──► 6 7 11 13 14 15 16 17 19 21 22 24 25 26 30 32 35 36 737 ──► 8 9 11 12 13 15 16 17 19 22 23 24 25 26 29 30 31 36 ──────────────── four─character numbers that are prime in the most bases: (19 bases) ──────────────── 1727 ──► 8 9 11 12 13 15 16 17 19 20 22 23 24 26 27 29 31 33 36 5347 ──► 8 9 10 11 12 13 16 18 19 22 24 25 26 30 31 32 33 34 36 ──────────────── five─character numbers that are prime in the most bases: (18 bases) ──────────────── 30271 ──► 8 10 12 13 16 17 18 20 21 23 24 25 31 32 33 34 35 36
Rust
// [dependencies]
// primal = "0.3"
fn digits(mut n: u32, dig: &mut [u32]) {
for i in 0..dig.len() {
dig[i] = n % 10;
n /= 10;
}
}
fn evalpoly(x: u64, p: &[u32]) -> u64 {
let mut result = 0;
for y in p.iter().rev() {
result *= x;
result += *y as u64;
}
result
}
fn max_prime_bases(ndig: u32, maxbase: u32) {
let mut maxlen = 0;
let mut maxprimebases = Vec::new();
let limit = 10u32.pow(ndig);
let mut dig = vec![0; ndig as usize];
for n in limit / 10..limit {
digits(n, &mut dig);
let bases: Vec<u32> = (2..=maxbase)
.filter(|&x| dig.iter().all(|&y| y < x) && primal::is_prime(evalpoly(x as u64, &dig)))
.collect();
if bases.len() > maxlen {
maxlen = bases.len();
maxprimebases.clear();
}
if bases.len() == maxlen {
maxprimebases.push((n, bases));
}
}
println!(
"{} character numeric strings that are prime in maximum bases: {}",
ndig, maxlen
);
for (n, bases) in maxprimebases {
println!("{} => {:?}", n, bases);
}
println!();
}
fn main() {
for n in 1..=6 {
max_prime_bases(n, 36);
}
}
- Output:
1 character numeric strings that are prime in maximum bases: 34 2 => [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] 2 character numeric strings that are prime in maximum bases: 18 21 => [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36] 3 character numeric strings that are prime in maximum bases: 18 131 => [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34] 551 => [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36] 737 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36] 4 character numeric strings that are prime in maximum bases: 19 1727 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36] 5347 => [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36] 5 character numeric strings that are prime in maximum bases: 18 30271 => [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36] 6 character numeric strings that are prime in maximum bases: 18 441431 => [5, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 23, 26, 28, 30, 31, 32, 33]
Up to base 62
// [dependencies]
// primal = "0.3"
fn to_string(digits: &[usize]) -> String {
const DIGITS: [char; 62] = [
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R',
'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
];
let mut str = String::new();
for d in digits {
str.push(DIGITS[*d]);
}
str
}
fn increment(digits: &mut [usize], base: usize) -> bool {
for d in digits.iter_mut().rev() {
if *d + 1 != base {
*d += 1;
return true;
}
*d = 0;
}
false
}
fn multi_base_primes(max_base: usize, max_length: usize) {
let sieve = primal::Sieve::new(max_base.pow(max_length as u32));
for length in 1..=max_length {
let mut most_bases = 0;
let mut max_strings = Vec::new();
let mut digits = vec![0; length];
digits[0] = 1;
let mut bases = Vec::new();
loop {
let mut min_base = 2;
if let Some(max) = digits.iter().max() {
min_base = std::cmp::max(min_base, max + 1);
}
if most_bases <= max_base - min_base + 1 {
bases.clear();
for b in min_base..=max_base {
if max_base - b + 1 + bases.len() < most_bases {
break;
}
let mut n = 0;
for d in &digits {
n = n * b + d;
}
if sieve.is_prime(n) {
bases.push(b);
}
}
if bases.len() > most_bases {
most_bases = bases.len();
max_strings.clear();
}
if bases.len() == most_bases {
max_strings.push((digits.clone(), bases.clone()));
}
}
if !increment(&mut digits, max_base) {
break;
}
}
println!(
"{}-character strings which are prime in most bases: {}",
length, most_bases
);
for (digits, bases) in max_strings {
println!("{} -> {:?}", to_string(&digits), bases);
}
println!();
}
}
fn main() {
let args: Vec<String> = std::env::args().collect();
let mut max_base = 36;
let mut max_length = 4;
let mut arg = 0;
while arg + 1 < args.len() {
if args[arg] == "-max_base" {
arg += 1;
match args[arg].parse::<usize>() {
Ok(n) => max_base = n,
Err(error) => {
eprintln!("{}", error);
return;
}
}
} else if args[arg] == "-max_length" {
arg += 1;
match args[arg].parse::<usize>() {
Ok(n) => max_length = n,
Err(error) => {
eprintln!("{}", error);
return;
}
}
}
arg += 1;
}
if max_base > 62 {
eprintln!("Maximum base cannot be greater than 62.");
} else if max_base < 2 {
eprintln!("Maximum base cannot be less than 2.");
} else {
use std::time::Instant;
let now = Instant::now();
multi_base_primes(max_base, max_length);
let time = now.elapsed();
println!("elapsed time: {} milliseconds", time.as_millis());
}
}
- Output:
CPU: Intel Core i5-4570 3.2GHz. Maximum base 36, maximum length 6:
1-character strings which are prime in most bases: 34 2 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] 2-character strings which are prime in most bases: 18 21 -> [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36] 3-character strings which are prime in most bases: 18 131 -> [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34] 551 -> [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36] 737 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36] 4-character strings which are prime in most bases: 19 1727 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36] 5347 -> [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36] 5-character strings which are prime in most bases: 18 30271 -> [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36] 6-character strings which are prime in most bases: 18 441431 -> [5, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 23, 26, 28, 30, 31, 32, 33] elapsed time: 15139 milliseconds
Maximum base 62, maximum length 5:
1-character strings which are prime in most bases: 60 2 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62] 2-character strings which are prime in most bases: 31 65 -> [7, 8, 9, 11, 13, 14, 16, 17, 18, 21, 22, 24, 27, 28, 29, 31, 32, 37, 38, 39, 41, 42, 43, 44, 46, 48, 51, 52, 57, 58, 59] 3-character strings which are prime in most bases: 33 1l1 -> [22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 51, 52, 53, 54, 57, 58, 59, 60, 61, 62] b9b -> [13, 14, 15, 16, 17, 19, 20, 21, 23, 24, 26, 27, 28, 30, 31, 34, 36, 39, 40, 42, 45, 47, 49, 50, 52, 53, 54, 57, 58, 59, 60, 61, 62] 4-character strings which are prime in most bases: 32 1727 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36, 37, 38, 39, 41, 45, 46, 48, 50, 51, 57, 58, 60, 61] 417b -> [12, 13, 15, 16, 17, 18, 19, 21, 23, 25, 28, 30, 32, 34, 35, 37, 38, 39, 41, 45, 48, 49, 50, 51, 52, 54, 56, 57, 58, 59, 61, 62] 5-character strings which are prime in most bases: 30 50161 -> [7, 8, 9, 13, 17, 18, 19, 20, 25, 28, 29, 30, 31, 33, 35, 36, 38, 39, 41, 42, 43, 44, 47, 48, 52, 55, 56, 59, 60, 62] elapsed time: 9569 milliseconds
Sidef
func max_prime_bases(ndig, maxbase=36) {
var maxprimebases = [[]]
var nwithbases = [0]
var maxprime = (10**ndig - 1)
for p in (idiv(maxprime + 1, 10) .. maxprime) {
var dig = p.digits
var bases = (2..maxbase -> grep {|b| dig.all { _ < b } && dig.digits2num(b).is_prime })
if (bases.len > maxprimebases.first.len) {
maxprimebases = [bases]
nwithbases = [p]
}
elsif (bases.len == maxprimebases.first.len) {
maxprimebases << bases
nwithbases << p
}
}
var (alen, vlen) = (maxprimebases.first.len, maxprimebases.len)
say("\nThe maximum number of prime valued bases for base 10 numeric strings of length ",
ndig, " is #{alen}. The base 10 value list of ", vlen > 1 ? "these" : "this", " is:")
maxprimebases.each_kv {|k,v| say(nwithbases[k], " => ", v) }
}
for n in (1..5) {
max_prime_bases(n)
}
- Output:
The maximum number of prime valued bases for base 10 numeric strings of length 1 is 34. The base 10 value list of this is: 2 => [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The maximum number of prime valued bases for base 10 numeric strings of length 2 is 18. The base 10 value list of this is: 21 => [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36] The maximum number of prime valued bases for base 10 numeric strings of length 3 is 18. The base 10 value list of these is: 131 => [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34] 551 => [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36] 737 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36] The maximum number of prime valued bases for base 10 numeric strings of length 4 is 19. The base 10 value list of these is: 1727 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36] 5347 => [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36] The maximum number of prime valued bases for base 10 numeric strings of length 5 is 18. The base 10 value list of this is: 30271 => [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36]
Wren
This takes about 1.6 seconds to process up to 4 character strings and 58 seconds for the extra credit which is not too bad for the Wren interpreter.
import "./math" for Int, Nums
var maxDepth = 5
var maxBase = 36
var c = Int.primeSieve(maxBase.pow(maxDepth), false)
var digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
var maxStrings = []
var mostBases = -1
var process = Fn.new { |indices|
var minBase = 2.max(Nums.max(indices) + 1)
if (maxBase - minBase + 1 < mostBases) return // can't affect results so return
var bases = []
for (b in minBase..maxBase) {
var n = 0
for (i in indices) n = n * b + i
if (!c[n]) bases.add(b)
}
var count = bases.count
if (count > mostBases) {
mostBases = count
maxStrings = [[indices.toList, bases]]
} else if (count == mostBases) {
maxStrings.add([indices.toList, bases])
}
}
var printResults = Fn.new {
System.print("%(maxStrings[0][1].count)")
for (m in maxStrings) {
var s = m[0].reduce("") { |acc, i| acc + digits[i] }
System.print("%(s) -> %(m[1])")
}
}
var nestedFor // recursive
nestedFor = Fn.new { |indices, length, level|
if (level == indices.count) {
process.call(indices)
} else {
indices[level] = (level == 0) ? 1 : 0
while (indices[level] < length) {
nestedFor.call(indices, length, level + 1)
indices[level] = indices[level] + 1
}
}
}
for (depth in 1..maxDepth) {
System.write("%(depth) character strings which are prime in most bases: ")
maxStrings = []
mostBases = -1
var indices = List.filled(depth, 0)
nestedFor.call(indices, maxBase, 0)
printResults.call()
System.print()
}
- Output:
1 character strings which are prime in most bases: 34 2 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] 2 character strings which are prime in most bases: 18 21 -> [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36] 3 character strings which are prime in most bases: 18 131 -> [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34] 551 -> [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36] 737 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36] 4 character strings which are prime in most bases: 19 1727 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36] 5347 -> [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36] 5 character strings which are prime in most bases: 18 30271 -> [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36]
If we change maxBase to 62 and maxDepth to 4 in the above script, then the following results are reached in 17 seconds:
1 character strings which are prime in most bases: 60 2 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62] 2 character strings which are prime in most bases: 31 65 -> [7, 8, 9, 11, 13, 14, 16, 17, 18, 21, 22, 24, 27, 28, 29, 31, 32, 37, 38, 39, 41, 42, 43, 44, 46, 48, 51, 52, 57, 58, 59] 3 character strings which are prime in most bases: 33 1l1 -> [22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 51, 52, 53, 54, 57, 58, 59, 60, 61, 62] b9b -> [13, 14, 15, 16, 17, 19, 20, 21, 23, 24, 26, 27, 28, 30, 31, 34, 36, 39, 40, 42, 45, 47, 49, 50, 52, 53, 54, 57, 58, 59, 60, 61, 62] 4 character strings which are prime in most bases: 32 1727 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36, 37, 38, 39, 41, 45, 46, 48, 50, 51, 57, 58, 60, 61] 417b -> [12, 13, 15, 16, 17, 18, 19, 21, 23, 25, 28, 30, 32, 34, 35, 37, 38, 39, 41, 45, 48, 49, 50, 51, 52, 54, 56, 57, 58, 59, 61, 62]