How to resolve the algorithm Sequence: nth number with exactly n divisors step by step in the Nim programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Sequence: nth number with exactly n divisors step by step in the Nim programming language

Table of Contents

Problem Statement

Calculate the sequence where each term an is the nth that has n divisors. Show here, on this page, at least the first 15 terms of the sequence.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sequence: nth number with exactly n divisors step by step in the Nim programming language

Source code in the nim programming language

import math, strformat
import bignum

type Record = tuple[num, count: Natural]

template isOdd(n: Natural): bool =
  (n and 1) != 0

func isPrime(n: int): bool =
  let bi = newInt(n)
  result = bi.probablyPrime(25) != 0

proc findPrimes(limit: Natural): seq[int] {.compileTime.} =
  result = @[2]
  var isComposite = newSeq[bool](limit + 1)
  var p = 3
  while true:
    let p2 = p * p
    if p2 > limit: break
    for i in countup(p2, limit, 2 * p):
      isComposite[i] = true
    while true:
      inc p, 2
      if not isComposite[p]: break
  for n in countup(3, limit, 2):
    if not isComposite[n]:
      result.add n

const Primes = findPrimes(22_000)

proc countDivisors(n: Natural): int =
  result = 1
  var n = n
  for i, p in Primes:
    if p * p > n: break
    if n mod p != 0: continue
    n = n div p
    var count = 1
    while n mod p == 0:
      n = n div p
      inc count
    result *= count + 1
    if n == 1: return
  if n != 1: result *= 2

const Max = 45
var records: array[0..Max, Record]
echo &"The first {Max} terms in the sequence are:"

for n in 1..Max:

  if n.isPrime:
    var z = newInt(Primes[n - 1])
    z = pow(z, culong(n - 1))
    echo &"{n:2}: {z}"

  else:
    var count = records[n].count
    if count == n:
      echo &"{n:2}: {records[n].num}"
      continue
    let odd = n.isOdd
    let d = if odd or n == 2 or n == 10: 1 else: 2
    var k = records[n].num
    while true:
      inc k, d
      if odd:
        let sq = sqrt(k.toFloat).int
        if sq * sq != k: continue
      let cd = k.countDivisors()
      if cd == n:
        inc count
        if count == n:
          echo &"{n:2}: {k}"
          break
      elif cd in (n + 1)..Max and records[cd].count < cd and
           k > records[cd].num and (d == 1 or d == 2 and not cd.isOdd):
        records[cd].num = k
        inc records[cd].count


  

You may also check:How to resolve the algorithm Square-free integers step by step in the AWK programming language
You may also check:How to resolve the algorithm Forest fire step by step in the J programming language
You may also check:How to resolve the algorithm Strip comments from a string step by step in the Scheme programming language
You may also check:How to resolve the algorithm Numbers which are the cube roots of the product of their proper divisors step by step in the Python programming language
You may also check:How to resolve the algorithm Increment a numerical string step by step in the Ursa programming language