A055076 Multiplicity of Max{gcd(d, n/d)} when d runs over divisors of n.

1, 2, 2, 1, 2, 4, 2, 2, 1, 4, 2, 2, 2, 4, 4, 1, 2, 2, 2, 2, 4, 4, 2, 4, 1, 4, 2, 2, 2, 8, 2, 2, 4, 4, 4, 1, 2, 4, 4, 4, 2, 8, 2, 2, 2, 4, 2, 2, 1, 2, 4, 2, 2, 4, 4, 4, 4, 4, 2, 4, 2, 4, 2, 1, 4, 8, 2, 2, 4, 8, 2, 2, 2, 4, 2, 2, 4, 8, 2, 2, 1, 4, 2, 4, 4, 4, 4, 4, 2, 4, 4, 2, 4, 4, 4, 4, 2, 2, 2, 1, 2, 8, 2, 4, 8

Offset

1,2

Comments

Number of distinct values of gcd(d, n!/d) if d runs over divisors of n! seems to be A046951(n).

a(n) = 1 iff n is a square. - Bernard Schott, Oct 22 2019

a(n) is the number of the unitary divisors (cf. A077610) of n that are exponentially odd (A268335). - Amiram Eldar, Nov 11 2022

The number of infinitary divisors of n that are squarefree (A005117). - Amiram Eldar, Jan 09 2024

Links

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Vaclav Kotesovec, Graph - the asymptotic ratio (100000 terms).

Christian Krause, LODA, an assembly language, a computational model and a tool for mining integer sequences.

Index entries for sequences computed from exponents in factorization of n.

Formula

Multiplicative with a(p^e) = 2^(e mod 2). - Vladeta Jovovic, Dec 13 2002

a(n) = 2^A162642(n). - Antti Karttunen, Dec 02 2017

a(n) = A034444(A007913(n)). [Found by LODA miner, see C. Krause link. Essentially the same formula as the above ones] - Antti Karttunen, Apr 05 2021

From Amiram Eldar, Sep 09 2023: (Start)

a(n) = A034444(A350389(n)).

Dirichlet g.f.: zeta(2*s) * Product_{p prime} (1 + 2/p^s). (End)

From Vaclav Kotesovec, Sep 09 2023: (Start)

Let f(s) = Product_{p prime} (1 - 3/p^(2*s) + 2/p^(3*s)).

Dirichlet g.f.: zeta(s)^2 * zeta(2*s) * f(s).

Sum_{k=1..n} a(k) ~ (Pi^2 * f(1) * n / 6) * (log(n) + 2*gamma - 1 + 12*zeta'(2)/Pi^2 + f'(1)/f(1)), where

f(1) = A065473 = Product_{primes p} (1 - 3/p^2 + 2/p^3) = 0.286747428434478734107892712789838446434331844097056995641477859336652243...,

f'(1) = f(1) * Sum_{primes p} 6*log(p) / (p^2 + p - 2) = f(1) * 2.798014228561519243358371276385174449737670294137200281334256087932048625...

and gamma is the Euler-Mascheroni constant A001620. (End)

Example

n=120, the set of gcd(d, 120/d) values for the 16 divisors of 120 is {1,2,1,2,1,2,1,2,2,1,2,1,2,1,2,1}. The max is 2 and it occurs 8 times, so a(120)=8. This sequence seems to consist of powers of 2.

Maple

with(numtheory):
a:= n->(p->coeff(p, x, degree(p)))(add(x^igcd(d, n/d), d=divisors(n))):
seq(a(n), n=1..105);  # Alois P. Heinz, Jul 21 2015

Mathematica

a[n_] := With[{g = GCD[#, n/#]& /@ Divisors[n]}, Count[g, Max[g]]];
Array[a, 105] (* Jean-François Alcover, Mar 28 2017 *)
f[p_, e_] := 2^Mod[e, 2]; a[n_] := Times @@ f @@@ FactorInteger[n]; a[1] = 1; Array[a, 100] (* Amiram Eldar, Nov 11 2022 *)

Prog

(PARI) A055076(n) = if(1==n, n, my(es=factor(n)[, 2]~); prod(i=1, #es, 2^(es[i]%2))); \\ Antti Karttunen, Apr 05 2021
(Scheme, with memoization-macro definec)
(definec (A055076 n) (if (= 1 n) n (* (+ 1 (A000035 (A067029 n))) (A055076 (A028234 n))))) ;; Antti Karttunen, Dec 02 2017

Crossrefs

Cf. A000188, A005117, A007913, A034444, A077610, A162642, A268335, A295316, A350389.

Sequence in context: A354349 A278763 A278762 * A069780 A369307 A366308

Adjacent sequences: A055073 A055074 A055075 * A055077 A055078 A055079

Keyword

nonn,easy,mult

Author

Labos Elemer, Jun 13 2000

Status

approved