Multi-base primes
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++
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). <lang cpp>#include <algorithm>
- include <cmath>
- include <cstdint>
- include <iostream>
- include <vector>
std::vector<bool> prime_sieve(uint64_t limit) {
std::vector<bool> sieve(limit, true); if (limit > 0) sieve[0] = false; if (limit > 1) sieve[1] = false; for (uint64_t i = 4; i < limit; i += 2) sieve[i] = false; for (uint64_t p = 3;; p += 2) { uint64_t q = p * p; if (q >= limit) break; if (sieve[p]) { uint64_t inc = 2 * p; for (; q < limit; q += inc) sieve[q] = false; } } return sieve;
}
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[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; std::string str; for (auto i : v) str += digits[i]; return str;
};
class multi_base_primes { public:
explicit multi_base_primes(unsigned int depth); void run();
private:
void process(const std::vector<unsigned int>& indices); void nested_for(std::vector<unsigned int>& indices, unsigned int level); static const unsigned int max_base = 36; unsigned int max_depth; std::vector<bool> sieve; unsigned int most_bases = 0; std::vector<std::pair<std::vector<unsigned int>, std::vector<unsigned int>>> max_strings;
};
multi_base_primes::multi_base_primes(unsigned int depth)
: max_depth(depth), sieve(prime_sieve(static_cast<uint64_t>(std::pow(max_base, depth)))) {}
void multi_base_primes::run() {
for (unsigned int depth = 1; depth <= max_depth; ++depth) { std::cout << depth << " character strings which are prime in most bases: "; max_strings.clear(); most_bases = 0; std::vector<unsigned int> indices(depth, 0); nested_for(indices, 0); 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'; }
}
void multi_base_primes::process(const std::vector<unsigned int>& indices) {
auto max = std::max_element(indices.begin(), indices.end()); unsigned int min_base = 2; if (max != indices.end()) min_base = std::max(min_base, *max + 1); if (most_bases > max_base - min_base) return; std::vector<unsigned int> bases; for (unsigned int b = min_base; b <= max_base; ++b) { uint64_t n = 0; for (auto i : indices) n = n * b + i; if (sieve[n]) bases.push_back(b); } if (bases.size() > most_bases) { most_bases = bases.size(); max_strings.clear(); } if (bases.size() == most_bases) max_strings.emplace_back(indices, bases);
}
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]; } }
}
int main() {
multi_base_primes mbp(6); mbp.run();
}</lang>
- Output:
1 character strings which are prime in most bases: 34 2 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] 2 character strings which are prime in most bases: 18 21 -> [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36] 3 character strings which are prime in most bases: 18 131 -> [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34] 551 -> [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36] 737 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36] 4 character strings which are prime in most bases: 19 1727 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36] 5347 -> [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36] 5 character strings which are prime in most bases: 18 30271 -> [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36] 6 character strings which are prime in most bases: 18 441431 -> [5, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 23, 26, 28, 30, 31, 32, 33]
F#
This task uses Extensible Prime Generator (F#) <lang fsharp> // Multi-base primes. Nigel Galloway: July 4th., 2021 let digits="0123456789abcdefghijklmnopqrstuvwxyz" let fG n g=let rec fN g=function i when i<n->i::g |i->fN((i%n)::g)(i/n) in primes32()|>Seq.skipWhile((>)(pown n (g-1)))|>Seq.takeWhile((>)(pown n g))|>Seq.map(fun g->(n,fN [] g)) let fN g={2..36}|>Seq.collect(fun n->fG n g)|>Seq.groupBy snd|>Seq.groupBy(snd>>(Seq.length))|>Seq.maxBy fst {1..4}|>Seq.iter(fun g->let n,i=fN g in printfn "The following strings of length %d represent primes in the maximum number of bases(%d):" g n
i|>Seq.iter(fun(n,g)->printf " %s->" (n|>List.map(fun n->digits.[n])|>Array.ofList|>System.String) g|>Seq.iter(fun(g,_)->printf "%d " g); printfn ""); printfn "")
</lang>
- Output:
The following strings of length 1 represent primes in the maximum number of bases(34): 2->3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 The following strings of length 2 represent primes in the maximum number of bases(18): 21->3 5 6 8 9 11 14 15 18 20 21 23 26 29 30 33 35 36 The following strings of length 3 represent primes in the maximum number of bases(18): 131->4 5 7 8 9 10 12 14 15 18 19 20 23 25 27 29 30 34 551->6 7 11 13 14 15 16 17 19 21 22 24 25 26 30 32 35 36 737->8 9 11 12 13 15 16 17 19 22 23 24 25 26 29 30 31 36 The following strings of length 4 represent primes in the maximum number of bases(19): 1727->8 9 11 12 13 15 16 17 19 20 22 23 24 26 27 29 31 33 36 5347->8 9 10 11 12 13 16 18 19 22 24 25 26 30 31 32 33 34 36
Factor
<lang factor>USING: assocs assocs.extras formatting io kernel math math.functions math.parser math.primes math.ranges present sequences ;
- prime?* ( n -- ? ) [ prime? ] [ f ] if* ; inline
- (bases) ( n -- range quot )
present 2 36 [a,b] [ base> prime?* ] with ; inline
- <digits> ( n -- range ) [ 1 - ] keep [ 10^ ] bi@ [a,b) ;
- multibase ( n -- assoc )
<digits> [ (bases) count ] zip-with assoc-invert expand-keys-push-at >alist [ first ] supremum-by ;
- multibase. ( n -- )
dup multibase first2 [ "%d-digit numbers that are prime in the most bases: %d\n" printf ] dip [ dup (bases) filter "%d => %[%d, %]\n" printf ] each ;
4 [1,b] [ multibase. nl ] each</lang>
- Output:
1-digit numbers that are prime in the most bases: 34 2 => { 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36 } 2-digit numbers that are prime in the most bases: 18 21 => { 3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36 } 3-digit numbers that are prime in the most bases: 18 131 => { 4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34 } 551 => { 6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36 } 737 => { 8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36 } 4-digit numbers that are prime in the most bases: 19 1727 => { 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36 } 5347 => { 8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36 }
Go
This takes about 1.2 seconds and 31.3 seconds to process up to 5 and 6 character strings, respectively. <lang go>package main
import (
"fmt" "math" "rcu"
)
var maxDepth = 6 var c = rcu.PrimeSieve(int(math.Pow(36, float64(maxDepth))), true) var digits = "0123456789abcdefghijklmnopqrstuvwxyz" 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 37 - minBase < mostBases { return // can't affect results so return } var bases []int for b := minBase; b <= 36; 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, len(digits), 0) printResults() fmt.Println() }
}</lang>
- Output:
1 character strings which are prime in most bases: 34 2 -> [3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36] 2 character strings which are prime in most bases: 18 21 -> [3 5 6 8 9 11 14 15 18 20 21 23 26 29 30 33 35 36] 3 character strings which are prime in most bases: 18 131 -> [4 5 7 8 9 10 12 14 15 18 19 20 23 25 27 29 30 34] 551 -> [6 7 11 13 14 15 16 17 19 21 22 24 25 26 30 32 35 36] 737 -> [8 9 11 12 13 15 16 17 19 22 23 24 25 26 29 30 31 36] 4 character strings which are prime in most bases: 19 1727 -> [8 9 11 12 13 15 16 17 19 20 22 23 24 26 27 29 31 33 36] 5347 -> [8 9 10 11 12 13 16 18 19 22 24 25 26 30 31 32 33 34 36] 5 character strings which are prime in most bases: 18 30271 -> [8 10 12 13 16 17 18 20 21 23 24 25 31 32 33 34 35 36] 6 character strings which are prime in most bases: 18 441431 -> [5 8 9 11 12 14 16 17 19 21 22 23 26 28 30 31 32 33]
Julia
<lang julia>using Primes
function maxprimebases(ndig, maxbase)
maxprimebases = [Int[]] nwithbases = [0] maxprime = 10^(ndig) - 1 for p in div(maxprime + 1, 10):maxprime dig = digits(p) bases = [b for b in 2:maxbase if (isprime(evalpoly(b, dig)) && all(i -> i < b, dig))] if length(bases) > length(first(maxprimebases)) maxprimebases = [bases] nwithbases = [p] elseif length(bases) == length(first(maxprimebases)) push!(maxprimebases, bases) push!(nwithbases, p) end end alen, vlen = length(first(maxprimebases)), length(maxprimebases) println("\nThe maximum number of prime valued bases for base 10 numeric strings of length ", ndig, " is $alen. The base 10 value list of ", vlen > 1 ? "these" : "this", " is:") for i in eachindex(maxprimebases) println(nwithbases[i], " => ", maxprimebases[i]) end
end
@time for n in 1:6
maxprimebases(n, 36)
end
</lang>
- Output:
The maximum number of prime valued bases for base 10 numeric strings of length 1 is 34. The base 10 value list of this is: 2 => [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The maximum number of prime valued bases for base 10 numeric strings of length 2 is 18. The base 10 value list of this is: 21 => [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36] The maximum number of prime valued bases for base 10 numeric strings of length 3 is 18. The base 10 value list of these is: 131 => [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34] 551 => [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36] 737 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36] The maximum number of prime valued bases for base 10 numeric strings of length 4 is 19. The base 10 value list of these is: 1727 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36] 5347 => [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36] The maximum number of prime valued bases for base 10 numeric strings of length 5 is 18. The base 10 value list of this is: 30271 => [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36] The maximum number of prime valued bases for base 10 numeric strings of length 6 is 18. The base 10 value list of this is: 441431 => [5, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 23, 26, 28, 30, 31, 32, 33] 4.808196 seconds (8.58 M allocations: 357.983 MiB, 0.75% gc time)
Pascal
First counting the bases that convert a decimal string of n into a prime number.
Afterwards only checking the maxcount for the used bases.
Most time consuming is sieving for the primes.
<lang pascal>program DecStringIsPrimeInBase;
//base 10 numeric string
{$IFDEF FPC}
{$MODE DELPHI} {$OPTIMIZATION ON,ALL}
// {$R+,O+} {$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF} uses
sysutils;
const
MINBASE = 2; MAXBASE = 36;//10;//10 is minimum MAXDIGITCOUNT = 6;//9;// MAXFAC = 10*10*10*10*10*10;//10*10*10*10*10*10*10*10*10;//
type
tdigits = array [0..15] of byte; tChkLst = array of byte; tSol = array of Uint32;
//sieve primes see http://rosettacode.org/wiki/Sieve_of_Eratosthenes#alternative_using_wheel var
BoolPrimes: array of boolean; BaseCnvCount :tChkLst;
function BuildWheel(primeLimit:Int32):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:Int32); 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;
function getDecDigitsAndMaxDgt(n:Uint32;var dgt:tDigits):uint32; var
q,r,i: Uint32;
Begin
fillChar(dgt[0],SizeOf(dgt),#0); i := 0; result := 0; repeat q := n DIV 10; r := (n-q*10); n := q; dgt[i] := r; inc(i); if result < r then result := r; until n = 0;
end;
function CnvtoBase(const dgt:tDigits;base:Uint32):Uint32; var
i: Int32;
Begin
i := MAXDIGITCOUNT; while (dgt[i] = 0) AND (i>0) do dec(i);
result := 0; repeat result := base*result+dgt[i]; dec(i); until (i< 0);
end;
procedure ConvertToBases(n:Uint32); var
Digits :tdigits; base,minimalBase,Counter: Uint32;
begin
//base 10 Counter := Ord(boolprimes[n]); //minimalBase <= max. digit +1 minimalBase := getDecDigitsAndMaxDgt(n,Digits)+1; if minimalBase < MinBase then minimalBase := MinBase;
for base := minimalBase TO 9 do inc(counter,Ord(boolprimes[CnvtoBase(Digits,base)])); for base := 11 TO MAXBASE do inc(counter,Ord(boolprimes[CnvtoBase(Digits,base)]));
BaseCnvCount[n] := Counter;
end;
function GetMax(MinLmt,MaxLmt:Uint32):tSol; var
i,pc,max,Idx: Int32;
Begin
setlength(result,0); max :=-1; Idx:= 0; For i := MinLmt to MaxLmt do Begin pc := BaseCnvCount[i]; if pc= 0 then continue; if max<=pc then begin if max = pc 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[Idx-1] := i; max := pc; end; end; end;
end;
function Out_String(n:Uint32;var s: AnsiString):Uint32; var
dgt:tDigits; sl : string[8]; base,minimalbase: Uint32;
Begin
result := 0; minimalbase:= getDecDigitsAndMaxDgt(n,dgt)+1; str(n:7,sl); s := sl+' -> ['; For base := minimalbase to MAXBASE do if boolprimes[CnvtoBase(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
T0 : Int64; i,lmt,minLmt : Uint32;
begin
T0 := GetTickCount64; lmt := 0; //maxvalue of "99...99" in Maxbase for i := 1 to MAXDIGITCOUNT do lmt := (lmt*MAXBASE+9); writeln('max prime limit ',lmt); Sieve(lmt); Setlength(BaseCnvCount,MAXFAC);
write('Prime sieving ',(GetTickCount64-T0)/1000:6:3,' s'); T0 := GetTickCount64; For i := High(BaseCnvCount) downto 2 do ConvertToBases(i); writeln(' Converting ',(GetTickCount64-T0)/1000:6:3,' s'); writeln;
i := 1; minLmt := 1; repeat write(i:2,' character strings which are prime in count bases = '); Out_Sol(GetMax(minLmt,10*minLmt-1)); minLmt *= 10; inc(i); until minLmt >= MAXFAC; {$IFDEF WINDOWS} readln; {$ENDIF}
end.</lang>
- Output:
TIO.RUN // extreme volatile timings ala Prime sieving 7.7 s .. 4,7s Converting nearly stable max prime limit 559744029 Prime sieving 2.098 s Converting 0.368 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] Real time: 2.658 s User time: 2.295 s Sys. time: 0.319 s CPU share: 98.31 % //at home //Prime sieving 1.072 s Converting 0.181 s
Phix
Originally translated from Rust, but changed to a much fuller range of digits, as per talk page.
with javascript_semantics 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':'a'-10) 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?4:6) do max_prime_bases(n, 36) 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):
Raku
Up to 4 character strings finish fairly quickly. 5 character strings take a while.
All your base are belong to us. You have no chance to survive make your prime. <lang perl6>use Math::Primesieve; my $sieve = Math::Primesieve.new;
my %prime-base;
my $chars = 4; # for demonstration purposes. Change to 5 for the whole shmegegge.
my $threshold = ('1' ~ 'Z' x $chars).parse-base(36);
my @primes = $sieve.primes($threshold);
%prime-base.push: $_ for (2..36).map: -> $base {
$threshold = (($base - 1).base($base) x $chars).parse-base($base); @primes[^(@primes.first: * > $threshold, :k)].race.map: { .base($base) => $base }
}
%prime-base.=grep: +*.value.elems > 10;
for 1 .. $chars -> $m {
say "$m character strings that are prime in maximum bases: " ~ (my $e = ((%prime-base.grep( *.key.chars == $m )).max: +*.value.elems).value.elems); .say for %prime-base.grep( +*.value.elems == $e ).grep(*.key.chars == $m).sort: *.key; say ;
}</lang>
- Output:
1 character strings that are prime in maximum bases: 34 2 => [3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36] 2 character strings that are prime in maximum bases: 18 21 => [3 5 6 8 9 11 14 15 18 20 21 23 26 29 30 33 35 36] 3 character strings that are prime in maximum bases: 18 131 => [4 5 7 8 9 10 12 14 15 18 19 20 23 25 27 29 30 34] 551 => [6 7 11 13 14 15 16 17 19 21 22 24 25 26 30 32 35 36] 737 => [8 9 11 12 13 15 16 17 19 22 23 24 25 26 29 30 31 36] 4 character strings that are prime in maximum bases: 19 1727 => [8 9 11 12 13 15 16 17 19 20 22 23 24 26 27 29 31 33 36] 5347 => [8 9 10 11 12 13 16 18 19 22 24 25 26 30 31 32 33 34 36] 5 character strings that are prime in maximum bases: 18 30271 => [8 10 12 13 16 17 18 20 21 23 24 25 31 32 33 34 35 36]
REXXt
<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= 4 /*Not specified? Then use the default.*/ call genP /*build array of semaphores for primes.*/ name= 'one two three four five six seven eight' /*names for some low decimal numbers. */ $.=
do j=1 for # /*only use primes that are within range*/ do b=36 by -1 for 35; n= base(@.j, b) /*use different bases for each prime. */ L= length(n); if L>widths then iterate /*obtain length; Lenth too big? Skip.*/ if L==1 then $.L.n= b $.L.n /*Length = unity? Prepend the base.*/ else $.L.n= $.L.n b /* " ¬= " Append " " */ end /*b*/ end /*j*/ /*display info for each of the widths. */ do w=1 for widths; cnt= 0 /*show for each width: cnt,number,bases*/ bot= left(1, w, 0); top= left(9, w, 9) /*calculate range for DO. */ do n=bot to top; y= words($.w.n) /*find the sets of numbers for a width.*/ if y>cnt then do; mxn=n; cnt= max(cnt, y); end /*found a max? Remember it*/ end /*n*/ say; say say center(' 'word(name, w)'─character numbers that are prime in the most bases: ',, 101, "─") do n=bot to top; y= words($.w.n) /*search again for maxes. */ 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; s.#= @.# **2 /*number of primes so far; prime². */ do j=@.#+2 by 2 to 36*10**widths /*find odd primes from here on. */ parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/ if j// 3==0 then iterate /*" " " 3? */ if j// 7==0 then iterate /*" " " 7? */ do k=5 while s.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; s.#= j*j /*bump # of Ps; assign next P; P square*/ end /*j*/; return</lang>
- output when using the default input:
────────────────────── one─character numbers that are prime in the most 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: ────────────────────── 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: ───────────────────── 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: ────────────────────── 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
Rust
<lang rust>// [dependencies] // primal = "0.3"
fn digits(mut n: u32, dig: &mut [u32]) {
for i in 0..dig.len() { dig[i] = n % 10; n /= 10; }
}
fn evalpoly(x: u64, p: &[u32]) -> u64 {
let mut result = 0; for y in p.iter().rev() { result *= x; result += *y as u64; } result
}
fn max_prime_bases(ndig: u32, maxbase: u32) {
let mut maxlen = 0; let mut maxprimebases = Vec::new(); let limit = 10u32.pow(ndig); let mut dig = vec![0; ndig as usize]; for n in limit / 10..limit { digits(n, &mut dig); let bases: Vec<u32> = (2..=maxbase) .filter(|&x| dig.iter().all(|&y| y < x) && primal::is_prime(evalpoly(x as u64, &dig))) .collect(); if bases.len() > maxlen { maxlen = bases.len(); maxprimebases.clear(); } if bases.len() == maxlen { maxprimebases.push((n, bases)); } } println!( "{} character numeric strings that are prime in maximum bases: {}", ndig, maxlen ); for (n, bases) in maxprimebases { println!("{} => {:?}", n, bases); } println!();
}
fn main() {
for n in 1..=6 { max_prime_bases(n, 36); }
}</lang>
- Output:
1 character numeric strings that are prime in maximum bases: 34 2 => [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] 2 character numeric strings that are prime in maximum bases: 18 21 => [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36] 3 character numeric strings that are prime in maximum bases: 18 131 => [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34] 551 => [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36] 737 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36] 4 character numeric strings that are prime in maximum bases: 19 1727 => [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36] 5347 => [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36] 5 character numeric strings that are prime in maximum bases: 18 30271 => [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36] 6 character numeric strings that are prime in maximum bases: 18 441431 => [5, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 23, 26, 28, 30, 31, 32, 33]
Wren
This takes about 1.6 seconds to process up to 4 character strings and 58 seconds for the extra credit which is not too bad for the Wren interpreter. <lang ecmascript>import "/math" for Int, Nums import "/fmt" for Conv
var maxDepth = 5 var c = Int.primeSieve(36.pow(maxDepth), false) var digits = Conv.digits // all digits up to base 36 var maxStrings = [] var mostBases = -1
var process = Fn.new { |indices|
var minBase = 2.max(Nums.max(indices) + 1) if (37 - minBase < mostBases) return // can't affect results so return var bases = [] for (b in minBase..36) { 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, digits.count, 0) printResults.call() System.print()
}</lang>
- Output:
1 character strings which are prime in most bases: 34 2 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] 2 character strings which are prime in most bases: 18 21 -> [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36] 3 character strings which are prime in most bases: 18 131 -> [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34] 551 -> [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36] 737 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36] 4 character strings which are prime in most bases: 19 1727 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36] 5347 -> [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36] 5 character strings which are prime in most bases: 18 30271 -> [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36]