A050873 -id:A050873 - cp's OEIS frontend

A255655 The sum of the odd terms in row n of A050873.

1, 1, 5, 2, 9, 5, 13, 4, 21, 9, 21, 10, 25, 13, 45, 8, 33, 21, 37, 18, 65, 21, 45, 20, 65, 25, 81, 26, 57, 45, 61, 16, 105, 33, 117, 42, 73, 37, 125, 36, 81, 65, 85, 42, 189, 45, 93, 40, 133, 65, 165, 50, 105, 81, 189, 52, 185, 57, 117, 90

Offset: 1

Geoffrey Critzer, Mar 01 2015

			a(10)=9 because row 10 of A050873 is gcd(10,k) for k=1,2,...10: 1, 2, 1, 2, 5, 2, 1, 2, 1, 10. If we sum the odd terms in this row we have 1+1+5+1+1=9.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A001620, A018804, A050873, A193356.

nn = 60; f[list_, i_] := list[[i]]; a =Table[EulerPhi[n], {n, 1, nn}]; b =
Table[If[OddQ[n], n, 0], {n, 1, nn}]; Table[DirichletConvolve[f[a, n], f[b, n], n, m], {m, 1, nn}]
Table[Sum[(d*(1-(-1)^d)/2)*EulerPhi[n/d], {d, Divisors[n]}], {n, 1, 50}] (* Vaclav Kotesovec, Feb 02 2019 *)
f[p_, e_] := p^(e-1) * If[p == 2, 1, (p-1)*e + p]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Apr 30 2023 *)

a(n) = sum(k=1, n, my(g = gcd(n, k)); if (g % 2, g, 0)); \\ Michel Marcus, Feb 05 2018

For odd n, a(n) = A018804(n).
Dirichlet g.f.: zeta(s-1)^2*(1 - 2^(1-s))/zeta(s).
a(n) = Sum_{d|n} A193356(d)*A000010(n/d). - Werner Schulte, Feb 04 2018
Multiplicative with a(2^e)=2^(e-1) for e>0 and a(p^e)=((p-1)*e+p)*p^(e-1) for e>0 and p>2. - Werner Schulte, Feb 04 2018
Sum_{k=1..n} a(k) ~ 3*n^2 / (2*Pi^2) * (log(n) - 1/2 + 2*gamma + log(2) - 6*Zeta'(2)/Pi^2), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Feb 02 2019

A018804 Pillai's arithmetical function: Sum_{k=1..n} gcd(k, n).

Original entry on oeis.org

1, 3, 5, 8, 9, 15, 13, 20, 21, 27, 21, 40, 25, 39, 45, 48, 33, 63, 37, 72, 65, 63, 45, 100, 65, 75, 81, 104, 57, 135, 61, 112, 105, 99, 117, 168, 73, 111, 125, 180, 81, 195, 85, 168, 189, 135, 93, 240, 133, 195, 165, 200, 105, 243, 189, 260, 185, 171, 117, 360

Offset: 1

David W. Wilson

a(n) is the number of times the number 1 appears in the character table of the cyclic group C_n. - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 02 2001
a(n) is the number of ways to express all fractions f/g whereby each product (f/g)*n is a natural number between 1 and n (using fractions of the form f/g with 1 <= f,g <= n). For example, for n=4 there are 8 such fractions: 1/1, 1/2, 2/2, 3/3, 1/4, 2/4, 3/4 and 4/4. - Ron Lalonde (ronronronlalonde(AT)hotmail.com), Oct 03 2002
Number of non-congruent solutions to xy == 0 (mod n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 06 2003
Conjecture: n>1 divides a(n)+1 iff n is prime. - Thomas Ordowski, Oct 22 2014
The above conjecture is false, with counterexample given by n = 3*37*43*42307*116341 and a(n)+1 = 26*n. - Varun Vejalla, Jun 19 2025
a(n) is the number of 0's in the multiplication table Z/nZ (cf. A000010 for number of 1's). - Eric Desbiaux, Jun 11 2015
{a(n)} == 1, 3, 1, 0, 1, 3, 1, 0, ... (mod 4). - Isaac Saffold, Dec 30 2017
Since a(p^e) = p^(e-1)*((p-1)e+p) it follows a(p) = 2p-1 and therefore p divides a(p)+1. - Ruediger Jehn, Jun 23 2022

			G.f. = x + 3*x^2 + 5*x^3 + 8*x^4 + 9*x^5 + 15*x^6 + 13*x^7 + 20*x^8 + ...

S. S. Pillai, On an arithmetic function, J. Annamalai University 2 (1933), pp. 243-248.
J. Sándor, A generalized Pillai function, Octogon Mathematical Magazine Vol. 9, No. 2 (2001), 746-748.

Seiichi Manyama, Table of n, a(n) for n = 1..10000 (first 2000 terms from T. D. Noe)
U. Abel, W. Awan, and V. Kushnirevych, A Generalization of the Gcd-Sum Function, J. Int. Seq. 16 (2013) #13.6.7.
Antal Bege, Hadamard product of GCD matrices, Acta Univ. Sapientiae, Mathematica, 1, 1 (2009) 43-49.
Olivier Bordelles, The Composition of the gcd and Certain Arithmetic Functions, J. Int. Seq. 13 (2010) #10.7.1.
Olivier Bordelles, An Asymptotic Formula for Short Sums of Gcd-Sum Functions, Journal of Integer Sequences, Vol. 15 (2012), #12.6.8.
Olivier Bordelles, A Multidimensional Cesáro Type Identity and Applications, J. Int. Seq. 18 (2015) # 15.3.7.
Kevin A. Broughan, The gcd-sum function, Journal of Integer Sequences 4 (2001), Article 01.2.2, 19 pp.
J.-M. De Koninck and I. Kátai, Some remarks on a paper of L. Toth, JIS 13 (2010) 10.1.2.
Pentti Haukkanen and László Tóth, Menon-type identities again: Note on a paper by Li, Kim and Qiao, arXiv:1911.05411 [math.NT], 2019.
Soichi Ikeda and Kaneaki Matsuoka, On the Lcm-Sum Function, Journal of Integer Sequences, Vol. 17 (2014), Article 14.1.7.
Mathematical Reflections, Solution to Problem O364, Issue 2, 2016, p 24. [Cached copy at Wayback Machine]
Taylor McAdam, Almost-primes in horospherical flows on the space of lattices, arXiv:1802.08764 [math.DS], 2018.
Taylor McAdam, Almost-prime times in horospherical flows on the space of lattices, Journal of Modern Dynamics (2019) Vol. 15, 277-327.
J. Ransford, A Sum of Gcd’s over Friable Numbers, JIS vol 19 (2016) # 16.3.2
Jeffrey Shallit, Problem E 2821, American Mathematical Monthly 87 (1980), 220.
Jeffrey Shallit, Solution, American Mathematical Monthly, 88 (1981), 444-445.
László Tóth, A gcd-sum function over regular integers modulo n, JIS 12 (2009) 09.2.5.
László Tóth, On the Bi-Unitary Analogues of Euler's Arithmetical Function and the Gcd-Sum Function, JIS 12 (2009) 09.5.2.
László Tóth, A survey of gcd-sum functions, J. Integer Sequences 13 (2010), Article 10.8.1, 23 pp.
László Tóth, Weighted gcd-sum functions, J. Integer Sequences, 14 (2011), Article 11.7.7.
D. Zhang and W. Zhai, Mean Values of a Gcd-Sum Function Over Regular Integers Modulo n, J. Int. Seq. 13 (2010), 10.4.7.
D. Zhang and W. Zhai, Mean Values of a Class of Arithmetical Functions, J. Int. Seq. 14 (2011) #11.6.5.
D. Zhang and W. Zhai, On an Open Problem of Tóth, J. Int. Seq. 16 (2013) #13.6.5.

Column 1 of A343510 and A343516.
Cf. A080997, A080998 for rankings of the positive integers in terms of centrality, defined to be the average fraction of an integer that it shares with the other integers as a gcd, or A018804(n)/n^2, also A080999, a permutation of this sequence (A080999(n) = A018804(A080997(n))).
Cf. A185210, A010766, A054523, A127468, A050873, A078430, A095026, A227507, A000010, A344372, A272718 (partial sums), A368736 - A368741.

a018804 n = sum $ map (gcd n) [1..n]  -- Reinhard Zumkeller, Jul 16 2012

[&+[Gcd(n,k):k in [1..n]]:n in [1..60]]; // Marius A. Burtea, Nov 14 2019

a:=n->sum(igcd(n,j),j=1..n): seq(a(n), n=1..60); # Zerinvary Lajos, Nov 05 2006

f[n_] := Block[{d = Divisors[n]}, Sum[ d*EulerPhi[n/d], {d, d}]]; Table[f[n], {n, 60}] (* Robert G. Wilson v, Mar 20 2012 *)
a[ n_] := If[ n < 1, 0, n Sum[ EulerPhi[d] / d, {d, Divisors@n}]]; (* Michael Somos, Jan 07 2017 *)
f[p_, e_] := (e*(p - 1)/p + 1)*p^e; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* Amiram Eldar, Jul 19 2019 *)

