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