How to resolve the algorithm Möbius function step by step in the Nim programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Möbius function step by step in the Nim programming language

Table of Contents

Problem Statement

The classical Möbius function: μ(n) is an important multiplicative function in number theory and combinatorics. There are several ways to implement a Möbius function. A fairly straightforward method is to find the prime factors of a positive integer n, then define μ(n) based on the sum of the primitive factors. It has the values {−1, 0, 1} depending on the factorization of n:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Möbius function step by step in the Nim programming language

Source code in the nim programming language

import std/[math, sequtils, strformat]

func getStep(n: int): int {.inline.} =
  result = 1 + n shl 2 - n shr 1 shl 1
 
func primeFac(n: int): seq[int] =
  var 
    maxq = int(sqrt(float(n)))
    d = 1
    q: int = 2 + (n and 1)   # Start with 2 or 3 according to oddity.

  while q <= maxq and n %% q != 0:
    q = getStep(d)
    inc d
  if q <= maxq:
    let q1 = primeFac(n /% q)
    let q2 = primeFac(q)
    result = concat(q2, q1, result)
  else:
    result.add(n)

func squareFree(num: int): bool = 
  let fact = primeFac num

  for i in fact:
    if fact.count(i) > 1:
      return false

  return true

func mobius(num: int): int = 
  if num == 1: return num

  let fact = primeFac num

  for i in fact: 
    ## check if it has a squared prime factor
    if fact.count(i) == 2: 
      return 0

  if num.squareFree:
    if fact.len mod 2 == 0: 
      return 1
    else:
      return -1

when isMainModule:
  echo "The first 199 möbius numbers are:" 

  for i in 1..199:
    stdout.write fmt"{mobius(i):4}"
    if i mod 20 == 0:
      echo "" # print newline


  

You may also check:How to resolve the algorithm Integer sequence step by step in the Befunge programming language
You may also check:How to resolve the algorithm Plasma effect step by step in the Perl programming language
You may also check:How to resolve the algorithm Factorial step by step in the Pure programming language
You may also check:How to resolve the algorithm Bitmap step by step in the Xojo programming language
You may also check:How to resolve the algorithm List comprehensions step by step in the Nim programming language