A054531 -id:A054531 - cp's OEIS frontend

A226314 Triangle read by rows: T(i,j) = j+(i-j)/gcd(i,j) (1<=i<=j).

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

Offset: 1

N. J. A. Sloane, Jun 09 2013

The triangle of fractions A226314(i,j)/A054531(i,j) is an efficient way to enumerate the rationals [Fortnow].

Sum(A226314(n,k)/A054531(n,k): 1<=k<=n) = A226555(n)/A040001(n). - Reinhard Zumkeller, Jun 10 2013

			Triangle begins:
[1]
[1, 2]
[1, 2, 3]
[1, 3, 3, 4]
[1, 2, 3, 4, 5]
[1, 4, 5, 5, 5, 6]
[1, 2, 3, 4, 5, 6, 7]
[1, 5, 3, 7, 5, 7, 7, 8]
[1, 2, 7, 4, 5, 8, 7, 8, 9]
[1, 6, 3, 7, 9, 8, 7, 9, 9, 10]
...
The resulting triangle of fractions begins:
1,
1/2, 2,
1/3, 2/3, 3,
1/4, 3/2, 3/4, 4,
1/5, 2/5, 3/5, 4/5, 5,
...

Reinhard Zumkeller, Rows n = 1..120 of triangle, flattened
Lance Fortnow, Counting the Rationals Quickly, Computational Complexity Weblog, Monday, March 01, 2004.
Yoram Sagher, Counting the rationals, Amer. Math. Monthly, 96 (1989), p. 823. Math. Rev. 90i:04001.

Cf. A002262.

Cf. A037161, A037162, A066657, A066658.

a226314 n k = n - (n - k) `div` gcd n k
a226314_row n = a226314_tabl !! (n-1)
a226314_tabl = map f $ tail a002262_tabl where
   f us'@(_:us) = map (v -) $ zipWith div vs (map (gcd v) us)
     where (v:vs) = reverse us'
-- Reinhard Zumkeller, Jun 10 2013

f:=(i,j) -> j+(i-j)/gcd(i,j);
g:=n->[seq(f(i,n),i=1..n)];
for n from 1 to 20 do lprint(g(n)); od:

A164306 Triangle read by rows: T(n, k) = k / gcd(k, n), 1 <= k <= n.

Original entry on oeis.org

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

Offset: 1

Reinhard Zumkeller, Aug 12 2009

