A006579 -id:A006579 - cp's OEIS frontend

A003989 Triangle T from the array A(x, y) = gcd(x,y), for x >= 1, y >= 1, read by antidiagonals.

1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 1, 2, 1, 1, 1, 3, 1, 1, 3, 1, 1, 1, 2, 1, 2, 5, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 7, 2, 1, 2, 1, 2, 1, 1, 1, 3, 1, 5, 3, 1, 1, 3, 5, 1, 3, 1, 1, 1, 2, 1

Offset: 1

Marc LeBrun

For m < n, the maximal number of nonattacking queens that can be placed on the n by m rectangular toroidal chessboard is gcd(m,n), except in the case m=3, n=6.
The determinant of the matrix of the first n rows and columns is A001088(n). [Smith, Mansion] - Michael Somos, Jun 25 2012
Imagine a torus having regular polygonal cross-section of m sides. Now, break the torus and twist the free ends, preserving rotational symmetry, then reattach the ends. Let n be the number of faces passed in twisting the torus before reattaching it. For example, if n = m, then the torus has exactly one full twist. Do this for arbitrary m and n (m > 1, n > 0). Now, count the independent, closed paths on the surface of the resulting torus, where a path is "closed" if and only if it returns to its starting point after a finite number of times around the surface of the torus. Conjecture: this number is always gcd(m,n). NOTE: This figure constitutes a group with m and n the binary arguments and gcd(m,n) the resulting value. Twisting in the reverse direction is the inverse operation, and breaking & reattaching in place is the identity operation. - Jason Richardson-White, May 06 2013
Regarded as a triangle, table of gcd(n - k +1, k) for 1 <= k <= n. - Franklin T. Adams-Watters, Oct 09 2014
The n-th row of the triangle is 1,...,1, if and only if, n + 1 is prime. - Alexandra Hercilia Pereira Silva, Oct 03 2020

			The array A begins:
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
  [1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1]
  [1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 4]
  [1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1]
  [1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2]
  [1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 7, 1, 1]
  [1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8]
  [1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1]
  [1, 2, 1, 2, 5, 2, 1, 2, 1, 10, 1, 2, 1, 2, 5, 2]
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1]
  [1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12, 1, 2, 3, 4]
  ...
The triangle T begins:
  n\k 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
  1:  1
  2:  1  1
  3:  1  2  1
  4:  1  1  1  1
  5:  1  2  3  2  1
  6:  1  1  1  1  1  1
  7:  1  2  1  4  1  2  1
  8:  1  1  3  1  1  3  1  1
  9:  1  2  1  2  5  2  1  2  1
 10:  1  1  1  1  1  1  1  1  1  1
 11:  1  2  3  4  1  6  1  4  3  2  1
 12:  1  1  1  1  1  1  1  1  1  1  1  1
 13:  1  2  1  2  1  2  7  2  1  2  1  2  1
 14:  1  1  3  1  5  3  1  1  3  5  1  3  1  1
 15:  1  2  1  4  1  2  1  8  1  2  1  4  1  2  1
 ...  - _Wolfdieter Lang_, May 12 2018

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., 1994, ch. 4.
D. E. Knuth, The Art of Computer Programming, Addison-Wesley, section 4.5.2.

T. D. Noe, First 100 antidiagonals of array, flattened
Grant Cairns, Queens on Non-square Tori, El. J. Combinatorics, N6, 2001.
Marc Chamberland, Factored matrices can generate combinatorial identities, Linear Algebra and its Applications, Volume 438, Issue 4, 2013, pp. 1667-1677.
Warren P. Johnson, An LDU Factorization in Elementary Number Theory, Mathematics Magazine, Vol. 76, No. 5 (Dec., 2003), pp. 392-394.
P. Mansion, On an Arithmetical Theorem of Professor Smith's, Messenger of Mathematics, (1878), pp. 81-82.
Kival Ngaokrajang, Pattern of GCD(x,y) > 1 for x and y = 1..60. Non-isolated values larger than 1 (polyomino shapes) are colored.
Marcelo Polezzi, A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor, The American Mathematical Monthly, Vol. 104, No. 5 (May, 1997), pp. 445-446.
Mihai Prunescu and Joseph Shunia, Arithmetic-term representations for the greatest common divisor, arXiv:2411.06430 [math.NT], 2024.
H. J. S. Smith, On the value of a certain arithmetical determinant, Proc. London Math. Soc. 7 (1875-1876), pp. 208-212.
Index entries for sequences related to lcm's

