A036378 -id:A036378 - cp's OEIS frontend

A225152 Let b(k) be A036378, then a(n) is the number of b(k) terms such that 2^n < b(k) <= 2^(n+1).

2, 0, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 0

Frank M Jackson, Apr 30 2013

A036378 is a complete sequence.

			a(7) = 2 as between 128 and 256 there are 2 terms (A036378) namely 137 and 255.

Cf. A036378, A052005.

getterm[n2_] := PrimePi[2^(n2+1)]-PrimePi[2^n2];
termcount[n3_] := (m1=0; While[getterm[m1]<=2^n3, m1++]; m1);
Table[termcount[p+1]-termcount[p], {p, 0, 39}]

A000720 pi(n), the number of primes <= n. Sometimes called PrimePi(n) to distinguish it from the number 3.14159...

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 21, 21, 21, 21, 21, 21

Offset: 1

N. J. A. Sloane

Partial sums of A010051 (characteristic function of primes). - Jeremy Gardiner, Aug 13 2002
pi(n) and prime(n) are inverse functions: a(A000040(n)) = n and A000040(n) is the least number m such that A000040(a(m)) = A000040(n). A000040(a(n)) = n if (and only if) n is prime. - Jonathan Sondow, Dec 27 2004
See the additional references and links mentioned in A143227. - Jonathan Sondow, Aug 03 2008
A lower bound that gets better with larger N is that there are at least T prime numbers less than N, where the recursive function T is: T = N - N*Sum_{i=0..T(sqrt(N))} A005867(i)/A002110(i). - Ben Paul Thurston, Aug 23 2010
Number of partitions of 2n into exactly two parts with the smallest part prime. - Wesley Ivan Hurt, Jul 20 2013
Equivalent to the Riemann hypothesis: abs(a(n) - li(n)) < sqrt(n)*log(n)/(8*Pi), for n >= 2657, where li(n) is the logarithmic integral (Lowell Schoenfeld). - Ilya Gutkovskiy, Jul 05 2016
The second Hardy-Littlewood conjecture, that pi(x) + pi(y) >= pi(x + y) for integers x and y with min{x, y} >= 2, is known to hold for (x, y) sufficiently large (Udrescu 1975). - Peter Luschny, Jan 12 2021

			There are 3 primes <= 6, namely 2, 3 and 5, so pi(6) = 3.

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, p. 8.
Raymond Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; p. 129.
Florian Cajori, A History of Mathematical Notations, Dover edition (2012), par. 409.
Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 5.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, Theorems 6, 7, 420.
G. J. O. Jameson, The Prime Number Theorem, Camb. Univ. Press, 2003. [See also the review by D. M. Bressoud (link below).]
Władysław Narkiewicz, The Development of Prime Number Theory, Springer-Verlag, 2000.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 132-133, 157-184.
József Sándor, Dragoslav S. Mitrinovic and Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, Section VII.1. (For inequalities, etc.).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Gerald Tenenbaum and Michel Mendès France, Prime Numbers and Their Distribution, AMS Providence RI, 1999.
V. Udrescu, Some remarks concerning the conjecture pi(x + y) <= pi(x) + pi(y), Rev. Roumaine Math. Pures Appl. 20 (1975), 1201-1208.

