cp's OEIS Frontend

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

%I A002808 M3272 N1322 #322 Apr 04 2025 22:34:52
%S A002808 4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,32,33,34,35,36,
%T A002808 38,39,40,42,44,45,46,48,49,50,51,52,54,55,56,57,58,60,62,63,64,65,66,
%U A002808 68,69,70,72,74,75,76,77,78,80,81,82,84,85,86,87,88
%N A002808 The composite numbers: numbers n of the form x*y for x > 1 and y > 1.
%C A002808 The natural numbers 1,2,... are divided into three sets: 1 (the unit), the primes (A000040) and the composite numbers (A002808).
%C A002808 The number of composite numbers <= n (A065855) = n - pi(n) (A000720) - 1.
%C A002808 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
%C A002808 The composite numbers have the semiprimes A001358 as primitive elements.
%C A002808 A211110(a(n)) > 1. - _Reinhard Zumkeller_, Apr 02 2012
%C A002808 A060448(a(n)) > 1. - _Reinhard Zumkeller_, Apr 05 2012
%C A002808 A086971(a(n)) > 0. - _Reinhard Zumkeller_, Dec 14 2012
%C A002808 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
%C A002808 a(n) = A056608(n) * A160180(n). - _Reinhard Zumkeller_, Mar 29 2014
%C A002808 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
%C A002808 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
%C A002808 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
%C A002808 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
%C A002808 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
%C A002808 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
%C A002808 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
%D A002808 T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.
%D A002808 A. E. Bojarincev, Asymptotic expressions for the n-th composite number, Univ. Mat. Zap. 6:21-43 (1967). - In Russian.
%D A002808 John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 127.
%D A002808 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.
%D A002808 R. K. Guy, Unsolved Problems Number Theory, Section A.
%D A002808 G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 2.
%D A002808 D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 66.
%D A002808 Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 51.
%D A002808 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002808 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002808 N. J. A. Sloane, <a href="/A002808/b002808.txt">Table of n, a(n) for n = 1..17737</a> [composites up to 20000]
%H A002808 Rolf Brandl, <a href="http://www.jstor.org/stable/2323681">Integer polynomials that are reducible modulo all primes</a>, Amer. Math. Monthly 93 (1986), pp. 286-288.
%H A002808 C. K. Caldwell, <a href="https://t5k.org/glossary/page.php?sort=Composite">Composite Numbers</a>
%H A002808 Felix Huber, <a href="/A002808/a002808_1.pdf">Illustration for a(1)-a(12)</a>
%H A002808 Laurentiu Panaitopol, <a href="http://www.emis.de/journals/JIPAM/article153.html?sid=153">Some properties of the series of composed [sic] numbers</a>, Journal of Inequalities in Pure and Applied Mathematics 2:3 (2001).
%H A002808 Carlos Rivera, <a href="http://www.primepuzzles.net/puzzles/puzz_076.htm">Puzzle 76, z(n)=sigma(n) + phi(n) - 2n</a>, The Prime Puzzles and Problems Connection.
%H A002808 J. Barkley Rosser and Lowell Schoenfeld, <a href="http://projecteuclid.org/euclid.ijm/1255631807">Approximate formulas for some functions of prime numbers</a>, Illinois J. Math. 6 1962 64-94
%H A002808 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CompositeNumber.html">Composite Number</a>
%H A002808 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H A002808 <a href="/index/Go#GEB">Index entries for sequences from "Goedel, Escher, Bach"</a>
%F A002808 a(n) = pi(a(n)) + 1 + n, where pi is the prime counting function.
%F A002808 a(n) = A136527(n, n).
%F A002808 A000005(a(n)) > 2. - _Juri-Stepan Gerasimov_, Oct 17 2009
%F A002808 A001222(a(n)) > 1. - _Juri-Stepan Gerasimov_, Oct 30 2009
%F A002808 A000203(a(n)) < A007955(a(n)). - _Juri-Stepan Gerasimov_, Mar 17 2011
%F A002808 A066247(a(n)) = 1. - _Reinhard Zumkeller_, Feb 05 2012
%F A002808 Sum_{n>=1} 1/a(n)^s = Zeta(s)-1-P(s), where P is prime zeta. - _Enrique Pérez Herrero_, Aug 08 2012
%F A002808 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
%F A002808 a(n) > n + A000720(n) + 1. - _François Huppé_, Jan 08 2025
%p A002808 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
%p A002808 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
%t A002808 Select[Range[2,100], !PrimeQ[#]&] (* _Zak Seidov_, Mar 05 2011 *)
%t A002808 With[{nn=100},Complement[Range[nn],Prime[Range[PrimePi[nn]]]]] (* _Harvey P. Dale_, May 01 2012 *)
%t A002808 Select[Range[100], CompositeQ] (* _Jean-François Alcover_, Nov 07 2021 *)
%o A002808 (PARI) A002808(n)=for(k=0,primepi(n),isprime(n++)&&k--);n \\ For illustration only: see below. - _M. F. Hasler_, Oct 31 2008
%o A002808 (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
%o A002808 (PARI) forcomposite(n=1, 1e2, print1(n, ", ")) \\ _Felix Fröhlich_, Aug 03 2014
%o A002808 (PARI) for(n=1, 1e3, if(bigomega(n) > 1, print1(n, ", "))) \\ _Altug Alkan_, Oct 14 2015
%o A002808 (Haskell)
%o A002808 a002808 n = a002808_list !! (n-1)
%o A002808 a002808_list = filter ((== 1) . a066247) [2..]
%o A002808 -- _Reinhard Zumkeller_, Feb 04 2012
%o A002808 (Python)
%o A002808 from sympy import primepi
%o A002808 def A002808(n):
%o A002808     m, k = n, primepi(n) + 1 + n
%o A002808     while m != k:
%o A002808         m, k = k, primepi(k) + 1 + n
%o A002808     return m # _Chai Wah Wu_, Jul 15 2015, updated Apr 14 2016
%o A002808 (Python)
%o A002808 from sympy import isprime
%o A002808 def ok(n): return n > 1 and not isprime(n)
%o A002808 print([k for k in range(89) if ok(k)]) # _Michael S. Branicky_, Nov 07 2021
%o A002808 (Python)
%o A002808 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
%o A002808 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))
%o A002808 # generators of composite numbers:
%o A002808 A002808_upto=lambda stop=1<<59: filter(is_A002808, range(2,stop))
%o A002808 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
%o A002808 (Magma) [n: n in [2..250] | not IsPrime(n)]; // _G. C. Greubel_, Feb 24 2024
%o A002808 (SageMath) [n for n in (2..250) if not is_prime(n)] # _G. C. Greubel_, Feb 24 2024
%Y A002808 Complement of A008578. - _Omar E. Pol_, Dec 16 2016
%Y A002808 Cf. A000040, A018252, A065090, A136527.
%Y A002808 Cf. A073783 (first differences), A073445 (second differences).
%Y A002808 Boustrophedon transforms: A230954, A230955.
%Y A002808 Cf. A163870 (nontrivial divisors).
%Y A002808 Related sequences:
%Y A002808 Primes (p) and composites (c): A000040, A002808, A000720, A065855.
%Y A002808 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.
%Y A002808 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.
%K A002808 nonn,nice,easy,core
%O A002808 1,1
%A A002808 _N. J. A. Sloane_
%E A002808 Deleted an incomplete and broken link. - _N. J. A. Sloane_, Dec 16 2010