Class PrimeCountUpperBounds


  • public class PrimeCountUpperBounds
    extends Object
    Bounds for the prime counting function pi(x) = number of primes in (0, x].
    Author:
    Tilman Neumann
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static long Axler_1_1​(long x)
      Axler, https://arxiv.org/pdf/1409.1780.pdf, Theorem 1.1: pi(x) < x/ln(x) + x/ln^2(x) + 2*x/ln^3(x) + 6.35*x/ln^4(x) + 24.35*x/ln^5(x) + 121.75*x/ln^6(x) + 730.5*x(ln^7(x) + 6801.4*x/ln^8(x) for x>1.
      static long Axler_1_3​(long x)
      Axler, https://arxiv.org/pdf/1409.1780.pdf, Theorem 1.3: pi(x) < x / [ln(x) - 1 - 1/ln(x) - 3.35/ln^2(x) - 12.65/ln^3(x) - 71.7/ln^4(x) - 466.1275/ln^5(x) - 3489.8225/ln^6(x)], for x > e^3.804.
      static long Axler_3_5a​(long x)
      Axler, https://arxiv.org/pdf/1409.1780.pdf, Corollary 3.5a: pi(x) < x / [ln(x) - 1 - 1/ln(x) - 3.35/ln^2(x) - 12.65/ln^3(x) - 89.6/ln^4(x)] for x >= 21.95.
      static long Axler_3_5b​(long x)
      Axler, https://arxiv.org/pdf/1409.1780.pdf, Corollary 3.5b: pi(x) < x / [ln(x) - 1 - 1/ln(x) - 3.35/ln^2(x) - 15.43/ln^3(x)] for x >= 14.36.
      static long Axler_3_5c​(long x)
      Axler, https://arxiv.org/pdf/1409.1780.pdf, Corollary 3.5c: pi(x) < x / [ln(x) - 1 - 1/ln(x) - 3.83/ln^2(x)] for x >= 9.25.
      static long Axler_3_5d​(long x)
      Axler, https://arxiv.org/pdf/1409.1780.pdf, Corollary 3.5d: pi(x) < x / [ln(x) - 1 - 1.17/ln(x)]
      Works for x >= 2.634.800.823 and then it is the best bound for x < 6.200.000.000 approximately.
      static long combinedUpperBound​(long x)
      Computes an upper bound for the prime counting function pi(x) := number of primes in (0, x].
      static long Dusart2010_eq6_5​(long x)
      Dusart 2010 theorem 6.9, eq.
      static long Dusart2010_eq6_6​(long x)
      Dusart 2010 theorem 6.9, eq.
      static long Dusart2010_eq6_7​(long x)
      Dusart 2010 theorem 6.9, eq.
      static long Rosser_Schoenfeld​(long x)
      Rosser, Schoenfeld: pi(x) < 1.25506*x / ln(x) for x > 1.
    • Method Detail

      • combinedUpperBound

        public static long combinedUpperBound​(long x)
        Computes an upper bound for the prime counting function pi(x) := number of primes in (0, x].
        Parameters:
        x -
        Returns:
        upper bound for the number of primes < x
      • Axler_1_1

        public static long Axler_1_1​(long x)
        Axler, https://arxiv.org/pdf/1409.1780.pdf, Theorem 1.1: pi(x) < x/ln(x) + x/ln^2(x) + 2*x/ln^3(x) + 6.35*x/ln^4(x) + 24.35*x/ln^5(x) + 121.75*x/ln^6(x) + 730.5*x(ln^7(x) + 6801.4*x/ln^8(x) for x>1. "Improves Dusart's estimate for every x > e^23.11" = 1.08779...e10. Statement verified, correct.
        Parameters:
        x -
        Returns:
        upper bound for the number of primes < x
      • Axler_1_3

        public static long Axler_1_3​(long x)
        Axler, https://arxiv.org/pdf/1409.1780.pdf, Theorem 1.3: pi(x) < x / [ln(x) - 1 - 1/ln(x) - 3.35/ln^2(x) - 12.65/ln^3(x) - 71.7/ln^4(x) - 466.1275/ln^5(x) - 3489.8225/ln^6(x)], for x > e^3.804. Axler comments: "improvement of Theorem 1.1 for every sufficiently large x". This is true, but the improvement is quite small. From data up to x ~ 4.112 * 10^11 I estimated that Theorem 1.3 is better than Corollar 3.5c for approximately x > 2.470.000.000.000.
        Parameters:
        x -
        Returns:
        upper bound for the number of primes < x
      • Axler_3_5a

        public static long Axler_3_5a​(long x)
        Axler, https://arxiv.org/pdf/1409.1780.pdf, Corollary 3.5a: pi(x) < x / [ln(x) - 1 - 1/ln(x) - 3.35/ln^2(x) - 12.65/ln^3(x) - 89.6/ln^4(x)] for x >= 21.95.
        Parameters:
        x -
        Returns:
        upper bound for the number of primes < x
      • Axler_3_5b

        public static long Axler_3_5b​(long x)
        Axler, https://arxiv.org/pdf/1409.1780.pdf, Corollary 3.5b: pi(x) < x / [ln(x) - 1 - 1/ln(x) - 3.35/ln^2(x) - 15.43/ln^3(x)] for x >= 14.36.
        Parameters:
        x -
        Returns:
        upper bound for the number of primes < x
      • Axler_3_5c

        public static long Axler_3_5c​(long x)
        Axler, https://arxiv.org/pdf/1409.1780.pdf, Corollary 3.5c: pi(x) < x / [ln(x) - 1 - 1/ln(x) - 3.83/ln^2(x)] for x >= 9.25. Best stable algorithm for all x tested so far! (x <= 50673847669).
        Parameters:
        x -
        Returns:
        upper bound for the number of primes < x
      • Axler_3_5d

        public static long Axler_3_5d​(long x)
        Axler, https://arxiv.org/pdf/1409.1780.pdf, Corollary 3.5d: pi(x) < x / [ln(x) - 1 - 1.17/ln(x)]
        Works for x >= 2.634.800.823 and then it is the best bound for x < 6.200.000.000 approximately.
        Parameters:
        x -
        Returns:
        upper bound for the number of primes < x
      • Dusart2010_eq6_5

        public static long Dusart2010_eq6_5​(long x)
        Dusart 2010 theorem 6.9, eq. (6.5), holds for any x >= 1.
        Parameters:
        x -
        Returns:
        upper bound for the number of primes < x
      • Dusart2010_eq6_6

        public static long Dusart2010_eq6_6​(long x)
        Dusart 2010 theorem 6.9, eq. (6.6), holds for any x >= 60184.
        Parameters:
        x -
        Returns:
        upper bound for the number of primes < x
        See Also:
        "https://arxiv.org/PS_cache/arxiv/pdf/1002/1002.0442v1.pdf"
      • Dusart2010_eq6_7

        public static long Dusart2010_eq6_7​(long x)
        Dusart 2010 theorem 6.9, eq. (6.7), holds for any x >= 2953652287.
        Parameters:
        x -
        Returns:
        upper bound for the number of primes < x
        See Also:
        "https://arxiv.org/PS_cache/arxiv/pdf/1002/1002.0442v1.pdf"
      • Rosser_Schoenfeld

        public static long Rosser_Schoenfeld​(long x)
        Rosser, Schoenfeld: pi(x) < 1.25506*x / ln(x) for x > 1.
        Parameters:
        x -
        Returns:
        upper bound for the number of primes < x