68 lines
1.7 KiB
Nim
68 lines
1.7 KiB
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()
|