The OEIS is supported by the many generous donors to the OEIS Foundation. 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) 891
 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. 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. 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. 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). 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 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 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) = 1 + a(n-1) + f(n) for n > 1 with a(1) = 4 where f(n) = 1 if n belongs to A014689, 0 otherwise. - Mikhail Kurkov, Dec 21 2021 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, CompositeQ] (* Jean-François Alcover, Nov 07 2021 *) 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 (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 (Haskell) a002808 n = a002808_list !! (n-1) a002808_list = filter ((== 1) . a066247) [2..] -- Reinhard Zumkeller, Feb 04 2012 (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 CROSSREFS Complement of A008578. - Omar E. Pol, Dec 16 2016 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: A133576 A192607 A088224 * A018252 A141468 A140347 Adjacent sequences:  A002805 A002806 A002807 * A002809 A002810 A002811 KEYWORD nonn,nice,easy,core AUTHOR 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 | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 26 20:44 EDT 2022. Contains 357048 sequences. (Running on oeis4.)