cp's OEIS Frontend

A046644 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.

%I A046644 #114 May 05 2025 16:38:39
%S A046644 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 A046644 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 A046644 2,32,2,4,16,1024,4,8,2,16,4,8,2,128,2,4,16,16,4,8
%N A046644 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 A046644 From _Antti Karttunen_, Aug 21 2018: (Start)
%C A046644 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 A046644 Proof:
%C A046644   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 A046644   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 A046644   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 A046644   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 A046644 (End)
%C A046644 From _Antti Karttunen_, Aug 21 2018: (Start)
%C A046644 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 A046644   Numerators   Dirichlet convolution of numerator(n)/a(n) yields
%C A046644   -------      -----------
%C A046644   A046643      A000012
%C A046644   A257098      A008683
%C A046644   A317935      A003557
%C A046644   A318321      A003961
%C A046644   A317830      A175851
%C A046644   A317833      A078898
%C A046644   A317834      A078899
%C A046644   A317847      A303757
%C A046644   A317835      ε + A003415
%C A046644   A317845      ε + A001065
%C A046644   A317846      ε + A051953
%C A046644   A317936      ε + A100995
%C A046644   A317937      ε + A001221
%C A046644   A317938      ε + A001222
%C A046644   A317939      ε + A010051 (= A080339)
%C A046644 (End)
%C A046644 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 A046644 Antti Karttunen, <a href="/A046644/b046644.txt">Table of n, a(n) for n = 1..8192</a>
%H A046644 Wikipedia, <a href="https://en.wikipedia.org/wiki/Dirichlet_convolution">Dirichlet convolution</a>
%H A046644 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%F A046644 From _Antti Karttunen_, Jul 08 2017: (Start)
%F A046644 Multiplicative with a(p^n) = 2^A005187(n).
%F A046644 a(1) = 1; for n > 1, a(n) = A000079(A005187(A067029(n))) * a(A028234(n)).
%F A046644 a(n) = A000079(A046645(n)).
%F A046644 (End)
%F A046644 Sum_{j=1..n} A046643(j)/A046644(j) ~ n / sqrt(Pi*log(n)) * (1 + (1 - gamma/2)/(2*log(n))), where gamma is the Euler-Mascheroni constant A001620. - _Vaclav Kotesovec_, May 04 2025
%t A046644 b[1] = 1; b[n_] := b[n] = (dn = Divisors[n]; c = 1;
%t A046644 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 A046644 a18804[n_] := Sum[n EulerPhi[d]/d, {d, Divisors[n]}];
%t A046644 f[1] = 1; f[n_] := f[n] = 1/2 (a18804[n] - Sum[f[d] f[n/d], {d, Divisors[ n][[2 ;; -2]]}]);
%t A046644 a[n_] := f[n] // Denominator;
%t A046644 Array[a, 78] (* _Jean-François Alcover_, Sep 13 2018, after A318443 *)
%o A046644 (PARI)
%o A046644 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 A046644(n) = denominator(A046643perA046644(n)); \\ After the Maple-program given in A046643, _Antti Karttunen_, Jul 08 2017
%o A046644 (PARI)
%o A046644 A005187(n) = { my(s=n); while(n>>=1, s+=n); s; };
%o A046644 A046644(n) = factorback(apply(e -> 2^A005187(e),factor(n)[,2])); \\ _Antti Karttunen_, Aug 12 2018
%o A046644 (PARI) for(n=1, 100, print1(denominator(direuler(p=2, n, 1/(1-X)^(1/2))[n]), ", ")) \\ _Vaclav Kotesovec_, May 04 2025
%o A046644 (Scheme)
%o A046644 ;; With memoization-macro definec.
%o A046644 (definec (A046644 n) (if (= 1 n) n (* (A000079 (A005187 (A067029 n))) (A046644 (A028234 n))))) ;; _Antti Karttunen_, Jul 08 2017
%Y A046644 Cf. A000079, A005187, A028234, A037445, A050376, A067029, A082522, A268388.
%Y A046644 See A046643 for more details. See also A046645, A317940.
%Y A046644 Cf. A299150, A299152, A317832, A317926, A317932, A317934 (for denominator sequences of other similar constructions).
%K A046644 nonn,easy,frac,nice,mult
%O A046644 1,2
%A A046644 _N. J. A. Sloane_