Class PrimePiSequence

java.lang.Object
org.episteme.core.mathematics.analysis.series.PrimePiSequence
All Implemented Interfaces:
Function<Natural,Integer>, Function<Natural,Integer>, Relation<Natural,Integer>, IntegerSequence, Sequence<Integer>
public class PrimePiSequence extends Object implements IntegerSequence
Prime counting function π(n) (OEIS A000720).

Ï€(n) gives the number of primes less than or equal to n. For example:

  • Ï€(1) = 0: no primes ≤ 1
  • Ï€(2) = 1: {2}
  • Ï€(10) = 4: {2, 3, 5, 7}
  • Ï€(100) = 25
  • Ï€(1000) = 168

Asymptotic Behavior

The Prime Number Theorem states that: 

Ï€(n) ~ n / ln(n)
More precisely, Legendre's approximation: 
π(n) ≈ n / (ln(n) - 1.08366)

Implementation

This implementation uses:

  • Sieve of Eratosthenes for small n (invalid input: '<' 10^6)
  • Miller-Rabin primality test for large n
  • Caching for performance

OEIS Reference

A000720

References

  • Gauss, C. F. (1849). Letter to Encke
  • Hadamard, J. invalid input: '&' de la Vallée Poussin, C. (1896). "Prime Number Theorem"
  • Riemann, B. (1859). "On the Number of Primes Less Than a Given Magnitude"
Since:
1.0
Author:
Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

  • Constructor Details

    • PrimePiSequence

      public PrimePiSequence()

  • Method Details

    • get

      public Integer get(Natural n)
      Description copied from interface: Sequence
      Returns the n-th term of the sequence (0-indexed).

      This is the canonical method using Episteme number types.

      Specified by:
      get in interface Sequence<Integer>
      Parameters:
      n - the index (n ≥ 0)
      Returns:
      a(n)

    • countPrimes

      public int countPrimes(long n)
      Counts the number of primes ≤ n.
      Parameters:
      n - the upper bound
      Returns:
      π(n)

    • approximatePi

      public double approximatePi(long n)
      Approximates π(n) using the Prime Number Theorem.
      Parameters:
      n - the value
      Returns:
      approximation of π(n)

    • getPrimesUpTo

      public List<Long> getPrimesUpTo(long n)
      Returns all primes up to n.
      Parameters:
      n - the upper bound
      Returns:
      list of primes ≤ n

    • getOEISId

      public String getOEISId()
      Description copied from interface: Sequence
      Returns the OEIS (Online Encyclopedia of Integer Sequences) identifier. For example, "A000045" for Fibonacci numbers.
      Specified by:
      getOEISId in interface Sequence<Integer>
      Returns:
      OEIS ID or null if not catalogued

    • getFirstN

      public int[] getFirstN(int count)
      Returns π(n) for the first n values.
      Parameters:
      count - number of terms
      Returns:
      array [π(0), π(1), ..., π(count-1)]

    • toString

      public String toString()
      Overrides:
      toString in class Object