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,7

Links

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

Formula

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

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

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 *)

Prog

(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] ];
(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

Crossrefs

Cf. A000040, A036234, A000720, A158973.

Sequence in context: A032140 A032044 A321762 * A355659 A152993 A178133

Adjacent sequences: A158971 A158972 A158973 * A158975 A158976 A158977

Keyword

nonn

Author

Jaroslav Krizek, Apr 01 2009

Extensions

Edited and extended by Klaus Brockhaus, Apr 06 2009

Status

approved