Rows, columns and diagonals: A089128, A109007, A109008, A109009, A109010, A109011, A109012, A109013, A109014, A109015.
A109004 is (0, 0) based.
Cf.  A001088, A003990, A003991, A050873, A051731, A054431, A054522.
Cf. also A091255 for GF(2)[X] polynomial analog.
A(x, y) = A075174(A004198(A075173(x), A075173(y))) = A075176(A004198(A075175(x), A075175(y))).
Antidiagonal sums are in A006579.

Flat(List([1..15],n->List([1..n],k->Gcd(n-k+1,k)))); # Muniru A Asiru, Aug 26 2018

a:=(n,k)->gcd(n-k+1,k): seq(seq(a(n,k),k=1..n),n=1..15); # Muniru A Asiru, Aug 26 2018

Table[ GCD[x - y + 1, y], {x, 1, 15}, {y, 1, x}] // Flatten (* Jean-François Alcover, Dec 12 2012 *)

{A(n, m) = gcd(n, m)}; /* Michael Somos, Jun 25 2012 */

Multiplicative in both parameters with a(p^e, m) = gcd(p^e, m). - David W. Wilson, Jun 12 2005
T(n, k) = A(n - k + 1, k) = gcd(n - k + 1, k), n >= 1, k = 1..n. See a comment above and the Mathematica program. - Wolfdieter Lang, May 12 2018
Dirichlet generating function: Sum_{n>=1} Sum_{k>=1} gcd(n, k)/n^s/k^c = zeta(s)*zeta(c)*zeta(s + c - 1)/zeta(s + c). - Mats Granvik, Feb 13 2021
The LU decomposition of this square array = A051731 * transpose(A054522) (see Johnson (2003) or Chamberland (2013), p. 1673). - Peter Bala, Oct 15 2023

A051190 a(n) = Product_{k=1..n-1} gcd(k,n).

Original entry on oeis.org

1, 1, 1, 2, 1, 12, 1, 16, 9, 80, 1, 3456, 1, 448, 2025, 2048, 1, 186624, 1, 1024000, 35721, 11264, 1, 573308928, 625, 53248, 59049, 179830784, 1, 1007769600000, 1, 67108864, 7144929, 1114112, 37515625, 160489808068608, 1, 4980736, 89813529

Offset: 1

Antti Karttunen, Oct 21 1999

a(n) > 1 if and only if n is composite. - Charles R Greathouse IV, Jan 04 2013

T. D. Noe, Table of n, a(n) for n = 1..200
OEIS Wiki, Generalizations of the factorial

Cf. A067911, A006579, A224479, A092287.

a051190 n = product $ map (gcd n) [1..n-1]
-- Reinhard Zumkeller, Nov 22 2011

A051190 := proc(n) local i; mul(igcd(n, i ), i = 1..(n-1)) end;

a[n_] := If[PrimeQ[n], 1, Times @@ (GCD[n, #]& /@ Range[n-1])]; Table[a[n], {n, 1, 39}]  (* Jean-François Alcover, Jul 18 2012 *)
Table[Times @@ GCD[n, Range[n-1]], {n, 50}] (* T. D. Noe, Apr 12 2013 *)
Table[Product[GCD[k,n],{k,n-1}],{n,50}] (* Harvey P. Dale, Jan 29 2025 *)

a(n)=my(f=factor(n)); prod(i=1, #f[,1], prod(j=1, f[i,2], f[i,1]^(n\f[i,1]^j)))/n \\ Charles R Greathouse IV, Jan 04 2013

a(n) = prod(k=1,n-1,gcd(k,n)); /* Joerg Arndt, Apr 14 2013 */

A051190 = lambda n: mul(gcd(n,i) for i in (1..n-1))
[A051190(n) for n in (1..39)] # Peter Luschny, Apr 07 2013

# A second, faster version, based on the prime factorization of a(n):
def A051190(n):
    R = 1
    if not is_prime(n) :
        for p in primes(n//2+1):
            s = 0; r = n; t = n-1
            while r > 0 :
                r = r//p; t = t//p
                s += (r-t)*(r+t-1)
            R *= p^(s/2)
    return R
[A051190(i) for i in (1..1000)]  # Peter Luschny, Apr 08 2013

a(n) = Product_{ d divides n, d < n } d^phi(n/d). - Peter Luschny, Apr 07 2013
a(n) = A067911(n) / n. - Peter Luschny, Apr 07 2013
Product_{j=1..n} Product_{k=1..j-1} gcd(j,k), n >= 1. - Daniel Forgues, Apr 11 2013
a(n) = sqrt( (1/n) * (A092287(n) / A092287(n-1)) ). - Daniel Forgues, Apr 13 2013

A106475 An alternating sum of greatest common divisors.

Original entry on oeis.org

1, 0, 1, -4, 1, -8, 1, -16, -3, -16, 1, -36, 1, -24, -15, -48, 1, -48, 1, -68, -23, -40, 1, -112, -15, -48, -27, -100, 1, -120, 1, -128, -39, -64, -47, -180, 1, -72, -47, -208, 1, -176, 1, -164, -99, -88, 1, -304, -35, -160, -63, -196, 1, -216, -79, -304, -71, -112, 1, -420, 1, -120, -147, -320, -95, -288, 1, -260, -87

Offset: 0

Paul Barry, May 03 2005

With interpolated 0's, this is Sum_{k=0..n} gcd(n-k+1,k+1)*(-1)^k.

Antti Karttunen, Table of n, a(n) for n = 0..16384

Cf. A001620, A003989, A006579, A199084, A306016, A344371, A344372.

Negated bisection of A344373.

Table[Sum[GCD[2n-k+1,k+1](-1)^k,{k,0,2n}],{n,0,100}] (* Giorgos Kalogeropoulos, Mar 31 2021 *)

A106475(n) = sum(k=0,(2*n),gcd(1+n+n-k, k+1)*((-1)^k)); \\ Antti Karttunen, Mar 30 2021

a(n) = Sum_{k=0..2*n} gcd(2*n-k+1, k+1)*(-1)^k.
a(n) = 2(n+1) - A344371(2(n+1)) = 2(n+1) - A344372(n+1) = 2(n+1) + A199084(2(n+1)). - Max Alekseyev, May 16 2021
Sum_{k=1..n} a(k) ~ n^2 * (1 - (4/Pi^2)*(log(n) + 2*gamma - 1/2 - log(2)/3 - zeta'(2)/zeta(2))), where gamma is Euler's constant (A001620). - Amiram Eldar, Mar 30 2024

More terms from Antti Karttunen, Mar 30 2021

A093820 a(n) = Sum_{k=1..n-1} gcd(n, a(k)) for n > 1; a(1) = 1.

Original entry on oeis.org

1, 1, 2, 4, 4, 8, 6, 22, 10, 24, 20, 42, 12, 36, 32, 64, 16, 64, 18, 82, 50, 60, 22, 144, 60, 48, 64, 96, 28, 172, 30, 282, 78, 64, 70, 256, 36, 72, 106, 254, 80, 204, 84, 176, 166, 88, 92, 518, 78, 200, 136, 210, 104, 244, 134, 346, 96, 112, 58, 538, 120, 120, 216

Offset: 1

Reinhard Zumkeller, May 21 2004

nonn

a(n) = n-1 iff n is prime.

a(n) >= n-1. All terms except a(1) = a(2) = 1 are even. - Ivan Neretin, Apr 06 2016

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A006579.

Cf. A056144.

a093820 n = a093820_list !! (n-1)
a093820_list = 1 : f [2..] [1] where
   f (x:xs) ys = y : f xs (y:ys) where y = sum $ map (gcd x) ys
-- Reinhard Zumkeller, Oct 10 2013

Fold[Append[#1, Total@GCD[#1, #2]] &, {1}, Range[2, 64]] (* Ivan Neretin, Apr 06 2016 *)

lista(nn) = {va = vector(nn); va[1] = 1; for (i = 2, nn, va[i] = sum(k=1, i-1, gcd(i, va[k]));); va;} \\ Michel Marcus, Oct 04 2013

Definition corrected by Antti Karttunen, Jun 04 2004

A332049 a(n) = (1/2) * Sum_{d|n, d > 1} d * phi(d).

Original entry on oeis.org

0, 1, 3, 5, 10, 10, 21, 21, 30, 31, 55, 38, 78, 64, 73, 85, 136, 91, 171, 115, 150, 166, 253, 150, 260, 235, 273, 236, 406, 220, 465, 341, 388, 409, 451, 335, 666, 514, 549, 451, 820, 451, 903, 610, 640, 760, 1081, 598, 1050, 781, 955, 863, 1378, 820, 1165

Offset: 1

Ilya Gutkovskiy, Feb 06 2020

Sum of numerators of the reduced fractions 1/n, ..., (n-1)/n. Note that if n is a prime p this is p*(p-1)/2 as all fractions are already reduced. For 1/n, ..., n/n, see A057661.

			For n = 5, fractions are 1/5, 2/5, 3/5, 4/5, sum of numerators is 10.
For n = 8, fractions are 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8, sum of numerators is 21.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000010, A002618, A006579, A023896, A057660, A057661.

toNums a = fmap (numerator . (% a))
toNumList a = toNums a [1..(a-1)]
sumList = sum . toNumList <$> [2..200]

[0] cat [(1/2)*&+[ d*EulerPhi(d):d in Set(Divisors(n)) diff {1}]:n in [2..60]]; // Marius A. Burtea, Feb 07 2020

N:= 100: # for a(1)..a(N)
V:= Vector(N):
for d from 2 to N do
  v:= d*numtheory:-phi(d)/2;
  R:= [seq(i,i=d..N,d)];
  V[R]:= V[R] +~ v
od:
convert(V,list); # Robert Israel, Feb 07 2020

Table[(1/2) Sum[If[d > 1, d EulerPhi[d], 0], {d, Divisors[n]}], {n, 1, 55}]
nmax = 55; CoefficientList[Series[(1/2) Sum[EulerPhi[k^2] x^k/(1 - x^k), {k, 2, nmax}], {x, 0, nmax}], x] // Rest
Table[Sum[k/GCD[n, k], {k, 1, n - 1}], {n, 1, 55}]
Table[(DivisorSigma[2, n^2] - DivisorSigma[1, n^2])/(2 DivisorSigma[1, n^2]), {n, 1, 55}]

a(n) = sumdiv(n, d, if (d>1, d*eulerphi(d)))/2; \\ Michel Marcus, Feb 07 2020

G.f.: (1/2) * Sum_{k>=2} phi(k^2) * x^k / (1 - x^k).
a(n) = Sum_{k=1..n-1} k / gcd(n,k).
a(n) = (sigma_2(n^2) - sigma_1(n^2)) / (2 * sigma_1(n^2)).
a(n) = Sum_{d|n, d > 1} A023896(d).
a(n) = A057661(n) - 1 = (A057660(n) - 1) / 2.

A178881 Sum of all pairs of greatest common divisors for (i,j) where 1 <= i < j <= n.

Original entry on oeis.org

0, 1, 3, 7, 11, 20, 26, 38, 50, 67, 77, 105, 117, 142, 172, 204, 220, 265, 283, 335, 379, 420, 442, 518, 558, 607, 661, 737, 765, 870, 900, 980, 1052, 1117, 1199, 1331, 1367, 1440, 1526, 1666, 1706, 1859, 1901, 2025, 2169, 2258, 2304, 2496, 2580, 2725

Offset: 1

Enric Cusell (cusell(AT)gmail.com), Jun 20 2010

nonn

You could also be looking for the case where i = j is allowed, which gives A272718(n) = a(n) + n*(n+1)/2.

			Denote gcd(i,j) by (i,j), then a(6) = (1,2) + (1,3) + (1,4) + (1,5) + (1,6) + (2,3) + (2,4) + (2,5) + (2,6) + (3,4) + (3,5) + (3,6) + (4,5) + (4,6) + (5,6) = 20. - _Jianing Song_, Feb 07 2021

Akshay Bansal, Table of n, a(n) for n = 1..10000
Akshay Bansal, C program.
Olivier Bordellès, A note on the average order of the gcd-sum function, Journal of Integer Sequences, Vol. 10 (2007), Article 07.3.3.
Uva Online Judge Algorithm Problem number 11424.

Cf. A018806, A000010, A001620, A074962, A272718.

Partial sums of A006579.

f[p_, e_] := (e*(p - 1)/p + 1)*p^e; s[n_] := Times @@ f @@@ FactorInteger[n] - n; Accumulate[Array[s, 100]] (* Amiram Eldar, Dec 10 2024 *)

a(n)=sum(k=1, n, eulerphi(k)*(n\k)^2)/2-n*(n+1)/4 \\ Charles R Greathouse IV, Apr 11 2016

first(n)=my(v=vector(n),t); for(k=1,n, t=eulerphi(k); for(m=k,n, v[m] += t*(m\k)^2)); v/2-vector(n,k,k*(k+1)/4) \\ Charles R Greathouse IV, Apr 11 2016

a(n) = Sum_{i=1..n-1, j=i+1..n} gcd(i,j).
From Jianing Song, Feb 07 2021: (Start)
a(n) = (A018806(n) - n*(n+1)/2) / 2 = (Sum_{k=1..n} phi(k)*(floor(n/k))^2 - n*(n+1)/2) / 2, phi = A000010.
a(n) = A018806(n) - A272718(n).
According to Bordellès (2007), a(n) = (3/Pi^2)*n^2*log(n) + k*n^2 + O(n^(1+theta+epsilon)), where k = (3/Pi^2)*(gamma - 1/2 + log(A^12/(2*Pi))), gamma = A001620, A ~= 1.282427129 is the Glaisher-Kinkelin constant A074962, theta is a certain constant defined in terms of the divisor function and known to lie between 1/4 and 131/416, and epsilon is any positive number. See also A272718. (End)

A268631 Number of ordered pairs (a,b) of positive integers less than n with the property that n divides ab.

Original entry on oeis.org

0, 0, 0, 1, 0, 4, 0, 5, 4, 8, 0, 17, 0, 12, 16, 17, 0, 28, 0, 33, 24, 20, 0, 53, 16, 24, 28, 49, 0, 76, 0, 49, 40, 32, 48, 97, 0, 36, 48, 101, 0, 112, 0, 81, 100, 44, 0, 145, 36, 96, 64, 97, 0, 136, 80, 149, 72, 56, 0, 241, 0, 60, 148, 129, 96, 184, 0, 129, 88, 212

Offset: 1

Matthew McMullen, Feb 09 2016

nonn

a(n)=0 iff n is prime or 1. a(n) is odd iff n is a multiple of 4.

			For n=10 the a(10)=8 ordered pairs are (2,5), (5,2), (4,5), (5,4), (5,6), (6,5), (5,8), and (8,5).

Antti Karttunen, Table of n, a(n) for n = 1..20000

Cf. A006579.

a[n_] := Sum[Sum[1, {i, Divisors[n*k]}] - 2*Sum[1, {i, TakeWhile[Divisors[n*k], # <= k &]}], {k, 1, n - 1}]

a(n) = sum(k=1, n-1, sumdiv(n*k, d, (d > k) && (d < n))); \\ Michel Marcus, Feb 09 2016

from math import prod
from sympy import factorint
def A268631(n): return 1 - 2*n + prod(p**(e-1)*((p-1)*e+p) for p, e in factorint(n).items()) # Chai Wah Wu, May 15 2022

a(n) = Sum_{k=1..n-1} (number of divisors of nk that are between k and n, exclusive).
a(n) = Sum_{k=1..n-1} (number of divisors of nk - 2*(number of divisors of nk that are <= k)).
a(n) = A006579(n) - (n-1). - Michel Marcus, Feb 09 2016
a(p^k) = (p(k-1)-k)*p^(k-1)+1 for prime p. - Chai Wah Wu, May 15 2022

A069914 a(n) = Sum_{d|n} (d-1)*sigma(n/d).

Original entry on oeis.org

0, 1, 2, 6, 4, 15, 6, 23, 16, 27, 10, 64, 12, 39, 42, 72, 16, 98, 18, 110, 60, 63, 22, 213, 48, 75, 84, 156, 28, 245, 30, 201, 96, 99, 102, 380, 36, 111, 114, 357, 40, 345, 42, 248, 248, 135, 46, 618, 96, 278, 150, 294, 52, 478, 162, 501, 168, 171, 58, 924, 60, 183

Offset: 1

Vladeta Jovovic, May 04 2002

nonn

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A000203, A006579, A007429, A060640.

Table[Plus @@ (DivisorSigma[1, ds = Divisors[n]]*(n/ds - 1)), {n, 62}] (* Ivan Neretin, May 17 2015 *)

a(n) = sumdiv(n, d, (d-1)*sigma(n/d)) \\ Michel Marcus, Jun 17 2013

a(n) = A060640(n) - A007429(n).

G.f.: Sum_{k>=1} sigma(k) * x^(2*k) / (1 - x^k)^2. - Ilya Gutkovskiy, Aug 19 2021

A137324 a(n) = Sum_{prime p < n} gcd(n,p).

Original entry on oeis.org

1, 3, 2, 6, 3, 5, 6, 9, 4, 8, 5, 13, 12, 7, 6, 10, 7, 13, 16, 19, 8, 12, 13, 22, 11, 16, 9, 17, 10, 12, 23, 28, 21, 14, 11, 31, 26, 17, 12, 22, 13, 25, 20, 37, 14, 18, 21, 20, 33, 28, 15, 19, 30, 23, 36, 45, 16, 24, 17, 49, 26, 19, 34, 31, 18, 36, 43, 30, 19, 23, 20, 58, 27, 40, 37

Offset: 3

Max Sills, Apr 06 2008

			a(10) = 9 because gcd(10,2) = 2, gcd(10,3) = 1, gcd(10,5) = 5, gcd(10,7) = 1; 2 + 1 + 5 + 1 = 9.
The underlying irregular table of gcd(n,2), gcd(n,3), gcd(n,5), gcd(n,7), etc., for which a(n) provides row sums, is obtained by deleting columns from A050873(n,k) and looks as follows for n=3,4,5,...:
  1
  2 1
  1 1
  2 3 1
  1 1 1
  2 1 1 1
  1 3 1 1
  2 1 5 1
  1 1 1 1
  2 3 1 1 1
  1 1 1 1 1
  2 1 1 7 1 1
  1 3 5 1 1 1
  2 1 1 1 1 1
  1 1 1 1 1 1
  2 3 1 1 1 1 1
  1 1 1 1 1 1 1
  2 1 5 1 1 1 1 1

Cf. A000720, A006579, A048865, A105221.

[&+[Gcd(n,p):p in PrimesInInterval(1,n-1)]:n in [3..77]]; // Marius A. Burtea, Aug 07 2019

A137324 := proc(n) local a,i; a :=0 ; for i from 1 to numtheory[pi](n-1) do a := a+gcd(n,ithprime(i)) ; od: a; end: seq(A137324(n),n=3..80) ; # R. J. Mathar, Apr 09 2008

Table[Plus @@ GCD[n, Select[Range[n - 1], PrimeQ[ # ] &]], {n, 3, 70}] (* Stefan Steinerberger, Apr 09 2008 *)

a(n) = sum(k=1, n-1, gcd(n,k)*isprime(k)); \\ Michel Marcus, Nov 07 2014

from math import gcd
from sympy import primerange
def a(n): return sum(gcd(n, p) for p in primerange(1, n))
print([a(n) for n in range(3, 78)]) # Michael S. Branicky, Nov 21 2021

a(p) = A000720(p) - 1 for prime p. - R. J. Mathar, Apr 09 2008

a(n) = A048865(n) + A105221(n). - Wesley Ivan Hurt, Nov 21 2021

Corrected and extended by R. J. Mathar and Stefan Steinerberger, Apr 09 2008

cp's OEIS Frontend

A106474 a(n) = A006579(4n+4)/4.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A003989 Triangle T from the array A(x, y) = gcd(x,y), for x >= 1, y >= 1, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Formula

A051190 a(n) = Product_{k=1..n-1} gcd(k,n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Sage

Sage

Formula

A106475 An alternating sum of greatest common divisors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A093820 a(n) = Sum_{k=1..n-1} gcd(n, a(k)) for n > 1; a(1) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Extensions

A332049 a(n) = (1/2) * Sum_{d|n, d > 1} d * phi(d).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula