Multi-base primes: Difference between revisions
m (Rust - minor edit) |
(Added Sidef) |
||
Line 1,591: | Line 1,591: | ||
elapsed time: 9569 milliseconds |
elapsed time: 9569 milliseconds |
||
</pre> |
|||
=={{header|Sidef}}== |
|||
{{trans|Julia}} |
|||
<lang ruby>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) |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
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] |
|||
</pre> |
</pre> |
||
Revision as of 13:32, 8 August 2021
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. <lang cpp>#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;
}</lang>
- 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#) <lang fsharp> // 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 "")
</lang>
- 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
<lang 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</lang>
- 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 }
Go
This takes about 1.2 seconds and 31.3 seconds to process up to 5 and 6 character strings, respectively. <lang go>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() }
}</lang>
- 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]
Julia
<lang 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
</lang>
- 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
<lang julia>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
</lang>
- 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]
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).
<lang Nim>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()</lang>
- 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.
<lang pascal>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.</lang>
- 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
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. <lang perl6>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 ;
}</lang>
- 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.
<lang perl6>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 ;
}</lang>
- 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
<lang 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; Lenth 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</lang>
- 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
<lang 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); }
}</lang>
- 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
<lang rust>// [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()); }
}</lang>
- 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
<lang ruby>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)
}</lang>
- 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. <lang ecmascript>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()
}</lang>
- 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]