Rosetta Code

Multi-base primes: Difference between revisions

Page Discussion

Multi-base primes (view source)

Revision as of 00:06, 6 March 2024

26,007 bytes added ,  2 months ago
Added FreeBASIC
m (→‎Up to base 62: make sub item)
(Added FreeBASIC)
 
(26 intermediate revisions by 10 users not shown)
Line 1:
{{draft task|Prime Numbers}}
 
Prime numbers are prime no matter what base they are represented in.
Line 45:
 
=={{header|C++}}==
{{translibheader|WrenPrimesieve}}
Originally translated from [[#Wren|Wren]] with ideas borrowed from other solutions.
This takes 1.1 seconds to process up to 5 character strings and 40 seconds to process up to 6 characters (3.2GHz Intel Core i5).
The maximum base and number of characters can be specified as command line arguments.
<lang cpp>#include <algorithm>
<syntaxhighlight lang="cpp">#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <primesieve.hpp>
 
std::vector<bool>class prime_sieve(uint64_t limit) {
public:
std::vector<bool> sieve(limit, true);
ifexplicit prime_sieve(uint64_t limit > 0);
bool is_prime(uint64_t n) const {
sieve[0] = false;
return n == 2 || ((n & 1) == 1 && sieve[n >> 1]);
if (limit > 1)
}
sieve[1] = false;
 
for (uint64_t i = 4; i < limit; i += 2)
private:
sieve[i] = false;
std::vector<bool> sieve;
for (uint64_t p = 3;; p += 2) {
};
uint64_t q = p * p;
 
if (q >= limit)
prime_sieve::prime_sieve(uint64_t limit) : sieve((limit + 1) / 2, false) {
break;
primesieve::iterator iter;
if (sieve[p]) {
uint64_t prime = iter.next_prime(); // consume 2
uint64_t inc = 2 * p;
while ((prime = for iter.next_prime(; q)) <= limit;) q += inc){
sieve[prime >> sieve[q1] = falsetrue;
}
}
return sieve;
}
 
template <typename T> void print(std::ostream& out, const std::vector<T>& v) {
void print(std::ostream& out, const std::vector<T>& v) {
if (!v.empty()) {
out << '[';
Line 87 ⟶ 89:
 
std::string to_string(const std::vector<unsigned int>& v) {
static constexpr char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
std::string str;
for (auto i : v)
str += digits[i];
return str;
};
 
bool increment(std::vector<unsigned int>& digits, unsigned int max_base) {
class multi_base_primes {
for (auto i = digits.rbegin(); i != digits.rend(); ++i) {
public:
if (*i + 1 != max_base) {
explicit multi_base_primes(unsigned int depth);
void run() ++*i;
return true;
 
}
private:
*i = 0;
void process(const std::vector<unsigned int>& indices);
}
void nested_for(std::vector<unsigned int>& indices, unsigned int level);
return false;
static const unsigned int max_base = 36;
}
unsigned int max_depth;
std::vector<bool> sieve;
unsigned int most_bases = 0;
std::vector<std::pair<std::vector<unsigned int>, std::vector<unsigned int>>>
max_strings;
};
 
multi_base_primes::multi_base_primes(unsigned int depth)
: max_depth(depth),
sieve(prime_sieve(static_cast<uint64_t>(std::pow(max_base, depth)))) {}
 
void multi_base_primes::run(unsigned int max_base, unsigned int max_length) {
prime_sieve sieve(static_cast<uint64_t>(std::pow(max_base, max_length)));
for (unsigned int depth = 1; depth <= max_depth; ++depth) {
for (unsigned int length = 1; length <= max_length; ++length) {
std::cout << depth
std::cout << length
<< " character strings which are prime in most bases: ";
<< "-character strings which are prime in most bases: ";
max_strings.clear();
unsigned int most_bases = 0;
std::vector<unsigned int> indices(depth, 0);
std::pair<std::vector<unsigned int>, std::vector<unsigned int>>>
nested_for(indices, 0);
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) {
Line 132 ⟶ 154:
}
 
int main(int argc, char** argv) {
void multi_base_primes::process(const std::vector<unsigned int>& indices) {
unsigned int max_base = 36;
auto max = std::max_element(indices.begin(), indices.end());
unsigned int min_basemax_length = 24;
iffor (maxint arg != indices.end()1; arg + 1 < argc; ++arg) {
min_baseif = std::max(min_basestrcmp(argv[arg], *max"-max_base") +== 10);
if (most_bases > max_base -= strtoul(argv[++arg], nullptr, min_base10);
else if (strcmp(argv[arg], "-max_length") == 0)
return;
max_length = strtoul(argv[++arg], nullptr, 10);
std::vector<unsigned int> bases;
for (unsigned int b = min_base; b <= max_base; ++b) {
uint64_t n = 0;
for (auto i : indices)
n = n * b + i;
if (sieve[n])
bases.push_back(b);
}
if (bases.size()max_base > most_bases62) {
std::cerr << "Max base cannot be greater than 62.\n";
most_bases = bases.size();
max_strings.clear()return EXIT_FAILURE;
}
if (bases.size()max_base ==< most_bases2) {
std::cerr << "Max base cannot be less than 2.\n";
max_strings.emplace_back(indices, bases);
return EXIT_FAILURE;
}
 
void multi_base_primes::nested_for(std::vector<unsigned int>& indices,
unsigned int level) {
if (level == indices.size()) {
process(indices);
} else {
indices[level] = (level == 0) ? 1 : 0;
while (indices[level] < max_base) {
nested_for(indices, level + 1);
++indices[level];
}
}
multi_base_primes(max_base, max_length);
}
return EXIT_SUCCESS;
 
}</syntaxhighlight>
int main() {
multi_base_primes mbp(6);
mbp.run();
}</lang>
 
{{out}}
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).
<pre>
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]
 
</pre>
 
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).
<pre>
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]
 
</pre>
Line 200 ⟶ 224:
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<langsyntaxhighlight lang="fsharp">
// Multi-base primes. Nigel Galloway: July 4th., 2021
let digits="0123456789abcdefghijklmnopqrstuvwxyz"
Line 208 ⟶ 232:
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 "")
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 228 ⟶ 252:
=={{header|Factor}}==
{{works with|Factor|0.99 2021-06-02}}
<langsyntaxhighlight lang="factor">USING: assocs assocs.extras formatting io kernel math
math.functions math.parser math.primes math.ranges present
sequences ;
Line 248 ⟶ 272:
[ dup (bases) filter "%d => %[%d, %]\n" printf ] each ;
 
4 [1,b] [ multibase. nl ] each</langsyntaxhighlight>
{{out}}
<pre>
Line 266 ⟶ 290:
5347 => { 8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36 }
</pre>
 
=={{header|FreeBASIC}}==
{{trans|Phix}}
<syntaxhighlight lang="vbnet">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</syntaxhighlight>
{{out}}
<pre>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</pre>
 
If we set maxBase to 62:
<pre>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</pre>
 
=={{header|Go}}==
Line 271 ⟶ 432:
{{libheader|Go-rcu}}
This takes about 1.2 seconds and 31.3 seconds to process up to 5 and 6 character strings, respectively.
<langsyntaxhighlight lang="go">package main
 
import (
Line 367 ⟶ 528:
fmt.Println()
}
}</langsyntaxhighlight>
 
{{out}}
Line 412 ⟶ 573:
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]
</pre>
 
=={{header|Java}}==
<syntaxhighlight lang="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;
}
</syntaxhighlight>
{{ out }}
<pre>
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]
</pre>
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Primes
 
function maxprimebases(ndig, maxbase)
Line 443 ⟶ 739:
maxprimebases(n, 36)
end
</langsyntaxhighlight>{{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:
Line 469 ⟶ 765:
 
=== Up to base 62 ===
<langsyntaxhighlight lang="julia">using Primes
 
function maxprimebases(ndig, maxbase)
Line 499 ⟶ 795:
end
 
for n in 1:45
maxprimebases(n, 36)
maxprimebases(n, 62)
end
</langsyntaxhighlight>{{out}}
<pre>
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:
Line 533 ⟶ 829:
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]
</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">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</syntaxhighlight>
{{out}}
<pre>{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}}</pre>
 
=={{header|Nim}}==
Line 540 ⟶ 879:
 
 
<langsyntaxhighlight Nimlang="nim">import math, sequtils, strutils
 
const
Line 607 ⟶ 946:
for m in ctx.maxStrings:
echo m.indices.mapIt(Digits[it]).join(), " → ", m[1].join(" ")
echo()</langsyntaxhighlight>
 
{{out}}
Line 634 ⟶ 973:
First counting the bases that convert a MAXBASE string of n into a prime number.<BR>
Afterwards only checking the maxcount for the used bases.<BR>
<syntaxhighlight lang="pascal">program MAXBaseStringIsPrimeInBase;
Most time consuming is sieving for the primes.
<lang pascal>program MAXBaseStringIsPrimeInBase;
{$IFDEF FPC}
{$MODE DELPHI}
{$OPTIMIZATION ON,ALL}
// {$R+,O+}
{$ELSE}
{$APPTYPE CONSOLE}
Line 646 ⟶ 983:
sysutils;
const
CharOfBase= '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
MINBASE = 2;
MAXBASE = 62;//36;//62;
MAXDIGITCOUNT = 65;//56;
type
tdigits = arraypacked [0..15] of byte;//must be 0..15record
dgtDgts : array [0..13] of byte;
dgtMaxIdx,
dgtMaxDgtVal :byte;
dgtNum : Uint64;
end;
tSol = array of Uint64;
var
BoolPrimes: array of boolean;
 
//memorize the highest used digit
MaxDgtPos : UInt32;
function BuildWheel(primeLimit:Int64):NativeUint;
var
Line 742 ⟶ 1,084:
end;
 
functionprocedure getDgtsInMAXBASEandMaxDigitCnvtoBASE(n:Uint64;var dgt:tDigits);n:uint32Uint64;base:NativeUint);
var
pQ :pQWord;
q,r: Uint64;
i :Int64 Int32;
Begin
pQ := @dgt[0];
pQ[0] := 0;pQ[1] := 0;
//aka fillChar(dgt[0],SizeOf(dgt),#0);
 
i := 0;
resultwith :=dgt 0;do
repeatBegin
fillchar(dgtDgts,SizeOf(dgtDgts),#0);
q := n DIV MAXBASE;
r dgtNum:= (n-q*MAXBASE);
dgt[i] := r;repeat
if result < r then result := rn;
inc(i) q := n div base;
n : r -= q*base;
until n := 0q;
MaxDgtPos dgtDgts[i] := i-1r;
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 CnvtoBaseCnvDgtAsInBase(const dgt:tDigits;base:NativeUint;DgtCnt:NativeInt):Uint64;
var
tmpDgt,i: NativeInt;
Begin
result := 0;
with dgt do
repeat
Begin
result := base*result+dgt[DgtCnt];
dec(DgtCnt)i:= dgtMaxIdx;
repeat
until (DgtCnt< 0);
tmpDgt := dgtDgts[i];
result *= base;
dec(i);
result +=tmpDgt;
until (i< 0);
end;
end;
 
procedure IncInBaseDigits(var dgt:tDigits;base:NativeInt);
function CntPrimeInBases(n:Uint64;max:Int32):Uint32;
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
Digits :tdigits;
pr : Uint64;
base,dgtCnt: Uint32;
begin
result := 0;
IncInBaseDigits(Digits,MAXBASE);
Base := getDgtsInMAXBASEandMaxDigit(n,Digits)+1;
base := Digits.dgtMaxDgtVal+1;
IF Digits[0] = 0 then
//divisible by every base
IF Digits.dgtDgts[0] = 0 then
EXIT;
ifIF base < MinBaseMINBASE then base := MINBASE;
base := MinBase;
// if (MAXBASE - Base) <= (max-result) then BREAK;
max := (max+Base-MAXBASE);
if (max>=0) then
EXIT;
for base := base TO MAXBASE do
dgtCnt := MAXDIGITCOUNT-1;
while (dgtCnt>0) AND (Digits[dgtCnt]= 0) do
dec(dgtCnt);
result := Ord(boolprimes[n]);
for base := base TO MAXBASE-1 do
begin
pr := CnvtoBaseCnvDgtAsInBase(Digits,base,MaxDgtPos);
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;
Line 815 ⟶ 1,202:
For i := MinLmt to MaxLmt do
Begin
baseCnt := CntPrimeInBases(idgt,max);
if baseCnt = 0 then
continue;
Line 840 ⟶ 1,227:
function Out_String(n:Uint64;var s: AnsiString):Uint32;
//out-sourced for debugging purpose
const
CharOfBase= '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
var
dgt:tDigits;
sl : string[815];
base,i: Int32;
Begin
result := 0;
CnvtoBASE(dgt,n,MaxBase);
base:= getDgtsInMAXBASEandMaxDigit(n,dgt)+1;
sl := '';
with dgt do
i := MaxDgtPos;
begin
while (i>=0)do
base:= dgtMaxDgtVal+1;
Begin
IF base < MINBASE then
sl += CharOfBase[dgt[i]+1];
base := MINBASE;
dec(i);
i := dgtMaxIdx;
while (i>=0)do
Begin
sl += CharOfBase[dgtDgts[i]+1];
dec(i);
end;
s := sl+' -> [';
end;
s := sl+' -> [';
 
For base := base to MAXBASE do
if boolprimes[CnvtoBaseCnvDgtAsInBase(dgt,base,MaxDgtPos)] then
begin
inc(result);
Line 887 ⟶ 1,277:
 
var
dgt:tDigits;
T0 : Int64;
lmt,minLmti : UInt32NativeInt;
ilmt,minLmt : Uint32UInt64;
begin
T0 := GetTickCount64;
Line 896 ⟶ 1,287:
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.</langsyntaxhighlight>
{{out}}
<pre>
 
//at home 2200G 16GB Linux
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 54.003986 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]
Line 938 ⟶ 1,359:
441431 -> [5,8,9,11,12,14,16,17,19,21,22,23,26,28,30,31,32,33]
 
Converting 2415.313507 s// 24.3s before
real 0m29,389s
######################
TIO.RUN// extreme volatile timings for sieving primes
Maxbase = 62 maxcharacters = 5
max prime limit 916132831
Prime sieving 14.576 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]
 