{a(n) = direuler(p=2, n, (1 - X) / (1 - p*X)^2)[n]}; /* Michael Somos, May 31 2000 */

a(n)={ my(ct=0); for(i=0,n-1,for(j=0,n-1, ct+=(Mod(i*j,n)==0) ) ); ct; } \\ Joerg Arndt, Aug 03 2013

a(n)=my(f=factor(n)); prod(i=1,#f~,(f[i,2]*(f[i,1]-1)/f[i,1] + 1)*f[i,1]^f[i,2]) \\ Charles R Greathouse IV, Oct 28 2014

a(n) = sumdiv(n, d, n*eulerphi(d)/d); \\ Michel Marcus, Jan 07 2017

from sympy.ntheory import totient, divisors
print([sum(n*totient(d)//d for d in divisors(n)) for n in range(1, 101)]) # Indranil Ghosh, Apr 04 2017

from sympy import factorint
from math import prod
def A018804(n): return prod(p**(e-1)*((p-1)*e+p) for p, e in factorint(n).items()) # Chai Wah Wu, Nov 29 2021

a(n) = Sum_{d|n} d*phi(n/d), where phi(n) is Euler totient function (cf. A000010). - Vladeta Jovovic, Apr 04 2001
Multiplicative; for prime p, a(p^e) = p^(e-1)*((p-1)e+p).
Dirichlet g.f.: zeta(s-1)^2/zeta(s).
a(n) = Sum_{d|n} d*tau(d)*mu(n/d). - Benoit Cloitre, Oct 23 2003
Equals A054523 * [1,2,3,...]. Equals row sums of triangle A010766. - Gary W. Adamson, May 20 2007
Equals inverse Mobius transform of A029935 = A054525 * (1, 2, 4, 5, 8, 8, 12, 12, ...). - Gary W. Adamson, Aug 02 2008, corrected Feb 07 2023
Equals row sums of triangle A127478. - Gary W. Adamson, Aug 03 2008
G.f.: Sum_{k>=1} phi(k)*x^k/(1 - x^k)^2, where phi(k) is the Euler totient function. - Ilya Gutkovskiy, Jan 02 2017
a(n) = Sum_{a = 1..n} Sum_{b = 1..n} Sum_{c = 1..n} 1, for n > 1. The sum is over a,b,c such that n*c - a*b = 0. - Benedict W. J. Irwin, Apr 04 2017
Proof: Let gcd(a, n) = g and x = n/g. Define B = {x, 2*x, ..., g*x}; then for all b in B there exists a number c such that a*b = n*c. Since the set B has g elements it follows that Sum_{b=1..n} Sum_{c=1..n} 1 >= g = gcd(a, n) and therefore Sum_{a=1..n} Sum_{b=1..n} Sum_{c=1..n} 1 >= Sum_{a=1..n} gcd(a, n). On the other hand, for all b not in B there is no number c <= n such that a*b = n*c and hence Sum_{b = 1..n} Sum_{c = 1..n} 1 = g. Therefore Sum_{a=1..n} Sum_{b = 1..n} Sum_{c = 1..n} 1 = a(n). - Ruediger Jehn, Jun 23 2022
a(2*n) = a(n)*(3-A007814(n)/(A007814(n)+2)) - Velin Yanev, Jun 30 2017
Proof: Let m = A007814(m) and decompose n into n = k*2^m. We know from Chai Wah Wu's program below that a(n) = Product(p_i^(e_i-1)*((p_i-1)*e_i+p_i)) where the numbers p_i are the prime factors of n and e_i are the corresponding exponents. Hence a(2n) = 2^m*(m+3)*a(k) = 2^m*(m+3)*a(k). On the other hand, a(n) = 2^(m-1)*(m+2)*a(k). Dividing the first equation by the second yields a(2n)/a(n) = 2*(m+3)/(m+2), which equals 3 - m/(m+2). Hence a(2n) = a(n)*(3 - m/(m+2)). - Ruediger Jehn, Jun 23 2022
Sum_{k=1..n} a(k) ~ 3*n^2/Pi^2 * (log(n) - 1/2 + 2*gamma - 6*Zeta'(2)/Pi^2), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Feb 08 2019
a(n) = Sum_{k=1..n} n/gcd(n,k)*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 10 2021
log(a(n)/n) << log n log log log n/log log n; in particular, a(n) << n^(1+e) for any e > 0. See Broughan link for bounds in terms of omega(n). - Charles R Greathouse IV, Sep 08 2022
a(n) = (1/4)*Sum_{k = 1..4*n} (-1)^k * gcd(k, 4*n) = (1/4) * A344372(2*n). - Peter Bala, Jan 01 2024

A022998 If n is odd then n, otherwise 2n.

Original entry on oeis.org

0, 1, 4, 3, 8, 5, 12, 7, 16, 9, 20, 11, 24, 13, 28, 15, 32, 17, 36, 19, 40, 21, 44, 23, 48, 25, 52, 27, 56, 29, 60, 31, 64, 33, 68, 35, 72, 37, 76, 39, 80, 41, 84, 43, 88, 45, 92, 47, 96, 49, 100, 51, 104, 53, 108, 55, 112, 57, 116, 59, 120, 61, 124, 63, 128, 65, 132, 67

Offset: 0

N. J. A. Sloane

Also for n > 0: numerator of Sum_{i=1..n} 2/(i*(i+1)), denominator=A026741. - Reinhard Zumkeller, Jul 25 2002
For n > 2: a(n) = gcd(A143051((n-1)^2), A143051(1+(n-1)^2)) = A050873(A000290(n-1), A002522(n-1)). - Reinhard Zumkeller, Jul 20 2008
Partial sums give the generalized octagonal numbers A001082. - Omar E. Pol, Sep 10 2011
Multiples of 4 and odd numbers interleaved. - Omar E. Pol, Sep 25 2011
The Pisano period lengths modulo m appear to be A066043(m). - R. J. Mathar, Oct 08 2011
The partial sums a(n)/A026741(n+1) given by R. Zumkeller in a comment above are 2*n/(n+1) (telescopic sum), and thus converge to 2. - Wolfdieter Lang, Apr 09 2013
a(n) = numerator(H(n,1)), where H(n,1) = 2*n/(n+1) is the harmonic mean of 1 and n. a(n) = 2*n/gcd(2n, n+1) = 2*n/gcd(n+1,2). a(n) = A227041(n,1), n>=1. - Wolfdieter Lang, Jul 04 2013
a(n) = numerator of the mean (2n/(n+1), after reduction), of the compositions of n; denominator is given by A001792(n-1). - Clark Kimberling, Mar 11 2014
A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n,m)) for all natural numbers n and m. The sequence of convergents of the 2-periodic continued fraction [0; 1, -4, 1, -4, ...] = 1/(1 - 1/(4 - 1/(1 - 1/(4 - ...)))) begins [0/1, 1/1, 4/3, 3/2, 8/5, 5/3, 12/7, ...]. The present sequence is the sequence of numerators. The sequence of denominators of the continued fraction convergents [1, 1, 3, 2, 5, 3, 7, ...] is A026741, also a strong divisibility sequence. Cf. A203976. - Peter Bala, May 19 2014
a(n) is also the length of the n-th line segment of a rectangular spiral on the infinite square grid. The vertices of the spiral are the generalized octagonal numbers. - Omar E. Pol, Jul 27 2018
a(n) is the number of petals of the Rhodonea curve r = a*cos(n*theta) or r = a*sin(n*theta). - Matt Westwood, Nov 19 2019

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Rose
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (0,2,0,-1).

Cf. A026741, A059026, A203976, A345082.
Column 4 of A195151. - Omar E. Pol, Sep 25 2011
Cf. A000034, A001082 (partial sums).
Cf. A227041 (first column). - Wolfdieter Lang, Jul 04 2013
Row 2 of A349593. A385555, A385556, A385557, A385558, A385559, and A385560 are respectively rows 3, 4, 5-6, 7, 8, and 9-10.

a022998 n = a000034 (n + 1) * n
a022998_list = zipWith (*) [0..] $ tail a000034_list
-- Reinhard Zumkeller, Mar 31 2012

[((-1)^n+3)*n/2: n in [0..70]]; // Vincenzo Librandi, Sep 17 2011

A022998 := proc(n) if type(n,'odd') then n ; else 2*n; end if; end proc: # R. J. Mathar, Mar 10 2011

Table[n (3 + (-1)^n)/2, {n, 0, 100}] (* Wesley Ivan Hurt, Dec 13 2013 *)
Table[If[OddQ[n],n,2n],{n,0,150}] (* or *) Riffle[ 2*Range[ 0,150,2], Range[ 1,150,2]] (* Harvey P. Dale, Feb 06 2017 *)

PARI
```
a(n)=if(n%2,n,2*n)
```

def A022998(n): return n if n&1 else n<<1 # Chai Wah Wu, Mar 05 2024

[n*(1+((n+1)%2)) for n in (0..80)] # G. C. Greubel, Jul 31 2022

Denominator of (n+1)*(n-1)*(2*n+1)/(2*n) (for n > 0).
a(n+1) = lcm(n, n+2)/n + lcm(n, n+2)/(n+2) for all n >= 1. - Asher Auel, Dec 15 2000
Multiplicative with a(2^e) = 2^(e+1), a(p^e) = p^e, p > 2.
G.f. x*(1 + 4*x + x^2)/(1-x^2)^2. - Ralf Stephan, Jun 10 2003
a(n) = 3*n/2 + n*(-1)^n/2 = n*(3 + (-1)^n)/2. - Paul Barry, Sep 04 2003
a(n) = A059029(n-1) + 1 = A043547(n+2) - 2.
a(n)*a(n+3) = -4 + a(n+1)*a(n+2).
a(n) = n*(((n+1) mod 2) + 1) = n^2 + 2*n - 2*n*floor((n+1)/2). - William A. Tedeschi, Feb 29 2008
a(n) = denominator((n+1)/(2*n)) for n >= 1; A026741(n+1) = numerator((n+1)/(2*n)) for n >= 1. - Johannes W. Meijer, Jun 18 2009
a(n) = 2*a(n-2) - a(n-4).
Dirichlet g.f. zeta(s-1)*(1+2^(1-s)). - R. J. Mathar, Mar 10 2011
a(n) = n * (2 - n mod 2) = n * A000034(n+1). - Reinhard Zumkeller, Mar 31 2012
a(n) = floor(2*n/(1 + (n mod 2))). - Wesley Ivan Hurt, Dec 13 2013
From Ilya Gutkovskiy, Mar 16 2017: (Start)
E.g.f.: x*(2*sinh(x) + cosh(x)).
It appears that a(n) is the period of the sequence k*(k + 1)/2 mod n. (End) [This is correct; see A349593. - Jianing Song, Jul 03 2025]
a(n) = Sum_{d | n} A345082(d). - Peter Bala, Jan 13 2024

More terms from Michael Somos, Aug 07 2000

A057660 a(n) = Sum_{k=1..n} n/gcd(n,k).

Original entry on oeis.org

1, 3, 7, 11, 21, 21, 43, 43, 61, 63, 111, 77, 157, 129, 147, 171, 273, 183, 343, 231, 301, 333, 507, 301, 521, 471, 547, 473, 813, 441, 931, 683, 777, 819, 903, 671, 1333, 1029, 1099, 903, 1641, 903, 1807, 1221, 1281, 1521, 2163, 1197, 2101, 1563, 1911, 1727

Offset: 1

Henry Gould, Oct 15 2000

Also sum of the orders of the elements in a cyclic group with n elements, i.e., row sums of A054531. - Avi Peretz (njk(AT)netvision.net.il), Mar 31 2001
Also inverse Moebius transform of EulerPhi(n^2), A002618.
Sequence is multiplicative with a(p^e) = (p^(2*e+1)+1)/(p+1). Example: a(10) = a(2)*a(5) = 3*21 = 63.
a(n) is the number of pairs (a, b) such that the equation ax = b is solvable in the ring (Zn, +, x). See the Mathematical Reflections link. - Michel Marcus, Jan 07 2017
From Jake Duzyk, Jun 06 2023: (Start)
These are the "contraharmonic means" of the improper divisors of square integers (inclusive of 1 and the square integer itself).
Permitting "Contraharmonic Divisor Numbers" to be defined analogously to Øystein Ore's Harmonic Divisor Numbers, the only numbers for which there exists an integer contraharmonic mean of the divisors are the square numbers, and a(n) is the n-th integer contraharmonic mean, expressible also as the sum of squares of divisors of n^2 divided by the sum of divisors of n^2. That is, a(n) = sigma_2(n^2)/sigma(n^2).
(a(n) = A001157(k)/A000203(k) where k is the n-th number such that A001157(k)/A000203(k) is an integer, i.e., k = n^2.)
This sequence is an analog of A001600 (Harmonic means of divisors of harmonic numbers) and A102187 (Arithmetic means of divisors of arithmetic numbers). (End)

David M. Burton, Elementary Number Theory, Allyn and Bacon Inc., Boston MA, 1976, p. 152.
H. W. Gould and Temba Shonhiwa, Functions of GCD's and LCM's, Indian J. Math. (Allahabad), Vol. 39, No. 1 (1997), pp. 11-35.
H. W. Gould and Temba Shonhiwa, A generalization of Cesaro's function and other results, Indian J. Math. (Allahabad), Vol. 39, No. 2 (1997), pp. 183-194.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Habib Amiri and S. M. Jafarian Amiri, Sum of element orders on finite groups of the same order, J. Algebra Appl. 10 (2011), no. 2, 187--190. MR2795731 (2012d:20050)
Habib Amiri, S. M. Jafarian Amiri, and I. M. Isaacs, Sums of element orders in finite groups Comm. Algebra 37 (2009), no. 9, 2978--2980. MR2554185 (2010i:20022)
Miriam Mahannah El-Farrah, Expectation Numbers of Cyclic Groups, MS Thesis, Western Kentucky University, August 2015.
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018, p. 154-5.
Walther Janous, Problem 10829, Amer. Math. Monthly, 107 (2000), p. 753.
Yadollah Marefat, Ali Iranmanesh, and Abolfazl Tehranian, On the sum of element orders of finite simple groups, J. Algebra Applications, 12 (2013), #1350026.
Mathematical Reflections, Solution to Problem U338, Issue 4, 2015, p 17.
Joachim von zur Gathen, Arnold Knopfmacher, Florian Luca, Lutz G. Lucht, and Igor E. Shparlinski, Average order of cyclic groups, J. Théorie Nombres Bordeaux 16 (1) (2004) 107-123.

Cf. A000010, A000203, A000290, A001157, A018804, A050873, A051193, A054522, A057661, A061255, A065764, A078747, A174405 (partial sums), A176797, A226512.

Cf. A308471.

a057660 n = sum $ map (div n) $ a050873_row n
-- Reinhard Zumkeller, Nov 25 2013

Table[ DivisorSigma[ 2, n^2 ] / DivisorSigma[ 1, n^2 ], {n, 1, 128} ]
Table[Total[Denominator[Range[n]/n]], {n, 55}] (* Alonso del Arte, Oct 07 2011 *)
f[p_, e_] := (p^(2*e + 1) + 1)/(p + 1); a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* Amiram Eldar, Nov 21 2020 *)

a(n)=if(n<1,0,sumdiv(n,d,d*eulerphi(d)))

a(n)=sumdivmult(n,d, eulerphi(d)*d) \\ Charles R Greathouse IV, Sep 09 2014

from math import gcd
def A057660(n): return sum(n//gcd(n,k) for k in range(1,n+1)) # Chai Wah Wu, Aug 24 2023

from math import prod
from sympy import factorint
def A057660(n): return prod((p**((e<<1)+1)+1)//(p+1) for p,e in factorint(n).items()) # Chai Wah Wu, Aug 05 2024

a(n) = Sum_{d|n} d*A000010(d) = Sum_{d|n} d*A054522(n,d), sum of d times phi(d) for all divisors d of n, where phi is Euler's phi function.
a(n) = sigma_2(n^2)/sigma_1(n^2) = A001157(A000290(n))/A000203(A000290(n)) = A001157(A000290(n))/A065764(n). - Labos Elemer, Nov 21 2001
a(n) = Sum_{d|n} A000010(d^2). - Enrique Pérez Herrero, Jul 12 2010
a(n) <= (n-1)*n + 1, with equality if and only if n is noncomposite. - Daniel Forgues, Apr 30 2013
G.f.: Sum_{n >= 1} n*phi(n)*x^n/(1 - x^n) = x + 3*x^2 + 7*x^3 + 11*x^4 + .... Dirichlet g.f.: sum {n >= 1} a(n)/n^s = zeta(s)*zeta(s-2)/zeta(s-1) for Re s > 3.  Cf. A078747 and A176797. - Peter Bala, Dec 30 2013
a(n) = Sum_{i=1..n} numerator(n/i). - Wesley Ivan Hurt, Feb 26 2017
L.g.f.: -log(Product_{k>=1} (1 - x^k)^phi(k)) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, May 21 2018
From Richard L. Ollerton, May 10 2021: (Start)
a(n) = Sum_{k=1..n} lcm(n,k)/k.
a(n) = Sum_{k=1..n} gcd(n,k)*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
From Vaclav Kotesovec, Jun 13 2021: (Start)
Sum_{k=1..n} a(k)/k ~ 3*zeta(3)*n^2/Pi^2.
Sum_{k=1..n} k^2/a(k) ~ A345294 * n.
Sum_{k=1..n} k*A000010(k)/a(k) ~ A345295 * n. (End)
Sum_{k=1..n} a(k) ~ 2*zeta(3)*n^3/Pi^2. - Vaclav Kotesovec, Jun 10 2023

More terms from James Sellers, Oct 16 2000

A127093 Triangle read by rows: T(n,k)=k if k is a divisor of n; otherwise, T(n,k)=0 (1 <= k <= n).

Original entry on oeis.org

1, 1, 2, 1, 0, 3, 1, 2, 0, 4, 1, 0, 0, 0, 5, 1, 2, 3, 0, 0, 6, 1, 0, 0, 0, 0, 0, 7, 1, 2, 0, 4, 0, 0, 0, 8, 1, 0, 3, 0, 0, 0, 0, 0, 9, 1, 2, 0, 0, 5, 0, 0, 0, 0, 10, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 1, 2, 3, 4, 0, 6, 0, 0, 0, 0, 0, 12, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13, 1, 2, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 14

Offset: 1

Gary W. Adamson, Jan 05 2007, Apr 04 2007

Sum of terms in row n = sigma(n) (sum of divisors of n).
Euler's derivation of A127093 in polynomial form is in his proof of the formula for Sigma(n): (let S=Sigma, then Euler proved that S(n) = S(n-1) + S(n-2) - S(n-5) - S(n-7) + S(n-12) + S(n-15) - S(n-22) - S(n-26), ...).
[Young, pp. 365-366], Euler begins, s = (1-x)*(1-x^2)*(1-x^3)*... = 1 - x - x^2 + x^5 + x^7 - x^12 ...; log s = log(1-x) + log(1-x^2) + log(1-x^3) ...; differentiating and then changing signs, Euler has t = x/(1-x) + 2x^2/(1-x^2) + 3x^3/(1-x^3) + 4x^4/(1-x^4) + 5x^5/(1-x^5) + ...
Finally, Euler expands each term of t into a geometric series, getting A127093 in polynomial form: t =
  x +  x^2 +  x^3 +  x^4 +  x^5 +  x^6 +  x^7 +  x^8 + ...
    + 2x^2        + 2x^4        + 2x^6        + 2x^8 + ...
           + 3x^3               + 3x^6               + ...
                  + 4x^4                      + 4x^8 + ...
                         + 5x^5                      + ...
                                + 6x^6               + ...
                                       + 7x^7        + ...
                                              + 8x^8 + ...
T(n,k) is the sum of all the k-th roots of unity each raised to the n-th power. - Geoffrey Critzer, Jan 02 2016
From Davis Smith, Mar 11 2019: (Start)
For n > 1, A020639(n) is the leftmost term, other than 0 or 1, in the n-th row of this array. As mentioned in the Formula section, the k-th column is period k: repeat [k, 0, 0, ..., 0], but this also means that it's the characteristic function of the multiples of k multiplied by k. T(n,1) = A000012(n), T(n,2) = 2*A059841(n), T(n,3) = 3*A079978(n), T(n,4) = 4*A121262(n), T(n,5) = 5*A079998(n), and so on.
The terms in the n-th row, other than 0, are the factors of n. If n > 1 and for every k, 1 <= k < n, T(n,k) = 0 or 1, then n is prime. (End)
From Gary W. Adamson, Aug 07 2019: (Start)
Row terms of the triangle can be used to calculate E(n) in A002654): (1, 1, 0, 1, 2, 0, 0, 1, 1, 2, ...), and A004018, the number of points in a square lattice on the circle of radius sqrt(n), A004018: (1, 4, 4, 0, 4, 8, 0, 0, 4, ...).
As to row terms in the triangle, let E(n) of even terms = 0,
  E(integers of the form 4*k - 1 = (-1), and E(integers of the form 4*k + 1 = 1.
Then E(n) is the sum of the E(n)'s of the factors of n in the triangle rows.  Example: E(10) = Sum: ((E(1) + E(2) + E(5) + E(10)) = ((1 + 0 + 1 + 0) = 2, matching A002654(10).
To get A004018, multiply the result by 4, getting A004018(10) = 8.
The total numbers of lattice points = 4r^2 = E(1) + ((E(2))/2 + ((E(3))/3 + ((E(4))/4 + ((E(5))/5 + .... Since E(even integers) are zero, E(integers of the form (4*k - 1)) = (-1), and E(integers of the form (4*k + 1)) = (+1); we are left with 4r^2 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - ..., which is approximately equal to Pi(r^2). (End)
T(n,k) is also the number of parts in the partition of n into k equal parts. - Omar E. Pol, May 05 2020

			T(8,4) = 4 since 4 divides 8.
T(9,3) = 3 since 3 divides 9.
First few rows of the triangle:
  1;
  1, 2;
  1, 0, 3;
  1, 2, 0, 4;
  1, 0, 0, 0, 5;
  1, 2, 3, 0, 0, 6;
  1, 0, 0, 0, 0, 0, 7;
  1, 2, 0, 4, 0, 0, 0, 8;
  1, 0, 3, 0, 0, 0, 0, 0, 9;
  ...

David Wells, "Prime Numbers, the Most Mysterious Figures in Math", John Wiley & Sons, 2005, appendix.
L. Euler, "Discovery of a Most Extraordinary Law of the Numbers Concerning the Sum of Their Divisors"; pp. 358-367 of Robert M. Young, "Excursions in Calculus, An Interplay of the Continuous and the Discrete", MAA, 1992. See p. 366.

Reinhard Zumkeller, Rows n = 1..100 of triangle, flattened
Grant Sanderson, Pi hiding in prime regularities
Leonhard Euler, Découverte d'une loi tout extraordinaire des nombres par rapport à la somme de leurs diviseurs, 1747, The Euler Archive, (Eneström Index) E175.
Leonhard Euler, Observatio de summis divisorum
Eric Weisstein's World of Mathematics, Divisor

Reversal = A127094
Cf. A127094, A123229, A127096, A127097, A127098, A127099, A000203, A126988, A127013, A127057, A038040, A024916, A060640, A001001.
Cf. A000005, A060640.
Cf. A027750.
Cf. A000012 (the first column), A020639, A059841 (the second column when multiplied by 2), A079978 (the third column when multiplied by 2), A079998 (the fifth column when multiplied by 5), A121262 (the fourth column when multiplied by 4).
Cf. A002654, A004018, A008683, A050873.

mod(row()-1;column()) - mod(row();column()) + 1 - Mats Granvik, Aug 31 2007

a127093 n k = a127093_row n !! (k-1)
a127093_row n = zipWith (*) [1..n] $ map ((0 ^) . (mod n)) [1..n]
a127093_tabl = map a127093_row [1..]
-- Reinhard Zumkeller, Jan 15 2011

A127093:=proc(n,k) if type(n/k, integer)=true then k else 0 fi end:
for n from 1 to 16 do seq(A127093(n,k),k=1..n) od; # yields sequence in triangular form - Emeric Deutsch, Jan 20 2007

t[n_, k_] := k*Boole[Divisible[n, k]]; Table[t[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 17 2014 *)
Table[ SeriesCoefficient[k*x^k/(1 - x^k), {x, 0, n}], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Apr 14 2015 *)

trianglerows(n) = for(x=1, n, for(k=1, x, if(x%k==0, print1(k, ", "), print1("0, "))); print(""))
/* Print initial 9 rows of triangle as follows: */
trianglerows(9) \\ Felix Fröhlich, Mar 26 2019

k-th column is composed of "k" interspersed with (k-1) zeros.
Let M = A127093 as an infinite lower triangular matrix and V = the harmonic series as a vector: [1/1, 1/2, 1/3, ...]. then M*V = d(n), A000005: [1, 2, 2, 3, 2, 4, 2, 4, 3, 4, ...]. M^2 * V = A060640: [1, 5, 7, 17, 11, 35, 15, 49, 34, 55, ...]. - Gary W. Adamson, May 10 2007
T(n,k) = ((n-1) mod k) - (n mod k) + 1 (1 <= k <= n). - Mats Granvik, Aug 31 2007
T(n,k) = k * 0^(n mod k). - Reinhard Zumkeller, Jan 15 2011
G.f.: Sum_{k>=1} k * x^k * y^k/(1-x^k) = Sum_{m>=1} x^m * y/(1 - x^m*y)^2. - Robert Israel, Aug 08 2016
T(n,k) = Sum_{d|k} mu(k/d)*sigma(gcd(n,d)). - Ridouane Oudra, Apr 05 2025

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

Original entry on oeis.org

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

A054521 Triangle read by rows: T(n,k) = 1 if gcd(n, k) = 1, T(n,k) = 0 otherwise (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0

Offset: 1

N. J. A. Sloane, Apr 09 2000

Row sums = phi(n), A000010: (1, 1, 2, 2, 4, 2, 6, ...). - Gary W. Adamson, May 20 2007
Characteristic function of A169581: a(A169581(n)) = 1; a(A169582(n)) = 0. - Reinhard Zumkeller, Dec 02 2009
The function T(n,k) = T(k,n) is defined for k > n but only the values for 1 <= k <= n as a triangular array are listed here.
T(n,k) = |K(n-k|k)| where K(i|j) is the Kronecker symbol. - Peter Luschny, Aug 05 2012
Twice the sum over the antidiagonals, starting with entry T(n-1,1), for n >= 3, is the same as the row n sum (i.e., phi(n): 2*Sum_{k=1..floor(n/2)} T(n-k,k) = phi(n), n >= 3). - Wolfdieter Lang, Apr 26 2013
The number of zeros in the n-th row of the triangle is cototient(n) = A051953(n). - Omar E. Pol, Apr 21 2017
This triangle is the j = 1 sub-triangle of A349221(n,k) = Sum_{j>=1} [k|binomial(n-1,k-1) AND gcd(n,k) = j], n >= 1, 1 <= k <= n, where [] is the Iverson bracket. - Richard L. Ollerton, Dec 14 2021

			The triangle T(n,k) begins:
  n\k  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 ...
   1:  1
   2:  1  0
   3:  1  1  0
   4:  1  0  1  0
   5:  1  1  1  1  0
   6:  1  0  0  0  1  0
   7:  1  1  1  1  1  1  0
   8:  1  0  1  0  1  0  1  0
   9:  1  1  0  1  1  0  1  1  0
  10:  1  0  1  0  0  0  1  0  1  0
  11:  1  1  1  1  1  1  1  1  1  1  0
  12:  1  0  0  0  1  0  1  0  0  0  1  0
  13:  1  1  1  1  1  1  1  1  1  1  1  1  0
  14:  1  0  1  0  1  0  0  0  1  0  1  0  1  0
  15:  1  1  0  1  0  0  1  1  0  0  1  0  1  1  0
  ... (Reformatted by _Wolfdieter Lang_, Apr 26 2013)
Sums over antidiagonals: n = 3: 2*T(2,1) = 2 = T(3,1) + T(3,2) = phi(3). n = 4: 2*(T(3,1) + T(2,2)) = 2 = phi(4), etc. - _Wolfdieter Lang_, Apr 26 2013

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
Jakub Jaroslaw Ciaston, A054531 vs A164306 (plot shows these ones)
Index entries for characteristic functions

Cf. A051731, A054522, A215200.
Cf. A050873, A063524.
Cf. A349221.

a054521 n k = a054521_tabl !! (n-1) !! (k-1)
a054521_row n = a054521_tabl !! (n-1)
a054521_tabl = map (map a063524) a050873_tabl
a054521_list = concat a054521_tabl
-- Reinhard Zumkeller, Sep 03 2015

A054521_row := n -> seq(abs(numtheory[jacobi](n-k,k)),k=1..n);
for n from 1 to 13 do A054521_row(n) od; # Peter Luschny, Aug 05 2012

T[ n_, k_] := Boole[ n>0 && k>0 && GCD[ n, k] == 1] (* Michael Somos, Jul 17 2011 *)
T[ n_, k_] := If[ n<1 || k<1, 0, If[ k>n, T[ k, n], If[ k==1, 1, If[ n>k, T[ k, Mod[ n, k, 1]], 0]]]] (* Michael Somos, Jul 17 2011 *)

{T(n, k) = n>0 && k>0 && gcd(n, k)==1} /* Michael Somos, Jul 17 2011 */

def A054521_row(n): return [abs(kronecker_symbol(n-k,k)) for k in (1..n)]
for n in (1..13): print(A054521_row(n)) # Peter Luschny, Aug 05 2012

T(n,k) = A063524(A050873(n,k)). - Reinhard Zumkeller, Dec 02 2009, corrected Sep 03 2015

T(n,k) = A054431(n,k) = A054431(k,n). - R. J. Mathar, Jul 21 2016

A054522 Triangle T(n,k): T(n,k) = phi(k) if k divides n, T(n,k)=0 otherwise (n >= 1, 1<=k<=n). T(n,k) = number of elements of order k in cyclic group of order n.

Original entry on oeis.org

1, 1, 1, 1, 0, 2, 1, 1, 0, 2, 1, 0, 0, 0, 4, 1, 1, 2, 0, 0, 2, 1, 0, 0, 0, 0, 0, 6, 1, 1, 0, 2, 0, 0, 0, 4, 1, 0, 2, 0, 0, 0, 0, 0, 6, 1, 1, 0, 0, 4, 0, 0, 0, 0, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 1, 1, 2, 2, 0, 2, 0, 0, 0, 0, 0, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 1, 1, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0

Offset: 1

N. J. A. Sloane, Apr 09 2000

T(n,1) = 1; T(n,n) = A000010(n).

This triangle is the transpose of the upper triangular array U in the LU decomposition of the square array A003989. - Peter Bala, Oct 15 2023

			1;
1, 1;
1, 0, 2;
1, 1, 0, 2;
1, 0, 0, 0, 4;
1, 1, 2, 0, 0, 2;
1, 0, 0, 0, 0, 0, 6;
1, 1, 0, 2, 0, 0, 0, 4;
1, 0, 2, 0, 0, 0, 0, 0, 6;

Reinhard Zumkeller, Rows n=1..100 of triangle, flattened
R. J. Mathar, Plots of cycle graphs of the finite groups up to order 36, (2015)

Cf. A003989, A054521, A008683, A050873.

a054522 n k = a054522_tabl !! (n-1) !! (k-1)
a054522_tabl = map a054522_row [1..]
a054522_row n = map (\k -> if n `mod` k == 0 then a000010 k else 0) [1..n]
-- Reinhard Zumkeller, Oct 18 2011

A054522 := proc(n,k)
    if modp(n,k) = 0 then
        numtheory[phi](k) ;
    else
        0;
    end if;
end proc:
seq(seq(A054522(n,k),k=1..n),n=1..15) ; # R. J. Mathar, Aug 06 2016

t[n_, k_] /; Divisible[n, k] := EulerPhi[k]; t[, ] = 0; Flatten[Table[t[n, k], {n, 1, 14}, {k, 1, n}]] (* Jean-François Alcover, Nov 25 2011 *)
Flatten[Table[If[Divisible[n,k],EulerPhi[k],0],{n,15},{k,n}]] (* Harvey P. Dale, Feb 27 2012 *)

T(n,k)=if(k<1 || k>n,0,if(n%k,0,eulerphi(k)))

Sum (T(n,k): k = 1 .. n) = n. - Reinhard Zumkeller, Oct 18 2011

T(n,k) = Sum_{d|k} mu(k/d)*gcd(n,d). - Ridouane Oudra, Apr 05 2025

A054531 Triangular array T read by rows: T(n,k) = n/gcd(n,k) (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 2, 4, 1, 5, 5, 5, 5, 1, 6, 3, 2, 3, 6, 1, 7, 7, 7, 7, 7, 7, 1, 8, 4, 8, 2, 8, 4, 8, 1, 9, 9, 3, 9, 9, 3, 9, 9, 1, 10, 5, 10, 5, 2, 5, 10, 5, 10, 1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 12, 6, 4, 3, 12, 2, 12, 3, 4, 6, 12, 1, 13, 13, 13, 13, 13

Offset: 1

N. J. A. Sloane, Apr 09 2000

Sum of n-th row = A057660(n). - Reinhard Zumkeller, Aug 12 2009
Read as a linear sequence, this is conjectured to be the length of the shortest cycle of pebble-moves among the partitions of n (cf. A201144). - Andrew V. Sutherland, Nov 27 2011
The triangle of fractions A226314(i,j)/A054531(i,j) is an efficient way to enumerate the rationals [Fortnow]. - N. J. A. Sloane, Jun 09 2013

			Triangle begins
   1;
   2,  1;
   3,  3,  1;
   4,  2,  4,  1;
   5,  5,  5,  5,  1;
   6,  3,  2,  3,  6,  1;
   7,  7,  7,  7,  7,  7,  1;
   8,  4,  8,  2,  8,  4,  8,  1;
   9,  9,  3,  9,  9,  3,  9,  9,  1;
  10,  5, 10,  5,  2,  5, 10,  5, 10,  1;
  11, 11, 11, 11, 11, 11, 11, 11, 11, 11,  1;
  12,  6,  4,  3, 12,  2, 12,  3,  4,  6, 12,  1;
  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,  1;

Reinhard Zumkeller, Rows n = 1..120 of triangle, flattened
Lance Fortnow, Counting the Rationals Quickly, Computational Complexity Weblog, Monday, March 01, 2004.
R. J. Mathar, Plots of cycle graphs of the finite groups up to order 36, (2015).
Yoram Sagher, Counting the rationals, Amer. Math. Monthly, 96 (1989), p. 823. Math. Rev. 90i:04001.

Cf. A050873, A164306, A226314, A277227 (row reversed, k=0..n-1).

a054531 n k = div n $ gcd n k
a054531_row n = a054531_tabl !! (n-1)
a054531_tabl = zipWith (\u vs -> map (div u) vs) [1..] a050873_tabl
-- Reinhard Zumkeller, Jun 10 2013

Table[n/GCD[n,k], {n,1,10}, {k,1,n}]//Flatten (* G. C. Greubel, Sep 13 2017 *)

for(n=1,10, for(k=1,n, print1(n/gcd(n,k), ", "))) \\ G. C. Greubel, Sep 13 2017

A109007 a(n) = gcd(n,3).

Original entry on oeis.org

3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 1

Offset: 0

Mitch Harris

For n>1: a(n) = GCD of the n-th and (n+2)-th triangular numbers = A050873(A000217(n+2), A000217(n)). - Reinhard Zumkeller, May 28 2007
From Klaus Brockhaus, May 24 2010: (Start)
Continued fraction expansion of (3+sqrt(17))/2.
Decimal expansion of 311/999. (End)

Index entries for linear recurrences with constant coefficients, signature (0,0,1).

Cf. A000217, A026741, A050873, A109004, A130334.

Cf. A178255 (decimal expansion of (3+sqrt(17))/2). - Klaus Brockhaus, May 24 2010

[Gcd(n,3) : n in [0..100]]; // Wesley Ivan Hurt, Jul 24 2016

A109007:=n->gcd(n,3): seq(A109007(n), n=0..100); # Wesley Ivan Hurt, Jul 24 2016

GCD[Range[0,100],3] (* or *) PadRight[{},110,{3,1,1}] (* Harvey P. Dale, Jun 28 2015 *)

a(n)=gcd(n,3) \\ Charles R Greathouse IV, Sep 24 2015

a(n) = 1 + 2*[3|n] = 1 + 2(1 + 2*cos(2*n*Pi/3))/3, where [x|y] = 1 when x divides y, 0 otherwise.
a(n) = a(n-3) for n>2.
Multiplicative with a(p^e, 3) = gcd(p^e, 3). - David W. Wilson, Jun 12 2005
O.g.f.: -(3+x+x^2)/((x-1)*(x^2+x+1)). - R. J. Mathar, Nov 24 2007
Dirichlet g.f. zeta(s)*(1+2/3^s). - R. J. Mathar, Apr 08 2011
a(n) = 2*floor(((n-1) mod 3)/2) + 1. - Gary Detlefs, Dec 28 2011
a(n) = 3^(1 - sgn(n mod 3)). - Wesley Ivan Hurt, Jul 24 2016
a(n) = 3/(1 + 2*((n^2) mod 3)). - Timothy Hopper, Feb 25 2017
a(n) = (5 + 4*cos(2*n*Pi/3))/3. - Wesley Ivan Hurt, Oct 04 2018

cp's OEIS Frontend

A255655 The sum of the odd terms in row n of A050873.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A018804 Pillai's arithmetical function: Sum_{k=1..n} gcd(k, n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Formula

A022998 If n is odd then n, otherwise 2n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

SageMath

Formula

Extensions

A057660 a(n) = Sum_{k=1..n} n/gcd(n,k).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A127093 Triangle read by rows: T(n,k)=k if k is a divisor of n; otherwise, T(n,k)=0 (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Excel

Haskell

Maple