Multi-base primes: Difference between revisions
(julia example) |
m (grammar) |
||
Line 86: | Line 86: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
<lang |
<lang juliausing Primes |
||
function maxprimebases(ndig, maxbase) |
function maxprimebases(ndig, maxbase) |
||
Line 103: | Line 103: | ||
end |
end |
||
end |
end |
||
alen, vlen = length(first(maxprimebases)), length(maxprimebases) |
|||
println("\nThe maximum number of prime valued bases for base 10 numeric strings of length ", |
println("\nThe maximum number of prime valued bases for base 10 numeric strings of length ", |
||
ndig, " is |
ndig, " is $alen. The base 10 value list of ", vlen > 1 ? "these" : "this", " is:") |
||
for |
for i in eachindex(maxprimebases) |
||
println(nwithbases[i], " => ", |
println(nwithbases[i], " => ", maxprimebases[i]) |
||
end |
end |
||
end |
end |
||
Line 114: | Line 115: | ||
end |
end |
||
</lang>{{out}} |
</lang>{{out}} |
||
<pre> |
<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 |
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] |
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 |
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] |
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 |
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] |
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] |
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] |
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 |
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] |
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] |
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 |
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] |
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/these is: |
|||
441431 => [5, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 23, 26, 28, 30, 31, 32, 33] |
|||
4.870393 seconds (8.58 M allocations: 357.982 MiB, 0.62% gc time) |
|||
</pre> |
</pre> |
||
Revision as of 01:19, 3 July 2021
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
<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 juliausing 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]
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
Not very quick - about 49 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 minBase = Fn.new { |s|
var min = 2 for (e in s) { var b = digits.indexOf(e) + 1 if (b > min) min = b } return min
}
var process = Fn.new { |s|
var bases = [] for (b in minBase.call(s)..36) { 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]