A002808 - OEIS

%I M3272 N1322 #305 Oct 22 2024 02:51:30

%S 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 38,39,40,42,44,45,46,48,49,50,51,52,54,55,56,57,58,60,62,63,64,65,66,

%U 68,69,70,72,74,75,76,77,78,80,81,82,84,85,86,87,88

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

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

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

%C 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 The composite numbers have the semiprimes A001358 as primitive elements.

%C A211110(a(n)) > 1. - _Reinhard Zumkeller_, Apr 02 2012

%C A060448(a(n)) > 1. - _Reinhard Zumkeller_, Apr 05 2012

%C A086971(a(n)) > 0. - _Reinhard Zumkeller_, Dec 14 2012

%C 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 a(n) = A056608(n) * A160180(n). - _Reinhard Zumkeller_, Mar 29 2014

%C 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 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 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 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 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 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 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 T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.

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

%D 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 R. K. Guy, Unsolved Problems Number Theory, Section A.

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

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

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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H N. J. A. Sloane, <a href="/A002808/b002808.txt">Table of n, a(n) for n = 1..17737</a> [composites up to 20000]

%H 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 C. K. Caldwell, <a href="https://t5k.org/glossary/page.php?sort=Composite">Composite Numbers</a>

%H Felix Huber, <a href="/A002808/a002808_1.pdf">Illustration for a(1)-a(12)</a>

%H 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompositeNumber.html">Composite Number</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Go#GEB">Index entries for sequences from "Goedel, Escher, Bach"</a>

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

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

%F A000005(a(n)) > 2. - _Juri-Stepan Gerasimov_, Oct 17 2009

%F A001222(a(n)) > 1. - _Juri-Stepan Gerasimov_, Oct 30 2009

%F A000203(a(n)) < A007955(a(n)). - _Juri-Stepan Gerasimov_, Mar 17 2011

%F A066247(a(n)) = 1. - _Reinhard Zumkeller_, Feb 05 2012

%F 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 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

%p 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 := 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 Select[Range[2,100], !PrimeQ[#]&] (* _Zak Seidov_, Mar 05 2011 *)

%t With[{nn=100},Complement[Range[nn],Prime[Range[PrimePi[nn]]]]] (* _Harvey P. Dale_, May 01 2012 *)

%t Select[Range[100], CompositeQ] (* _Jean-François Alcover_, Nov 07 2021 *)

%o (PARI) A002808(n)=for(k=0,primepi(n),isprime(n++)&&k--);n \\ _M. F. Hasler_, Oct 31 2008

%o (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 (PARI) forcomposite(n=1, 1e2, print1(n, ", ")) \\ _Felix Fröhlich_, Aug 03 2014

%o (PARI) for(n=1, 1e3, if(bigomega(n) > 1, print1(n, ", "))) \\ _Altug Alkan_, Oct 14 2015

%o (Haskell)

%o a002808 n = a002808_list !! (n-1)

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

%o -- _Reinhard Zumkeller_, Feb 04 2012

%o (Python)

%o from sympy import primepi

%o def A002808(n):

%o     m, k = n, primepi(n) + 1 + n

%o     while m != k:

%o         m, k = k, primepi(k) + 1 + n

%o     return m # _Chai Wah Wu_, Jul 15 2015, updated Apr 14 2016

%o (Python)

%o from sympy import isprime

%o def ok(n): return n > 1 and not isprime(n)

%o print([k for k in range(89) if ok(k)]) # _Michael S. Branicky_, Nov 07 2021

%o (Magma) [n: n in [2..250] | not IsPrime(n)]; // _G. C. Greubel_, Feb 24 2024

%o (SageMath) [n for n in (2..250) if not is_prime(n)] # _G. C. Greubel_, Feb 24 2024

%Y Complement of A008578. - _Omar E. Pol_, Dec 16 2016

%Y Cf. A000040, A018252, A065090, A136527.

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

%Y Boustrophedon transforms: A230954, A230955.

%Y Cf. A163870 (nontrivial divisors).

%Y Related sequences:

%Y Primes (p) and composites (c): A000040, A002808, A000720, A065855.

%Y 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 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 nonn,nice,easy,core

%O 1,1

%A _N. J. A. Sloane_

%E Deleted an incomplete and broken link. - _N. J. A. Sloane_, Dec 16 2010