A109004 -id:A109004 - cp's OEIS frontend

A209295 Antidiagonal sums of the gcd(.,.) array A109004.

0, 2, 5, 8, 12, 14, 21, 20, 28, 30, 37, 32, 52, 38, 53, 60, 64, 50, 81, 56, 92, 86, 85, 68, 124, 90, 101, 108, 132, 86, 165, 92, 144, 138, 133, 152, 204, 110, 149, 164, 220, 122, 237, 128, 212, 234, 181, 140, 288, 182, 245, 216, 252, 158, 297, 244

Offset: 0

R. J. Mathar, Jan 17 2013

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 5000 terms from G. C. Greubel)

Cf. A006580, A018804, A109004.

A209295:= func< n | n eq 0 select 0 else (&+[(n/d+1)*EulerPhi(d): d in Divisors(n)]) >;
[A209295(n): n in [0..40]]; // G. C. Greubel, Jun 24 2024

a:= n-> add(igcd(j, n-j), j=0..n):
seq(a(n), n=0..70);  # Alois P. Heinz, Aug 25 2019
# Alternative (computes [a(n), n=0..10000] about 25 times faster):
a := n -> add(numtheory:-phi(d)*(n/d + 1), d = numtheory:-divisors(n)):
seq(a(n), n = 0..57); # Peter Luschny, Aug 25 2019

Table[Sum[GCD[n-k,k], {k,0,n}], {n,0,50}] (* G. C. Greubel, Jan 04 2018 *)
f[p_, e_] := (e*(p - 1)/p + 1)*p^e; a[n_] := n + Times @@ f @@@ FactorInteger[n]; a[0] = 0; Array[a, 100, 0] (* Amiram Eldar, Apr 28 2023 *)

a(n) = n + sum(k=1, n, gcd(n,k)); \\ Michel Marcus, Jan 05 2018

def A209295(n): return sum((n/k+1)*euler_phi(k) for k in (1..n) if (k).divides(n))
[A209295(n) for n in range(41)] # G. C. Greubel, Jun 24 2024

a(0) = 0; a(n) = A018804(n) + n for n > 0. [Amended by Georg Fischer, Jan 25 2020]

a(n) = Sum_{d|n} phi(d)*(n/d + 1) for n >= 1. - Peter Luschny, Aug 25 2019

A374443 Triangle read by rows: T(n, k) = rad(gcd(n, k)) if n, k > 0, T(0, 0) = 1, where rad = A007947 and gcd = A109004.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 3, 1, 1, 3, 2, 1, 2, 1, 2, 5, 1, 1, 1, 1, 5, 6, 1, 2, 3, 2, 1, 6, 7, 1, 1, 1, 1, 1, 1, 7, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 1, 1, 3, 1, 1, 3, 1, 1, 3, 10, 1, 2, 1, 2, 5, 2, 1, 2, 1, 10, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6

Offset: 0

Peter Luschny and Michael De Vlieger, Jul 12 2024

			Triangle starts:
  [ 0]  1;
  [ 1]  1, 1;
  [ 2]  2, 1, 2;
  [ 3]  3, 1, 1, 3;
  [ 4]  2, 1, 2, 1, 2;
  [ 5]  5, 1, 1, 1, 1, 5;
  [ 6]  6, 1, 2, 3, 2, 1, 6;
  [ 7]  7, 1, 1, 1, 1, 1, 1, 7;
  [ 8]  2, 1, 2, 1, 2, 1, 2, 1, 2;
  [ 9]  3, 1, 1, 3, 1, 1, 3, 1, 1, 3;
  [10] 10, 1, 2, 1, 2, 5, 2, 1, 2, 1, 10;
  [11] 11, 1, 1, 1, 1, 1, 1, 1, 1, 1,  1, 11;

Variant: A374433.

Cf. A374442 (row sums), A007947, A109004.

rad := n -> ifelse(n = 0, 1, NumberTheory:-Radical(n)):
T := (n, k) -> rad(igcd(n, k)); seq(seq(T(n, k), k = 0..n), n = 0..11);

rad[n_] := If[n == 0, 1, Product[p, {p, Select[Divisors[n], PrimeQ]}]];
T[n_, k_] := rad[GCD[n, k]]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten

from math import gcd, prod
from sympy.ntheory import primefactors
def T(n, k) -> int: return prod(primefactors(gcd(n, k)))
for n in range(16): print([T(n, k) for k in range(n+1)])  # Peter Luschny, Jun 22 2025

A383441 a(n) is the total of iterations needed in the binary GCD algorithm to compute gcd(n, k) for k = 0..n. The corresponding row of gcds is row n of A109004.

Original entry on oeis.org

0, 0, 0, 2, 1, 5, 5, 12, 5, 11, 12, 23, 13, 29, 27, 31, 17, 38, 26, 47, 31, 42, 51, 70, 35, 63, 64, 72, 62, 96, 69, 104, 49, 80, 84, 86, 64, 123, 103, 118, 77, 130, 94, 152, 115, 128, 151, 174, 90, 163, 138, 164, 144, 197, 157, 188, 144, 187, 206, 229, 157, 251

Offset: 0

Peter Luschny, May 16 2025

nonn

The reference Python implementation is provided in the links. It is a variant of Algorithm B described by Knuth in TAOCP Vol. 2, potentially offering some speedup in Python.

Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, section 4.7, p. 83.
D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 2, Seminumerical Algorithms. Chapter 4.5.2 The greatest Common Divisor, Page 321, Algorithm B.

Peter Luschny, Table of n, a(n) for n = 0..10000
Richard P. Brent, Further analysis of the binary Euclidean algorithm, Technical Report PRG TR-7-99, Oxford University Computing Laboratory, November 1999, arXiv:1303.2772 [cs.DS].
Peter Luschny, Binary Gcd, May 2025.
Peter Luschny, Illustration of the distribution of the values.
Damien Stehlé and Paul Zimmermann, A Binary Recursive Gcd Algorithm, 6th International Symposium on Algorithmic Number Theory - ANTS VI, 2004, Burligton, US, pp. 411-425.

Cf. A109004, A000265.

gcd_bin_count := proc(a, b) local count, odd, A, B, D;
if a = 0 or a = b or b = 0 then return 0 fi; count := 0;
odd := n -> n*2^(-padic:-ordp(n, 2));  # A000265
A := odd(a); B := odd(b);
while B <> A do count := count + 1;
   D := ifelse(A < B, B - A, A - B);
   B := ifelse(A < B, A, B);
   A := odd(D);
od; count end:
a := n -> local k; add(gcd_bin_count(n, k), k = 0..n):
seq(a(n), n = 0..61);

Python
```
# See the links.
```

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

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

A109008 a(n) = gcd(n,4).

Original entry on oeis.org

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

Offset: 0

Mitch Harris

Period 4: repeat [4, 1, 2, 1]. - Wesley Ivan Hurt, Aug 31 2014

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

Cf. A109004.

a109008 = gcd 4
a109008_list = cycle [4,1,2,1]  -- Reinhard Zumkeller, Nov 25 2013

[Gcd(n,4) : n in [0..100]]; // Wesley Ivan Hurt, Aug 31 2014

A109008:=n->gcd(n,4): seq(A109008(n), n=0..100); # Wesley Ivan Hurt, Aug 31 2014

Table[GCD[n, 4], {n, 0, 100}] (* Wesley Ivan Hurt, Aug 31 2014 *)

a(n)=gcd(n,4) \\ Charles R Greathouse IV, Oct 07 2015

