A055399 -id:A055399 - cp's OEIS frontend

A055396 Smallest prime dividing n is a(n)-th prime (a(1)=0).

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

Offset: 1

Henry Bottomley, May 15 2000

nonn

Grundy numbers of the game in which you decrease n by a number prime to n, and the game ends when 1 is reached. - Eric M. Schmidt, Jul 21 2013
a(n) = the smallest part of the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product(p_j-th prime, j=1...r) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(21) = 2; indeed, the partition having Heinz number 21 = 3*7 is [2,4]. - Emeric Deutsch, Jun 04 2015
a(n) is the number of numbers whose largest proper divisor is n, i.e., for n>1, number of occurrences of n in A032742. - Stanislav Sykora, Nov 04 2016
For n > 1, a(n) gives the number of row where n occurs in arrays A083221 and A246278. - Antti Karttunen, Mar 07 2017

			a(15) = 2 because 15=3*5, 3<5 and 3 is the 2nd prime.

John H. Conway, On Numbers and Games, 2nd Edition, p. 129.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Douglas E. Iannucci and Urban Larsson, Game values of arithmetic functions, arXiv:2101.07608 [math.NT], 2021.
Wikipedia, Nimber (explains the term Grundy number).
Index entries for sequences computed from indices in prime factorization
Index entries for sequences generated by sieves

Cf. A004280, A020639, A032742, A038179, A049084, A055399, A061395, A215366, A243055, A257993, A276086.

Cf. also A078898, A246277, A250469 and arrays A083221 and A246278.

a055396 = a049084 . a020639  -- Reinhard Zumkeller, Apr 05 2012

with(numtheory):
a:= n-> `if`(n=1, 0, pi(min(factorset(n)[]))):
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 03 2013

a[1] = 0; a[n_] := PrimePi[ FactorInteger[n][[1, 1]] ]; Table[a[n], {n, 1, 96}](* Jean-François Alcover, Jun 11 2012 *)

a(n)=if(n==1,0,primepi(factor(n)[1,1])) \\ Charles R Greathouse IV, Apr 23 2015

from sympy import primepi, isprime, primefactors
def a049084(n): return primepi(n)*(1*isprime(n))
def a(n): return 0 if n==1 else a049084(min(primefactors(n))) # Indranil Ghosh, May 05 2017

From Reinhard Zumkeller, May 22 2003: (Start)
a(n) = A049084(A020639(n)).
A000040(a(n)) = A020639(n); a(n) <= A061395(n).
(End)
From Antti Karttunen, Mar 07 2017: (Start)
A243055(n) = A061395(n) - a(n).
a(A276086(n)) = A257993(n).
(End)

A063962 Number of distinct prime divisors of n that are <= sqrt(n).

Original entry on oeis.org

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

Offset: 1

Reinhard Zumkeller, Sep 04 2001

nonn

For all primes p: a(p) = 0 (not marked) and for k > 1 a(p^k) = 1.
a(1) = 0 and for n > 0 a(n) is the number of marks when applying the sieve of Eratosthenes where a stage for prime p starts at p^2.
If we define a divisor d|n to be inferior if d <= n/d, then inferior divisors are counted by A038548 and listed by A161906. This sequence counts inferior prime divisors. - Gus Wiseman, Feb 25 2021

			a(33) = a(3*11) = 1, as 3^2 = 9 < 33 and 11^2 = 121 > 33.
From _Gus Wiseman_, Feb 25 2021: (Start)
The a(n) inferior prime divisors (columns) for selected n:
n =  3  8  24  3660  390  3570 87780
   ---------------------------------
    {}  2   2     2    2     2     2
            3     3    3     3     3
                  5    5     5     5
                      13     7     7
                            17    11
                                  19
(End)

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

Cf. A055399, A001221.
Cf. A027748, A063962.
Zeros are at indices A008578.
The divisors are listed by A161906 and add up to A097974.
Dominates A333806 (the strictly inferior version).
The superior version is A341591.
The strictly superior version is A341642.
A001221 counts prime divisors, with sum A001414.
A033677 selects the smallest superior divisor.
A038548 counts inferior divisors.
A063538/A063539 have/lack a superior prime divisor.
A161908 lists superior divisors.
A207375 lists central divisors.
A217581 selects the greatest inferior prime divisor.
A341676 lists the unique superior prime divisors.
- Inferior: A033676, A066839, A069288, A072499, A333749, A333750.
- Superior: A051283, A059172, A070038, A072500, A116883, A341592, A341675.
- Strictly Inferior: A056924, A060775, A070039, A333805, A341596, A341674.
- Strictly Superior: A056924, A140271, A238535, A341594, A341595, A341673.
Cf. A000005, A001248, A005117, A006530, A020639, A048098, A064052, A341643.

a063962 n = length [p | p <- a027748_row n, p ^ 2 <= n]
-- Reinhard Zumkeller, Apr 05 2012

with(numtheory): a:=proc(n) local c,F,f,i: c:=0: F:=factorset(n): f:=nops(F): for i from 1 to f do if F[i]^2<=n then c:=c+1 else c:=c: fi od: c; end: seq(a(n),n=1..105); # Emeric Deutsch

