analyticnt

package
v0.8.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 19, 2026 License: MIT Imports: 5 Imported by: 0

Documentation

Overview

Package analyticnt is a self-contained analytic number theory toolkit built entirely on the Go standard library.

It is a sibling subpackage of github.com/malcolmston/algebra but does not depend on it. Everything here is implemented directly on machine floats, integers, and math/big / math/cmplx values.

Contents

Prime enumeration and exact counting: Sieve, PrimesUpTo, NthPrime, IsPrime, PrimePi, PrimePiLegendre, PrimePiMeissel, LegendrePhi.

Prime-counting approximations: Li, LiOffset, Ei, E1, RiemannR, PrimePiApprox, NthPrimeApprox, SoldnerConstant.

Chebyshev and von Mangoldt functions: ChebyshevTheta, ChebyshevPsi, VonMangoldt, VonMangoldtLambda, SecondChebyshev.

The Riemann zeta function: Zeta, ZetaComplex, DirichletEta, DirichletEtaComplex, RiemannSiegelTheta, RiemannSiegelZ, ZetaZero, ZetaZeros, HardyZ, GramPoint.

Dirichlet characters and L-functions: DirichletCharacter, PrincipalCharacter, LegendreCharacter, DirichletL, LFunctionReal.

Multiplicative functions and Mertens: MobiusMu, MertensFunction, EulerPhi, Liouville, Omega, BigOmega, MertensConstant, TwinPrimeConstant, BrunConstant, ArtinConstant.

Prime-number-theorem error terms and prime-gap statistics: PiError, PsiError, PrimeGaps, MaximalPrimeGaps, TwinPrimesUpTo, CousinPrimesUpTo, SexyPrimesUpTo, PrimeCountingBias.

Conventions

Real-valued approximation routines return float64 and document the input domain on which they are valid. Functions that violate a documented precondition (for example a negative count) panic rather than returning a silently wrong value. Any routine that consumes randomness takes an explicit int64 seed and uses a deterministic math/rand source, so results are fully reproducible.

Index

Examples

Constants

View Source 
const (
	// MertensConstant is the Meissel–Mertens constant M ≈ 0.2614972128,
	// appearing in Σ_{p≤x} 1/p = ln ln x + M + o(1).
	MertensConstant = 0.26149721284764278375542683860869585905

	// TwinPrimeConstant is Hardy–Littlewood's C₂ ≈ 0.6601618158, controlling
	// the density of twin primes.
	TwinPrimeConstant = 0.66016181584686957392781211001455577843

	// BrunConstant is Brun's constant B₂ ≈ 1.902160583, the (conjectured)
	// convergent sum of reciprocals of twin primes.
	BrunConstant = 1.902160583104

	// ArtinConstant is Artin's constant ≈ 0.3739558136, the density of primes
	// with a given primitive root under Artin's conjecture.
	ArtinConstant = 0.37395581361920228805472805434641641511162924

	// LandauRamanujanConstant ≈ 0.7642236535, governing the density of sums of
	// two squares.
	LandauRamanujanConstant = 0.76422365358922066299069873125009232811679

	// FellerTornierConstant ≈ 0.6613170495.
	FellerTornierConstant = 0.66131704946962233528766040608130611265

	// SarnakConstant (Hafner–Sarnak–McCurley) ≈ 0.3532363719.
	SarnakConstant = 0.35323637185499598454351655043268201581

	// GlaisherKinkelin is Glaisher's constant A ≈ 1.2824271291, related to
	// ζ'(−1).
	GlaisherKinkelin = 1.28242712910062263687534256886979172776768893

	// CatalanConstant is Catalan's constant G ≈ 0.9159655942.
	CatalanConstant = 0.91596559417721901505460351493238411077414937

	// StieltjesGamma0 is the 0-th Stieltjes constant, equal to Euler's γ.
	StieltjesGamma0 = EulerGamma

	// StieltjesGamma1 is the 1-st Stieltjes constant γ₁ ≈ −0.0728158454.
	StieltjesGamma1 = -0.072815845483676724860586375874901319138

	// StieltjesGamma2 is the 2-nd Stieltjes constant γ₂ ≈ −0.0096903632.
	StieltjesGamma2 = -0.0096903631928723184845303860352125293590

	// LegendreConstant is Legendre's empirical constant B ≈ 1.08366 used in the
	// estimate x/(ln x − B).
	LegendreConstant = 1.08366
)

Analytic number theory constants. Values are given to double precision.

View Source 
const AperyConstant = 1.20205690315959428539973816151144999076498629

AperyConstant is ζ(3) ≈ 1.2020569032, Apéry's constant.

View Source 
const EulerGamma = 0.57721566490153286060651209008240243104215933593992

EulerGamma is the Euler–Mascheroni constant γ.

View Source 
const SoldnerConstant = 1.45136923488338105028396848589202744949303228

SoldnerConstant is the Ramanujan–Soldner constant μ ≈ 1.4513692349, the unique positive root of the logarithmic integral li(μ) = 0.

Variables

View Source 
var ErrNonPositive = errors.New("analyticnt: argument must be positive")

ErrNonPositive is returned or panicked with when a routine that requires a positive argument receives a non-positive one.

