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

%I #16 Sep 08 2022 08:45:43

%S 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 12,19,16,19,20,21,16,24,23,24,20,27,22,28,25,25,29,31,23,32,30,33,32,

%U 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 a(n) is the number of numbers k <= n such that not all proper divisors of k are divisors of n.

%H Robert Israel, <a href="/A158974/b158974.txt">Table of n, a(n) for n = 1..10000</a>

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

%e 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 f:= proc(n) local d;

%p d:= numtheory:-divisors(n);

%p nops(remove(t -> (numtheory:-divisors(t) minus {t}) subset d, [$4..n-1]))

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, Mar 30 2020

%t a[n_] := Select[Most[Divisors[#]]& /@ Range[n], AnyTrue[#, !Divisible[n, #]&]&] // Length;

%t Array[a, 100] (* _Jean-François Alcover_, Jul 17 2020 *)

%o (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 (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 Cf. A000040, A036234, A000720, A158973.

%K nonn

%O 1,7

%A _Jaroslav Krizek_, Apr 01 2009

%E Edited and extended by _Klaus Brockhaus_, Apr 06 2009