How to resolve the algorithm Multi-base primes step by step in the Nim programming language

Published on 12 May 2024 09:40 PM
#Nim

How to resolve the algorithm Multi-base primes step by step in the Nim programming language

Table of Contents

Problem Statement

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.

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.

Do the same for the maximum 5 character string.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Multi-base primes step by step in the Nim programming language

Source code in the nim programming language

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()

You may also check:How to resolve the algorithm Cantor set step by step in the Factor programming language
You may also check:How to resolve the algorithm Return multiple values step by step in the C programming language
You may also check:How to resolve the algorithm Horner's rule for polynomial evaluation step by step in the PowerShell programming language
You may also check:How to resolve the algorithm Keyboard input/Flush the keyboard buffer step by step in the Delphi programming language
You may also check:How to resolve the algorithm Inheritance/Multiple step by step in the Nemerle programming language