cp's OEIS Frontend

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

%I A158974 #16 Sep 08 2022 08:45:43
%S A158974 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,
%T A158974 12,19,16,19,20,21,16,24,23,24,20,27,22,28,25,25,29,31,23,32,30,33,32,
%U A158974 36,31,36,32,38,39,41,31,42,41,39,40,44,41,47,44,47,43,50,40,51,50,49,50
%N A158974 a(n) is the number of numbers k <= n such that not all proper divisors of k are divisors of n.
%H A158974 Robert Israel, <a href="/A158974/b158974.txt">Table of n, a(n) for n = 1..10000</a>
%F A158974 For primes p, a(p) = p - A036234(p) = p - A000720(p) - 1.
%e A158974 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.
%p A158974 f:= proc(n) local d;
%p A158974    d:= numtheory:-divisors(n);
%p A158974    nops(remove(t -> (numtheory:-divisors(t) minus {t}) subset d, [$4..n-1]))
%p A158974 end proc:
%p A158974 map(f, [$1..100]); # _Robert Israel_, Mar 30 2020
%t A158974 a[n_] := Select[Most[Divisors[#]]& /@ Range[n], AnyTrue[#, !Divisible[n, #]&]&] // Length;
%t A158974 Array[a, 100] (* _Jean-François Alcover_, Jul 17 2020 *)
%o A158974 (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] ];
%o A158974 (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
%Y A158974 Cf. A000040, A036234, A000720, A158973.
%K A158974 nonn
%O A158974 1,7
%A A158974 _Jaroslav Krizek_, Apr 01 2009
%E A158974 Edited and extended by _Klaus Brockhaus_, Apr 06 2009