Multi-base primes: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: upgraded REXX program to solve for five-character numbers that are prime in the most bases.) |
|||
Line 445: | Line 445: | ||
4.808196 seconds (8.58 M allocations: 357.983 MiB, 0.75% gc time) |
4.808196 seconds (8.58 M allocations: 357.983 MiB, 0.75% gc time) |
||
</pre> |
</pre> |
||
=={{header|Nim}}== |
|||
{{trans|Go}} |
|||
Compiled via C++ with full optimizations and runtime checks deactivated, the program takes 1 second to process up to 5 character strings and 34 seconds to process up to 6 characters (i5-8250U CPU @ 1.60GHz). Curiously, compiled via C it is slower (1.1 s and 38 seconds). |
|||
<lang Nim>import math, sequtils, strutils |
|||
const |
|||
MaxDepth = 6 |
|||
Max = 36^MaxDepth - 1 # Max value for MaxDepth digits in base 36. |
|||
Digits = "0123456789abcdefghijklmnopqrstuvwxyz" |
|||
# Sieve of Erathostenes. |
|||
var composite: array[1..(Max div 2), bool] # Only odd numbers. |
|||
for i in 1..composite.high: |
|||
let n = 2 * i + 1 |
|||
let n2 = n * n |
|||
if n2 > Max: break |
|||
if not composite[i]: |
|||
for k in countup(n2, Max, 2 * n): |
|||
composite[k shr 1] = true |
|||
template isPrime(n: int): bool = |
|||
if n <= 1: false |
|||
elif (n and 1) == 0: n == 2 |
|||
else: not composite[n shr 1] |
|||
type Context = object |
|||
indices: seq[int] |
|||
mostBases: int |
|||
maxStrings: seq[tuple[indices, bases: seq[int]]] |
|||
func initContext(depth: int): Context = |
|||
result.indices.setLen(depth) |
|||
result.mostBases = -1 |
|||
proc process(ctx: var Context) = |
|||
let minBase = max(2, max(ctx.indices) + 1) |
|||
if 37 - minBase < ctx.mostBases: return |
|||
var bases: seq[int] |
|||
for b in minBase..36: |
|||
var n = 0 |
|||
for i in ctx.indices: |
|||
n = n * b + i |
|||
if n.isPrime: bases.add b |
|||
var count = bases.len |
|||
if count > ctx.mostBases: |
|||
ctx.mostBases = count |
|||
ctx.maxStrings = @{ctx.indices: bases} |
|||
elif count == ctx.mostBases: |
|||
ctx.maxStrings.add (ctx.indices, bases) |
|||
proc nestedFor(ctx: var Context; length, level: int) = |
|||
if level == ctx.indices.len: |
|||
ctx.process() |
|||
else: |
|||
ctx.indices[level] = if level == 0: 1 else: 0 |
|||
while ctx.indices[level] < length: |
|||
ctx.nestedFor(length, level + 1) |
|||
inc ctx.indices[level] |
|||
for depth in 1..MaxDepth: |
|||
var ctx = initContext(depth) |
|||
ctx.nestedFor(Digits.len, 0) |
|||
echo depth, " character strings which are prime in most bases: ", ctx.maxStrings[0].bases.len |
|||
for m in ctx.maxStrings: |
|||
echo m.indices.mapIt(Digits[it]).join(), " → ", m[1].join(" ") |
|||
echo()</lang> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |