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

Author

Labos Elemer, Jun 13 2000

Keywords

• nonn
• easy
• mult

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

Examples

			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.
		

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.

Crossrefs

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

Programs

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 *)

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

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)