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