Daniel Forgues, Table of n, pi(n) for n = 1..100000 (first 20000 terms from N. J. A. Sloane; see below for links with 823852 terms (Verma) and more (Caldwell))
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Christian Axler, Über die Primzahl-Zählfunktion, die n-te Primzahl und verallgemeinerte Ramanujan-Primzahlen, Ph.D. thesis 2013, in German, English summary.
Paul T. Bateman and Harold G. Diamond, A Hundred Years of Prime Numbers, Amer. Math. Month., Vol. 103, No. 9 (Nov. 1996), pp. 729-741, MAA Washington DC.
Steve Bennett, The role of Riemann's zeta function in the analytic proof of the Prime Number Theorem, 2004.
Claudio Bonanno and Mirko S. Mega, Toward a dynamical model for prime numbers, Chaos, Solitons & Fractals, Vol. 20, No. 1 (2004), pp. 107-118; arXiv preprint, arXiv:cond-mat/0309251, 2003.
David M. Bressoud, Review of "The Prime Number Theorem" by G. J. O. Jameson, MAA Reviews, 2005. - from _N. J. A. Sloane_, Dec 29 2018
D. M. Bressoud and Stan Wagon, Computational Number Theory: Basic Algorithms, Springer/Key, 2000 (with a Mathematica package for computational number theory).
Ben Brubaker, The Prime Number Theorem.
C. K. Caldwell, The Prime Glossary: Prime number theorem.
W. W. L. Chen, Distribution of Prime Numbers.
Jean-Marie de Koninck and Aleksandar Ivić, Topics in Arithmetical Functions: Asymptotic Formulae for Sums of Reciprocals of Arithmetical Functions and Related Fields, Amsterdam, Netherlands: North-Holland, 1980. See Chapter 9, p. 231.
Marc Deléglise, Computation of large values of pi(x), 1996.
Pierre Dusart, Autour de la fonction qui compte le nombre de nombres premiers, Thèse, Université de Limoges, France (1998).
Pierre Dusart, The k-th prime is greater than k(ln k + ln ln k-1) for k>=2, Mathematics of Computation, Vo. 68, No. 225 (1999), pp. 411-415.
Encyclopedia Britannica, The Prime Number Theorem [web.archive.org's copy of a no longer available personal copy of the Encyclopedia's article]
R. Gray and J. D. Mitchell, Largest subsemigroups of the full transformation monoid, Discrete Math., 308 (2008), 4801-4810.
G. H. Hardy and J. E. Littlewood, Contributions to the theory of the Riemann zeta-function and the theory of the distribution of primes, Acta Mathematica, Vol. 41 (1916), pp. 119-196.
G. H. Hardy and J. E. Littlewood, Some problems of 'Partitio numerorum'; III: On the expression of a number as a sum of primes, Acta Math., Vol. 44, No. 1 (1923), pp. 1-70.
Mehdi Hassani, Approximation of pi(x) by Psi(x), J. Inequ. Pure Appl. Math., Vol. 7, No. 1 (2006), Article #7.
Y.-C. Kim, Note on the Prime Number Theorem, arXiv:math/0502062 [math.NT], 2005.
Tzanio V. Kolev, On the number of Prime Numbers less than a Given Quantity, 2000.
Angel V. Kumchev, The Distribution of Prime Numbers, 2005.
J. C. Lagarias, V. S. Miller and A. M. Odlyzko, Computing pi(x): The Meissel-Lehmer method, Math. Comp., Vol. 44, No. 170 (1985), pp. 537-560.
Jeffrey C. Lagarias and Andrew M. Odlyzko, Computing pi(x): An analytic method, Journal of Algorithms, Vol. 8, No. 2 (1987), pp. 173-191; alternative link.
John Lorch, The Distribution of Primes, B.S. Undergraduate Mathematics Exchange, Vol. 3, No. 1 (Fall 2005).
Nathan McKenzie, Computing the Prime Counting Function with Linnik's Identity, personal blog, March 24, 2011.
Murat Baris Paksoy, Derived Ramanujan primes: R'_n, arXiv:1210.6991 [math.NT], 2012.
Bent E. Petersen, Prime Number Theorem, Seminar Lecture Note, 1996; version 2002-05-14.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Omar E. Pol, Determinacion geometrica de los numeros primos y perfectos, personal website, 2001 (?); Illustration of initial terms: Divisors and pi(x).
Bernhard Riemann, On the Number of Prime Numbers, 1859, last page (various transcripts)
J. Barkley Rosser, Explicit Bounds for Some Functions of Prime Numbers, American Journal of Mathematics, Vol. 63, No. 1 (1941), pp. 211-232.
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Ill. Journ. Math. 6 (1962) 64-94.
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers (scan of some key pages from an ancient annotated photocopy).
Sebastian Martin Ruiz and Jonathan Sondow, Formulas for pi(n) and the n-th prime, arXiv:math/0210312 [math.NT], 2002, 2014.
Jeffrey Shallit, Bibliography on calculation of pi(x).
Jonathan Sondow, Ramanujan Primes and Bertrand's Postulate, The American Mathematical Monthly, Vol. 116, No. 7 (2009), pp. 630-635; arXiv preprint, arXiv:0907.5232 [math.NT], 2009-2010.
Igor Turkanov, The prime counting function, arXiv:1603.02914 [math.NT], 2016.
Gaurav Verma and Srujan Sapkal, Table of n, pi(n) for n = 1..823852.
Matthew R. Watkins, The distribution of Prime Numbers.
Matthew R. Watkins, The prime number theorem (some references).
Eric Weisstein's World of Mathematics, Prime Counting Function.
Wikipedia, Prime number theorem.
Wikipedia, Prime-counting function.
C. P. Willans, On formulae for the nth prime, Math. Gazette 48 (1964), 413-415.
Marek Wolf, Applications of Statistical Mechanics in Number Theory, Physica A, vol. 274, no. 2, 1999, pp. 149-157; 1999 preprint.
Wolfram Research, First 50 values of pi(n).
Index entries for "core" sequences

Cf. A048989, A000040, A132090, A137588, A139328, A104272, A143223, A143224, A143225, A143226, A143227.
Cf. A143538, A036234, A033844, A034387, A034386, A179215, A010051, A212210-A212213, A233824, A056171, A304483.
Closely related:
A099802: Number of primes <= 2n.
A060715: Number of primes between n and 2n (exclusive).
A035250: Number of primes between n and 2n (inclusive).
A038107: Number of primes < n^2.
A014085: Number of primes between n^2 and (n+1)^2.
A007053: Number of primes <= 2^n.
A036378: Number of primes p between powers of 2, 2^n < p <= 2^(n+1).
A006880: Number of primes < 10^n.
A006879: Number of primes with n digits.
A033270: Number of odd primes <= n.
A065855: Number of composites <= n.
For lists of large values of a(n) see, e.g., A005669(n) = a(A002386(n)), A214935(n) = a(A205827(n)).
Related sequences:
Primes (p) and composites (c): A000040, A002808, A065855.
Primes between p(n) and 2*p(n): A063124, A070046; between c(n) and 2*c(n): A376761; between n and 2*n: A035250, A060715, A077463, A108954.
Composites between p(n) and 2*p(n): A246514; between c(n) and 2*c(n): A376760; between n and 2*n: A075084, A307912, A307989, A376759.

