A109004 -id:A109004 - cp's OEIS frontend

A140819 Triangle read by rows: T(n, m) = m if 2m = n, otherwise 2gcd(n, m).

0, 2, 2, 4, 1, 4, 6, 2, 2, 6, 8, 2, 2, 2, 8, 10, 2, 2, 2, 2, 10, 12, 2, 4, 3, 4, 2, 12, 14, 2, 2, 2, 2, 2, 2, 14, 16, 2, 4, 2, 4, 2, 4, 2, 16, 18, 2, 2, 6, 2, 2, 6, 2, 2, 18

Offset: 0

Roger L. Bagula and Mats Granvik, Jul 16 2008

			{0},
{2, 2},
{4, 1, 4},
{6, 2, 2, 6},
{8, 2, 2, 2, 8},
{10, 2, 2, 2, 2, 10},
{12, 2, 4, 3, 4, 2, 12},
{14, 2, 2, 2, 2, 2, 2, 14},
{16, 2, 4, 2, 4, 2, 4, 2, 16},
{18, 2, 2, 6, 2, 2, 6, 2, 2, 18}

Cf. A109004, A140685.

M[d_, x_, y_] := Sum[Sum[If[n == m, GCD[d - 1, m - 1], If[n == d - m + 1, GCD[ d - 1, n - 1], 0]]*x^(n - 1)*y^(m - 1), {n, 1, d}], {m, 1, d}]
Table[CoefficientList[M[d, x, 1], x], {d, 1, 10}]
Flatten[%]
Table[Apply[Plus, CoefficientList[M[d, x, 1], x]], {d, 1, 10}]

Definition simplified by the editors of the OEIS, Jan 03 2024

A140822 Triangle T(n,m) = binomial(n,gcd(n,m)) read by rows, 0<=m<=n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 5, 5, 5, 1, 1, 6, 15, 20, 15, 6, 1, 1, 7, 7, 7, 7, 7, 7, 1, 1, 8, 28, 8, 70, 8, 28, 8, 1, 1, 9, 9, 84, 9, 9, 84, 9, 9, 1, 1, 10, 45, 10, 45, 252, 45, 10, 45, 10, 1

Offset: 0

Roger L. Bagula and Gary W. Adamson, Jul 16 2008

Row sums are 1, 2, 4, 8, 16, 22, 64, 44, 160, 224, 474,...

			1;
1, 1;
1, 2, 1;
1, 3, 3, 1;
1, 4, 6, 4, 1;
1, 5, 5, 5, 5, 1;
1, 6, 15, 20, 15, 6, 1;
1, 7, 7, 7, 7, 7, 7, 1;
1, 8, 28, 8, 70, 8, 28, 8, 1;
1, 9, 9, 84, 9, 9, 84, 9, 9, 1;
1, 10, 45, 10, 45, 252, 45, 10, 45, 10, 1;

a = Table[Table[Binomial[n, GCD[n, m]], {m, 0, n}], {n, 0, 10}]; Flatten[a]

T(n,m) = A007318(n,A109004(n,m)).

Offset corrected by R. J. Mathar, Nov 07 2011

A140875 Triangle read by rows: T(n,m) = gcd(n,m+2) - 2*gcd(n,m+1) - gcd(n,m), with diagonal and subdiagonal removed.

Original entry on oeis.org

-2, -4, 0, -4, -4, 0, -6, -2, -2, 2, -6, -2, -6, -6, 2, -8, -2, -2, -2, -2, 4, -8, -4, 0, -8, -4, -4, 4, -10, 0, -6, -4, 0, -6, -4, 6, -10, -4, -2, 0, -10, -8, -2, -4, 6, -12, -2, -2, -2, -2, -2, -2, -2, -2, 8, -12, -2, -4, -10, 0, -12, -4, -6, -8, -6, 8, -14, -2, -2, -2, -2, -2, -2, -2, -2, -2, -2, 10

Offset: 1

