%I #105 Sep 21 2018 02:11:04
%S 1,2,2,8,2,4,2,16,8,4,2,16,2,4,4,128,2,16,2,16,4,4,2,32,8,4,16,16,2,8,
%T 2,256,4,4,4,64,2,4,4,32,2,8,2,16,16,4,2,256,8,16,4,16,2,32,4,32,4,4,
%U 2,32,2,4,16,1024,4,8,2,16,4,8,2,128,2,4,16,16,4,8
%N From square root of Riemann zeta function: form Dirichlet series Sum b_n/n^s whose square is zeta function; sequence gives denominator of b_n.
%C From _Antti Karttunen_, Aug 21 2018: (Start)
%C a(n) is the denominator of any rational-valued sequence f(n) which has been defined as f(n) = (1/2) * (b(n) - Sum_{d|n, d>1, d<n} f(d) * f(n/d)), with f(1) = 1, where b(n) is any integer-valued sequence such that b(1) = 1 and b(p) = odd for all primes p. In other words, integer sequence b is obtained as the Dirichlet Convolution of rational sequence f (the latter is the "Dirichlet Square Root" of the former).
%C Proof:
%C Proof is by induction. We assume as our induction hypothesis that the given multiplicative formula for A046644 (resp. additive formula for A046645) holds for all proper divisors d|n, d<n. As base cases, we have a(1) = 1 and for primes p, as f(p) = b(p)/2 = odd/2, a(p) = 2 and A046645(p) = 1. [Remark: for squares of primes, f(p^2) = (4*b(p^2) - 1)/8, thus a(p^2) = 8.]
%C First we note that A005187(x+y) <= A005187(x) + A005187(y), with equivalence attained only when A004198(x,y) = 0, that is, when x and y do not have any 1-bits in the shared positions. Let m = Sum_{e} A005187(e), with e ranging over the exponents in prime factorization of n.
%C For [case A] any n in A268388 it happens that only when d (and thus also n/d) are infinitary divisors of n will Sum_{e} A005187(e) [where e now ranges over the union of multisets of exponents in the prime factorizations of d and n/d] attain value m, which is the maximum possible for such sums computed for all divisor pairs d and n/d. For any n in A268388, A037445(n) = 2^k, k >= 2, thus A037445(n) - 2 = 2 mod 4 (excluding 1 and n from the count, thus -2). Thus, in the recursive formula above, the maximal denominator that occurs in the sum is 2^m which occurs k times, with k being an even number, but not a multiple of 4, thus the factor (1/2) in the front of the whole sum will ensure that the denominator of the whole expression is 2^m [which thus is equal to 2^A046645(n) = a(n)].
%C On the other hand [case B], for squares in A050376 (A082522, numbers of the form p^(2^k) with p prime and k>0), all the sums A005187(x)+A005187(y), where x+y = 2^k, 0 < x <= y < 2^k are less than A005187(2^k), thus it is the lonely "middle pair" f(p^(2^(k-1))) * f(p^(2^(k-1))) among all the pairs f(d)*f(n/d), 1 < d < n = p^(2^k) which yields the maximal denominator. Furthermore, as it occurs an odd number of times (only once), the common factor (1/2) for the whole sum will increase the exponent of 2 in denominator by one, which will be (2*A005187(2^(k-1))) + 1 = A005187(2^k) = A046645(p^(2^k)).
%C (End)
%C From _Antti Karttunen_, Aug 21 2018: (Start)
%C The following list gives a few such pairs num(n), b(n) for which b(n) is Dirichlet convolution of num(n)/a(n). Here ε stands for sequence A063524 (1, 0, 0, ...).
%C Numerators Dirichlet convolution of numerator(n)/a(n) yields
%C ------- -----------
%C A046643 A000012
%C A257098 A008683
%C A317935 A003557
%C A318321 A003961
%C A317830 A175851
%C A317833 A078898
%C A317834 A078899
%C A317847 A303757
%C A317835 ε + A003415
%C A317845 ε + A001065
%C A317846 ε + A051953
%C A317936 ε + A100995
%C A317937 ε + A001221
%C A317938 ε + A001222
%C A317939 ε + A010051 (= A080339)
%C (End)
%C This sequence gives an upper bound for the denominators of any rational-valued sequence obtained as the "Dirichlet Square Root" of any integer-valued sequence. - _Andrew Howroyd_, Aug 23 2018
%H Antti Karttunen, <a href="/A046644/b046644.txt">Table of n, a(n) for n = 1..8192</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Dirichlet_convolution">Dirichlet convolution</a>
%H <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F From _Antti Karttunen_, Jul 08 2017: (Start)
%F Multiplicative with a(p^n) = 2^A005187(n).
%F a(1) = 1; for n > 1, a(n) = A000079(A005187(A067029(n))) * a(A028234(n)).
%F a(n) = A000079(A046645(n)).
%F (End)
%t b[1] = 1; b[n_] := b[n] = (dn = Divisors[n]; c = 1;
%t Do[c = c - b[dn[[i]]]*b[n/dn[[i]]], {i, 2, Length[dn] - 1}]; c/2); a[n_] := Denominator[b[n]]; a /@ Range[78] (* _Jean-François Alcover_, Apr 04 2011, after Maple code in A046643 *)
%t a18804[n_] := Sum[n EulerPhi[d]/d, {d, Divisors[n]}];
%t f[1] = 1; f[n_] := f[n] = 1/2 (a18804[n] - Sum[f[d] f[n/d], {d, Divisors[ n][[2 ;; -2]]}]);
%t a[n_] := f[n] // Denominator;
%t Array[a, 78] (* _Jean-François Alcover_, Sep 13 2018, after A318443 *)
%o (PARI)
%o A046643perA046644(n) = { my(c=1); if(1==n,c,fordiv(n,d, if((d>1)&&(d<n), c -= (A046643perA046644(d)*A046643perA046644(n/d)))); (c/2)); }
%o A046644(n) = denominator(A046643perA046644(n)); \\ After the Maple-program given in A046643, _Antti Karttunen_, Jul 08 2017
%o (PARI)
%o A005187(n) = { my(s=n); while(n>>=1, s+=n); s; };
%o A046644(n) = factorback(apply(e -> 2^A005187(e),factor(n)[,2])); \\ _Antti Karttunen_, Aug 12 2018
%o (Scheme, with memoization-macro definec)
%o (definec (A046644 n) (if (= 1 n) n (* (A000079 (A005187 (A067029 n))) (A046644 (A028234 n))))) ;; _Antti Karttunen_, Jul 08 2017
%Y Cf. A000079, A005187, A028234, A037445, A050376, A067029, A082522, A268388.
%Y See A046643 for more details. See also A046645, A317940.
%Y Cf. A299150, A299152, A317832, A317926, A317932, A317934 (for denominator sequences of other similar constructions).
%K nonn,easy,frac,nice,mult
%O 1,2
%A _N. J. A. Sloane_