real 0m20,566s</pre>
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]
 
=={{header|Perl}}==
3 character strings which are prime in count bases = 33
{{trans|Raku}}
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]
{{libheader|ntheory}}
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]
<syntaxhighlight lang="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);
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]
 
my $chars = 5;
5 character strings which are prime in count bases = 30
my $upto = fromdigits( '1' . 'Z' x $chars, 36);
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]
my @primes = @{primes( $upto )};
 
for my $base (2..36) {
Converting 19.044 s
my $n = todigitstring($base-1, $base) x $chars;
Real time: 33.929 s User time: 24.091 s Sys. time: 9.093 s CPU share: 97.80 %
my $threshold = fromdigits($n, $base);
//at home real 0m12,614s user 0m12,336s sys 0m0,238s
my $i = firstidx { $_ > $threshold } @primes;
</pre>
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 ''
}</syntaxhighlight>
{{out}}
<pre>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</pre>
 
=={{header|Phix}}==
Originally translated from Rust, but changed to a much fuller range of digits, as per talk page.
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">maxbase</span><span style="color: #0000FF;">=</span><span style="color: #000000;">36</span> <span style="color: #000080;font-style:italic;">-- or 62</span>
Line 1,047 ⟶ 1,494:
<span style="color: #000000;">max_prime_bases</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxbase</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,101 ⟶ 1,548:
 
