

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.


51



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, 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, 2, 32, 2, 4, 16, 1024, 4, 8, 2, 16, 4, 8, 2, 128, 2, 4, 16, 16, 4, 8
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

From Antti Karttunen, Aug 21 2018: (Start)
a(n) is the denominator of any rationalvalued sequence f(n) which has been defined as f(n) = (1/2) * (b(n)  Sum_{dn, d>1, d<n} f(d) * f(n/d)), with f(1) = 1, where b(n) is any integervalued 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).
Proof:
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 dn, 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.]
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 1bits in the shared positions. Let m = Sum_{e} A005187(e), with e ranging over the exponents in prime factorization of n.
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)].
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^(k1))) * f(p^(2^(k1))) 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^(k1))) + 1 = A005187(2^k) = A046645(p^(2^k)).
(End)
From Antti Karttunen, Aug 21 2018: (Start)
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, ...).
Numerators Dirichlet convolution of numerator(n)/a(n) yields
 
A046643 A000012
A257098 A008683
A317935 A003557
A318321 A003961
A317830 A175851
A317833 A078898
A317834 A078899
A317847 A303757
A317835 ε + A003415
A317845 ε + A001065
A317846 ε + A051953
A317936 ε + A100995
A317937 ε + A001221
A317938 ε + A001222
A317939 ε + A010051 (= A080339)
(End)
This sequence gives an upper bound for the denominators of any rationalvalued sequence obtained as the "Dirichlet Square Root" of any integervalued sequence.  Andrew Howroyd, Aug 23 2018


LINKS

Antti Karttunen, Table of n, a(n) for n = 1..8192
Wikipedia, Dirichlet convolution
Index entries for sequences computed from exponents in factorization of n


FORMULA

From Antti Karttunen, Jul 08 2017: (Start)
Multiplicative with a(p^n) = 2^A005187(n).
a(1) = 1; for n > 1, a(n) = A000079(A005187(A067029(n))) * a(A028234(n)).
a(n) = A000079(A046645(n)).
(End)


MATHEMATICA

b[1] = 1; b[n_] := b[n] = (dn = Divisors[n]; c = 1;
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] (* JeanFrançois Alcover, Apr 04 2011, after Maple code in A046643 *)
a18804[n_] := Sum[n EulerPhi[d]/d, {d, Divisors[n]}];
f[1] = 1; f[n_] := f[n] = 1/2 (a18804[n]  Sum[f[d] f[n/d], {d, Divisors[ n][[2 ;; 2]]}]);
a[n_] := f[n] // Denominator;
Array[a, 78] (* JeanFrançois Alcover, Sep 13 2018, after A318443 *)


PROG

(PARI)
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)); }
A046644(n) = denominator(A046643perA046644(n)); \\ After the Mapleprogram given in A046643, Antti Karttunen, Jul 08 2017
(PARI)
A005187(n) = { my(s=n); while(n>>=1, s+=n); s; };
A046644(n) = factorback(apply(e > 2^A005187(e), factor(n)[, 2])); \\ Antti Karttunen, Aug 12 2018
(Scheme, with memoizationmacro definec)
(definec (A046644 n) (if (= 1 n) n (* (A000079 (A005187 (A067029 n))) (A046644 (A028234 n))))) ;; Antti Karttunen, Jul 08 2017


CROSSREFS

Cf. A000079, A005187, A028234, A037445, A050376, A067029, A082522, A268388.
See A046643 for more details. See also A046645, A317940.
Cf. A299150, A299152, A317832, A317926, A317932, A317934 (for denominator sequences of other similar constructions).
Sequence in context: A029623 A325753 A208133 * A161915 A174354 A011147
Adjacent sequences: A046641 A046642 A046643 * A046645 A046646 A046647


KEYWORD

nonn,easy,frac,nice,mult


AUTHOR

N. J. A. Sloane


STATUS

approved



