cp's OEIS Frontend

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

%I A158973 #19 Sep 08 2022 08:45:43
%S A158973 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,
%T A158973 11,18,12,16,14,14,14,20,13,15,15,20,14,20,15,19,20,17,16,25,17,20,18,
%U A158973 20,17,23,19,24,19,19,18,29,19,21,24,24,21,25,20,24,22,27,21,32,22,24,26
%N A158973 a(n) = count of numbers k <= n such that all proper divisors of k are divisors of n.
%C A158973 For primes p, a(p) = A036234(p) = A000720(p) + 1.
%H A158973 Robert Israel, <a href="/A158973/b158973.txt">Table of n, a(n) for n = 1..10000</a>
%F A158973 a(n) = A000005(n) + A004788(n-1). - _Vladeta Jovovic_, Apr 07 2009 (Corrected by _Altug Alkan_, Nov 25 2015)
%e A158973 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.
%p A158973 N:= 1000: # to get a(1) to a(N)
%p A158973 A:= Vector(N, numtheory:-tau):
%p A158973 for p in select(isprime,[2,seq(i,i=3..N,2)]) do
%p A158973 for d from 0 to floor(log[p](N))-1 do
%p A158973   R:= [seq(seq(p^d*(i+p*j), j=1..floor((N/p^d - i)/p)), i=1..p-1)];
%p A158973   A[R]:= map(`+`,A[R],1);
%p A158973 od
%p A158973 od:
%p A158973 convert(A,list); # _Robert Israel_, Nov 24 2015
%t A158973 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 *)
%o A158973 (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] ];
%o A158973 (PARI) a004788(n) = {sfp = Set(); for (k=1, n-1, sfp = setunion(sfp, Set(factor(binomial(n, k))[, 1]))); return (length(sfp));}
%o A158973 a(n) = numdiv(n) + a004788(n-1); \\ _Altug Alkan_, Nov 25 2015
%Y A158973 Cf. A000040, A000720, A036234.
%K A158973 nonn
%O A158973 1,2
%A A158973 _Jaroslav Krizek_, Apr 01 2009
%E A158973 Edited and extended by _Klaus Brockhaus_, Apr 06 2009