cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-9 of 9 results.

A278110 a(n) = Product_{k=1..A056811(n)} A000040(k)^A278109(n,k).

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 4, 12, 12, 12, 24, 24, 24, 24, 48, 48, 144, 144, 288, 288, 288, 288, 576, 2880, 2880, 8640, 17280, 17280, 17280, 17280, 34560, 34560, 34560, 34560, 207360, 207360, 207360, 207360, 414720, 414720, 414720, 414720, 829440, 2488320
Offset: 1

Views

Author

Jason Kimberley, Feb 02 2017

Keywords

Links

Crossrefs

Cf. A033833, A181817, A278108, A278109.

Programs

  • Magma
    [&*[Integers()|p^(n div p^2):p in PrimesUpTo(Isqrt(n))]:n in[1..45]];

A072000 Number of semiprimes (A001358) <= n.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 6, 7, 8, 8, 8, 9, 10, 10, 10, 10, 10, 10, 10, 11, 12, 13, 13, 13, 14, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 20, 21, 21, 21, 21, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 24, 25, 25, 25, 26
Offset: 1

Views

Author

Benoit Cloitre, Jun 19 2002

Keywords

Comments

Number of k <= n such that bigomega(k) = 2.

References

  • A. Hildebrand, On the number of prime factors of an integer, in Ramanujan Revisited (Urbana-Champaign, Ill., 1987), pp. 167-185, Academic Press, Boston, MA, 1988.
  • E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1, Teubner, Leipzig, 1909; third edition : Chelsea, New York (1974).
  • G. Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, p. 203, Publications de l'Institut Cartan, 1990.

Links

Crossrefs

Cf. A000720, A001358, A066265, A064911.

Programs

  • Maple
    A072000 := proc(n) local sp,t ; sp := 0 ; for t from 1 to n do if numtheory[bigomega](t) = 2 then sp := sp+1 ; fi ; od ; sp ; end proc: # R. J. Mathar, Jun 10 2007
  • Mathematica
    semiPrimePi[n_] := Sum[ PrimePi[n/Prime@i] -i + 1, {i, PrimePi@Sqrt@n}]; Array[semiPrimePi, 78] (* Robert G. Wilson v, Jan 03 2006 *)