Roger L. Bagula and Gary W. Adamson, Jul 21 2008

			{ -2},
{ -4,  0},
{ -4, -4,  0},
{ -6, -2, -2,  2},
{ -6, -2, -6, -6,   2},
{ -8, -2, -2, -2,  -2,  4},
{ -8, -4,  0, -8,  -4, -4,  4},
{-10,  0, -6, -4,   0, -6, -4,  6},
{-10, -4, -2,  0, -10, -8, -2, -4, 6}

Cf. A109004.

G[n_, m_] := GCD[n, m]
D2[n_, m_] := If[m + 2 <= n, G[n, m + 2] - 2*G[n, m + 1] - G[n, m], {} ];
a = Table[Flatten[Table[D2[n, m], {m, 0, n}]], {n, 0, 10}]; Flatten[a]

Definition corrected and more terms from Georg Fischer, Jun 08 2023

A244590 a(n) = sum( floor(k*n/8), k=1..7 ).

Original entry on oeis.org

0, 0, 4, 7, 12, 14, 18, 21, 28, 28, 32, 35, 40, 42, 46, 49, 56, 56, 60, 63, 68, 70, 74, 77, 84, 84, 88, 91, 96, 98, 102, 105, 112, 112, 116, 119, 124, 126, 130, 133, 140, 140, 144, 147, 152, 154, 158, 161, 168, 168

Offset: 0

Gary Detlefs, Jun 30 2014

This sequence is G(n,8) where G(n,m) = sum(floor(k*n/m), k=1..m-1). This function is referenced in A109004 and is used in the following formula for gcd(n,m): gcd(n,m) = n+m-n*m+2*G(n,m).
Listed sequences of this form are:
G(n,2) ... A004526;
G(3,n) ... A130481;
G(n,4) ... A187326;
G(n,5) ... A187333;
G(n,6) ... A187336;
G(n,7) ... A187337;
G(n,k*n)/k = n*(n-1)/2  = G(n,n+k)-G(n,k).
It is of interest to note that this alternate form of gcd(n,m) will be undefined if m is a function having a zero in it. For example, gcd(n, n mod 4) would be undefined but gcd(n mod 4, n) would be defined.

Cf. A109004.

[&+[Floor(k*n/8): k in [1..7]]: n in [0..50]]; // Bruno Berselli, Jul 01 2014

G:=(n,m)-> sum(floor(k*n/m), k=1..m-1): seq(G(n,8), n = 0..60);

Table[Sum[Floor[k n/8], {k, 1, 7}], {n, 0, 50}] (* Bruno Berselli, Jul 01 2014 *)

[sum(floor(k*n/8) for k in (1..7)) for n in (0..50)] # Bruno Berselli, Jul 01 2014

a(n) = sum( floor(k*n/8), k=1..7 ).
a(n) = ( gcd(n,8) - (n+8) + n*8 )/2.
G.f.: x^2*(4 + 3*x + 5*x^2 + 2*x^3 + 4*x^4 + 3*x^5 + 7*x^6)/((1 + x)*(1 - x)^2*(1 + x^2)*(1 + x^4)). [Bruno Berselli, Jul 01 2014]

Some terms corrected by Bruno Berselli, Jul 01 2014

A330761 Array read by antidiagonals: T(n,k) is the number of faces on a ring formed by connecting the ends of a prismatic rod whose cross-section is an n-sided regular polygon after applying a twist of k/n turns.

Original entry on oeis.org

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

Offset: 1

Harry E. Neel, Dec 29 2019

This sequence begins with two (2). A prismatic rod having two (biconvex) sides is the simplest three-dimensional construct for consideration here. Such a rod when twisted can only have one side and edge or two sides and edges. (Because the numbers of sides and edges are always equal, generally only sides or faces will be referenced.) The number of faces (surfaces) on rings generated by twisting (or not) prismatic rods is the greatest common divisor (GCD) of the number of sides of the rod, n, and the amount of twist, k, applied to the rod before forming a ring. That is that number of faces is equal to gcd(n,k). Because of the relationship of the number of sides of a prismatic rod and the variable of twist that may be applied, all prismatic rods that have a polygonal cross-section that is prime in number (2, 3, 5, 7, 11, etc.) and formed into rings will always have only 1 face (surface) if twisted by any amount that is not a multiple of the prime. E.g., a prismatic rod with a pentagonal cross-section will have 5 faces if left untwisted or if twisted 5/5, 10/5, etc. Any other amount of rotation will always produce 1 face.

