How to resolve the algorithm Meissel–Mertens constant step by step in the Nim programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Meissel–Mertens constant step by step in the Nim programming language

Table of Contents

Problem Statement

Calculate Meissel–Mertens constant up to a precision your language can handle.

Analogous to Euler's constant, which is important in determining the sum of reciprocal natural numbers, Meissel-Mertens' constant is important in calculating the sum of reciprocal primes.

We consider the finite sum of reciprocal natural numbers: 1 + 1/2 + 1/3 + 1/4 + 1/5 ... 1/n this sum can be well approximated with: log(n) + E where E denotes Euler's constant: 0.57721... log(n) denotes the natural logarithm of n.

Now consider the finite sum of reciprocal primes: 1/2 + 1/3 + 1/5 + 1/7 + 1/11 ... 1/p this sum can be well approximated with: log( log(p) ) + M where M denotes Meissel-Mertens constant: 0.26149...

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Meissel–Mertens constant step by step in the Nim programming language

Source code in the nim programming language

import std/[math, strformat, strutils]

proc initPrimes(N: static int): seq[int] =
  ## Initialize the list of primes.

  const M = 2 * N - 1
  var composite = newSeq[bool](N)
  composite[0] = true   # 1 is not prime.

  # Conversions from index to value and value to index.
  template index(n: int): int = (n - 1) shr 1
  template value(idx: int): int = idx shl 1 + 1

  # Fill the sieve.
  var n = 3
  while n * n <= M:
    if not composite[n.index]:
      for k in countup(n * n, M, 2 * n):
        composite[k.index] = true
    inc n, 2

  # Build list of primes.
  result = @[2]
  for idx in 0..composite.high:
    if not composite[idx]:
      result.add idx.value


const N = 2^30
let primes = initPrimes(N)

echo "Primes added         M"
echo "────────────   ──────────────"
const γ = 0.57721566490153286   # Euler–Mascheroni constant.
let primeCount = primes.len
var sum = 0.0
var count = 0
for p in primes:
  let rp = 1 / p
  sum += ln(1 - rp) + rp
  inc count
  if count mod 10_000_000 == 0 or count == primeCount:
    echo &"{insertSep($count):>11}   {sum+γ:.12}"


  

You may also check:How to resolve the algorithm Hickerson series of almost integers step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Functional coverage tree step by step in the Perl programming language
You may also check:How to resolve the algorithm Loops/N plus one half step by step in the S-lang programming language
You may also check:How to resolve the algorithm Sierpinski carpet step by step in the Go programming language
You may also check:How to resolve the algorithm Sailors, coconuts and a monkey problem step by step in the uBasic/4tH programming language