a(n) = 1 + [2|n] + 2*[4|n] = 2 + (-1)^n + cos(n*Pi/2), where [x|y] = 1 when x divides y, 0 otherwise.
a(n) = a(n-4) for n>3.
Multiplicative with a(p^e) = gcd(p^e, 4). - David W. Wilson, Jun 12 2005
Dirichlet g.f.: (1  + 1/2^s + 2/4^s)*zeta(s). - R. J. Mathar, Feb 28 2011
G.f.: (4+x+2*x^2+x^3)/((1-x)*(1+x)*(1+x^2)). - R. J. Mathar, Apr 04 2011
a(n) = 1 + mod((n-1)^3, 4). - Wesley Ivan Hurt, Aug 31 2014
a(n) = 2 + cos(n*Pi) + cos(n*Pi/2). - Wesley Ivan Hurt, Jul 07 2016
E.g.f.: exp(-x) + 2*exp(x) + cos(x). - Ilya Gutkovskiy, Jul 07 2016

A225816 Square array A(n,k) = (k!)^n, n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 6, 4, 1, 1, 1, 24, 36, 8, 1, 1, 1, 120, 576, 216, 16, 1, 1, 1, 720, 14400, 13824, 1296, 32, 1, 1, 1, 5040, 518400, 1728000, 331776, 7776, 64, 1, 1, 1, 40320, 25401600, 373248000, 207360000, 7962624, 46656, 128, 1, 1

Offset: 0

Alois P. Heinz, Jul 29 2013

A(n,k) is the determinant of the k X k matrix M = [Stirling2(n+i,j)] for 1<=i,j<=k.  A(2,3) = det([1,3,1; 1,7,6; 1,15,25]) = 36.
A(n,k) is the determinant of the symmetric k X k matrix M = [sigma_n(gcd(i,j))] for 1<=i,j<=k.  A(2,3) = det([1,1,1; 1,5,1; 1,1,10]) = 36.
A(n,k) is (-1)^(n*k) times the determinant of the n X n matrix M = [Stirling1(k+i,j)] for 1<=i,j<=n.  A(2,3) = (-1)^(2+3) * det([-6,11; 24,-50]) = 36.
A(n,k) is the number of lattice paths from {n}^k to {0}^k using steps that decrement one component by 1 such that for each point (p_1,p_2,...,p_k) we have abs(p_i-p_j) <= 1 for 1<=i,j<=k.  A(2,3) = 36:
          (1,2,2)-(1,1,2)         (0,1,1)-(0,0,1)
         /       X       \       /       X       \
  (2,2,2)-(2,1,2) (1,2,1)-(1,1,1)-(1,0,1) (0,1,0)-(0,0,0).
         \       X       /       \       X       /
          (2,2,1) (2,1,1)         (1,1,0) (1,0,0)
A(n,k) is the number of set partitions of [k*(n+1)] into k blocks of size n+1 such that the elements of each block are distinct mod n+1.  A(2,3) = 36: 123|456|789, 126|345|789, ..., 189|234|567, 189|246|357.

			Square array A(n,k) begins:
  1, 1,  1,    1,       1,           1, ...
  1, 1,  2,    6,      24,         120, ...
  1, 1,  4,   36,     576,       14400, ...
  1, 1,  8,  216,   13824,     1728000, ...
  1, 1, 16, 1296,  331776,   207360000, ...
  1, 1, 32, 7776, 7962624, 24883200000, ...

Alois P. Heinz, Antidiagonals n = 0..36, flattened

Columns k=0+1, 2-4 give: A000012, A000079, A000400, A009968.
Rows n=0-4 give: A000012, A000142, A001044, A000442, A134375.
Main diagonal gives: A036740.
Cf. A008275, A048994, A008277, A048993, A003989, A109004, A109974.

A:= (n, k)-> k!^n:
seq(seq(A(n,d-n), n=0..d), d=0..12);

A(n,k) = (k!)^n.
A(n,k) = k^n * A(n,k-1) for k>0, A(n,0) = 1.
A(n,k) = k!  * A(n-1,k) for n>0, A(0,k) = 1.
G.f. of column k: 1/(1-k!*x).

