Multi-base primes: Difference between revisions
Added FreeBASIC
m (C++ performance improvement) |
(Added FreeBASIC) |
||
| (16 intermediate revisions by 8 users not shown) | |||
Line 1:
{{
Prime numbers are prime no matter what base they are represented in.
Line 45:
=={{header|C++}}==
{{libheader|Primesieve}}
Originally translated from [[#Wren|Wren]] with ideas borrowed from other solutions.
The maximum base and number of characters can be specified as command line arguments.
<
#include <cmath>
#include <cstdint>
Line 55 ⟶ 56:
#include <string>
#include <vector>
#include <primesieve.hpp>
public:
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 =
sieve[prime >>
}
}
Line 98:
bool increment(std::vector<unsigned int>& digits, unsigned int max_base) {
for (auto i = digits.rbegin(); i != digits.rend(); ++i) {
++*i;
return true;
}
*i = 0;
}
}
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
Line 134:
for (auto d : digits)
n = n * b + d;
if (sieve
bases.push_back(b);
}
Line 173:
multi_base_primes(max_base, max_length);
return EXIT_SUCCESS;
}</
{{out}}
Maximum base 36 and maximum length 6. This takes 0.
<pre>
1-character strings which are prime in most bases: 34
Line 201:
</pre>
Maximum base 62 and maximum length 5. This takes 0.
<pre>
1-character strings which are prime in most bases: 60
Line 224:
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<
// Multi-base primes. Nigel Galloway: July 4th., 2021
let digits="0123456789abcdefghijklmnopqrstuvwxyz"
Line 232:
i|>Seq.iter(fun(n,g)->printf " %s->" (n|>List.map(fun n->digits.[n])|>Array.ofList|>System.String)
g|>Seq.iter(fun(g,_)->printf "%d " g); printfn ""); printfn "")
</syntaxhighlight>
{{out}}
<pre>
Line 252:
=={{header|Factor}}==
{{works with|Factor|0.99 2021-06-02}}
<
math.functions math.parser math.primes math.ranges present
sequences ;
Line 272:
[ dup (bases) filter "%d => %[%d, %]\n" printf ] each ;
4 [1,b] [ multibase. nl ] each</
{{out}}
<pre>
Line 290:
5347 => { 8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36 }
</pre>
=={{header|FreeBASIC}}==
{{trans|Phix}}
<syntaxhighlight lang="vbnet">Const maxBase = 36 ' o 62
Function isPrime(Byval ValorEval As Integer) As Boolean
If ValorEval < 2 Then Return False
If ValorEval Mod 2 = 0 Then Return ValorEval = 2
If ValorEval Mod 3 = 0 Then Return ValorEval = 3
Dim d As Integer = 5
While d * d <= ValorEval
If ValorEval Mod d = 0 Then Return False Else d += 2
Wend
Return True
End Function
Function maxval(arr() As Integer) As Integer
Dim As Integer max_value = arr(0)
For i As Integer = 1 To Ubound(arr)
If arr(i) > max_value Then max_value = arr(i)
Next
Return max_value
End Function
Function join(arr() As Integer, delimiter As String) As String
Dim As String result = ""
For i As Integer = 0 To Ubound(arr)
result &= Str(arr(i))
If i < Ubound(arr) Then result &= delimiter
Next
Return result
End Function
Function evalPoly(x As Integer, p() As Integer) As Integer
Dim result As Integer = 0
For y As Integer = 0 To Ubound(p)
result = result * x + p(y)
Next
Return result
End Function
Function stringify(digits() As Integer) As String
Dim res As String
For i As Integer = 0 To Ubound(digits)
Dim di As Integer = digits(i)
res &= Chr(Iif(di <= 9, di + Asc("0"), Iif(di < 36, di + Asc("A") - 10, di + Asc("a") - 36)))
Next
Return res
End Function
Sub maxPrimeVases(ndig As Integer, maxVase As Integer)
Dim As Double t0 = Timer
Dim As String maxPrimeBases()
Dim As Integer digits(ndig - 1)
Dim As Integer maxlen = 0
Dim As Integer limit = 10 ^ ndig
Dim As Integer maxDigit = maxBase
If ndig > 1 Then digits(0) = 1
Do
For i As Integer = Ubound(digits) To 0 Step -1
Dim As Integer di = digits(i) + 1
If di < maxDigit Then
digits(i) = di
Exit For
Else
digits(i) = 0
End If
Next
Dim As Integer minBase = maxval(digits()) + 1
Dim As Integer maxPoss = maxBase - minBase + 1
If minBase = 1 Then Exit Do
Dim As Integer bases()
For base_ As Integer = minBase To maxBase
If isPrime(evalPoly(base_, digits())) Then
Redim Preserve bases(Ubound(bases) + 1)
bases(Ubound(bases)) = base_
Else
maxPoss -= 1
If maxPoss < maxlen Then Exit For
End If
Next
Dim As Integer l = Ubound(bases) + 1
If l > maxlen Then
maxlen = l
maxDigit = maxBase - maxlen
Redim maxPrimeBases(0)
End If
If l = maxlen Then
Redim Preserve maxPrimeBases(Ubound(maxPrimeBases) + 1)
maxPrimeBases(Ubound(maxPrimeBases)) = Chr(10) & stringify(digits()) & " => " & join(bases(), ", ")
End If
Loop
Print Using "# character strings which are prime in most bases: ## (#.##s):"; ndig; maxlen; Timer - t0;
For i As Integer = 0 To Ubound(maxPrimeBases)
Print maxPrimeBases(i);
Next
Print Chr(10)
End Sub
For n As Integer = 1 To Iif(maxBase > 36, 4, 6)
maxPrimeVases(n, maxBase)
Next n
Sleep</syntaxhighlight>
{{out}}
<pre>1 character strings which are prime in most bases: 34 (0.00s):
2 => 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36
2 character strings which are prime in most bases: 18 (0.00s):
21 => 3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36
3 character strings which are prime in most bases: 18 (0.01s):
131 => 4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34
551 => 6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36
737 => 8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36
4 character strings which are prime in most bases: 19 (0.08s):
1727 => 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36
5347 => 8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36
5 character strings which are prime in most bases: 18 (4.31s):
30271 => 8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36
6 character strings which are prime in most bases: 18 (238.32s):
441431 => 5, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 23, 26, 28, 30, 31, 32, 33</pre>
If we set maxBase to 62:
<pre>1 character strings which are prime in most bases: 60 (0.00s):
2 => 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62
2 character strings which are prime in most bases: 31 (0.00s):
65 => 7, 8, 9, 11, 13, 14, 16, 17, 18, 21, 22, 24, 27, 28, 29, 31, 32, 37, 38, 39, 41, 42, 43, 44, 46, 48, 51, 52, 57, 58, 59
3 character strings which are prime in most bases: 33 (0.03s):
1L1 => 22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 51, 52, 53, 54, 57, 58, 59, 60, 61, 62
B9B => 13, 14, 15, 16, 17, 19, 20, 21, 23, 24, 26, 27, 28, 30, 31, 34, 36, 39, 40, 42, 45, 47, 49, 50, 52, 53, 54, 57, 58, 59, 60, 61, 62
4 character strings which are prime in most bases: 32 (2.04s):
1727 => 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36, 37, 38, 39, 41, 45, 46, 48, 50, 51, 57, 58, 60, 61
417B => 12, 13, 15, 16, 17, 18, 19, 21, 23, 25, 28, 30, 32, 34, 35, 37, 38, 39, 41, 45, 48, 49, 50, 51, 52, 54, 56, 57, 58, 59, 61, 62</pre>
=={{header|Go}}==
Line 295 ⟶ 432:
{{libheader|Go-rcu}}
This takes about 1.2 seconds and 31.3 seconds to process up to 5 and 6 character strings, respectively.
<
import (
Line 391 ⟶ 528:
fmt.Println()
}
}</
{{out}}
Line 436 ⟶ 573:
5 character strings which are prime in most bases: 30
50161 -> [7 8 9 13 17 18 19 20 25 28 29 30 31 33 35 36 38 39 41 42 43 44 47 48 52 55 56 59 60 62]
</pre>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public final class MultibasePrimes {
public static void main(String[] aArgs) {
final int maxBase = 36;
final int maxLength = 5;
fillPrimes(maxBase, maxLength);
multibasePrimes(maxBase, maxLength);
}
private static void multibasePrimes(int aMaxBase, int aMaxLength) {
for ( int length = 1; length <= aMaxLength; length++ ) {
int maxBasesCount = 0;
List<Tuple> maxStrings = new ArrayList<Tuple>();
List<Integer> digits = new ArrayList<Integer>(Collections.nCopies(length, 0));
digits.set(0, 1);
List<Integer> bases = new ArrayList<Integer>();
do {
final int maxDigit = digits.stream().max(Integer::compare).get();
final int minBase = Math.max(2, maxDigit + 1);
if ( maxBasesCount > aMaxBase - minBase + 1 ) {
continue;
}
bases.clear();
for ( int base = minBase; base <= aMaxBase; base++ ) {
if ( aMaxBase - base + 1 + bases.size() < maxBasesCount ) {
break;
}
int number = 0;
for ( int digit : digits ) {
number = number * base + digit;
}
if ( primes[number] ) {
bases.add(base);
}
}
if ( bases.size() > maxBasesCount ) {
maxBasesCount = bases.size();
maxStrings.clear();
}
if ( bases.size() == maxBasesCount ) {
maxStrings.add( new Tuple( new ArrayList<Integer>(digits), new ArrayList<Integer>(bases) ) );
}
} while ( increment(digits, aMaxBase) );
System.out.println(length + "-character strings which are prime in the most bases: " + maxBasesCount);
for ( Tuple tuple : maxStrings ) {
System.out.println(numberBase(tuple.first) + " -> " + tuple.second);
}
System.out.println();
}
}
private static boolean increment(List<Integer> aDigits, int aMaxBase) {
for ( int i = aDigits.size() - 1; i >= 0; i-- ) {
if ( aDigits.get(i) + 1 != aMaxBase ) {
aDigits.set(i, aDigits.get(i) + 1);
return true;
}
aDigits.set(i, 0);
}
return false;
}
private static String numberBase(List<Integer> aList) {
final String digits = "0123456789abcdefghijklmnopqrstuvwxyz";
StringBuilder result = new StringBuilder();
for ( int number : aList ) {
result.append(digits.charAt(number));
}
return result.toString();
}
private static void fillPrimes(int aMaxBase, int aMaxLength) {
final int limit = (int) Math.pow(aMaxBase, aMaxLength);
primes = new boolean[limit + 1];
Arrays.fill(primes, true);
primes[0] = false;
primes[1] = false;
for ( int i = 2; i < Math.sqrt(limit); i++ ) {
if ( primes[i] ) {
int j = i * i;
while ( j <= limit ) {
primes[j] = false;
j += i;
}
}
}
}
private static class Tuple {
public Tuple(List<Integer> aFirst, List<Integer> aSecond) {
first = aFirst; second = aSecond;
}
private List<Integer> first, second;
}
private static boolean[] primes;
}
</syntaxhighlight>
{{ out }}
<pre>
1-character strings which are prime in the most bases: 34
2 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36]
2-character strings which are prime in the most bases: 18
21 -> [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36]
3-character strings which are prime in the most bases: 18
131 -> [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34]
551 -> [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36]
737 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36]
4-character strings which are prime in the most bases: 19
1727 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36]
5347 -> [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36]
5-character strings which are prime in the most bases: 18
30271 -> [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36]
</pre>
=={{header|Julia}}==
<
function maxprimebases(ndig, maxbase)
Line 467 ⟶ 739:
maxprimebases(n, 36)
end
</
<pre>
The maximum number of prime valued bases for base 10 numeric strings of length 1 is 34. The base 10 value list of this is:
Line 493 ⟶ 765:
=== Up to base 62 ===
<
function maxprimebases(ndig, maxbase)
Line 527 ⟶ 799:
maxprimebases(n, 62)
end
</
<pre>
The maximum number of prime valued bases for base up to 36 numeric strings of length 1 is 34. The value list of this is:
Line 564 ⟶ 836:
50161 => [7, 8, 9, 13, 17, 18, 19, 20, 25, 28, 29, 30, 31, 33, 35, 36, 38, 39, 41, 42, 43, 44, 47, 48, 52, 55, 56, 59, 60, 62]
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[OtherBasePrimes, OtherBasePrimesPower]
OtherBasePrimes[n_Integer] := Module[{digs, minbase, bases},
digs = IntegerDigits[n];
minbase = Max[digs] + 1;
bases = Range[minbase, 36];
Pick[bases, PrimeQ[FromDigits[digs, #] & /@ bases], True]
]
OtherBasePrimesPower[p_] := Module[{min, max, out, maxlen},
min = 10^p;
max = 10^(p + 1) - 1;
out = {#, OtherBasePrimes[#]} & /@ Range[min, max];
maxlen = Max[Length /@ out[[All, 2]]];
Select[out, Last /* Length /* EqualTo[maxlen]]
]
OtherBasePrimesPower[0] // Column
OtherBasePrimesPower[1] // Column
OtherBasePrimesPower[2] // Column
OtherBasePrimesPower[3] // Column
OtherBasePrimesPower[4] // Column
OtherBasePrimesPower[5] // Column</syntaxhighlight>
{{out}}
<pre>{2,{3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36}}
{21,{3,5,6,8,9,11,14,15,18,20,21,23,26,29,30,33,35,36}}
{131,{4,5,7,8,9,10,12,14,15,18,19,20,23,25,27,29,30,34}}
{551,{6,7,11,13,14,15,16,17,19,21,22,24,25,26,30,32,35,36}}
{737,{8,9,11,12,13,15,16,17,19,22,23,24,25,26,29,30,31,36}}
{1727,{8,9,11,12,13,15,16,17,19,20,22,23,24,26,27,29,31,33,36}}
{5347,{8,9,10,11,12,13,16,18,19,22,24,25,26,30,31,32,33,34,36}}
{30271,{8,10,12,13,16,17,18,20,21,23,24,25,31,32,33,34,35,36}}
{441431,{5,8,9,11,12,14,16,17,19,21,22,23,26,28,30,31,32,33}}</pre>
=={{header|Nim}}==
Line 570 ⟶ 879:
<
const
Line 637 ⟶ 946:
for m in ctx.maxStrings:
echo m.indices.mapIt(Digits[it]).join(), " → ", m[1].join(" ")
echo()</
{{out}}
Line 664 ⟶ 973:
First counting the bases that convert a MAXBASE string of n into a prime number.<BR>
Afterwards only checking the maxcount for the used bases.<BR>
<
{$IFDEF FPC}
{$MODE DELPHI}
Line 994 ⟶ 1,303:
writeln(' Converting ',(GetTickCount64-T0)/1000:6:3,' s');
{$IFDEF WINDOWS} readln; {$ENDIF}
end.</
{{out}}
<pre>
Line 1,053 ⟶ 1,362:
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}}==
Originally translated from Rust, but changed to a much fuller range of digits, as per talk page.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">maxbase</span><span style="color: #0000FF;">=</span><span style="color: #000000;">36</span> <span style="color: #000080;font-style:italic;">-- or 62</span>
Line 1,134 ⟶ 1,494:
<span style="color: #000000;">max_prime_bases</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">maxbase</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 1,188 ⟶ 1,548:
''All your base are belong to us. You have no chance to survive make your prime.''
<syntaxhighlight lang="raku"
my $sieve = Math::Primesieve.new;
Line 1,210 ⟶ 1,570:
.say for %prime-base.grep( +*.value.elems == $e ).grep(*.key.chars == $m).sort: *.key;
say '';
}</
{{out}}
Line 1,234 ⟶ 1,594:
You can't really assume that the maximum string will be all numeric digits. It is just an accident that they happen to work out that way with a upper limit of base 36. If we do the same filtering using a maximum of base 62, we end up with several that contain alphabetics.
<syntaxhighlight lang="raku"
use Base::Any;
Line 1,257 ⟶ 1,617:
.say for %prime-base.grep( +*.value.elems == $e ).grep(*.key.chars == $m).sort: *.key;
say '';
}</
{{out|Yields}}
<pre>1 character strings that are prime in maximum bases: 60
Line 1,274 ⟶ 1,634:
=={{header|REXX}}==
<
parse arg widths . /*obtain optional argument from the CL.*/
if widths=='' | widths=="," then widths= 5 /*Not specified? Then use the default.*/
Line 1,282 ⟶ 1,642:
do j=1 for # /*only use primes that are within range*/
do b=36 by -1 for 35; n= base(@.j, b) /*use different bases for each prime. */
L= length(n); if L>widths then iterate /*obtain length;
if L==1 then $.L.n= b $.L.n /*Length = unity? Prepend the base.*/
else $.L.n= $.L.n b /* " ¬= " Append " " */
Line 1,317 ⟶ 1,677:
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= # + 1; @.#= j; sq.#= j*j /*bump # Ps; assign next P; P squared.*/
end /*j*/; return</
{{out|output|text= when using the default input:}}
<pre>
Line 1,345 ⟶ 1,705:
=={{header|Rust}}==
{{trans|Julia}}
<
// primal = "0.3"
Line 1,396 ⟶ 1,756:
max_prime_bases(n, 36);
}
}</
{{out}}
Line 1,421 ⟶ 1,781:
441431 => [5, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 23, 26, 28, 30, 31, 32, 33]
</pre>
===Up to base 62===
{{trans|C++}}
<syntaxhighlight lang="rust">// [dependencies]
// primal = "0.3"
fn to_string(digits: &[usize]) -> String {
const DIGITS: [char; 62] = [
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R',
'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
];
let mut str = String::new();
for d in digits {
str.push(DIGITS[*d]);
}
str
}
fn increment(digits: &mut [usize], base: usize) -> bool {
for d in digits.iter_mut().rev() {
if *d + 1 != base {
*d += 1;
return true;
}
*d = 0;
}
false
}
fn multi_base_primes(max_base: usize, max_length: usize) {
let sieve = primal::Sieve::new(max_base.pow(max_length as u32));
for length in 1..=max_length {
let mut most_bases = 0;
let mut max_strings = Vec::new();
let mut digits = vec![0; length];
digits[0] = 1;
let mut bases = Vec::new();
loop {
let mut min_base = 2;
if let Some(max) = digits.iter().max() {
min_base = std::cmp::max(min_base, max + 1);
}
if most_bases <= max_base - min_base + 1 {
bases.clear();
for b in min_base..=max_base {
if max_base - b + 1 + bases.len() < most_bases {
break;
}
let mut n = 0;
for d in &digits {
n = n * b + d;
}
if sieve.is_prime(n) {
bases.push(b);
}
}
if bases.len() > most_bases {
most_bases = bases.len();
max_strings.clear();
}
if bases.len() == most_bases {
max_strings.push((digits.clone(), bases.clone()));
}
}
if !increment(&mut digits, max_base) {
break;
}
}
println!(
"{}-character strings which are prime in most bases: {}",
length, most_bases
);
for (digits, bases) in max_strings {
println!("{} -> {:?}", to_string(&digits), bases);
}
println!();
}
}
fn main() {
let args: Vec<String> = std::env::args().collect();
let mut max_base = 36;
let mut max_length = 4;
let mut arg = 0;
while arg + 1 < args.len() {
if args[arg] == "-max_base" {
arg += 1;
match args[arg].parse::<usize>() {
Ok(n) => max_base = n,
Err(error) => {
eprintln!("{}", error);
return;
}
}
} else if args[arg] == "-max_length" {
arg += 1;
match args[arg].parse::<usize>() {
Ok(n) => max_length = n,
Err(error) => {
eprintln!("{}", error);
return;
}
}
}
arg += 1;
}
if max_base > 62 {
eprintln!("Maximum base cannot be greater than 62.");
} else if max_base < 2 {
eprintln!("Maximum base cannot be less than 2.");
} else {
use std::time::Instant;
let now = Instant::now();
multi_base_primes(max_base, max_length);
let time = now.elapsed();
println!("elapsed time: {} milliseconds", time.as_millis());
}
}</syntaxhighlight>
{{out}}
CPU: Intel Core i5-4570 3.2GHz.
Maximum base 36, maximum length 6:
<pre>
1-character strings which are prime in most bases: 34
2 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36]
2-character strings which are prime in most bases: 18
21 -> [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36]
3-character strings which are prime in most bases: 18
131 -> [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34]
551 -> [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36]
737 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36]
4-character strings which are prime in most bases: 19
1727 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36]
5347 -> [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36]
5-character strings which are prime in most bases: 18
30271 -> [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36]
6-character strings which are prime in most bases: 18
441431 -> [5, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 23, 26, 28, 30, 31, 32, 33]
elapsed time: 15139 milliseconds
</pre>
Maximum base 62, maximum length 5:
<pre>
1-character strings which are prime in most bases: 60
2 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62]
2-character strings which are prime in most bases: 31
65 -> [7, 8, 9, 11, 13, 14, 16, 17, 18, 21, 22, 24, 27, 28, 29, 31, 32, 37, 38, 39, 41, 42, 43, 44, 46, 48, 51, 52, 57, 58, 59]
3-character strings which are prime in most bases: 33
1l1 -> [22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 51, 52, 53, 54, 57, 58, 59, 60, 61, 62]
b9b -> [13, 14, 15, 16, 17, 19, 20, 21, 23, 24, 26, 27, 28, 30, 31, 34, 36, 39, 40, 42, 45, 47, 49, 50, 52, 53, 54, 57, 58, 59, 60, 61, 62]
4-character strings which are prime in most bases: 32
1727 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36, 37, 38, 39, 41, 45, 46, 48, 50, 51, 57, 58, 60, 61]
417b -> [12, 13, 15, 16, 17, 18, 19, 21, 23, 25, 28, 30, 32, 34, 35, 37, 38, 39, 41, 45, 48, 49, 50, 51, 52, 54, 56, 57, 58, 59, 61, 62]
5-character strings which are prime in most bases: 30
50161 -> [7, 8, 9, 13, 17, 18, 19, 20, 25, 28, 29, 30, 31, 33, 35, 36, 38, 39, 41, 42, 43, 44, 47, 48, 52, 55, 56, 59, 60, 62]
elapsed time: 9569 milliseconds
</pre>
=={{header|Sidef}}==
{{trans|Julia}}
<syntaxhighlight lang="ruby">func max_prime_bases(ndig, maxbase=36) {
var maxprimebases = [[]]
var nwithbases = [0]
var maxprime = (10**ndig - 1)
for p in (idiv(maxprime + 1, 10) .. maxprime) {
var dig = p.digits
var bases = (2..maxbase -> grep {|b| dig.all { _ < b } && dig.digits2num(b).is_prime })
if (bases.len > maxprimebases.first.len) {
maxprimebases = [bases]
nwithbases = [p]
}
elsif (bases.len == maxprimebases.first.len) {
maxprimebases << bases
nwithbases << p
}
}
var (alen, vlen) = (maxprimebases.first.len, maxprimebases.len)
say("\nThe maximum number of prime valued bases for base 10 numeric strings of length ",
ndig, " is #{alen}. The base 10 value list of ", vlen > 1 ? "these" : "this", " is:")
maxprimebases.each_kv {|k,v| say(nwithbases[k], " => ", v) }
}
for n in (1..5) {
max_prime_bases(n)
}</syntaxhighlight>
{{out}}
<pre>
The maximum number of prime valued bases for base 10 numeric strings of length 1 is 34. The base 10 value list of this is:
2 => [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36]
The maximum number of prime valued bases for base 10 numeric strings of length 2 is 18. The base 10 value list of this is:
21 => [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36]
The maximum number of prime valued bases for base 10 numeric strings of length 3 is 18. The base 10 value list of these is:
131 => [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34]
551 => [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36]
737 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36]
The maximum number of prime valued bases for base 10 numeric strings of length 4 is 19. The base 10 value list of these is:
1727 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36]
5347 => [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36]
The maximum number of prime valued bases for base 10 numeric strings of length 5 is 18. The base 10 value list of this is:
30271 => [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36]
</pre>
Line 1,427 ⟶ 2,009:
{{libheader|Wren-fmt}}
This takes about 1.6 seconds to process up to 4 character strings and 58 seconds for the extra credit which is not too bad for the Wren interpreter.
<
var maxDepth = 5
Line 1,483 ⟶ 2,065:
printResults.call()
System.print()
}</
{{out}}
| |||