The direction of rotation does not matter. This is an infinite sequence in the sense that primes are infinite (not to mention composites). However, it is noted that actual constructs have limitations.

			A prismatic rod having a cross-section that is an octagon will have:
8 faces if no twist is applied or if the amount of twisting is a multiple of 8: 0/8, 8/8, 16/8, etc.;
4 faces if the amount of twisting is 4/8, 12/8, etc.
2 faces if the amount of twisting is 2/8, 6/8, 10/8, etc.
1 face if the amount of twisting is 1/8, 3/8, 5/8, 7/8, 9/8, etc.
Note that the number of faces is equal to gcd(n,k) where n=number of sides of the prismatic rod and k=amount of twist applied to the rod.
T(n,k) as a table begins:
(n=number of sides of polygon; k=amount of fractional twist applied)
   n |k=0  1  2  3  4  5  6  7  8  9 10 11 12 13 ...
  ---+-------------------------------------------
   2 |  2  1  2  1  2  1  2  1  2  1  2  1  2  1...
   3 |  3  1  1  3  1  1  3  1  1  3  1  1  3  1...
   4 |  4  1  2  1  4  1  2  1  4  1  2  1  4  1...
   5 |  5  1  1  1  1  5  1  1  1  1  5  1  1  1...
   6 |  6  1  2  3  2  1  6  1  2  3  2  1  6  1...
   7 |  7  1  1  1  1  1  1  7  1  1  1  1  1  1...
   8 |  8  1  2  1  4  1  2  1  8  1  2  1  4  1...
   9 |  9  1  1  3  1  1  3  1  1  9  1  1  3  1...
  10 | 10  1  2  1  2  5  2  1  2  1 10  1  2  1...
  11 | 11  1  1  1  1  1  1  1  1  1  1 11  1  1...
  12 | 12  1  2  3  4  1  6  1  4  3  2  1 12  1...
  13 | 13  1  1  1  1  1  1  1  1  1  1  1  1 13...
  ...

Martin Gardner, Mathematical Games, A Möbius band has a finite thickness, and so it is actually a twisted prism, Scientific American, August, 1978, 18-25.

Subtable of A109004.

T(n, k) = gcd(n, k).

A384446 Triangle read by rows: T(n, k) = |gcd(n, k) - k|.

Original entry on oeis.org

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

Offset: 0

Peter Luschny, May 29 2025

T(n, k) can be understood as a measure of the divisibility of n by k.

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

Cf. A002262, A109004, A372727.

from math import gcd
print([abs(gcd(n, k) - k) for n in range(13) for k in range(n + 1)])

T(n, 0) = n.
T(n, k) = 0 if k divides n, in particular T(n, 1) = T(n, n) = 0.
T(n, k) = |A002262(n, k) - A109004(n, k)|.

A384447 Array read by ascending antidiagonals: A(n, k) = gcd(n, k) if n > 0 otherwise 0.

Original entry on oeis.org

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

Offset: 0

Peter Luschny, Jun 02 2025