A107711 Triangle read by rows: T(0,0)=1, T(n,m) = binomial(n,m) * gcd(n,m)/n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 5, 10, 5, 1, 1, 1, 1, 3, 5, 5, 3, 1, 1, 1, 1, 7, 7, 35, 7, 7, 1, 1, 1, 1, 4, 28, 14, 14, 28, 4, 1, 1, 1, 1, 9, 12, 42, 126, 42, 12, 9, 1, 1, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 1, 1, 11, 55, 165, 66, 462, 66, 165, 55, 11, 1, 1

Offset: 0

Leroy Quet, Jun 10 2005

T(0,0) is an indeterminate, but 1 seems a logical value to assign it. T(n,0) = T(n,1) = T(n,n-1) = T(n,n) = 1.

T(2n,n) = A001700(n-1) (n>=1). - Emeric Deutsch, Jun 13 2005

			T(6,2)=5 because binomial(6,2)*gcd(6,2)/6 = 15*2/6 = 5.
The triangle T(n,m) begins:
n\m 0  1  2   3   4    5   6   7  8  9  10...
0:  1
1:  1  1
2:  1  1  1
3:  1  1  1   1
4:  1  1  3   1   1
5:  1  1  2   2   1    1
6:  1  1  5  10   5    1   1
7:  1  1  3   5   5    3   1   1
8:  1  1  7   7  35    7   7   1  1
9:  1  1  4  28  14   14  28   4  1  1
10: 1  1  9  12  42  126  42  12  9  1   1
n\m 0  1  2   3   4    5   6   7  8  9  10...
... reformatted - _Wolfdieter Lang_, Feb 23 2014

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
Wolfdieter Lang, On Collatz' Words, Sequences and Trees, arXiv:1404.2710 [math.NT], 2014 and J. Int. Seq. 17 (2014) # 14.11.7.

Row sums A159554.
Cf. A007318, A001700, A000108, A050169, A234040, A026741, A234042.
Cf. A109004.

a107711 n k = a107711_tabl !! n !! k
a107711_row n = a107711_tabl !! n
a107711_tabl = [1] : zipWith (map . flip div) [1..]
               (tail $ zipWith (zipWith (*)) a007318_tabl a109004_tabl)
-- Reinhard Zumkeller, Feb 28 2014

a:=proc(n,k) if n=0 and k=0 then 1 elif k<=n then binomial(n,k)*gcd(n,k)/n else 0 fi end: for n from 0 to 13 do seq(a(n,k),k=0..n) od; # yields sequence in triangular form. - Emeric Deutsch, Jun 13 2005

T[0, 0] = 1; T[n_, m_] := Binomial[n, m] * GCD[n, m]/n;
Table[T[n, m], {n, 1, 13}, {m, 1, n}] // Flatten (* Jean-François Alcover, Nov 16 2017 *)

From Wolfdieter Lang, Feb 28 2014 (Start)
T(n, m) = T(n-1,m)*(n-1)*gcd(n,m)/((n-m)*gcd(n-1,m)), n > m >= 1, T(n, 0) = 1, T(n, n) = 1, otherwise 0.
T(n, m) = binomial(n-1,m-1)*gcd(n,m)/m for n >= m >= 1, T(n,0) = 1, otherwise 0 (from iteration of the preceding recurrence).
T(n, m) = T(n-1, m-1)*(n-1)*gcd(n,m)/(m*gcd(n-1,m-1)) for n >= m >= 2, T(n, 0) = 1, T(n, 1) = 0, otherwise 0 (from the preceding formula).
T(2*n, n) = A001700(n-1) (n>=1) (see the Emeric Deutsch comment above), T(2*n, n-1) = A234040(n), T(2*n+1,n) = A000108(n), n >= 0 (Catalan numbers).
Column sequences: T(n+2, 2) = A026741(n+1), T(n+3, 3) = A234041(n), T(n+4, 4) = A208950(n+2), T(n+5, 5) = A234042, n >= 0. (End)

More terms from Emeric Deutsch, Jun 13 2005

