A347494 - OEIS

%I #31 Sep 25 2021 03:44:36

%S 0,1,2,1,3,4,4,6,2,7,5,8,6,10,11,1,7,11,8,13,14,15,9,17,3,17,18,16,10,

%T 21,11,19,21,22,23,4,12,25,26,29,13,31,14,23,24,29,15,17,4,27,31,28,

%U 16,37,33,39,34,35,17,50,18,38,32,1,39,46,19,34,41,49,20,59

%N a(n) is the number of instances where tau(k)|tau(n); n>=1, k<n, where tau is the divisor counting function A000005.

%C a(n) >= 1, for n >= 2; equality only when n = 2^(p-1) for any prime p. More generally, if p is prime(m), q any prime, and n=p^(q-1) then tau(n) = q, and the only numbers k < m  such that tau(k)|tau(n) are 1 and q. Every prime < p contributes 1 to the count of a(n), and so does 1 itself, therefore a(n) = m-1+1 = m; see formula. Since for a given m, this holds for all primes q, it follows that every m > 0 appears in the sequence infinitely many times.

%H David A. Corneth, <a href="/A347494/b347494.txt">Table of n, a(n) for n = 1..10001</a>

%F a(prime(m)^(q-1)) = m  for m >= 1 and any prime q.

%e a(1) = 0 because there is no k < 1 such that tau(k)|tau(1).

%e a(2) = 1, since there is only one instance of tau(k)|tau(2), namely k=1.

%e a(3) = 2, since there are two instances of tau(k)|tau(3), namely k=1 and k=2.

%e a(4) = 3, since there is only one instance of tau(k)|tau(4), namely k=1, etc.

%t With[{s = DivisorSigma[0, Range[72]]}, Array[Count[Mod[#2, s[[Range[#1 - 1]]]], 0] & @@ {#, s[[#]]} &, Length[s] - 1, 2]] (* _Michael De Vlieger_, Sep 09 2021 *)

%o (PARI) first(n) = {my(l = List(), res = vector(n)); for(i = 1, n, nd = numdiv(i); if(nd > #l, for(i = #l + 1, nd, listput(l, 0) ) ); d = divisors(nd); for(j = 1, #d, res[i] += l[d[j]] ); l[nd]++; ); res } \\ _David A. Corneth_, Sep 03 2021

%Y Cf: A000005, A010553, A047983, A010553.

%K nonn

%O 1,3

%A _David James Sycamore_, Aug 31 2021