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.

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 }

Raku

Up to 4 character strings finish fairly quickly. 5 character strings take a while. <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]

Wren

Library: Wren-math

Library: Wren-fmt

Brute force approach but very slow - about 108 seconds to process up to 4 character strings. <lang ecmascript>import "/math" for Int import "/fmt" for Conv

var c = Int.primeSieve(36.pow(4), false) var digits = Conv.digits // all digits up to base 36 var maxStrings = [] var mostBases = -1

var process = Fn.new { |s|

   var bases = []
   for (b in 2..36) {
       var valid = digits[0...b]
       if (s.all { |d| valid.contains(d) }) {
           var i = Conv.atoi(s, b)
           if (!c[i]) bases.add(b)
       }
   }
   var count = bases.count
   if (count > mostBases) {
       mostBases = count
       maxStrings = s, bases
   } else if (count == mostBases) {
       maxStrings.add([s, bases])
   }

}

var printResults = Fn.new {

   System.print("%(maxStrings[0][1].count)")
   for (s in maxStrings) {
       System.print("%(s[0]) -> %(s[1])")
   }

}

System.write("1 character strings which are prime in most bases: ") for (s in digits) process.call(s) printResults.call()

System.write("\n2 character strings which are prime in most bases: ") maxStrings = [] mostBases = -1 for (d1 in digits.skip(1)) {

   for (d2 in digits) {
       var s = d1 + d2
       process.call(s)
   }

} printResults.call()

System.write("\n3 character strings which are prime in most bases: ") maxStrings = [] mostBases = -1 for (d1 in digits.skip(1)) {

   for (d2 in digits) {
       for (d3 in digits) {
           var s = d1 + d2 + d3
           process.call(s)
       }
   }

} printResults.call()

System.write("\n4 character strings which are prime in most bases: ") maxStrings = [] mostBases = -1 for (d1 in digits.skip(1)) {

   for (d2 in digits) {
       for (d3 in digits) {
           for (d4 in digits) {
               var s = d1 + d2 + d3 + d4
               process.call(s)
           }
       }
   }

} printResults.call()</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]