''All your base are belong to us. You have no chance to survive make your prime.''
<syntaxhighlight lang="raku" perl6line>use Math::Primesieve;
my $sieve = Math::Primesieve.new;
 
Line 1,123 ⟶ 1,570:
.say for %prime-base.grep( +*.value.elems == $e ).grep(*.key.chars == $m).sort: *.key;
say '';
}</langsyntaxhighlight>
 
{{out}}
Line 1,147 ⟶ 1,594:
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.
 
<syntaxhighlight lang="raku" perl6line>use Math::Primesieve;
use Base::Any;
 
Line 1,170 ⟶ 1,617:
.say for %prime-base.grep( +*.value.elems == $e ).grep(*.key.chars == $m).sort: *.key;
say '';
}</langsyntaxhighlight>
{{out|Yields}}
<pre>1 character strings that are prime in maximum bases: 60
Line 1,187 ⟶ 1,634:
 
=={{header|REXX}}==
<langsyntaxhighlight 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.*/
Line 1,195 ⟶ 1,642:
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; LenthLength too big? Skip.*/
if L==1 then $.L.n= b $.L.n /*Length = unity? Prepend the base.*/
else $.L.n= $.L.n b /* " ¬= " Append " " */
Line 1,208 ⟶ 1,655:
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 maxesmaximums. */
if y==cnt then say n '──►' strip($.w.n) /*display ───a─── maximum. */
end /*n*/
end /*w*/
Line 1,221 ⟶ 1,668:
end /*k*/; return z || substr(@, x+1, 1)
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
#= 5; ssq.#= @.# ** 2 /*number of primes so far; prime 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 divisibleis ÷ by 5? (right dig).*/
if j//3==0 then iterate; if j// 37==0 then iterate /*" " " " " 3?; ÷ by 7? */
do k=5 while sq.k<=j if j// 7==0 then iterate /*" " " 7? [↓] divide by the known odd primes.*/
doif j//@.k=5=0 whilethen iterate s.k<=j /*Is J ÷ X? Then not /*prime. [↓] 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; ssq.#= j*j /*bump # of Ps; assign next P; P squaresquared.*/
end /*j*/; return</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 1,259 ⟶ 1,705:
=={{header|Rust}}==
{{trans|Julia}}
<langsyntaxhighlight lang="rust">// [dependencies]
// primal = "0.3"
 
Line 1,310 ⟶ 1,756:
max_prime_bases(n, 36);
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,335 ⟶ 1,781:
441431 => [5, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 23, 26, 28, 30, 31, 32, 33]
 
</pre>
 
===Up to base 62===
{{trans|C++}}
<syntaxhighlight 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());
}
}</syntaxhighlight>
 
{{out}}
CPU: Intel Core i5-4570 3.2GHz.
Maximum base 36, maximum length 6:
<pre>
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
</pre>
 
Maximum base 62, maximum length 5:
<pre>
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
</pre>
 
=={{header|Sidef}}==
{{trans|Julia}}
<syntaxhighlight 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)
}</syntaxhighlight>
{{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>
 
Line 1,341 ⟶ 2,009:
{{libheader|Wren-fmt}}
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.
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int, Nums
var maxDepth = 5
Line 1,397 ⟶ 2,065:
printResults.call()
System.print()
}</langsyntaxhighlight>
 
{{out}}
Jjuanhdez
2,122

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/313413...361283"