Functions

func AverageGap 

func AverageGap(x int) float64

AverageGap returns the mean gap between consecutive primes up to x, which by the prime number theorem is asymptotic to ln x.

func Bernoulli 

func Bernoulli(n int) float64

Bernoulli returns the n-th Bernoulli number B_n as a float64, computed by the Akiyama–Tanigawa algorithm. This uses the convention B_1 = +1/2.

func BertrandPrime 

func BertrandPrime(n int64) int64

BertrandPrime returns a prime p with n < p < 2n for n >= 1 (guaranteed to exist by Bertrand's postulate). It returns the smallest such prime.

func BigOmega 

func BigOmega(n int64) int

BigOmega returns Ω(n), the number of prime factors of n counted with multiplicity. Ω(1) = 0.

func ChebyshevBiasCount 

func ChebyshevBiasCount(x int) int64

ChebyshevBiasCount compares the number of primes ≤ x in the non-residue class versus the residue class modulo q (for q = 4, classes 3 and 1), returning their difference N₃ − N₁, which is positive far more often than not (the Chebyshev bias).

func ChebyshevPsi 

func ChebyshevPsi(x float64) float64

ChebyshevPsi returns the second Chebyshev function ψ(x) = Σ_{n ≤ x} Λ(n) = Σ_{p^k ≤ x} ln p. By the prime number theorem ψ(x) ~ x.

func ChebyshevTheta 

func ChebyshevTheta(x float64) float64

ChebyshevTheta returns the first Chebyshev function θ(x) = Σ_{p ≤ x} ln p, summing the natural logarithm over primes p at most x.

func ChebyshevThetaExp 

func ChebyshevThetaExp(x float64) float64

ChebyshevThetaExp returns e^{θ(x)} = Π_{p ≤ x} p, the primorial of x, as a float64. For large x this overflows to +Inf; use with care.

func ClassNumberDirichlet 

func ClassNumberDirichlet(p int64) int64

ClassNumberDirichlet returns the class number h(−p) of the imaginary quadratic field Q(√−p) for a prime p ≡ 3 (mod 4), computed from the quadratic character via the analytic class-number formula h = (1/(2−(2|p))) Σ_{a=1}^{(p−1)/2} (a|p). It is an integer for these p.

func CompletedZeta 

func CompletedZeta(s complex128) complex128

CompletedZeta returns the completed zeta function ξ̂(s) = π^{−s/2} Γ(s/2) ζ(s), which satisfies the symmetric functional equation ξ̂(s) = ξ̂(1−s).

func CountPrimesCongruent 

func CountPrimesCongruent(a, q int64, x int) int64

CountPrimesCongruent returns the number of primes p ≤ x with p ≡ a (mod q). By Dirichlet's theorem, for gcd(a,q)=1 these are asymptotically equidistributed across the φ(q) admissible residue classes.

func CousinPrimesUpTo 

func CousinPrimesUpTo(x int) [][2]int64

CousinPrimesUpTo returns all cousin-prime pairs (p, p+4) with p+4 ≤ x.

func CramerGap 

func CramerGap(p float64) float64

CramerGap returns Cramér's heuristic estimate (ln p)² for the gap following a prime p, the conjectured order of the maximal prime gap near p.

func Digamma 

func Digamma(x float64) float64

Digamma returns the digamma function ψ(x) = Γ'(x)/Γ(x) for real x > 0, using the recurrence to shift the argument upward followed by the standard asymptotic series.

func DirichletBeta 

func DirichletBeta(s float64) float64

DirichletBeta returns the Dirichlet beta function β(s) = Σ_{n≥0} (−1)^n (2n+1)^{-s}, the L-function of the non-principal character modulo 4. β(2) is Catalan's constant.

func DirichletEta 

func DirichletEta(s float64) float64

DirichletEta returns the Dirichlet eta function η(s) = Σ (-1)^{n-1} n^{-s} = (1 − 2^{1−s}) ζ(s) for real s. At s = 1 the removable singularity gives η(1) = ln 2.

func DirichletEtaComplex 

func DirichletEtaComplex(s complex128) complex128

DirichletEtaComplex returns η(s) = (1 − 2^{1−s}) ζ(s) for complex s, with the removable value η(1) = ln 2.

func DirichletL 

func DirichletL(s complex128, chi DirichletCharacter) complex128

DirichletL returns the Dirichlet L-function L(s, χ) for a complex argument s (with s ≠ 1 when χ is principal), using the Hurwitz-zeta decomposition L(s, χ) = q^{-s} Σ_{a=1}^{q} χ(a) ζ(s, a/q).

func DirichletLSeries 

func DirichletLSeries(s float64, chi DirichletCharacter, terms int) complex128

DirichletLSeries returns the truncated Dirichlet series Σ_{n=1}^{terms} χ(n) n^{-s} for real s > 1. It converges slowly and is provided mainly for cross-checking DirichletL on the half-plane of absolute convergence.

func DirichletLambda 

func DirichletLambda(s float64) float64

DirichletLambda returns the Dirichlet lambda function λ(s) = Σ_{n≥0} (2n+1)^{-s} = (1 − 2^{-s}) ζ(s) for real s > 1.

func DivisorCount 

func DivisorCount(n int64) int64

DivisorCount returns τ(n) = d(n), the number of positive divisors of n.

func DivisorSigma 

func DivisorSigma(k int, n int64) int64

DivisorSigma returns σ_k(n), the sum of the k-th powers of the divisors of n. σ_0 = τ (divisor count) and σ_1 is the sum of divisors.

func E1 

func E1(x float64) float64

E1 returns the exponential integral E1(x) = ∫_x^∞ e^{-t}/t dt for x > 0. It uses a power series for small x and a continued fraction for large x.

func Ei 

func Ei(x float64) float64

Ei returns the exponential integral Ei(x) = -PV ∫_{-x}^∞ e^{-t}/t dt, the principal value for x > 0 and the ordinary integral for x < 0. Ei has a logarithmic singularity at x = 0.

func EulerGammaExp 

func EulerGammaExp() float64

EulerGammaExp returns e^{−γ} ≈ 0.5614594836, the constant appearing in Mertens' third theorem.

func EulerPhi 

func EulerPhi(n int64) int64

EulerPhi returns Euler's totient φ(n), the number of integers in [1, n] coprime to n. n must be >= 1.

func ExplicitPsi 

func ExplicitPsi(x float64, numZeros int) float64

ExplicitPsi returns Riemann's explicit-formula approximation to ψ(x) using the first numZeros nontrivial zeros ρ = 1/2 + iγ: ψ(x) ≈ x − Σ_ρ x^ρ/ρ − ln(2π) − ½ln(1 − x^{-2}). The oscillatory zero sum is taken over conjugate pairs so the result is real.

func FactorInt 

func FactorInt(n int64) map[int64]int

FactorInt returns the prime factorization of n >= 1 as a map from prime to exponent. FactorInt(1) is the empty map.

func FactorialMod 

func FactorialMod(n, m int64) int64

FactorialMod returns n! mod m using iterative multiplication.

func GCD 

func GCD(a, b int64) int64

GCD returns the greatest common divisor of a and b (non-negative).

func Gamma 

func Gamma(x float64) float64

Gamma returns the gamma function Γ(x) for real x, delegating to the standard library implementation.

func GaussSum 

func GaussSum(chi DirichletCharacter) complex128

GaussSum returns the Gauss sum τ(χ) = Σ_{a=1}^{q} χ(a) e^{2πi a/q} associated with a Dirichlet character χ modulo q.

func GoldbachPair 

func GoldbachPair(n int) (p, q int64, ok bool)

GoldbachPair returns a pair of primes summing to the even integer n, choosing the pair with the smallest first prime. It returns (0,0,false) if none is found (which cannot happen for even n >= 4 within tested ranges).

func GoldbachPartitions 

func GoldbachPartitions(n int) int64

GoldbachPartitions returns the number of ways to write the even integer n as an unordered sum of two primes p + q with p ≤ q (the Goldbach partition count, Goldbach's comet). n must be even and >= 4.

func GramPoint 

func GramPoint(n int) float64

GramPoint returns the n-th Gram point g_n, the solution of θ(g_n) = nπ, found by Newton iteration. Gram points interlace the zeros of ζ for small n.

func HardyLittlewoodTwinEstimate 

func HardyLittlewoodTwinEstimate(x float64) float64

HardyLittlewoodTwinEstimate returns the Hardy–Littlewood asymptotic estimate 2·C₂·x/(ln x)² for the number of twin primes up to x.

func HardyZ 

func HardyZ(t float64) float64

HardyZ returns Hardy's Z-function Z(t) = e^{iθ(t)} ζ(1/2 + it), which is real for real t and shares its real zeros with ζ on the critical line. It is evaluated here directly from ζ(1/2 + it).

func HurwitzZeta 

func HurwitzZeta(s, a float64) float64

HurwitzZeta returns the Hurwitz zeta function ζ(s, a) = Σ_{n≥0} (n+a)^{-s} for real s > 1 and a > 0, via Euler–Maclaurin summation (which also continues it to s < 1, s ≠ 1).

func HurwitzZetaComplex 

func HurwitzZetaComplex(s complex128, a float64) complex128

HurwitzZetaComplex returns ζ(s, a) for complex s (s ≠ 1) and real a > 0.

func InverseLi 

func InverseLi(y float64) float64

InverseLi returns the value x such that LiOffset(x) = y, obtained by Newton iteration on Li. It inverts the standard prime-counting estimate and is the basis of accurate n-th-prime approximations. y must be > 0.

func IsCoprime 

func IsCoprime(a, b int64) bool

IsCoprime reports whether a and b are coprime (gcd 1).

func IsPrime 

func IsPrime(n int64) bool

IsPrime reports whether n is prime using deterministic trial division backed by a 6k±1 wheel. It is correct for all int64 inputs.

func IsPrimePower 

func IsPrimePower(n int64) (ok bool, p int64, k int)

IsPrimePower reports whether n = p^k for some prime p and k >= 1, and if so returns the base prime p and exponent k. When n is not a prime power it returns (false, 0, 0).

func IsSafePrime 

func IsSafePrime(p int64) bool

IsSafePrime reports whether p is a safe prime, i.e. (p−1)/2 is also prime.

func IsSophieGermain 

func IsSophieGermain(p int64) bool

IsSophieGermain reports whether p and 2p+1 are both prime (p is a Sophie Germain prime).

func IsSquareFree 

func IsSquareFree(n int64) bool

IsSquareFree reports whether n has no repeated prime factor.

func IsWilsonPrime 

func IsWilsonPrime(p int64) bool

IsWilsonPrime reports whether p is a Wilson prime, i.e. p² divides (p−1)! + 1. Only three are known (5, 13, 563); this checks by direct computation and is suitable for small p.

func JacobiSymbol 

func JacobiSymbol(a, n int64) int

JacobiSymbol returns the Jacobi symbol (a|n) for odd n >= 1, generalizing the Legendre symbol multiplicatively over the prime factorization of n.

func JordanTotient 

func JordanTotient(k int, n int64) int64

JordanTotient returns the Jordan totient J_k(n) = n^k Π_{p|n}(1 − p^{-k}), generalizing Euler's totient (k = 1).

func LCM 

func LCM(a, b int64) int64

LCM returns the least common multiple of a and b. LCM(0, x) = 0.

func LFunctionReal 

func LFunctionReal(s float64, chi DirichletCharacter) complex128

LFunctionReal returns L(s, χ) for a real argument s, returning the value as a complex128 (which is real for real characters).

func LegendrePhi 

func LegendrePhi(x int64, a int) int64

LegendrePhi returns Legendre's φ(x, a): the count of integers in [1, x] not divisible by any of the first a primes. It is evaluated by the standard recursion φ(x, a) = φ(x, a−1) − φ(⌊x/p_a⌋, a−1) with φ(x, 0) = ⌊x⌋.

func LegendreSymbol 

func LegendreSymbol(a, p int64) int

LegendreSymbol returns the Legendre symbol (a|p) for an odd prime p using Euler's criterion, evaluated as a^{(p−1)/2} mod p mapped to {−1, 0, 1}.

func Li 

func Li(x float64) float64

Li returns the logarithmic integral li(x) = PV ∫_0^x dt/ln t for x > 0, x ≠ 1. It is computed as Ei(ln x). li(1) is a singularity and li near 1 is large in magnitude.

func LiOffset 

func LiOffset(x float64) float64

LiOffset returns the offset logarithmic integral Li(x) = li(x) − li(2) = ∫_2^x dt/ln t. This is the standard smooth estimate for the prime-counting function π(x). x must be >= 2.

Example 
package main

import (
	"fmt"

	ant "github.com/malcolmston/algebra/analyticnt"
)

func main() {
	fmt.Printf("%.2f\n", ant.LiOffset(1000))
}

Output:
176.56

func LiValueAt2 

func LiValueAt2() float64

LiValueAt2 returns li(2) ≈ 1.045163780117493.

func Liouville 

func Liouville(n int64) int

Liouville returns the Liouville function λ(n) = (−1)^{Ω(n)}, where Ω counts prime factors with multiplicity. λ(1) = 1.

func LogGamma 

func LogGamma(x float64) float64

LogGamma returns the natural logarithm of |Γ(x)| for real x.

func LogGammaComplex 

func LogGammaComplex(z complex128) complex128

LogGammaComplex returns log Γ(z) (principal branch) for complex z with positive real part sufficiently large, using the Lanczos approximation. It is used by the Riemann–Siegel theta function.

func MangoldtSummatory 

func MangoldtSummatory(N int64) float64

MangoldtSummatory returns Σ_{n≤N} Λ(n)/n as a partial sum related to the logarithmic derivative of ζ; it is a small utility for PNT experiments.

func MaxPrimeGap 

func MaxPrimeGap(x int) (gap int64, startingPrime int64)

MaxPrimeGap returns the largest gap between consecutive primes up to x, along with the prime that begins it.

func MaximalPrimeGaps 

func MaximalPrimeGaps(x int) [][2]int64

MaximalPrimeGaps returns the record ("maximal") prime gaps up to x: each entry is a gap strictly larger than every earlier gap, paired with the prime that starts it. The result is a slice of [gap, startingPrime] pairs.

func MeritOfGap 

func MeritOfGap(g int64, p int64) float64

MeritOfGap returns the merit of a prime gap g following prime p, defined as g/ln p; merits above about 30 correspond to exceptionally large gaps.

func MertensFunction 

func MertensFunction(n int) int64

MertensFunction returns the Mertens function M(n) = Σ_{k=1}^{n} μ(k). n must be >= 0; M(0) = 0.

func MertensProduct 

func MertensProduct(x float64) float64

MertensProduct returns Π_{p ≤ x} (1 − 1/p). By Mertens' third theorem this is asymptotic to e^{−γ}/ln x.

func MertensSequence 

func MertensSequence(n int) []int64

MertensSequence returns the running Mertens values M(0), M(1), …, M(n) as a slice of length n+1.

func MobiusMu 

func MobiusMu(n int64) int

MobiusMu returns the Möbius function μ(n): 1 if n is a square-free positive integer with an even number of prime factors, −1 if square-free with an odd number, and 0 if n has a squared prime factor. μ(1) = 1.

Example 
package main

import (
	"fmt"

	ant "github.com/malcolmston/algebra/analyticnt"
)

func main() {
	fmt.Println(ant.MobiusMu(30), ant.MobiusMu(12))
}

Output:
-1 0

func MobiusSieve 

func MobiusSieve(n int) []int

MobiusSieve returns μ(k) for every k from 0 to n as a slice of length n+1, with entry 0 left as 0. It is far faster than repeated MobiusMu calls.

func MobiusSummatoryReciprocal 

func MobiusSummatoryReciprocal(N int) float64

MobiusSummatoryReciprocal returns Σ_{n≤N} μ(n)/n, which tends to 0 and whose value is bounded by 1 in absolute value.

func NextPrime 

func NextPrime(n int64) int64

NextPrime returns the smallest prime strictly greater than n.

func NthPrime 

func NthPrime(n int) int64

NthPrime returns the n-th prime (1-indexed): NthPrime(1) == 2, NthPrime(2) == 3, and so on. n must be >= 1.

func NthPrimeApprox 

func NthPrimeApprox(n int) float64

NthPrimeApprox returns an asymptotic estimate of the n-th prime using the expansion p_n ≈ n(ln n + ln ln n − 1 + (ln ln n − 2)/ln n). n must be >= 6 for the expansion to be meaningful; smaller n fall back to a coarse bound.

func NthPrimeInverseR 

func NthPrimeInverseR(n int) float64

NthPrimeInverseR returns the n-th prime estimated by inverting the Riemann R function, i.e. solving R(x) = n by Newton iteration. This is one of the most accurate closed-form estimators available.

func Omega 

func Omega(n int64) int

Omega returns ω(n), the number of distinct prime factors of n. ω(1) = 0.

func PiError 

func PiError(x int64) float64

PiError returns the signed error li(x) − π(x) of the offset-logarithmic integral estimate of the prime-counting function at integer x. For all tabulated x this is positive (the first sign change occurs near the enormous Skewes number).

func PiErrorRiemann 

func PiErrorRiemann(x int64) float64

PiErrorRiemann returns the signed error R(x) − π(x) of the Riemann estimate.

func PrevPrime 

func PrevPrime(n int64) int64

PrevPrime returns the largest prime strictly less than n, or 0 if there is none (n <= 2).

func PrimeCountBetween 

func PrimeCountBetween(lo, hi int64) int64

PrimeCountBetween returns the number of primes p with lo < p <= hi.

func PrimeCountingBias 

func PrimeCountingBias(x int64) (bias float64, liOverestimates bool)

PrimeCountingBias returns li(x) − π(x) as a float and reports whether the value is positive (li over-estimates π), illustrating the Chebyshev bias.

func PrimeDensity 

func PrimeDensity(x float64) float64

PrimeDensity returns the prime density 1/ln x, the probability that a number near x is prime according to the prime number theorem.

func PrimeFactors 

func PrimeFactors(n int64) []int64

PrimeFactors returns the distinct prime factors of n in increasing order.

func PrimeFactorsWithMultiplicity 

func PrimeFactorsWithMultiplicity(n int64) []int64

PrimeFactorsWithMultiplicity returns the prime factors of n listed with repetition, in increasing order, so that their product is n.

func PrimeGapHistogram 

func PrimeGapHistogram(x int) map[int64]int

PrimeGapHistogram returns a map from gap size to its frequency among consecutive primes up to x.

func PrimeGaps 

func PrimeGaps(x int) []int64

PrimeGaps returns the sequence of gaps p_{n+1} − p_n between consecutive primes up to x. The i-th entry is the gap after the i-th prime.

func PrimeHarmonic 

func PrimeHarmonic(x float64) float64

PrimeHarmonic returns Σ_{p ≤ x} 1/p, the sum of reciprocals of primes up to x. By Mertens' theorem it grows like ln ln x + M.

func PrimeIndex 

func PrimeIndex(p int64) int64

PrimeIndex returns the 1-based index of prime p in the sequence of primes (so PrimeIndex(2) == 1). If p is not prime it returns 0.

func PrimeLogHarmonic 

func PrimeLogHarmonic(x float64) float64

PrimeLogHarmonic returns Σ_{p ≤ x} (ln p)/p, which by Mertens' first theorem is asymptotic to ln x.

func PrimePi 

func PrimePi(x int64) int64

PrimePi returns the exact prime-counting function pi(x): the number of primes p with p <= x. It sieves up to floor(x) and is intended for moderate x.

Example 
package main

import (
	"fmt"

	ant "github.com/malcolmston/algebra/analyticnt"
)

func main() {
	fmt.Println(ant.PrimePi(100))
}

Output:
25

func PrimePiApprox 

func PrimePiApprox(x float64) float64

PrimePiApprox returns the recommended real-valued estimate of π(x), namely the Riemann R function for x >= 2 and 0 below that.

func PrimePiCheck 

func PrimePiCheck(x int64) (value int64, agree bool)

PrimePiCheck cross-checks all three exact counters (sieve, Legendre, Meissel) at x and reports whether they agree, returning the common value and the agreement flag.

func PrimePiGauss 

func PrimePiGauss(x float64) float64

PrimePiGauss returns Gauss's original estimate x/ln x of π(x).

func PrimePiLegendre 

func PrimePiLegendre(x int64) int64

PrimePiLegendre returns π(x) via Legendre's formula π(x) = φ(x, a) + a − 1, where a = π(⌊√x⌋). It is exact.

func PrimePiLegendreApprox 

func PrimePiLegendreApprox(x float64) float64

PrimePiLegendreApprox returns Legendre's classical estimate x/(ln x − B) with B = 1.08366 (Legendre's constant). It is historically important but less accurate than li or R.

func PrimePiLi 

func PrimePiLi(x float64) float64

PrimePiLi returns the offset logarithmic-integral estimate Li(x) of π(x) for x >= 2.

func PrimePiMeissel 

func PrimePiMeissel(x int64) int64

PrimePiMeissel returns π(x) via the Meissel formula, which reduces the work relative to Legendre's method. With a = π(x^{1/3}) and b = π(x^{1/2}), π(x) = φ(x, a) + (b + a − 2)(b − a + 1)/2 − Σ_{i=a+1}^{b} π(⌊x/p_i⌋). It is exact and agrees with PrimePi.

func PrimePiSieve 

func PrimePiSieve(n int) []int64

PrimePiSieve returns pi(k) for every k from 0 to n as a cumulative slice of length n+1, where result[k] is the number of primes <= k.

func PrimePowerCount 

func PrimePowerCount(x int64) int64

PrimePowerCount returns the number of prime powers p^k (k >= 1) not exceeding x. This is the summatory function of the prime-power indicator.

func PrimePowersUpTo 

func PrimePowersUpTo(x int64) []int64

PrimePowersUpTo returns every prime power p^k (k >= 1) that is ≤ x, in increasing order.

func PrimeTripletsUpTo 

func PrimeTripletsUpTo(x int) [][3]int64

PrimeTripletsUpTo returns prime triplets (p, p+2, p+6) or (p, p+4, p+6) — the two admissible constellations of diameter 6 — with the largest member ≤ x.

func PrimeZeta 

func PrimeZeta(s float64) float64

PrimeZeta returns the prime zeta function P(s) = Σ_p p^{-s} for real s > 1, computed by Möbius inversion P(s) = Σ_{n≥1} μ(n)/n · ln ζ(ns).

func PrimesInRange 

func PrimesInRange(lo, hi int) []int64

PrimesInRange returns all primes p with lo <= p <= hi in increasing order.

func PrimesInResidueClass 

func PrimesInResidueClass(a, q int64, x int) []int64

PrimesInResidueClass returns the primes p ≤ x with p ≡ a (mod q).

func PrimesUpTo 

func PrimesUpTo(n int) []int64

PrimesUpTo returns all primes p with p <= n in increasing order. n may be negative, in which case the empty slice is returned.

func PrimorialPrimes 

func PrimorialPrimes(k int) []int64

PrimorialPrimes returns the first k primes whose product is the k-th primorial. It is a convenience wrapper returning the prime list only.

func PsiError 

func PsiError(x float64) float64

PsiError returns the normalized error (ψ(x) − x)/√x of the second Chebyshev function, the quantity whose boundedness is equivalent to the Riemann hypothesis.

func PsiSchoenfeldBound 

func PsiSchoenfeldBound(x float64) float64

PsiSchoenfeldBound returns Schoenfeld's RH-conditional bound |ψ(x) − x| < (1/(8π))·√x·(ln x)², valid for x >= 73.2.

func Radical 

func Radical(n int64) int64

Radical returns rad(n), the product of the distinct prime factors of n. rad(1) = 1.

func RandomPrimeBelow 

func RandomPrimeBelow(n int, seed int64) int64

RandomPrimeBelow returns a uniformly random prime strictly less than n using a deterministic math/rand source seeded by seed. It returns 0 if there is no prime below n.

func RiemannHypothesisBound 

func RiemannHypothesisBound(x float64) float64

RiemannHypothesisBound returns the RH-conditional error bound for |π(x) − li(x)|, namely (1/(8π))·√x·ln x, which holds for x >= 2657 under the Riemann hypothesis (Schoenfeld).

func RiemannR 

func RiemannR(x float64) float64

RiemannR returns the Riemann prime-counting approximation R(x), evaluated via the Gram series R(x) = 1 + Σ_{k≥1} (ln x)^k / (k · k! · ζ(k+1)). For x >= 2 it is a markedly better estimate of π(x) than li(x).

func RiemannRPrime 

func RiemannRPrime(x float64) float64

RiemannRPrime returns the derivative R'(x) via the series R'(x) = Σ_{k≥1} (ln x)^{k-1} / (x · k! · ζ(k+1)), useful for inverting R.

func RiemannRScaled 

func RiemannRScaled(x float64) float64

RiemannRScaled returns R(x) computed with the Möbius-inversion form R(x) = Σ_{n≥1} μ(n)/n · li(x^{1/n}). It agrees with the Gram-series RiemannR but exposes the alternative definition.

func RiemannSiegelTheta 

func RiemannSiegelTheta(t float64) float64

RiemannSiegelTheta returns the Riemann–Siegel theta function θ(t) = arg Γ(1/4 + it/2) − (t/2) ln π, real for real t. It is central to the study of ζ(1/2 + it).

func RiemannSiegelThetaAsymptotic 

func RiemannSiegelThetaAsymptotic(t float64) float64

RiemannSiegelThetaAsymptotic returns the standard asymptotic expansion of θ(t) for large t; it is faster than RiemannSiegelTheta but only accurate for t larger than roughly 10.

func RiemannSiegelZ 

func RiemannSiegelZ(t float64) float64

RiemannSiegelZ is a synonym for HardyZ, the real-valued function whose sign changes locate the nontrivial zeros of ζ on the critical line.

func RiemannVonMangoldtN 

func RiemannVonMangoldtN(T float64) float64

RiemannVonMangoldtN returns the counting function N(T), the approximate number of nontrivial zeros of ζ with imaginary part in (0, T], given by the Riemann–von Mangoldt formula θ(T)/π + 1.

func RiemannXiComplex 

func RiemannXiComplex(s complex128) complex128

RiemannXiComplex returns the Riemann ξ-function ξ(s) = ½ s(s−1) π^{−s/2} Γ(s/2) ζ(s), an entire function whose zeros are exactly the nontrivial zeros of ζ and which satisfies ξ(s) = ξ(1−s).

func RiemannXiReal 

func RiemannXiReal(s float64) complex128

RiemannXiReal returns ξ(s) for a real argument s as a complex128 (the value is real).

func SafePrimesUpTo 

func SafePrimesUpTo(x int) []int64

SafePrimesUpTo returns all safe primes q ≤ x, those for which (q−1)/2 is prime.

func SecondChebyshev 

func SecondChebyshev(x float64) float64

SecondChebyshev is a synonym for ChebyshevPsi.

func SemiprimeCount 

func SemiprimeCount(x int64) int64

SemiprimeCount returns the number of semiprimes ≤ x.

func Semiprimes 

func Semiprimes(x int64) []int64

Semiprimes returns all semiprimes (products of exactly two primes, counted with multiplicity, so squares of primes qualify) that are ≤ x.

func SexyPrimesUpTo 

func SexyPrimesUpTo(x int) [][2]int64

SexyPrimesUpTo returns all sexy-prime pairs (p, p+6) with p+6 ≤ x.

func Sieve 

func Sieve(n int) []bool

Sieve returns a boolean slice s of length n+1 where s[i] reports whether i is prime, for 0 <= i <= n. It uses the sieve of Eratosthenes. n must be non-negative.

func SkewesNumberLog 

func SkewesNumberLog() float64

SkewesNumberLog returns the natural logarithm of the classical Skewes number, the (very large) bound below which li(x) − π(x) was proven to change sign; it is included as a documented constant, ln(Sk) ≈ 7.7·10^{2}? Actually returns the widely cited exponent e^{e^{e^{79}}} is intractable, so this returns the modern Bays–Hudson crossover estimate ≈ 1.397·10^{316}.

func SophieGermainPrimesUpTo 

func SophieGermainPrimesUpTo(x int) []int64

SophieGermainPrimesUpTo returns all Sophie Germain primes p (p and 2p+1 both prime) with p ≤ x.

func SquareFreeCount 

func SquareFreeCount(x int64) int64

SquareFreeCount returns the number of square-free integers in [1, x], computed via Σ_{d≤√x} μ(d)⌊x/d²⌋. Its density approaches 6/π².

func ThetaError 

func ThetaError(x float64) float64

ThetaError returns the normalized error (θ(x) − x)/√x of the first Chebyshev function.

func TotientSummatory 

func TotientSummatory(n int) int64

TotientSummatory returns Φ(n) = Σ_{k=1}^{n} φ(k), whose asymptotic is 3n²/π².

func Trigamma 

func Trigamma(x float64) float64

Trigamma returns the trigamma function ψ₁(x) = d²/dx² ln Γ(x) for real x > 0.

func TwinPrimeCount 

func TwinPrimeCount(x int) int64

TwinPrimeCount returns the number of twin-prime pairs (p, p+2) with p+2 ≤ x.

func TwinPrimeDensity 

func TwinPrimeDensity(x float64) float64

TwinPrimeDensity returns the Hardy–Littlewood estimate of the number of twin prime pairs (p, p+2) with p ≤ x, namely 2·C₂·∫_2^x dt/(ln t)². It is evaluated with an offset-Li–like construction.

func TwinPrimesUpTo 

func TwinPrimesUpTo(x int) [][2]int64

TwinPrimesUpTo returns all twin-prime pairs (p, p+2) with p+2 ≤ x, as a slice of [p, p+2] pairs.

Example 
package main

import (
	"fmt"

	ant "github.com/malcolmston/algebra/analyticnt"
)

func main() {
	fmt.Println(ant.TwinPrimesUpTo(20))
}

Output:
[[3 5] [5 7] [11 13] [17 19]]

func VonMangoldt 

func VonMangoldt(n int64) float64

VonMangoldt returns the von Mangoldt function Λ(n): ln p if n = p^k for a prime p and integer k >= 1, and 0 otherwise. Λ(1) = 0.

func VonMangoldtLambda 

func VonMangoldtLambda(n int64) float64

VonMangoldtLambda is a synonym for VonMangoldt.

func VonMangoldtSum 

func VonMangoldtSum(N int64) float64

VonMangoldtSum returns Σ_{n ≤ N} Λ(n), which equals ψ(N). It is provided as an integer-argument companion to ChebyshevPsi.

func Zeta 

func Zeta(s float64) float64

Zeta returns the Riemann zeta function ζ(s) for a real argument s ≠ 1, using the Euler–Maclaurin summation formula, which analytically continues ζ to the whole real line except the pole at s = 1.

Example 
package main

import (
	"fmt"

	ant "github.com/malcolmston/algebra/analyticnt"
)

func main() {
	fmt.Printf("%.6f\n", ant.Zeta(2))
}

Output:
1.644934

func ZetaAtEvenInteger 

func ZetaAtEvenInteger(k int) float64

ZetaAtEvenInteger returns the exact value ζ(2k) = (−1)^{k+1} B_{2k} (2π)^{2k} / (2·(2k)!) for k >= 1, using tabulated Bernoulli numbers. For example ζ(2) = π²/6.

func ZetaComplex 

func ZetaComplex(s complex128) complex128

ZetaComplex returns ζ(s) for a complex argument s ≠ 1 via Euler–Maclaurin summation. It is accurate throughout the critical strip for moderate |Im s|.

func ZetaPrime 

func ZetaPrime(s float64) float64

ZetaPrime returns the derivative ζ'(s) for real s ≠ 1 via a central finite difference of the Euler–Maclaurin evaluation.

func ZetaZero 

func ZetaZero(n int) float64

ZetaZero returns the imaginary part of the n-th nontrivial zero of ζ on the critical line (n >= 1), located by bracketing sign changes of HardyZ and bisecting. The first zero is ≈ 14.134725.

Example 
package main

import (
	"fmt"

	ant "github.com/malcolmston/algebra/analyticnt"
)

func main() {
	fmt.Printf("%.4f\n", ant.ZetaZero(1))
}

Output:
14.1347

func ZetaZeroRealPart 

func ZetaZeroRealPart() float64

ZetaZeroRealPart returns the common real part 1/2 of every nontrivial zero on the critical line; it is a convenience constant-returning helper.

func ZetaZeros 

func ZetaZeros(n int) []float64

ZetaZeros returns the imaginary parts of the first n nontrivial zeros of ζ on the critical line, in increasing order. n must be >= 1.

Types

type DirichletCharacter 

type DirichletCharacter struct {
	Q      int64        // the modulus
	Values []complex128 // Values[a] = χ(a) for 0 <= a < q
}

DirichletCharacter represents a Dirichlet character χ modulo q: a completely multiplicative, q-periodic function on the integers, defined by its values on a reduced residue system. The zero-valued Values entries mark residues not coprime to q (where χ = 0).

func AllCharactersModulo 

func AllCharactersModulo(q int64) []DirichletCharacter

AllCharactersModulo returns the full group of φ(q) Dirichlet characters modulo q when (Z/qZ)* is cyclic. For non-cyclic moduli it returns only the principal character together with as many cyclic-root characters as it can build, so callers requiring completeness should restrict to cyclic q.

func CharacterFromPrimitiveRoot 

func CharacterFromPrimitiveRoot(q int64, j int) DirichletCharacter

CharacterFromPrimitiveRoot builds a Dirichlet character modulo q with cyclic group (Z/qZ)* by sending a fixed primitive root g to e^{2πi·j/φ(q)}. The index j (0 <= j < φ(q)) selects which character in the cyclic dual group is returned. q must have a primitive root (q = 1,2,4,p^k,2p^k).

func LegendreCharacter 

func LegendreCharacter(p int64) DirichletCharacter

LegendreCharacter returns the quadratic character modulo an odd prime p given by the Legendre symbol (a|p): +1 for quadratic residues, −1 for non-residues, 0 for multiples of p.

func PrincipalCharacter 

func PrincipalCharacter(q int64) DirichletCharacter

PrincipalCharacter returns the principal Dirichlet character χ₀ modulo q.

func (DirichletCharacter) Conjugate 

func (c DirichletCharacter) Conjugate() DirichletCharacter

Conjugate returns the complex-conjugate character χ̄, which is also the inverse character χ^{-1}.

func (DirichletCharacter) Eval 

func (c DirichletCharacter) Eval(n int64) complex128

Eval returns χ(n), reducing n modulo q. For n not coprime to q the result is 0.

func (DirichletCharacter) IsPrincipal 

func (c DirichletCharacter) IsPrincipal() bool

IsPrincipal reports whether χ is the principal character χ₀ modulo q, which is 1 on residues coprime to q and 0 otherwise.

func (DirichletCharacter) IsReal 

func (c DirichletCharacter) IsReal() bool

IsReal reports whether χ takes only real values (±1, 0), i.e. χ is a quadratic or principal character.

func (DirichletCharacter) Order 

func (c DirichletCharacter) Order() int

Order returns the multiplicative order of χ in the character group, i.e. the least k >= 1 with χ^k = χ₀.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.