A182843 Number of composite integers greater than or equal to n whose proper divisors are all less than n.

0, 0, 1, 3, 3, 6, 6, 10, 10, 11, 11, 16, 16, 22, 22, 23, 23, 30, 30, 38, 38, 39, 39, 48, 48, 50, 50, 51, 51, 61, 61, 72, 72, 73, 73, 75, 75, 87, 87, 88, 88, 101, 101, 115, 115, 116, 116, 131, 131, 134, 134, 135, 135, 151, 151, 153, 153, 154, 154, 171, 171, 189, 189, 190, 190, 192, 192, 211, 211

Offset: 1

Author

Fintan Costello, Feb 28 2011

Keywords

• nonn

Examples

			Example: For n=4 the only composite integers greater than or equal to 4 all of whose proper divisors are all less than 4 are 4,6, and 9.  Since there are 3 such integers, a(4)=3.
		

Links

• Fintan Costello, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A010051, A038802.

Programs

Mathematica

Join[{0}, Table[Length[Select[Range[n, n^2], ! PrimeQ[#] && Divisors[#][[-2]] < n &]], {n, 2, 100}]] (* T. D. Noe, Feb 28 2011 *)

Formula

a(n+1) = a(n)+b(n)+c(n), where b(n) is 1 if n is prime, 0 otherwise (sequence A010051) and c(n) is the number of primes less than the minimum prime factor of n. Since b(2n)=c(2n)=0 for all n>1 we see that a(2n+1)=a(2n) for all n>1. Taking d(n) to represent sequence A038802 we have a(2n)=a(2n-1)+c(2n-1)+d(n-1).