A158973 a(n) = count of numbers k <= n such that all proper divisors of k are divisors of n.

1, 2, 3, 4, 4, 6, 5, 7, 6, 7, 6, 11, 7, 9, 9, 10, 8, 12, 9, 13, 11, 11, 10, 17, 11, 12, 12, 14, 11, 18, 12, 16, 14, 14, 14, 20, 13, 15, 15, 20, 14, 20, 15, 19, 20, 17, 16, 25, 17, 20, 18, 20, 17, 23, 19, 24, 19, 19, 18, 29, 19, 21, 24, 24, 21, 25, 20, 24, 22, 27, 21, 32, 22, 24, 26

Offset

1,2

Comments

For primes p, a(p) = A036234(p) = A000720(p) + 1.

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Formula

a(n) = A000005(n) + A004788(n-1). - Vladeta Jovovic, Apr 07 2009 (Corrected by Altug Alkan, Nov 25 2015)

Example

For n = 8 we have the following proper divisors for k <= n: {1}, {1}, {1}, {1, 2}, {1}, {1, 2, 3}, {1}, {1, 2, 4}. Only k = 6 has a proper divisor that is not a divisor of 8, viz. 3. Hence a(8) = 7.

Maple

N:= 1000: # to get a(1) to a(N)
A:= Vector(N, numtheory:-tau):
for p in select(isprime, [2, seq(i, i=3..N, 2)]) do
for d from 0 to floor(log[p](N))-1 do
  R:= [seq(seq(p^d*(i+p*j), j=1..floor((N/p^d - i)/p)), i=1..p-1)];
  A[R]:= map(`+`, A[R], 1);
od
od:
convert(A, list); # Robert Israel, Nov 24 2015

Mathematica

f[n_] := Block[{d = Most@ Divisors@ n}, Select[Range@ n, Union[Most@ Divisors@ #, d] == d &]]; Array[Length@ f@ # &, {75}] (* Michael De Vlieger, Nov 25 2015 *)

Prog

(Magma) [ #[ k: k in [1..n] | forall(t){ d: d in Divisors(k) | d eq k or d in Divisors(n) } ]: n in [1..75] ];
(PARI) a004788(n) = {sfp = Set(); for (k=1, n-1, sfp = setunion(sfp, Set(factor(binomial(n, k))[, 1]))); return (length(sfp)); }
a(n) = numdiv(n) + a004788(n-1); \\ Altug Alkan, Nov 25 2015

Crossrefs

Cf. A000040, A000720, A036234.

Sequence in context: A181833 A202650 A228286 * A071323 A071324 A361003

Adjacent sequences: A158970 A158971 A158972 * A158974 A158975 A158976

Keyword

nonn

Author

Jaroslav Krizek, Apr 01 2009

Extensions

Edited and extended by Klaus Brockhaus, Apr 06 2009

Status

approved