A109009 a(n) = gcd(n,5).

Original entry on oeis.org

5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5

Offset: 0

Mitch Harris

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

Cf. A109004.

GCD[Range[0,100],5] (* or *) PadRight[{},120,{5,1,1,1,1}] (* Harvey P. Dale, Jun 29 2018 *)

a(n)=gcd(n,5) \\ Charles R Greathouse IV, Oct 07 2015

a(n) = 1 + 4*[5|n], where [x|y] = 1 when x divides y, 0 otherwise.
a(n) = a(n-5).
Multiplicative with a(p^e, 5) = gcd(p^e, 5). - David W. Wilson, Jun 12 2005
From R. J. Mathar, Apr 04 2011: (Start)
Dirichlet g.f.: zeta(s)*(1+4/5^s).
G.f.: ( -5-x-x^2-x^3-x^4 ) / ( (x-1)*(1+x+x^2+x^3+x^4) ). (End)
a(n) = 4*floor(1/2*cos((2*n*Pi)/5)+1/2) + 1.
     = 4*floor(((n-1) mod 5)/4) + 1. - Gary Detlefs, Dec 28 2011

A109012 a(n) = gcd(n,9).

Original entry on oeis.org

9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1

Offset: 0

Mitch Harris

Start with positive integer n. At each step, either (a) multiply by any positive integer or (b) remove all zeros from the number. a(n) is the smallest number that can be reached by this process. - David W. Wilson, Nov 01 2005
From Martin Fuller, Jul 09 2007: (Start)
Also the minimal positive difference between numbers whose digit sum is a multiple of n. Proof:
Construction: Pick a positive number that does not end with 9, and has a digit sum n-a(n). To form the lower number, append 9 until the digit sum is a multiple of n. This is always possible since the difference is gcd(n,9). Add a(n) to form the higher number, which will have digit sum n.
E.g., n=12: prefix=18, lower=18999, higher=19002, difference=3.
Minimality: All numbers are a multiple of a(n) if their digit sum is a multiple of n. Hence the minimal difference is at least a(n). (End)

Antti Karttunen, Table of n, a(n) for n = 0..100000
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,1).

Cf. A109004.
Cf. A109007, A109008, A109009, A109010, A109011, A109013, A109014, A109015.
Cf. A074232, A374039.

GCD[Range[0, 100], 9] (* Paolo Xausa, Aug 28 2024 *)

a(n)=gcd(n,9) \\ Charles R Greathouse IV, Oct 07 2015

from math import gcd
def a(n): return gcd(n, 9)
print([a(n) for n in range(101)]) # Michael S. Branicky, Sep 01 2021

a(n) = 1 + 2*[3|n] + 6*[9|n], where [x|y] = 1 when x divides y, 0 otherwise.
a(n) = a(n-9).
Multiplicative with a(p^e, 9) = gcd(p^e, 9). - David W. Wilson, Jun 12 2005
G.f.: (-9 - x - x^2 - 3*x^3 - x^4 - x^5 - 3*x^6 - x^7 - x^8) / ((x-1)*(1 + x + x^2)*(x^6 + x^3 + 1)). - R. J. Mathar, Apr 04 2011
Dirichlet g.f.: (1+2/3^s+6/9^s)*zeta(s). - R. J. Mathar, Apr 04 2011

cp's OEIS Frontend

A209295 Antidiagonal sums of the gcd(.,.) array A109004.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A374443 Triangle read by rows: T(n, k) = rad(gcd(n, k)) if n, k > 0, T(0, 0) = 1, where rad = A007947 and gcd = A109004.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Python

A383441 a(n) is the total of iterations needed in the binary GCD algorithm to compute gcd(n, k) for k = 0..n. The corresponding row of gcds is row n of A109004.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Python

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A109008 a(n) = gcd(n,4).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

A225816 Square array A(n,k) = (k!)^n, n>=0, k>=0, read by antidiagonals.

Views

Author