login
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.
54

%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_