(* If version >= 7 *) a[n_] := Select[Range[n], PrimeOmega[#] == 2 &] // Length; Table[a[n], {n, 1, 77}] (* Jean-François Alcover, Jun 29 2013 *)
Accumulate[Table[If[PrimeOmega[n]==2,1,0],{n,100}]] (* Harvey P. Dale, Jun 14 2014 *)
  • PARI
    for(n=1,100,print1(sum(i=1,n,if(bigomega(i)-2,0,1)),","))
  • PARI
    a(n)=my(s=0,i=0); forprime(p=2, sqrt(n), s+=primepi(n\p); i++); s - i * (i-1)/2 \\ Charles R Greathouse IV, Apr 21 2011
  • Python
    from math import isqrt
from sympy import primepi, prime
def A072000(n): return int(sum(primepi(n//prime(k))-k+1 for k in range(1,primepi(isqrt(n))+1))) # Chai Wah Wu, Jul 23 2024

Formula

Let PrimePi(x) denote the number of primes <= x (cf. A000720). Then 2*a(n) = Sum_{ primes p <= n/2 } PrimePi(n/p) + PrimePi(sqrt(n)). [Landau, p. 211]
Let PrimePi(x) denote the number of primes <= x (cf. A000720). Then a(n) = Sum_{i=1..PrimePi(sqrt(n))} (PrimePi(n/prime(i)) - i + 1). - Robert G. Wilson v, Feb 07 2006
a(n) = card { x <= n : bigomega(x) = 2 }.
Asymptotically a(n) ~ n*log(log(n))/log(n). [Landau, p. 211]
Let A be a positive integer. Then card { x <= n : bigomega(x) = A } ~ (n/log(n))*log(log(n))^(A-1)/(A-1)! [Landau, p. 211]
a(n) = A072613(n) + A056811(n). - R. J. Mathar, Jun 10 2007
a(n) = Sum_{i=1..n} A064911(i). - Jonathan Vos Post, Dec 30 2007
a(n)*A064911(n) = A174956(n). - Reinhard Zumkeller, Apr 03 2010

Extensions

Edited by Robert G. Wilson v, Feb 15 2006

A055399 Number of stages of sieve of Eratosthenes needed to identify n as prime or composite.

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 4, 1, 4, 1, 2, 1, 3, 1, 4, 1, 2, 1, 4, 1, 4, 1, 2, 1, 4, 1, 4, 1, 2, 1, 5, 1, 3, 1, 2, 1, 5, 1, 5, 1, 2, 1, 3, 1, 5, 1, 2, 1, 5, 1, 5, 1, 2, 1, 4, 1, 5, 1, 2, 1, 5, 1, 3, 1, 2, 1, 5
Offset: 3

Views

Author

Henry Bottomley, May 15 2000

Keywords

Comments

Primes are known as primes actually one step before a(n): at step k of the sieve, multiples of prime(k) are removed, the smallest integer removed being prime(k)^2; every remaining integer less than prime(k+1)^2 will then never be removed, and it is newly known at step k for those between prime(k)^2 and prime(k+1)^2. For example, at step 3, multiples of prime(3) = 5 are removed and remaining integers after this step are prime up to prime(4)^2 = 49; then, 29, 31, 37, 41, 43, 47 are known as prime at step 3. - Jean-Christophe Hervé, Nov 01 2013

Examples

			a(7)=2 because 7 is not removed by the first two stages of the sieve, but is less than the square of the second prime (though not the square of the first); a(35)=3 because 35 is removed in the third stage as a multiple of 5.

Links

Crossrefs

Cf. A000040, A002808, A004280, A038179, A055396, A054403, A055398, A083269, A010051, A056811.

Programs

  • Mathematica
    a[n_ /; !PrimeQ[n]] := PrimePi[ FactorInteger[n][[1, 1]]]; a[n_ /; PrimeQ[n]] := PrimePi[ NextPrime[ Sqrt[n]]]; Table[a[n], {n, 3, 107}](* Jean-François Alcover, Jun 11 2012, after formula *)

Formula

If n is composite, a(n) = A055396(n); if n is prime, a(n) = A056811(n)+1. [Corrected by Charles R Greathouse IV, Sep 03 2013]
a(n) = A010051(n)*(A056811(n)+1)+(1-A010051(n))*A055396(n). - Jean-Christophe Hervé, Nov 01 2013

A222759 Conjectured number of primes p for which binomial(n*p,p) (mod p^3) does not equal n.

Original entry on oeis.org

0, 2, 1, 0, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
Offset: 1

Views

Author

T. D. Noe, Mar 12 2013

Keywords

Comments

It appears that, for k > 2 and n >= prime(prime(k)^3), then a(n) >= k.
Sequences A000720 and A056811 give results for binomial(n*p,p) (mod p) and binomial(n*p,p) (mod p^2), respectively. It appears that mod p^3 is the last case; that is, this identity does not hold for higher powers. - T. D. Noe, Mar 14 2013

Links

Crossrefs

Cf. A096328 (prime(prime(n)^3)).
Cf. A000720, A056811 (primePi(n) and primePi(sqrt(n))).

Programs

  • Mathematica
    Table[Length[Select[Prime[Range[100]], Mod[Binomial[n*#,#], #^3] != n &]], {n, 87}]

A278109 Irregular triangle read by rows: T(n,k) = floor(n/prime(k)^2) for 1 <= prime(k)^2 <= n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 2, 1, 2, 1, 3, 1, 3, 1, 3, 1, 3, 1, 4, 1, 4, 1, 4, 2, 4, 2, 5, 2, 5, 2, 5, 2, 5, 2, 6, 2, 6, 2, 1, 6, 2, 1, 6, 3, 1, 7, 3, 1, 7, 3, 1, 7, 3, 1, 7, 3, 1, 8, 3, 1, 8, 3, 1, 8, 3, 1, 8, 3, 1, 9, 4, 1, 9, 4, 1, 9, 4, 1, 9, 4, 1, 10, 4, 1, 10, 4, 1, 10, 4, 1, 10, 4, 1, 11, 4, 1, 11, 5, 1
Offset: 4

Views

Author

Jason Kimberley, Feb 02 2017

Keywords

Comments

This triangle consists of those columns of A278108 with prime index.
The row length sequence is A056811.

Examples

			The initial rows (for n = 4..27) are:
1;
1;
1;
1;
2;
2, 1;
2, 1;
2, 1;
3, 1;
3, 1;
3, 1;
3, 1;
4, 1;
4, 1;
4, 2;
4, 2;
5, 2;
5, 2;
5, 2;
5, 2;
6, 2;
6, 2, 1;
6, 2, 1;
6, 3, 1;

Links

Crossrefs

Cf. A056811, A277648, A278108, A278110.

Programs

  • Magma
    [n div p^2:p in PrimesUpTo(Isqrt(n)),n in[1..45]];

Formula

T(n,k) = A278108(n,A000040(k)).

A230774 Number of primes less than first prime above square root of n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
Offset: 1

Views

Author

Jean-Christophe Hervé, Nov 01 2013

Keywords

Comments

Or repeat k (prime(k)^2 - prime(k-1)^2) times, with prime(0) set to 0 for k = 1.
This sequence is useful to compute A055399 for prime numbers.

Examples

			a(5) = a(6) = a(7) = a(8) = a(9) = 2 because prime(1) = 2 < sqrt(5 to 9) <= prime(2) = 3.

Links

Crossrefs

Cf. A050216, A056811, A055399, A230775.

Programs

  • Mathematica
    Table[1 + PrimePi[Sqrt[n-1]], {n, 100}] (* Alonso del Arte, Nov 01 2013 *)
  • Python
    from math import isqrt
from sympy import primepi
def A230774(n): return primepi(isqrt(n-1))+1 # Chai Wah Wu, Nov 04 2024

Formula

Repeat 1 prime(1)^2 = 4 times; for k>1, repeat k (prime(k)^2-prime(k-1)^2) = A050216(k-1) times.
a(n) - A056811(n) = characteristic function of squares of primes.

A078342 Number of positive integers less than n that are coprime to all primes less than or equal to the square root of n.

Original entry on oeis.org

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

Views

Author

Jon Perry, Nov 22 2002

Keywords

Examples

			a(8)=4 as sqrt(8)=~2.8 and from 1,2,3,4,5,6,7, only 1,3,5,7 are coprime to 2.

Links

Crossrefs

Cf. A000196, A000720, A056811.

Programs

  • Maple
    0, seq(numtheory:-pi(n-1) - numtheory:-pi(floor(sqrt(n))) + 1, n=2..100);
  • Mathematica
    a[1]=0; a[n_] := PrimePi[n-1]-PrimePi[Sqrt[n]]+1
  • PARI
    sqp(n)=local(sn,v,p,vc); sn=sqrt(n); v=vector(floor(sn)); p=2; v[1]=2; vc=2; while (nextprime(p+1)<=sn,p=nextprime(p+1); v[vc]=p; vc++); vecextract(v,concat("1..",vc-1));
newphi(n)=local(v,vl,fl,np); if(n==3, return(2)); v=sqp(n); vl=length(v); np=0; for (s=1,n-1,fl=false; for (r=1,vl,if (gcd(s,v[r])>1,fl=true; break)); if (fl==false,np++)); np
for (i=1,500,print1(newphi(i)",")) \\ Dean Hickerson Nov 24 2002
  • PARI
    a(n)=if(n>1, primepi(n-1) - primepi(sqrtint(n)) + 1, 0) \\ Charles R Greathouse IV, Oct 31 2016
  • PARI
    first(n)=my(v=vector(n),s,p=2,sq=4); forprime(q=3,n, s++; print("q = "q", s++ = "s); for(k=p,q-1, if(k==sq, sq=nextprime(sqrtint(sq)+1)^2; s--; print("k = "k", s-- = "s)); v[k]=s); p=q); v \\ Charles R Greathouse IV, Nov 08 2016

Formula

a(n) = pi(n-1) - pi(sqrt(n)) + 1 for n > 1.

A079715 a(n) = pi(n) - pi(sqrt(n)) + 1.

Original entry on oeis.org

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

Views

Author

Benoit Cloitre, Feb 16 2003

Keywords

Comments

A well-known application of the principle of inclusion-exclusion used in sieve methods.
Number of numbers less than or equal to n and coprime to the product of the primes less than sqrt(n), i.e., to A104588(n). - Lekraj Beedassy, Mar 17 2005

Links

Crossrefs

Cf. A000720, A056811, A056812, A104588.

Programs

  • Mathematica
    Table[PrimePi[n] - PrimePi[Sqrt[n]] + 1, {n, 1, 100}] (* G. C. Greubel, May 13 2017 *)
  • PARI
    for(n=1,100, print1(primepi(n) - primepi(sqrt(n)) + 1, ", ")) \\ G. C. Greubel, May 13 2017

Formula

a(n) = pi(n) - pi(sqrt(n)) + 1 = A000720(n) - A056811(n) + 1 = A056812(n) + 1.
a(n) = Sum_{k=1..n} mu(k)*floor(n/k) where each prime factor of k is <= sqrt(n). [Corrected by Steven Foster Clark, May 03 2023]

Extensions

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 12 2007

A230773 Minimum number of steps in an alternate definition of the Sieve of Eratosthenes needed to identify n as prime or composite.

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 3, 1, 4, 1, 2, 1, 4, 1, 3, 1, 2, 1, 4, 1, 4, 1, 2, 1, 3, 1, 4, 1, 2, 1, 4, 1, 4, 1, 2, 1, 4, 1, 4, 1, 2, 1, 4, 1, 3, 1, 2
Offset: 1

Views

Author

Jean-Christophe Hervé, Oct 30 2013

Keywords

Comments

This sequence differs from A055399 on prime numbers; as they are never removed during the sieve, it is partly a matter of convention to decide at which step they are classified as prime. Because the smallest integer to be removed at step k is prime(k)^2, integers between prime(k)^2 and prime(k+1)^2 and not removed after step k are known as prime after this step.
This is how this sequence is defined for noncomposite numbers (primes and 1): for any noncomposite number n between prime(k)^2 and prime(k+1)^2, a(n) = k. An exception is made for 3 to fit the usual presentation of the sieve, according to which 3 is classified as prime after the first step, that is, a(3) = 1 (it can be argued, though, that running the first step of the sieve is not actually necessary to identify 3 as prime because 3 < prime(1)^2: see the comment on A000040 by Daniel Forgues, referring to 2 and 3 as "forcibly prime" since there are no integers greater than 1 and less than or equal to their respective square roots).

Examples

			By convention, a(1)=a(2)=0, as 1 is not involved in the sieve, and 2 is known as prime before the first step (first integer > 1).
At step 1, multiples of 2 are removed, beginning with 4 = 2*2; 5 and 7 are not removed and cannot be removed at any further step because they are less than 3*3 = 9; therefore, integers from 4 to 8 are all classified as prime or not prime after the first step: a(4) = a(5) = a(6) = a(7) = a(8) = 1.
At step 2, all integers < 5^2 = 25 will be classified because those >= 9 and not already classified at step one are either multiple of 3 or prime; therefore, for 9 <= n < 25, a(n) = 1 if n is even, a(n) = 2 if n is odd.

Links

Crossrefs

Cf. A000040, A002808, A004280, A010051, A038179, A054403, A055396, A055398, A055399, A056811, A083269.

Formula

a(n) = A010051(n)*(A056811(n) + mod(n^2,3))+(1-A010051(n))*A055396(n)
(that is, if n is prime > 3, a(n) = primepi(firstprimebelow(sqrt(n)); else if n is composite, a(n) = A055396(n)).
a(n) = A055399(n) - A010051(n)*mod(n^2,3).
Showing 1-9 of 9 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.