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.
Raku
1 through 4 character string finish fairly quickly. 5 character strings take a while. <lang perl6>use Math::Primesieve; my $sieve = Math::Primesieve.new;
my %prime-base;
my $chars = 5;
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]