login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002808 The composite numbers: numbers n of the form x*y for x > 1 and y > 1.
(Formerly M3272 N1322)
625
4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

The natural numbers 1,2,... are divided into three sets: 1 (the unit), the primes (A000040) and the composite numbers (A002808).

The number of composite numbers <= n (A065855) = n - pi(n) (A000720) - 1.

m is composite iff sigma(m)+phi(m)>2m. - Farideh Firoozbakht, Jan 27 2005

The composite numbers have the semiprimes A001358 as primitive elements.

A211110(a(n)) > 1. - Reinhard Zumkeller, Apr 02 2012

A060448(a(n)) > 1. - Reinhard Zumkeller, Apr 05 2012

A086971(a(n)) > 0. - Reinhard Zumkeller, Dec 14 2012

Composite numbers n which are the product of r=A001222(n) prime numbers are sometimes called r-almost primes. Sequences listing r-almost primes are: A000040 (r = 1), A001358 (r = 2), A014612 (r = 3), A014613 (r = 4), A014614 (r = 5), A046306 (r = 6), A046308 (r = 7), A046310 (r = 8), A046312 (r = 9), A046314 (r = 10), A069272 (r = 11), A069273 (r = 12), A069274 (r = 13), A069275 (r = 14), A069276 (r = 15), A069277 (r = 16), A069278 (r = 17), A069279 (r = 18), A069280 (r = 19), A069281 (r = 20). - Jason Kimberley, Oct 02 2011

a(n) = A056608(n) * A160180(n). - Reinhard Zumkeller, Mar 29 2014

Degrees for which there are irreducible polynomials which are reducible mod p for all primes p, see Brandl. - Charles R Greathouse IV, Sep 04 2014

REFERENCES

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.

A. E. Bojarincev, Asymptotic expressions for the n-th composite number, Univ. Mat. Zap. 6:21-43 (1967). - In Russian.

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 2.

D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 66.

Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 51.

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

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 1..17737 [composites up to 20000]

Rolf Brandl, Integer polynomials that are reducible modulo all primes, Amer. Math. Monthly 93 (1986), pp. 286-288.

C. K. Caldwell, Composite Numbers

Laurentiu Panaitopol, Some properties of the series of composed [sic] numbers, Journal of Inequalities in Pure and Applied Mathematics 2:3 (2001).

J. Barkley Rosser, Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 1962 64-94

Eric Weisstein's World of Mathematics, Composite Number

Index entries for "core" sequences

Index entries for sequences from "Goedel, Escher, Bach"

FORMULA

a(n) = pi(a(n)) + 1 + n, where pi is the prime counting function.

A000005(a(n)) > 2. - Juri-Stepan Gerasimov, Oct 17 2009

A001222(a(n)) > 1. - Juri-Stepan Gerasimov, Oct 30 2009

A000203(a(n)) < A007955(a(n)). - Juri-Stepan Gerasimov, Mar 17 2011

A066247(a(n)) = 1. - Reinhard Zumkeller, Feb 05 2012

Dirichlet g.f. of A066247: Sum(n>=1) 1/a(n)^s = Zeta(s)-1-P(s), where P is prime zeta. - Enrique Pérez Herrero, Aug 08 2012

n + n/log n + n/log^2 n < a(n) < n + n/log n + 3n/log^2 n for n >= 4, see Panaitopol. Bojarincev gives an asymptotic version. - Charles R Greathouse IV, Oct 23 2012

MAPLE

t := []: for n from 2 to 20000 do if isprime(n) then else t := [op(t), n]; fi; od: t;

remove(isprime, [$3..89]); # Zerinvary Lajos, Mar 19 2007

A002808 := proc(n) option remember ; local a ; if n = 1 then 4; else for a from procname(n-1)+1 do if not isprime(a) then return a; end if; end do ; end if; end proc; # R. J. Mathar, Oct 27 2009

MATHEMATICA

Composite[n_Integer] := FixedPoint[n + PrimePi[ # ] + 1 &, n + PrimePi[n] + 1]; Array[Composite, 71] (* Robert G. Wilson v, Jan 13 2006 *)

Select[Range[2, 100], !PrimeQ[#]&] (* Zak Seidov, Mar 05 2011 *)

With[{nn=100}, Complement[Range[nn], Prime[Range[PrimePi[nn]]]]] (* Harvey P. Dale, May 01 2012 *)

PROG

(PARI) A002808(n)={for(k=0, primepi(n), isprime(n++)&&k--); n} \\ M. F. Hasler, Oct 31 2008

(PARI) A002808(n)={ my(k=-1); while( -n + n += -k + k=primepi(n), ); n} \\ For n=10^4 resp. 3*10^4, this is about 100 resp. 500 times faster than the former. - M. F. Hasler, Nov 11 2009

(Haskell)

a002808 n = a002808_list !! (n-1)

a002808_list = filter ((== 1) . a066247) [2..]

-- Reinhard Zumkeller, Feb 04 2012

(PARI) forcomposite(n=1, 1e2, print1(n, ", ")) \\ Felix Fröhlich, Aug 03 2014

CROSSREFS

Cf. A000040, A018252, A008578, A065090.

a(n) = A136527(n, n).

Cf. A073783 (first differences), A073445 (second differences).

Boustrophedon transforms: A230954, A230955.

Cf. A163870 (nontrivial divisors).

Sequence in context: A088224 * A018252 A141468 A140209 A140347 A077091

Adjacent sequences:  A002805 A002806 A002807 * A002809 A002810 A002811

KEYWORD

nonn,nice,easy,core,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

Deleted an incomplete and broken link. - N. J. A. Sloane, Dec 16 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

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

Last modified September 15 20:35 EDT 2014. Contains 246789 sequences.