Multi-base primes

Multi-base primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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++

Translation of: Wren

This takes 5 seconds to process up to 5 character strings and 156 seconds to process up to 6 characters (3.2GHz Intel Core i5). <lang cpp>#include <algorithm>

1. include <cmath>
2. include <cstdint>
3. include <iostream>
4. 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) {

   std::vector<unsigned int> bases;
   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);
   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]

Factor

Works with: Factor version 0.99 2021-06-02

<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 }

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)

Phix

with javascript_semantics 
function digs(integer n, ndig)
    sequence digits = repeat(0,ndig)
    for i=1 to length(digits) do
        digits[i] = remainder(n,10)
        n = floor(n/10)
    end for
    return digits
end function
 
function evalpoly(integer x, sequence p)
    integer result = 0
    for y=length(p) to 1 by -1 do
        result = result*x + p[y]
    end for
    return result
end function
 
procedure max_prime_bases(integer ndig, maxbase)
    atom t0 = time()
    sequence maxprimebases = {}
    integer maxlen = 0, limit = power(10,ndig)
    for n=limit/10 to limit-1 do
        sequence digits = digs(n,ndig), bases = {}
        for base=max(digits)+1 to maxbase do
            if is_prime(evalpoly(base,digits)) then
                bases &= base   
            end if
        end for
        integer l = length(bases)
        if l>maxlen then
            maxlen = l
            maxprimebases = {}
        end if
        if l=maxlen then
            maxprimebases &= {{n, bases}}
        end if
    end for
    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," %d => %V\n", maxprimebases[i])
    end for
    printf(1,"\n")
end procedure
 
for n=1 to iff(platform()=JS?5: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.3s):
 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 (4.9s):
 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 (1 minute and 59s):
 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 entry under pwa/p2js to avoid staring at a blank screen for ages

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]

Rust

Translation of: Julia

<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

Library: Wren-math

Library: Wren-fmt

This takes about 4.4 seconds to process up to 4 character strings and 170 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 bases = []
   var minBase = 2.max(Nums.max(indices) + 1)
   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]