Also the gcd of the coefficients of the partition polynomials (called 'De Moivre polynomials' by O'Sullivan, see link, Theorem 4.1). - Peter Luschny, Sep 20 2022

			From _Indranil Ghosh_, Feb 14 2017: (Start)
Triangle begins:
1,
1, 1,
1, 2, 1,
1, 1, 3, 1,
1, 2, 3, 4, 1,
1, 1, 1, 2, 5, 1,
1, 2, 3, 4, 5, 6, 1,
. . .
T(4,3) = 3 / gcd(3,4) = 3 / 1 = 3. (End)

Indranil Ghosh, Rows 1..120 of triangle, flattened.
Cormac O'Sullivan, De Moivre and Bell polynomials, arXiv:2203.02868 [math.CO], 2022.

Cf. A051537, A054531, A057661, A167192.

seq(seq(k / igcd(n, k), k = 1..n), n = 1..13); # Peter Luschny, Sep 20 2022

Flatten[Table[k/GCD[k,n],{n,20},{k,n}]] (* Harvey P. Dale, Jul 21 2013 *)

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

Sum of n-th row = A057661(n).

T(n, k) = A051537(n, k)/A054531(n, k). - Reinhard Zumkeller, Oct 30 2009

A167192 Triangle read by rows: T(n,k) = (n-k)/gcd(n,k), 1 <= k <= n.

Original entry on oeis.org

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

Offset: 1

Reinhard Zumkeller, Oct 30 2009

			The triangle T(n,k) begins:
n\k   1   2   3   4  5  6  7  8  9 10 11 12 13  14  15 ...
1:    0
2:    1   0
3:    2   1   0
4:    3   1   1   0
5:    4   3   2   1  0
6:    5   2   1   1  1  0
7:    6   5   4   3  2  1  0
8:    7   3   5   1  3  1  1  0
9:    8   7   2   5  4  1  2  1  0
10:   9   4   7   3  1  2  3  1  1  0
11:  10   9   8   7  6  5  4  3  2  1  0
12:  11   5   3   2  7  1  5  1  1  1  1  0
13:  12  11  10   9  8  7  6  5  4  3  2  1  0
14:  13   6  11   5  9  4  1  3  5  2  3  1  1   0
15:  14  13   4  11  2  3  8  7  2  1  4  1  2   1   0
- _Wolfdieter Lang_, Feb 20 2013

Indranil Ghosh, Rows 1..120 of triangle, flattened

Cf. A054531, A112543, A164306.

Flatten[Table[(n-k)/GCD[n,k],{n,20},{k,n}]] (* Harvey P. Dale, Nov 27 2015 *)

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

T(n,k) = (n-k)/gcd(n,k), 1 <= k <= n.
T(n,k) = A025581(n,k)/A050873(n,k);
T(n,1) = A001477(n-1);
T(n,2) = A026741(n-2) for n > 1;
T(n,3) = A051176(n-3) for n > 2;
T(n,4) = A060819(n-4) for n > 4;
T(n,n-3) = A144437(n) for n > 3;
T(n,n-2) = A000034(n) for n > 2;
T(n,n-1) = A000012(n);
T(n,n) = A000004(n).

A106448 Table of (x+y)/gcd(x,y) where (x,y) runs through the pairs (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), ...

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, May 21 2005

Can also be viewed as a triangular table T(n,k) (n>=1, 1<=k<=n) read by rows: T(1,1); T(2,1), T(2,2); T(3,1), T(3,2), T(3,3); T(4,1), T(4,2), T(4,3), T(4,4); ... where T(n,k) gives the least value v>0 such that v*k = 0 modulo n+1, i.e., in other words, T(n,k) = (n+1)/gcd(n+1,k).

			The top left corner of the square array is:
   2  3  4  5  6  7  8  9 10 11 ...
   3  2  5  3  7  4  9  5 11 ...
   4  5  2  7  8  3 10 11 ...
   5  3  7  2  9  5 11 ...
   6  7  8  9  2 11 ...
   7  4  3  5 11 ...
   8  9 10 11 ...
   9  5 11 ...
  10 11 ...
  11 ...

GF(2)[X] analog: A106449. Row 1 is n+1, row 2 is LEFT(LEFT(LEFT(A026741))), row 3 is LEFT^4(A051176). Essentially the same as A054531, but without its right-hand edge of all-1's.

Equals A003057/A003989.

T(n, k) = numerator((n+k)/n) = numerator((n+k)/k). - Michel Marcus, Dec 29 2013

A201144 The pebble sequence: a(n) is the length of the longest non-repeating sequence of pebble-moves among the partitions of n.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 8, 9, 11, 13, 13, 13, 14, 19, 21, 21, 18, 19, 22, 29, 31, 31, 25, 25, 26, 33, 41, 43, 43, 36, 32, 33, 37, 46, 55, 57, 57, 49, 41, 41, 42, 51, 61, 71, 73, 73, 64, 55, 50, 51, 56, 67, 78, 89, 91, 91, 81, 71, 61, 61, 62, 73, 85, 97, 109, 111, 111, 100, 89, 78, 72, 73, 79, 92, 105, 118, 131, 133, 133, 121, 109, 97, 85, 85, 86, 99, 113, 127, 141, 155, 157, 157, 144, 131, 118, 105, 98, 99, 106, 121

Offset: 1

N. J. A. Sloane, Nov 27 2011

nonn

You have n pebbles arranged in several piles. At each turn you take one pebble from each pile and put them into a new pile.
For example, if you start with one pile of 6, at the next step there are two piles: {1,5}, then {2,4}, and so on. Eventually the sequence of partitions will repeat.
Here a(n) is the maximal number of steps before a repeat among all starting partitions.

			For example, for n = 6, the worst case is {2,2,1,1}, and the steps are: {2, 2, 1, 1}, {1, 1, 4}, {3, 3}, {2, 2, 2}, {1, 1, 1, 3}, {2, 4}, {1, 2, 3}, {1, 2, 3}, {1, 2, 3}, {1, 2, 3}, {1, 2, 3}. Hence a(6) = 7.

Jorgen Brandt, Cycles of Partitions, Proc. AMS, Vol. 85, No. 3 (July, 1982), pp. 483-486
Tanya Khovanova and others, Postings to the Sequence Fans Mailing List, circa Nov 18 2009

For the length of the longest cycle, see A183110. For the length of the shortest cycle, see A054531.

In[33]:= << Combinatorica`
step[list_] := Sort[Select[Prepend[list - 1, Length[list]], # > 0 &]]
cycleStart[list_] := (res = 1; sofar = {list}; current = list;
nextStep = Nest[step, current, 1];
While[! MemberQ[sofar, nextStep], res++; current = nextStep;
  nextStep = Nest[step, current, 1]; sofar = Append[sofar, current]];
  res)
Table[Max[Map[cycleStart, Partitions[n]]], {n, 30}]
Out[36]= {1, 2, 3, 5, 6, 7, 8, 9, 11, 13, 13, 13, 14, 19, 21, 21, 18, 19, 22, 29, 31, 31, 25, 25, 26, 33, 41, 43, 43, 36}

A277227 Triangular array T read by rows: T(n,k) gives the additive orders k modulo n, for k = 0,1, ..., n-1.

Original entry on oeis.org

1, 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

Offset: 1

Wolfdieter Lang, Oct 20 2016

As a sequence A054531(n) = a(n+1), n >= 1.
As a triangular array this is the row reversed version of A054531.
The additive order of an element x of a group (G, +) is the least positive integer j with j*x := x + x + ... + x (j summands) = 0.
Equals A106448 when the first column (k = 0) of ones is removed. - Georg Fischer, Jul 26 2023

			The triangle begins:
n\k 0  1  2  3  4  5  6  7  8  9 10 11 ...
1:  1
2:  1  2
3:  1  3  3
4:  1  4  2  4
5:  1  5  5  5  5
6:  1  6  3  2  3  6
7:  1  7  7  7  7  7  7
8:  1  8  4  8  2  8  4  8
9:  1  9  9  3  9  9  3  9  9
10: 1 10  5 10  5  2  5 10  5 10
11: 1 11 11 11 11 11 11 11 11 11 11
12: 1 12  6  4  3 12  2 12  3  4  6 12
...
T(n, 0) = 1*0 = 0 = 0 (mod n), and n/GCD(n,0) = n/n = 1.
T(4, 2) = 2 because 2 + 2 = 4 = 0 (mod 4) and 2 is not 0 (mod 4).
T(4, 2) = n/GCD(2, 4) = 4/2 = 2.

Indranil Ghosh, Rows 1..100 of triangle, flattened

Cf. A054531, A106448.

T(n, k) = order of the elements k  of the finite abelian group (Z/(n Z), +), for k = 0, 1, ..., n-1.
T(n, k) = n/GCD(n, k), n >= 1, k = 0, 1, ..., n-1.
T(n, k) = A054531(n, n-k), n >=1, k = 0, 1, ..., n-1.

A341314 Array read by antidiagonals: T(n,k) = (n+k)/gcd(n,k), n>=0, k>=0.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Feb 17 2021

We define gcd(0,0) = 0.

This sequence arose when studying Reed Kelly's A214551.

			The array begins:
  0,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, ...
  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, ...
  1,  3,  2,  5,  3,  7,  4,  9,  5, 11,  6, 13,  7, ...
  1,  4,  5,  2,  7,  8,  3, 10, 11,  4, 13, 14,  5, ...
  1,  5,  3,  7,  2,  9,  5, 11,  3, 13,  7, 15,  4, ...
  1,  6,  7,  8,  9,  2, 11, 12, 13, 14,  3, 16, 17, ...
  1,  7,  4,  3,  5, 11,  2, 13,  7,  5,  8, 17,  3, ...
  1,  8,  9, 10, 11, 12, 13,  2, 15, 16, 17, 18, 19, ...
  1,  9,  5, 11,  3, 13,  7, 15,  2, 17,  9, 19,  5, ...
  1, 10, 11,  4, 13, 14,  5, 16, 17,  2, 19, 20,  7, ...
  1, 11,  6, 13,  7,  3,  8, 17,  9, 19,  2, 21, 11, ...
  1, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,  2, 23, ...
  1, 13,  7,  5,  4, 17,  3, 19,  5,  7, 11, 23,  2, ...
...
The first few antidiagonals are:
  [0]
  [1, 1]
  [1, 2, 1]
  [1, 3, 3, 1]
  [1, 4, 2, 4, 1]
  [1, 5, 5, 5, 5, 1]
  [1, 6, 3, 2, 3, 6, 1]
  [1, 7, 7, 7, 7, 7, 7, 1]
  [1, 8, 4, 8, 2, 8, 4, 8, 1]
  ...

A054531 is a similar sequence. See also A341315, A341316.

Cf. A214551.

fa:= (m,n) -> if m=0 and n=0 then 0 else (m+n)/igcd(m,n); fi;
for m from 0 to 12 do lprint([seq(fa(m-n,n),n=0..m)]); od:
for m from 0 to 12 do lprint([seq(fa(m,n),n=0..12)]); od:

A341315 Triangle read by rows: T(n,k) = (n+k)/gcd(n,k), n>=0, 0<=k<=n.

Original entry on oeis.org

0, 1, 2, 1, 3, 2, 1, 4, 5, 2, 1, 5, 3, 7, 2, 1, 6, 7, 8, 9, 2, 1, 7, 4, 3, 5, 11, 2, 1, 8, 9, 10, 11, 12, 13, 2, 1, 9, 5, 11, 3, 13, 7, 15, 2, 1, 10, 11, 4, 13, 14, 5, 16, 17, 2, 1, 11, 6, 13, 7, 3, 8, 17, 9, 19, 2, 1, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 2, 1, 13, 7, 5, 4, 17, 3, 19, 5, 7, 11, 23, 2

Offset: 0

N. J. A. Sloane, Feb 17 2021

We define gcd(0,0) = 0.

This is half of the array A341314. See that entry for further information.

			Triangle begins:
  [0]
  [1,  2]
  [1,  3,  2]
  [1,  4,  5,  2]
  [1,  5,  3,  7,  2]
  [1,  6,  7,  8,  9,  2]
  [1,  7,  4,  3,  5, 11,  2]
  [1,  8,  9, 10, 11, 12, 13,  2]
  [1,  9,  5, 11,  3, 13,  7, 15,  2]
  [1, 10, 11,  4, 13, 14,  5, 16, 17,  2]
  [1, 11,  6, 13,  7,  3,  8, 17,  9, 19, 2]
  [1, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 2]
  ...

Cf. A341314. A054531 is essentially the same triangle.

See A341316 for the row sums.

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

Original entry on oeis.org

1, -1, -1, 0, -1, 2, -1, 0, 1, 4, -1, -2, -1, 6, 5, 0, -1, -8, -1, -12, 7, 10, -1, 6, 3, 12, -5, -30, -1, -54, -1, 0, 11, 16, 9, 48, -1, 18, 13, 84, -1, -116, -1, -90, -41, 22, -1, -42, 5, -72, 17, -132, -1, 130, 13, 330, 19, 28, -1, 482, -1, 30, -83, 0, 15, -312, -1, -240, 23, -258

Offset: 1

Ilya Gutkovskiy, Apr 28 2021

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

Cf. A000010, A023900, A054531, A332792, A343762.

f:= proc(n) option remember; local G,g;
  G:= subs(1=NULL, map(igcd,[$1..n],n));
  -add(procname(n/g), g=G);
end proc:
f(1):= 1:
map(f, [$1..100]); # Robert Israel, Dec 21 2022

a[1] = 1; a[n_] := a[n] = -Sum[If[GCD[n, k] > 1, a[n/GCD[n, k]], 0], {k, 1, n}]; Table[a[n], {n, 1, 70}]
a[1] = 1; a[n_] := -Sum[If[d < n, EulerPhi[d] a[d], 0], {d, Divisors[n]}]; Table[a[n], {n, 1, 70}]

a(1) = 1; a(n) = -Sum_{d|n, d < n} phi(d) * a(d).

A296420 Period of last digit of multiples of n.

Original entry on oeis.org

1, 10, 5, 10, 5, 2, 5, 10, 5, 10, 1, 10, 5, 10, 5, 2, 5, 10, 5, 10, 1, 10, 5, 10, 5, 2, 5, 10, 5, 10, 1, 10, 5, 10, 5, 2, 5, 10, 5, 10, 1, 10, 5, 10, 5, 2, 5, 10, 5, 10, 1, 10, 5, 10, 5, 2, 5, 10, 5, 10, 1, 10, 5, 10, 5, 2, 5, 10, 5, 10, 1, 10, 5, 10, 5, 2, 5, 10

Offset: 0

Leonardo Sznajder, Dec 11 2017

The list is periodic, with period 10.

			a(6)=5 because multiples of 6 are 6, 12, 18, 24, 30, 36, 42 and the last digits of those numbers are 6,2,8,4,0,6,2,... with a period of 5.

Cf. A054531.

Array[10/GCD[#, 10] &, 77] (* Michael De Vlieger, Dec 23 2017 *)

a(n) = 10/gcd(n, 10) \\ Iain Fox, Dec 11 2017

More terms from Michael De Vlieger, Dec 23 2017.

Term a(0) = 1 prepended by Halfdan Skjerning, Jun 18 2019

cp's OEIS Frontend

A226314 Triangle read by rows: T(i,j) = j+(i-j)/gcd(i,j) (1<=i<=j).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

A164306 Triangle read by rows: T(n, k) = k / gcd(k, n), 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A167192 Triangle read by rows: T(n,k) = (n-k)/gcd(n,k), 1 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A106448 Table of (x+y)/gcd(x,y) where (x,y) runs through the pairs (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), ...

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A201144 The pebble sequence: a(n) is the length of the longest non-repeating sequence of pebble-moves among the partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A277227 Triangular array T read by rows: T(n,k) gives the additive orders k modulo n, for k = 0,1, ..., n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A341314 Array read by antidiagonals: T(n,k) = (n+k)/gcd(n,k), n>=0, k>=0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

A341315 Triangle read by rows: T(n,k) = (n+k)/gcd(n,k), n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Crossrefs

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