A158974 a(n) is the number of numbers k <= n such that not all proper divisors of k are divisors of n.

0, 0, 0, 0, 1, 0, 2, 1, 3, 3, 5, 1, 6, 5, 6, 6, 9, 6, 10, 7, 10, 11, 13, 7, 14, 14, 15, 14, 18, 12, 19, 16, 19, 20, 21, 16, 24, 23, 24, 20, 27, 22, 28, 25, 25, 29, 31, 23, 32, 30, 33, 32, 36, 31, 36, 32, 38, 39, 41, 31, 42, 41, 39, 40, 44, 41, 47, 44, 47, 43, 50, 40, 51, 50, 49, 50

Offset: 1

Author

Jaroslav Krizek, Apr 01 2009

Keywords

• nonn

Examples

			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) = 1.
		

Links

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

Crossrefs

Cf. A000040, A036234, A000720, A158973.

Programs

Magma

[ #[ k: k in [1..n] | exists(t){ d: d in Divisors(k) | d ne k and d notin Divisors(n) } ]: n in [1..76] ];

Maple

f:= proc(n) local d;
   d:= numtheory:-divisors(n);
   nops(remove(t -> (numtheory:-divisors(t) minus {t}) subset d, [$4..n-1]))
end proc:
map(f, [$1..100]); # Robert Israel, Mar 30 2020

Mathematica

a[n_] := Select[Most[Divisors[#]]& /@ Range[n], AnyTrue[#, !Divisible[n, #]&]&] // Length;
Array[a, 100] (* Jean-François Alcover, Jul 17 2020 *)

PARI

a(n) = my(dn = divisors(n)); sum(k=1, n, my(dk=setminus(divisors(k), Set(k))); #setintersect(dk, dn) != #dk); \\ Michel Marcus, Aug 27 2020

Formula

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

Extensions

Edited and extended by Klaus Brockhaus, Apr 06 2009