The set D = {A(n, k) : k >= 0} is a subset of [n] := {0, 1, 2,..., n} with the characteristic that for all d in D there exists a d' in D such that d*d'= n. Therefore, D may legitimately be called the 'set of divisors of n'.
However, this is not the standard definition from number theory textbooks, where an existential quantifier conjures up an infinite set out of nothing in the case n = 0. This view is also suggested by the characterization of the divisors of n as the fixed points of gcd on [n].
The form given here is constructive because it can be based on the Euclidean algorithm and with it the set of divisors is always finite.

			The array begins:
  [0] [0, 0, 0, 0, 0, 0, 0, 0, ...
  [1] [1, 1, 1, 1, 1, 1, 1, 1, ...
  [2] [2, 1, 2, 1, 2, 1, 2, 1, ...
  [3] [3, 1, 1, 3, 1, 1, 3, 1, ...
  [4] [4, 1, 2, 1, 4, 1, 2, 1, ...
  [5] [5, 1, 1, 1, 1, 5, 1, 1, ...
  [6] [6, 1, 2, 3, 2, 1, 6, 1, ...
  [7] [7, 1, 1, 1, 1, 1, 1, 7, ...
  [8] [8, 1, 2, 1, 4, 1, 2, 1, ...
  [9] [9, 1, 1, 3, 1, 1, 3, 1, ...
  ...

Cf. A109004, A027750.

A[n_,k_]:=(1-KroneckerDelta[n,0])GCD[n,k]; Table[A[n-k,k],{n,0,12},{k,0,n}]//Flatten (* Stefano Spezia, Jun 02 2025 *)

from math import gcd
def A(n, k): return gcd(n, k) if n > 0 else 0
for n in range(10): print([A(n, k) for k in range(8)])

A(n, k) = A109004(n, k) for 0 <= k <= n.

A384710 a(n) = Sum_{k=0..n} [gcd(k, n) = 1], where [.] are the Iverson brackets.

Original entry on oeis.org

0, 2, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44, 24

Offset: 0

Peter Luschny, Jun 07 2025

nonn

For n >= 2 identical to A000010, which is the main entry for this sequence. However, the fact that the function gcd as well as the Euclidean algorithm are defined for pairs (n >= 0, k >= 0) makes the choice of offset 0 appear more natural than that in A000010.

Graham, Knuth and Patashnik write: "We can make many formulas clearer by adopting a new notation now! Let us agree to write 'm ⟂ n', and to say "m is prime to n," if m and n are relatively prime." Here '⟂' is the perpendicular symbol (\perp in LaTeX, U+27C2 in Unicode), a binary relation symbol not to be confused with the "up tack" symbol (\bot in LaTeX, U+22A5 in Unicode).

			[gcd(0,0)] = [0] => a(0) = 0.
[gcd(0,1), gcd(1,1)] = [1, 1] => a(1) = 2.
[gcd(0,2), gcd(1,2), gcd(2,2)] = [2, 1, 2] => a(2) = 1.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., 1994, ch. 4.5.

Cf. A000010, A217831, A109004, A372728.

isPrimeTo := (k, n) -> ifelse(igcd(k, n) = 1, 1, 0):
a := n -> add(isPrimeTo(k, n), k = 0..n): seq(a(n), n = 0..70);

Table[Sum[Boole[CoprimeQ[k, n]], {k, 0, n}], {n, 0, 70}] (* Michael De Vlieger, Jun 07 2025 *)

a(n) = sum(k = 0, n, gcd(k, n) == 1); \\ Amiram Eldar, Jun 08 2025

from math import gcd
def a(n: int) -> int: return sum(int(1 == gcd(n, k)) for k in range(n + 1))
print([a(n) for n in range(71)])

The row sums of Euclid's triangle A217831.
The row sums of absolute terms of Kronecker's triangle A372728.
a(n) = card({A109004(n, k) = 1 : 0 <= k <= n}).

cp's OEIS Frontend

A140819 Triangle read by rows: T(n, m) = m if 2*m = n, otherwise 2*gcd(n, m).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Extensions

A140822 Triangle T(n,m) = binomial(n,gcd(n,m)) read by rows, 0<=m<=n.

Views

Author

Keywords

Comments

Examples

Programs

Mathematica

Formula

Extensions

A140875 Triangle read by rows: T(n,m) = gcd(n,m+2) - 2*gcd(n,m+1) - gcd(n,m), with diagonal and subdiagonal removed.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Extensions

A244590 a(n) = sum( floor(k*n/8), k=1..7 ).

Views

Author

Keywords

Comments

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

Extensions

A330761 Array read by antidiagonals: T(n,k) is the number of faces on a ring formed by connecting the ends of a prismatic rod whose cross-section is an n-sided regular polygon after applying a twist of k/n turns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A384446 Triangle read by rows: T(n, k) = |gcd(n, k) - k|.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

A384447 Array read by ascending antidiagonals: A(n, k) = gcd(n, k) if n > 0 otherwise 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

A384710 a(n) = Sum_{k=0..n} [gcd(k, n) = 1], where [.] are the Iverson brackets.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A140819 Triangle read by rows: T(n, m) = m if 2m = n, otherwise 2gcd(n, m).