A002808 The composite numbers: numbers n of the form x*y for x > 1 and y > 1.

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy
• core

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.

n is composite iff sigma(n) + phi(n) > 2n. This is a nice result of the well known theorem: For all positive integers n, n = Sum_{d|n} phi(d). For the proof see my contribution to puzzle 76 of Carlos Rivera's Primepuzzles. - Farideh Firoozbakht, Jan 27 2005, Jan 18 2015

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

An integer is composite if and only if it is the sum of strictly positive integers in arithmetic progression with common difference 2: 4 = 1 + 3, 6 = 2 + 4, 8 = 3 + 5, 9 = 1 + 3 + 5, etc. - Jean-Christophe Hervé, Oct 02 2014

This statement holds since k+(k+2)+...+k+2(n-1) = n*(n+k-1) = a*b with arbitrary a,b (taking n=a and k=b-a+1 if b>=a). - M. F. Hasler, Oct 04 2014

For n > 4, these are numbers n such that n!/n^2 = (n-1)!/n is an integer (see A056653). - Derek Orr, Apr 16 2015

Let f(x) = Sum_{i=1..x} Sum_{j=2..i-1} cos((2*Pi*x*j)/i). It is known that the zeros of f(x) are the prime numbers. So these are the numbers n such that f(n) > 0. - Michel Lagneau, Oct 13 2015

Numbers n that can be written as solutions of the Diophantine equation n = (x+2)(y+2) where {x,y} in N^2, pairs of natural numbers including zero (cf. Mathematica code and Davis). - Ron R Spencer and Bradley Klee, Aug 15 2016

Numbers n with a partition (containing at least two summands) so that its summands also multiply to n. If n is prime, there is no way to find those two (or more) summands. If n is composite, simply take a factor or several, write those divisors and fill with enough 1's so that they add up to n. For example: 4 = 2*2 = 2+2, 6 = 1*2*3 = 1+2+3, 8 = 1*1*2*4 = 1+1+2+4, 9 = 1*1*1*3*3 = 1+1+1+3+3. - Juhani Heino, Aug 02 2017

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.
• John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 127.
• Martin Davis, "Algorithms, Equations, and Logic", pp. 4-15 of S. Barry Cooper and Andrew Hodges, Eds., "The Once and Future Turing: Computing the World", Cambridge 2016.
• R. K. Guy, Unsolved Problems Number Theory, Section A.
• 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
• Felix Huber, Illustration for a(1)-a(12)
• Laurentiu Panaitopol, Some properties of the series of composed [sic] numbers, Journal of Inequalities in Pure and Applied Mathematics 2:3 (2001).
• Carlos Rivera, Puzzle 76, z(n)=sigma(n) + phi(n) - 2n, The Prime Puzzles and Problems Connection.
• J. Barkley Rosser and 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"

Crossrefs

Complement of A008578. - Omar E. Pol, Dec 16 2016

Cf. A000040, A018252, A065090, A136527.

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

Boustrophedon transforms: A230954, A230955.

Cf. A163870 (nontrivial divisors).

Related sequences:

Primes (p) and composites (c): A000040, A002808, A000720, 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.

Programs

Haskell

a002808 n = a002808_list !! (n-1)
a002808_list = filter ((== 1) . a066247) [2..]
-- Reinhard Zumkeller, Feb 04 2012

Magma

[n: n in [2..250] | not IsPrime(n)]; // G. C. Greubel, Feb 24 2024

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

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 *)
Select[Range[100], CompositeQ] (* Jean-François Alcover, Nov 07 2021 *)

PARI

A002808(n)=for(k=0,primepi(n),isprime(n++)&&k--);n \\ For illustration only: see below. - 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

PARI

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

PARI

for(n=1, 1e3, if(bigomega(n) > 1, print1(n, ", "))) \\ Altug Alkan, Oct 14 2015

Python

from sympy import primepi
def A002808(n):
    m, k = n, primepi(n) + 1 + n
    while m != k:
        m, k = k, primepi(k) + 1 + n
    return m # Chai Wah Wu, Jul 15 2015, updated Apr 14 2016

Python

from sympy import isprime
def ok(n): return n > 1 and not isprime(n)
print([k for k in range(89) if ok(k)]) # Michael S. Branicky, Nov 07 2021

Python

next_A002808=lambda n: next(n for n in range(n,n*5)if not isprime(n)) # next composite >= n > 0; next_A002808(n)==n <=> iscomposite(n). - M. F. Hasler, Mar 28 2025
is_A002808=lambda n:not isprime(n) and n>1 # where isprime(n) can be replaced with: all(n%d for d in range(2, int(n**.5)+1))
# generators of composite numbers:
A002808_upto=lambda stop=1<<59: filter(is_A002808, range(2,stop))
A002808_seq=lambda:(q:=2)and(n for p in primes if (o:=q)<(q:=p) for n in range(o+1,p)) # with, e.g.: primes=filter(isprime,range(2,1<<59)) # M. F. Hasler, Mar 28 2025

SageMath

[n for n in (2..250) if not is_prime(n)] # G. C. Greubel, Feb 24 2024

Formula

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

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

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

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

a(n) > n + A000720(n) + 1. - François Huppé, Jan 08 2025

Extensions

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