Join[{0},Table[Count[Transpose[FactorInteger[n]][[1]],?(#<=Sqrt[n]&)],{n,2,110}]] (* _Harvey P. Dale, Mar 26 2015 *)

{ for (n=1, 1000, f=factor(n)~; a=0; for (i=1, length(f), if (f[1, i]^2<=n, a++, break)); write("b063962.txt", n, " ", a) ) } \\ Harry J. Smith, Sep 04 2009

G.f.: Sum_{k>=1} x^(prime(k)^2) / (1 - x^prime(k)). - Ilya Gutkovskiy, Apr 04 2020

a(A002110(n)) = n for n > 2. - Gus Wiseman, Feb 25 2021

Revised definition from Emeric Deutsch, Jan 31 2006

A055398 Result of fourth stage of sieve of Eratosthenes (after eliminating multiples of 2, 3, 5, 7).

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209, 211, 221, 223, 227, 229, 233, 239

Offset: 1

Henry Bottomley, May 15 2000

nonn

Essentially the same as A052424. - R. J. Mathar, Oct 13 2008

Ahmed Hamdy A. Diab, Sequence eliminating law (SEL) and the interval formulas of prime numbers, arXiv:2012.03052 [math.NT], 2020.
H. B. Meyer, Eratosthenes' sieve

Cf. A000040, A004280, A038179, A055396, A055399.

Join[{2,3,5,7},Select[Table[n,{n,2,500}],Mod[#,2]!=0&&Mod[#,3]!=0&&Mod[#,5]!=0&&Mod[#,7]!=0&]] (* Vladimir Joseph Stephan Orlovsky, Feb 18 2011 *)

a(n+4) = 2 * floor((3 * floor((10 * floor((9 * floor((56 * floor((55 * floor((54 * floor((53 * floor((52 * floor((51 * floor((50 * floor((49 * n + 1) / 48) + 13) / 49) + 20) / 50) + 24) / 51) + 31) / 52) + 35) / 53) + 42) / 54) + 54) / 55) + 1) / 8) + 8) / 9) + 1) / 2) + 1 for n>=1; see (22) in Diab link. - Michel Marcus, Dec 14 2020

A079047 Number of primes between prime(n) and prime(n)^2.

Original entry on oeis.org

1, 2, 6, 11, 25, 33, 54, 64, 90, 136, 151, 207, 250, 269, 314, 393, 470, 501, 590, 655, 684, 789, 863, 976, 1138, 1226, 1267, 1353, 1394, 1493, 1846, 1944, 2108, 2156, 2454, 2511, 2692, 2877, 3004, 3201, 3395, 3470, 3825, 3901, 4044, 4118, 4580, 5058, 5225

Offset: 1

Jose R. Brox (tautocrona(AT)terra.es), Feb 01 2003

nonn

I conjecture that 25 and 64 are the only terms that are also square numbers.

The next squares are 564001 and 774400, which occur at positions 419 and 481. There are no other squares in the first 10000 terms. - T. D. Noe, Sep 11 2013

			a(1)=1 because between prime(1)=2 and 2^2=4 there's one prime (3). a(3)=6 because between prime(3)=5 and 5^2=25 there are 6 primes (7, 11, 13, 17, 19, 23).

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A055399, A066680.

Cf. A050216.

[#PrimesInInterval(NthPrime(n), NthPrime(n)^2)-1: n in [1..70]]; // Vincenzo Librandi, Jul 23 2019

Table[p = Prime[n]; PrimePi[p^2] - n, {n, 100}] (* T. D. Noe, Sep 11 2013 *)

forprime(p=2,500,res=0; forprime(q=p+1,p^2,res=res+1); print1(res","))

Data corrected by T. D. Noe, Oct 25 2006

Edited (removing comment & correction about irrelevant property) by Peter Munn, Jan 24 2023

A054403 Result of third stage of sieve of Eratosthenes (after eliminating multiples of 2, 3 and 5).

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97, 101, 103, 107, 109, 113, 119, 121, 127, 131, 133, 137, 139, 143, 149, 151, 157, 161, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 203, 209, 211

Offset: 1

Henry Bottomley, May 15 2000

nonn

Ahmed Hamdy A. Diab, Sequence eliminating law (SEL) and the interval formulas of prime numbers, arXiv:2012.03052 [math.NT], 2020.
H. B. Meyer, Eratosthenes' sieve
Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 0, 0, 0, 1, -1).

Cf. A000040, A004280, A038179, A055396, A055398, A055399.

Join[{2,3,5},Select[Table[n,{n,2,300}],Mod[#,2]!=0&&Mod[#,3]!=0&&Mod[#,5]!=0&]] (* Vladimir Joseph Stephan Orlovsky, Feb 18 2011*)

2, 3, 5 and numbers 30k +/- 1, 7, 11, or 13.

a(n+3) = 2*floor((3*floor((10*floor((9*n+1)/8)+8)/9)+1)/2)+1 for n>=1; see (19) in Diab link. - Michel Marcus, Dec 14 2020

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

Jean-Christophe Hervé, Nov 01 2013

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.

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

Jean-Christophe Hervé, Table of n, a(n) for n = 1..10000

Cf. A050216, A056811, A055399, A230775.

Table[1 + PrimePi[Sqrt[n-1]], {n, 100}] (* Alonso del Arte, Nov 01 2013 *)

from math import isqrt
from sympy import primepi
def A230774(n): return primepi(isqrt(n-1))+1 # Chai Wah Wu, Nov 04 2024

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.

A216240 Composite numbers arising in Eratosthenes sieve with removing the multiples of every other remaining numbers after 2 (see comment).

Original entry on oeis.org

9, 21, 33, 49, 51, 77, 87, 119, 121, 123, 141, 177, 187, 201, 203, 219, 237, 287, 289, 291, 309, 319, 327, 329, 357, 393, 413, 417, 447, 451, 469, 471, 493, 501, 511, 517, 543, 553, 573, 591, 633, 649, 669, 679, 687, 697, 721, 723, 737, 763, 771, 799, 803, 807

Offset: 1

Vladimir Shevelev, Mar 14 2013

nonn

We remove even numbers except for 2. The first two remaining numbers are 3,5. Further we remove all remaining numbers multiple of 5,except for 5. The following two remaining numbers are 7,9. Now we remove all remaining numbers multiple of 9, except for 9, etc. The sequence lists the remaining composite numbers.

Conjecture. There exists x_0 such that for every x>=x_0, the number of a(n)<=x is more than pi(x).

Peter J. C. Moses, Table of n, a(n) for n = 1..10000

Cf. A003309, A038179, A004280, A054103, A055398, A055399, A066680, A083140, A145592, A152021, A152114.

Module[{a=Insert[Range[1,1000,2], 2, 2], k=4}, While[Length[a] >= 2k, a = Flatten[{Take[a,k], Select[Take[a,-Length[a]+k], Mod[#,a[[k]]] != 0 &]}]; k+=2]; Rest[Select[a,!PrimeQ[#]&]]] (* Peter J. C. Moses, Mar 27 2013 *)

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

Jean-Christophe Hervé, Oct 30 2013

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).

			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.

Jean-Christophe Hervé, Table of n, a(n) for n = 1..10000
C. K. Caldwell, The Prime Glossary, Sieve of Eratosthenes
H. B. Meyer, Eratosthenes' sieve
F. Richman, Generating primes by the sieve of Eratosthenes
Wikipedia, Sieve of Eratosthenes

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

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).

A353283 Minimum number of numbers to drop to determine whether n is a prime number using the Sieve of Eratosthenes algorithm.

Original entry on oeis.org

0, 0, 1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 6, 8, 7, 9, 8, 10, 9, 12, 10, 13, 11, 15, 12, 16, 13, 18, 14, 19, 15, 20, 16, 23, 17, 24, 18, 24, 19, 27, 20, 28, 21, 28, 22, 31, 23, 33, 24, 32, 25, 36, 26, 37, 27, 36, 28, 41, 29, 42, 30, 40, 31, 45, 32, 47, 33, 44, 34, 50, 35, 51, 36, 48

Offset: 2

Nicola Pesenti, Apr 07 2022

nonn

Equivalent to removing all multiples of numbers from 2 to smallest divisor of n from the set [2..n].

There should be a simple formula. - N. J. A. Sloane, May 29 2022

			a(15) = 8 because:
First pass: drop multiples of 2:
  2 3 x 5 x 7 x 9 x 11 x 13 x 15
Second pass: drop multiples of 3:
  2 3 _ 5 _ 7 _ x _ 11 _ 13 _ x
15 was dropped so it is not prime; 8 numbers were dropped.

Rémy Sigrist, Table of n, a(n) for n = 2..10000
Wikipedia, Sieve of Eratosthenes

Cf. A020639, A055396, A055399.

f n=n-2-r[2..n] where
r(h:t)|n`elem`t=1+r[x|x<- t,x`mod`h>0]
       |1>0=length t

for (n=2, #b=apply (k->if (k==1, 0, primepi(divisors(k)[2])), [1..75]), print1 (sum(k=2, n, b[k]<=b[n])-b[n]", ")) \\ Rémy Sigrist, Jun 02 2022

a(2*n) = n - 1 for any n > 0. - Rémy Sigrist, Jun 02 2022

cp's OEIS Frontend

A055396 Smallest prime dividing n is a(n)-th prime (a(1)=0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A063962 Number of distinct prime divisors of n that are <= sqrt(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A055398 Result of fourth stage of sieve of Eratosthenes (after eliminating multiples of 2, 3, 5, 7).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A079047 Number of primes between prime(n) and prime(n)^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A054403 Result of third stage of sieve of Eratosthenes (after eliminating multiples of 2, 3 and 5).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A216240 Composite numbers arising in Eratosthenes sieve with removing the multiples of every other remaining numbers after 2 (see comment).

Views

Author

Keywords