a000720 n = a000720_list !! (n-1)
a000720_list = scanl1 (+) a010051_list  -- Reinhard Zumkeller, Sep 15 2011

[ #PrimesUpTo(n): n in [1..200] ];  // Bruno Berselli, Jul 06 2011

with(numtheory); A000720 := pi; [ seq(A000720(i),i=1..50) ];

A000720[n_] := PrimePi[n]; Table[ A000720[n], {n, 1, 100} ]
Array[ PrimePi[ # ]&, 100 ]
Accumulate[Table[Boole[PrimeQ[n]],{n,100}]] (* Harvey P. Dale, Jan 17 2015 *)

A000720=vector(100,n,omega(n!)) \\ For illustration only; better use A000720=primepi

vector(300,j,primepi(j)) \\ Joerg Arndt, May 09 2008

from sympy import primepi
for n in range(1,100): print(primepi(n), end=', ') # Stefano Spezia, Nov 30 2018

[prime_pi(n) for n in range(1, 79)]  # Zerinvary Lajos, Jun 06 2009

The prime number theorem gives the asymptotic expression a(n) ~ n/log(n).
For x > 1, pi(x) < (x / log x) * (1 + 3/(2 log x)). For x >= 59, pi(x) > (x / log x) * (1 + 1/(2 log x)). [Rosser and Schoenfeld]
For x >= 355991, pi(x) < (x / log(x)) * (1 + 1/log(x) + 2.51/(log(x))^2 ). For x >= 599, pi(x) > (x / log(x)) * (1 + 1/log(x)). [Dusart]
For x >= 55, x/(log(x) + 2) < pi(x) < x/(log(x) - 4). [Rosser]
For n > 1, A138194(n) <= a(n) <= A138195(n) (Tschebyscheff, 1850). - Reinhard Zumkeller, Mar 04 2008
For n >= 33, a(n) = 1 + Sum_{j=3..n} ((j-2)! - j*floor((j-2)!/j)) (Hardy and Wright); for n >= 1, a(n) = n - 1 + Sum_{j=2..n} (floor((2 - Sum_{i=1..j} (floor(j/i)-floor((j-1)/i)))/j)) (Ruiz and Sondow 2000). - Benoit Cloitre, Aug 31 2003
a(n) = A001221(A000142(n)). - Benoit Cloitre, Jun 03 2005
G.f.: Sum_{p prime} x^p/(1-x) = b(x)/(1-x), where b(x) is the g.f. for A010051. - Franklin T. Adams-Watters, Jun 15 2006
a(n) = A036234(n) - 1. - Jaroslav Krizek, Mar 23 2009
From Enrique Pérez Herrero, Jul 12 2010: (Start)
a(n) = Sum_{i=2..n} floor((i+1)/A000203(i)).
a(n) = Sum_{i=2..n} floor(A000010(n)/(i-1)).
a(n) = Sum_{i=2..n} floor(2/A000005(n)). (End)
Let pf(n) denote the set of prime factors of an integer n. Then a(n) = card(pf(n!/floor(n/2)!)). - Peter Luschny, Mar 13 2011
a(n) = -Sum_{p <= n} mu(p). - Wesley Ivan Hurt, Jan 04 2013
a(n) = (1/2)*Sum_{p <= n} (mu(p)*d(p)*sigma(p)*phi(p)) + sum_{p <= n} p^2. - Wesley Ivan Hurt, Jan 04 2013
a(1) = 0 and then, for all k >= 1, repeat k A001223(k) times. - Jean-Christophe Hervé, Oct 29 2013
a(n) = n/(log(n) - 1 - Sum_{k=1..m} A233824(k)/log(n)^k + O(1/log(n)^{m+1})) for m > 0. - Jonathan Sondow, Dec 19 2013
a(n) = A001221(A003418(n)). - Eric Desbiaux, May 01 2014
a(n) = Sum_{j=2..n} H(-sin^2 (Pi*(Gamma(j)+1)/j)) where H(x) is the Heaviside step function, taking H(0)=1. - Keshav Raghavan, Jun 18 2016
a(A014076(n)) = (1/2) * (A014076(n) + 1) - n + 1. - Christopher Heiling, Mar 03 2017
From Steven Foster Clark, Sep 25 2018: (Start)
a(n) = Sum_{m=1..n} A143519(m) * floor(n/m).
a(n) = Sum_{m=1..n} A001221(m) * A002321(floor(n/m)) where A002321() is the Mertens function.
a(n) = Sum_{m=1..n} |A143519(m)| * A002819(floor(n/m)) where A002819() is the Liouville Lambda summatory function and |x| is the absolute value of x.
a(n) = Sum_{m=1..n} A137851(m)/m * H(floor(n/m)) where H(n) = Sum_{m=1..n} 1/m is the harmonic number function.
a(n) = Sum_{m=1..log_2(n)} A008683(m) * A025528(floor(n^(1/m))) where A008683() is the Moebius mu function and A025528() is the prime-power counting function.
(End)
Sum_{k=2..n} 1/a(k) ~ (1/2) * log(n)^2 + O(log(n)) (de Koninck and Ivić, 1980). - Amiram Eldar, Mar 08 2021
a(n) ~ 1/(n^(1/n)-1). - Thomas Ordowski, Jan 30 2023
a(n) = Sum_{j=2..n} floor(((j - 1)! + 1)/j - floor((j - 1)!/j)) [Mináč, unpublished] (see Ribenboim, pp. 132-133). - Stefano Spezia, Apr 13 2025
a(n) = n - 1 - Sum_{k=2..floor(log_2(n))} pi_k(n), where pi_k(n) is the number of k-almost primes <= n. - Daniel Suteu, Aug 27 2025

Additional links contributed by Lekraj Beedassy, Dec 23 2003

Edited by M. F. Hasler, Apr 27 2018 and (links recovered) Dec 21 2018

A029837 Binary order of n: log_2(n) rounded up to next integer.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7

Offset: 1

N. J. A. Sloane

Or, ceiling(log_2(n)).
Worst-case cost of binary search.
Equal to number of binary digits in n unless n is a power of 2 when it is one less.
Thus a(n) gives the length of the binary representation of n - 1 (n >= 2), which is also A070939(n - 1).
Let x(0) = n > 1 and x(k + 1) = x(k) - floor(x(k)/2), then a(n) is the smallest integer such that x(a(n)) = 1. - Benoit Cloitre, Aug 29 2002
Also number of division steps when going from n to 1 by process of adding 1 if odd, or dividing by 2 if even. - Cino Hilliard, Mar 25 2003
Number of ways to write n as (x + 2^y), x >= 0. Number of ways to write n + 1 as 2^x + 3^y (cf. A004050). - Benoit Cloitre, Mar 29 2003
The minimum number of cuts for dividing an object into n (possibly unequal) pieces. - Karl Ove Hufthammer (karl(AT)huftis.org), Mar 29 2010
Partial sums of A209229; number of powers of 2 not greater than n. - Reinhard Zumkeller, Mar 07 2012

			a(1) = 0, since log_2(1) = 0.
a(2) = 1, since log_2(2) = 1.
a(3) = 2, since log_2(3) = 1.58...
a(n) = 7 for n = 65, 66, ..., 127, 128.
G.f. = x^2 + 2*x^3 + 2*x^4 + 3*x^5 + 3*x^6 + 3*x^7 + 3*x^8 + 4*x^9 + ... - _Michael Somos_, Jun 02 2019

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989, p. 70.
G. J. E. Rawlins, Compared to What? An Introduction to the Analysis of Algorithms, W. H. Freeman, 1992; see pp. 108, 118.

T. D. Noe, Table of n, a(n) for n = 1..10000
Cino Hilliard, The x+1 conjecture [broken link]
Lionel Levine, Fractal sequences and restricted Nim, arXiv:math/0409408 [math.CO], 2004.
Eric Weisstein's World of Mathematics, Bit Length.
Index entries for sequences related to binary expansion of n

Cf. A000523, A070939, A000193, A000195, A004233, A113473, A053644.
Partial sums of A036987.
Used for several definitions: A029827, A036378-A036390. Partial sums: A001855.

a029837 n = a029837_list !! (n-1)
a029837_list = scanl1 (+) a209229_list
-- Reinhard Zumkeller, Mar 07 2012
(Common Lisp) (defun A029837 (n) (integer-length (1- n))) ; James Spahlinger, Oct 15 2012

[Ceiling(Log(2, n)): n in [1..100]]; // Vincenzo Librandi, Jun 14 2019

a:= n-> (p-> p+`if`(2^pAlois P. Heinz, Mar 18 2013

a[n_] := Ceiling[Log[2, n]]; Array[a, 105] (* Robert G. Wilson v, Dec 09 2005 *)
Table[IntegerLength[n - 1, 2], {n, 1, 105}] (* Peter Luschny, Dec 02 2017 *)
a[n_] := If[n < 1, 0, BitLength[n - 1]]; (* Michael Somos, Jul 10 2018 *)
Join[{0}, IntegerLength[Range[130], 2]] (* Vincenzo Librandi, Jun 14 2019 *)

{a(n) = if( n<1, 0, ceil(log(n) / log(2)))};

/* Set p = 1, then: */
xpcount(n,p) = for(x=1, n, p1 = x; ct=0; while(p1>1, if(p1%2==0,p1/=2; ct++,p1 = p1*p+1)); print1(ct, ", "))

{a(n) = if( n<2, 0, exponent(n-1)+1)}; /* Michael Somos, Jul 10 2018 */

def A029837(n):
    s = bin(n)[2:]
    return len(s) - (1 if s.count('1') == 1 else 0) # Chai Wah Wu, Jul 09 2020

def A029837(n): return (n-1).bit_length() # Chai Wah Wu, Jun 30 2022

(1 to 80).map(n => Math.ceil(Math.log(n)/Math.log(2)).toInt) // Alonso del Arte, Feb 19 2020

a(n) = ceiling(log_2(n)).
a(1) = 0; for n > 1, a(2n) = a(n) + 1, a(2n + 1) = a(n) + 1. Alternatively, a(1) = 0; for n > 1, a(n) = a(ceiling(n/2)) + 1. [corrected by Ilya Gutkovskiy, Mar 21 2020]
a(n) = k such that n^(1/k - 1) > 2 > n^(1/k), or the least value of k for which floor n^(1/k) = 1. a(n) = k for all n such that 2^(k - 1) < n < 2^k. - Amarnath Murthy, May 06 2001
G.f.: x/(1 - x) * Sum_{k >= 0} x^2^k. - Ralf Stephan, Apr 13 2002
A062383(n-1) = 2^a(n). - Johannes W. Meijer, Jul 06 2009
a(n+1) = -Sum_{k = 1..n} mu(2*k)*floor(n/k). - Benoit Cloitre, Oct 21 2009
a(n+1) = A113473(n). - Michael Somos, Jun 02 2019

Additional comments from Daniele Parisse

More terms from Michael Somos, Aug 02 2002

A007053 Number of primes <= 2^n.

Original entry on oeis.org

0, 1, 2, 4, 6, 11, 18, 31, 54, 97, 172, 309, 564, 1028, 1900, 3512, 6542, 12251, 23000, 43390, 82025, 155611, 295947, 564163, 1077871, 2063689, 3957809, 7603553, 14630843, 28192750, 54400028, 105097565, 203280221, 393615806, 762939111, 1480206279, 2874398515, 5586502348, 10866266172, 21151907950, 41203088796, 80316571436, 156661034233, 305761713237, 597116381732, 1166746786182, 2280998753949, 4461632979717, 8731188863470, 17094432576778, 33483379603407, 65612899915304, 128625503610475

Offset: 0

N. J. A. Sloane, Mira Bernstein, Robert G. Wilson v, S. W. Golomb

Conjecture: The number 4 is the only perfect power in this sequence. In other words, it is impossible to have a(n) = x^m for some integers n > 3, m > 1 and x > 1. - Zhi-Wei Sun, Sep 30 2015

			pi(2^3)=4 since first 4 primes are 2,3,5,7 all <= 2^3 = 8.

Jens Franke et al., pi(10^24), Posting to the Number Theory Mailing List, Jul 29 2010.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

David Baugh, Table of n, a(n) for n = 0..92 (terms n = 87..92 found using Kim Walisch's primecount program, terms n = 0..86 from Charles R Greathouse IV and Douglas B. Staple, [a(0)-a(75) from Tomás Oliveira e Silva, a(76)-a(77) from Jens Franke et al., Jul 29 2010, a(78)-a(80) from Jens Franke et al. on the Riemann Hypothesis, verified unconditionally by Douglas B. Staple, and a(81)-a(86) from Douglas B. Staple])
Andrew R. Booker, The Nth Prime Page
S. W. Golomb, Letter to N. J. A. Sloane, Jul. 1991
Thomas R. Nicely, Some Results of Computational Research in Prime Numbers
Thomas R. Nicely, Some Results of Computational Research in Prime Numbers [Local copy, pdf only]
Tomás Oliveira e Silva, Tables of values of pi(x) and of pi2(x)
Tomás Oliveira e Silva, Computing pi(x): the combinatorial method, Revista Do Detua, Vol. 4, No 6, March 2006.
Douglas B. Staple, The combinatorial algorithm for computing pi(x), arXiv:1503.01839 [math.NT], 2015.
Index entries for sequences related to numbers of primes in various ranges

Cf. A006880, A036378.

Table[PrimePi[2^n], {n, 0, 46}] (* Robert G. Wilson v *)

a(n) = primepi(1<John W. Nicholson, May 16 2011

a(n) = A060967(2n). - R. J. Mathar, Sep 15 2012

More terms from Jud McCranie
Extended to n = 52 by Warren D. Smith, Dec 11 2000, computed with Meissel-Lehmer-Legendre inclusion exclusion formula code he wrote back in 1985, recently re-run.
Extended to n = 86 by Douglas B. Staple, Dec 18 2014

A061398 Number of squarefree integers between prime(n) and prime(n+1).

Original entry on oeis.org

0, 0, 1, 1, 0, 2, 0, 2, 1, 1, 3, 2, 1, 1, 1, 3, 0, 3, 2, 0, 3, 1, 3, 4, 0, 1, 2, 0, 2, 6, 2, 2, 1, 5, 0, 2, 3, 2, 1, 3, 0, 6, 0, 2, 0, 7, 8, 1, 0, 2, 3, 0, 3, 3, 3, 3, 0, 2, 1, 1, 5, 7, 2, 0, 1, 9, 2, 4, 0, 0, 4, 3, 2, 2, 2, 2, 5, 2, 4, 6, 0, 5, 0, 4, 1, 3, 4, 1, 1, 2, 6, 4, 1, 4, 2, 2, 7, 0, 8, 4, 4, 3, 2, 1, 2

Offset: 1

Labos Elemer, Jun 07 2001

nonn

			Between 113 and 127 the 6 squarefree numbers are 114, 115, 118, 119, 122, 123, so a(30)=6.
From _Gus Wiseman_, Nov 06 2024: (Start)
The a(n) squarefree numbers for n = 1..16:
  1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16
  ---------------------------------------------------------------
  .   .   6   10  .   14  .   21  26  30  33  38  42  46  51  55
                      15      22          34  39              57
                                          35                  58
(End)

Harry J. Smith, Table of n, a(n) for n = 1..1000

Cf. A000040, A005117, A013928.
Cf. A179211. [Reinhard Zumkeller, Jul 05 2010]
Counting all composite numbers (not just squarefree) gives A046933.
The version for nonsquarefree numbers is A061399.
Zeros are A068360.
The version for prime-powers is A080101.
Partial sums are A337030.
The version for non-prime-powers is A368748.
Excluding prime(n+1) from the range gives A373198.
Ones are A377430.
Positives are A377431.
The version for perfect-powers is A377432.
The version for non-perfect-powers is A377433 + 2.
For squarefree numbers (A005117) between primes:
- length is A061398 (this sequence)
- min is A112926
- max is A112925
- sum is A373197
For squarefree numbers between powers of two:
- length is A077643 (except initial terms), partial sums A143658
- min is A372683, difference A373125, indices A372540, firsts of A372475
- max is A372889, difference A373126
- sum is A373123
For primes between powers of two:
- length is A036378
- min is A104080 or A014210, indices A372684 (firsts of A035100)
- max is A014234, difference A013603
- sum is A293697 (except initial terms)
Cf. A001223, A049093, A049094, A076259, A077641, A377434, A377436.

p:= 2:
for n from 1 to 200 do
  q:= nextprime(p);
A[n]:= nops(select(numtheory:-issqrfree, [$p+1..q-1]));
p:= q;
od:
seq(A[i],i=1..200); # Robert Israel, Jan 06 2017

a[n_] := Count[Range[Prime[n]+1, Prime[n+1]-1], _?SquareFreeQ];
Array[a, 100] (* Jean-François Alcover, Feb 28 2019 *)
Count[Range[#[[1]]+1,#[[2]]-1],?(SquareFreeQ[#]&)]&/@Partition[ Prime[ Range[120]],2,1] (* _Harvey P. Dale, Oct 14 2021 *)

{ n=0; q=2; forprime (p=3, prime(1001), a=0; for (i=q+1, p-1, a+=issquarefree(i)); write("b061398.txt", n++, " ", a); q=p ) } \\ Harry J. Smith, Jul 22 2009

a(n) = my(pp=prime(n)+1); sum(k=pp, nextprime(pp)-1, issquarefree(k)); \\ Michel Marcus, Feb 28 2019

from math import isqrt
from sympy import mobius, prime, nextprime
def A061398(n):
    p = prime(n)
    q = nextprime(p)
    r = isqrt(p-1)+1
    return sum(mobius(k)*((q-1)//k**2) for k in range(r,isqrt(q-1)+1))+sum(mobius(k)*((q-1)//k**2-(p-1)//k**2) for k in range(1,r))-1 # Chai Wah Wu, Jun 01 2024

a(n) = A013928(A000040(n+1)) - A013928(A000040(n)) - 1. - Robert Israel, Jan 06 2017

a(n) = A373198(n) - 1. - Gus Wiseman, Nov 06 2024

A014234 Largest prime <= 2^n.

Original entry on oeis.org

2, 3, 7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909, 1073741789, 2147483647, 4294967291, 8589934583, 17179869143, 34359738337, 68719476731, 137438953447

Offset: 1

Jud McCranie

nonn

For n>1 largest prime factor of the denominator of A027611(2^n) = 2^n*(2^n)-th harmonic number. - Alexander Adamchuk, Aug 02 2006

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, p. 390.

T. D. Noe, Table of n, a(n) for n=1..1000
Fred Curtis, C++ program for A014234
Harry J. Smith, PrimePi2 - Computes the Prime Pi(x) counting function [Broken link]
Harry J. Smith, PrimePi2 - Computes the Prime Pi(x) counting function [Cached copy]

Cf. A000079, A014210.
Cf. A013603 (2^n - a(n)).
See comment for the relationship to A027611.
These primes have indices A007053 = number of primes <= 2^n.
The opposite is A104080, delta A092131, indices A372684.
For squarefree instead of prime we have A372889, indices A143658.
A036378 counts primes between powers of 2, A293697 adds them up.
Cf. A035100, A130739, A211997.

a:= n-> prevprime(2^n+1):
seq(a(n), n=1..40);  # Alois P. Heinz, Apr 23 2020

PrevPrim[n_] := Block[{k = n - 1}, While[ !PrimeQ[k], k-- ]; k]; Table[ Abs[ PrevPrim[2^n]], {n, 1, 30} ]
Join[{2},NextPrime[2^Range[2,40],-1]] (* Harvey P. Dale, Jun 26 2011 *)

a(n) = precprime(2^n) \\ Michel Marcus, Aug 08 2013

Terms for n=31, n=32 added by Fred Curtis (fred(AT)f2.org), Dec 08 2009

A373198 Number of squarefree numbers from prime(n) to prime(n+1) - 1.

Original entry on oeis.org

1, 1, 2, 2, 1, 3, 1, 3, 2, 2, 4, 3, 2, 2, 2, 4, 1, 4, 3, 1, 4, 2, 4, 5, 1, 2, 3, 1, 3, 7, 3, 3, 2, 6, 1, 3, 4, 3, 2, 4, 1, 7, 1, 3, 1, 8, 9, 2, 1, 3, 4, 1, 4, 4, 4, 4, 1, 3, 2, 2, 6, 8, 3, 1, 2, 10, 3, 5, 1, 1, 5, 4, 3, 3, 3, 3, 6, 3, 5, 7, 1, 6, 1, 5, 2, 4, 5

Offset: 1

Gus Wiseman, May 29 2024

nonn

			This is the sequence of row-lengths of A005117 treated as a triangle with row-sums A373197:
   2
   3
   5   6
   7  10
  11
  13  14  15
  17
  19  21  22
  23  26
  29  30
  31  33  34  35
  37  38  39
  41  42
  43  46
  47  51
  53  55  57  58

Counting all numbers (not just squarefree) gives A001223, sum A371201.
For composite instead of squarefree we have A046933.
For squarefree numbers (A005117) between primes:
- sum is A373197
- length is A373198 (this sequence) = A061398 - 1
- min is A000040
- max is A112925, opposite A112926
For squarefree numbers between powers of two:
- sum is A373123
- length is A077643, partial sums A143658
- min is A372683, delta A373125, indices A372540, firsts of A372475
- max is A372889, delta A373126
For primes between powers of two:
- sum is A293697 (except initial terms)
- length is A036378
- min is A104080 or A014210, indices A372684 (firsts of A035100)
- max is A014234, delta A013603
Cf. A372473 (firsts of A372472), A372541 (firsts of A372433).
Cf. A049093, A049094, A076259, A077641.

Table[Length[Select[Range[Prime[n],Prime[n+1]-1],SquareFreeQ]],{n,100}]

from math import isqrt
from sympy import prime, nextprime, mobius
def A373198(n):
    p = prime(n)
    q = nextprime(p)
    r = isqrt(p-1)+1
    return sum(mobius(k)*((q-1)//k**2) for k in range(r,isqrt(q-1)+1))+sum(mobius(k)*((q-1)//k**2-(p-1)//k**2) for k in range(1,r)) # Chai Wah Wu, Jun 01 2024

a(n) = A061398(n) + 1.

A304521 a(n) is the number of prime powers k such that ceiling(log_2(k)) = n.

Original entry on oeis.org

1, 2, 3, 4, 8, 9, 17, 26, 47, 81, 142, 264, 474, 883, 1629, 3045, 5735, 10780, 20429, 38688, 73654, 140426, 268341, 513867, 986034, 1894410, 3646135, 7027826, 13562626, 26208249, 50698866, 98184468, 190338062, 369326691, 717271794, 1394198587, 2712112562

Offset: 1

Jon E. Schoenfield, May 13 2018

nonn

Prime powers are defined as numbers of the form p^k with p prime and k >= 1 (A246655).

			a(1)=1 because the interval [2,2] contains 1 prime power: 2.
a(2)=2 because the interval [3,4] contains 2 prime powers: 3 and 4=2^2.
a(3)=3 because the prime powers in [5,8] are 5, 7, and 8=2^3.

Chai Wah Wu, Table of n, a(n) for n = 1..92

Cf. A029837, A036378, A246655.

a(n) = sum(k=2^(n-1)+1, 2^n, isprimepower(k) != 0); \\ Michel Marcus, May 17 2018

from sympy import primepi, integer_nthroot
def A304521(n):
    def f(x):
        m = 1<Chai Wah Wu, Jan 19 2025

A077643 Number of squarefree integers in closed interval [2^n, -1 + 2*2^n], i.e., among 2^n consecutive numbers beginning with 2^n.

Original entry on oeis.org

1, 2, 3, 5, 9, 19, 39, 79, 157, 310, 621, 1246, 2491, 4980, 9958, 19924, 39844, 79672, 159365, 318736, 637457, 1274916, 2549816, 5099651, 10199363, 20398663, 40797299, 81594571, 163189087, 326378438, 652756861, 1305513511, 2611026987, 5222053970, 10444108084

Offset: 0

Labos Elemer, Nov 14 2002

nonn

Number of squarefree numbers with binary expansion of length n, or with n bits. The sum of these numbers is given by A373123. - Gus Wiseman, Jun 02 2024

			For n=4: among the 16 numbers of {16, ..., 31}, nine are squarefree [17, 19, 21, 22, 23, 26, 29, 30, 31], so a(4) = 9.

Amiram Eldar, Table of n, a(n) for n = 0..63 (calculated from the b-file at A143658)

Cf. A077641, A077642.
Partial sums (except first term) are A143658.
Run-lengths of A372475.
The minimum is A372683, delta A373125, indices A372540.
The maximum is A372889 (except at n=1), delta A373126, indices A143658.
Row-sums are A373123.
A005117 lists squarefree numbers, first differences A076259.
A053797 gives nonempty lengths of exclusive gaps between squarefree numbers.
A029837 counts bits, row-lengths of A030190 and A030308.
For primes between powers of 2:
- sum A293697
- length A036378 or A162145
- min A104080 or A014210, delta A092131, indices A372684
- max A014234, delta A013603, indices A007053
For squarefree numbers between primes:
- sum A373197
- length A373198 = A061398 - 1
- min A000040
- max A112925 (delta A240473), opposite A112926 (delta A240474)
Cf. A010036, A029931, A035100, A049093-A049096, A372473 (firsts of A372472), A372541 (firsts of A372433).

Table[Apply[Plus, Table[Abs[MoebiusMu[2^w+j]], {j, 0, 2^w-1}]], {w, 0, 15}]
(* second program *)
Length/@Split[IntegerLength[Select[Range[10000],SquareFreeQ],2]]//Most (* Gus Wiseman, Jun 02 2024 *)

{ a(n) = sum(m=1,sqrtint(2^(n+1)-1), moebius(m) * ((2^(n+1)-1)\m^2 - (2^n-1)\m^2) ) } \\ Max Alekseyev, Oct 18 2008

a(n) = Sum_{j=0..-1+2^n} abs(mu(2^n + j)).

a(n)/2^n approaches 1/zeta(2), so limiting sequence is floor(2^n/zeta(2)), n >= 0. - Wouter Meeussen, May 25 2003

More terms from Mark Hudson (mrmarkhudson(AT)hotmail.com), Feb 12 2003
More terms from Wouter Meeussen, May 25 2003
a(25)-a(32) from Max Alekseyev, Oct 18 2008
a(33)-a(34) from Amiram Eldar, Jul 17 2024

A377430 Numbers k such that there is exactly one squarefree number between prime(k)+1 and prime(k+1)-1.

Original entry on oeis.org

3, 4, 9, 10, 13, 14, 15, 22, 26, 33, 39, 48, 59, 60, 65, 85, 88, 89, 93, 104, 113, 116, 122, 142, 143, 147, 148, 155, 181, 188, 198, 201, 209, 212, 213, 224, 226, 234, 235, 244, 254, 264, 265, 268, 287, 288, 313, 320, 328, 332, 333, 341, 343, 353, 361, 366

Offset: 1

Gus Wiseman, Oct 29 2024

nonn

			Primes 4 and 5 are 7 and 11, and the interval (8,9,10) contains only squarefree 10, so 4 is in the sequence.

Robert Israel, Table of n, a(n) for n = 1..10000

For composite instead of squarefree we have A029707.
These are the positions of 1 in A061398, or 2 in A373198.
For no squarefree numbers we have A068360.
For prime-power instead of squarefree we have A377287.
For at least one squarefree number we have A377431.
For perfect-power instead of squarefree we have A377434.
A000040 lists the primes, differences A001223, seconds A036263.
A002808 lists the composites, complement A008578.
A005117 lists the squarefree numbers, complement A013929.
A377038 gives k-differences of squarefree numbers.
Cf. A007674, A013603, A036378, A046933, A072284, A076259, A077641, A077643, A075526, A078147, A112925, A112926, A120992, A293697.

R:= NULL: count:= 0: q:= 2:
for k from 1 while count < 100 do
  p:= q; q:= nextprime(q);
  if nops(select(numtheory:-issqrfree,[$p+1 .. q-1]))=1 then
    R:= R,k; count:= count+1;
 fi
od:
R; # Robert Israel, Nov 29 2024

Select[Range[100], Length[Select[Range[Prime[#]+1,Prime[#+1]-1],SquareFreeQ]]==1&]

is(n,p=prime(n))=my(q=nextprime(p+1),s); for(k=p+1,q-1, if(issquarefree(k) && s++>1, return(0))); s==1 \\ Charles R Greathouse IV, Nov 29 2024

cp's OEIS Frontend

A225152 Let b(k) be A036378, then a(n) is the number of b(k) terms such that 2^n < b(k) <= 2^(n+1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A000720 pi(n), the number of primes <= n. Sometimes called PrimePi(n) to distinguish it from the number 3.14159...

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

A029837 Binary order of n: log_2(n) rounded up to next integer.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Scala

Formula

Extensions

A007053 Number of primes <= 2^n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A061398 Number of squarefree integers between prime(n) and prime(n+1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula