A285721 -id:A285721 - cp's OEIS frontend

A300237 a(n) = n - A286594(n) = n - A285721(n, sigma(n)).

1, 0, 0, 0, 0, 5, 0, 0, 3, 5, 0, 8, 0, 9, 11, 0, 0, 11, 0, 9, 9, 16, 0, 21, 15, 20, 12, 27, 0, 25, 0, 0, 26, 27, 26, 23, 0, 31, 30, 35, 0, 36, 0, 33, 38, 38, 0, 41, 35, 36, 44, 41, 0, 47, 44, 48, 42, 49, 0, 54, 0, 53, 51, 0, 55, 58, 0, 57, 61, 50, 0, 63, 0, 64, 62, 67, 54, 69, 0, 63, 39, 71, 0, 80, 74, 75, 79, 65, 0, 85, 84, 83, 77, 82, 87, 90, 0, 81

Offset: 1

Antti Karttunen, Mar 02 2018

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537
Antti Karttunen, Scheme (Racket) program to compute this sequence

Cf. A000203, A285721, A286594.

Cf. also A300227, A300228, A300234, A300238.

A285721(n,k) = if(n==k, 0, 1 + A285721(abs(n-k),min(n,k)));
A286594(n) = A285721(n,sigma(n));
A300237(n) = (n - A286594(n));

a(n) = n - A286594(n) = n - A285721(n, A000203(n)).

A300238 a(n) = n - A300234(n) = n - A285721(n, phi(n)).

Original entry on oeis.org

1, 1, 1, 3, 1, 4, 1, 7, 7, 7, 1, 10, 1, 10, 7, 15, 1, 16, 1, 17, 17, 16, 1, 22, 21, 19, 25, 24, 1, 24, 1, 31, 24, 25, 26, 34, 1, 28, 34, 37, 1, 38, 1, 38, 37, 34, 1, 46, 43, 47, 41, 45, 1, 52, 50, 52, 51, 43, 1, 54, 1, 46, 59, 63, 55, 58, 1, 59, 58, 57, 1, 70, 1, 55, 67, 66, 64, 72, 1, 77, 79, 61, 1, 80, 61, 64, 75, 82, 1, 84, 80, 80, 85, 70, 82, 94, 1, 94

Offset: 1

Antti Karttunen, Mar 02 2018

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537
Antti Karttunen, Scheme (Racket) program to compute this sequence

Cf. A000010, A285721.

Cf. also A286594, A300227, A300228, A300234, A300237.

A285721(n,k) = if(n==k, 0, 1 + A285721(abs(n-k),min(n,k)));
A300234(n) = A285721(n,eulerphi(n));
A300238(n) = (n - A300234(n));

a(n) = n - A300234(n) = n - A285721(n, A000010(n)).

A050602 Square array A(x,y), read by antidiagonals, where A(x,y) = 0 if (x AND y) = 0, otherwise A(x,y) = 1+A(x XOR y, 2*(x AND y)).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 2, 1, 2, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 2, 3, 1, 3, 2, 3, 0, 0, 0, 2, 2, 1, 1, 2, 2, 0, 0, 0, 1, 0, 2, 1, 1, 1, 2, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 2, 1, 2, 0, 2, 1, 2, 0, 2, 1, 2, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0

Offset: 0

Antti Karttunen, Jun 22 1999

Array is symmetric and is read by antidiagonals: (0,0), (0,1), (1,0), (0,2), (1,1), (2,0),  etc. - Antti Karttunen, Sep 04 2023
Comment from N. J. A. Sloane, Jun 21 2011: Apparently the same as the following sequence. Infinite square array read by antidiagonals, where T(m,n) = length of longest carry propagation when u and v are added in binary, for u >= 0, v >= 0.
See A192054 for definition of carry propagation. For example, T(3,5) = 3, since adding 011 + 101 in binary, the initial 1 propagates three places.

			The top left corner of the square array:
     |  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
-----+--------------------------------------------------------
   0 |  0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,
   1 |  0, 1, 0, 2, 0, 1, 0, 3, 0, 1,  0,  2,  0,  1,  0,  4,
   2 |  0, 0, 1, 1, 0, 0, 2, 2, 0, 0,  1,  1,  0,  0,  3,  3,
   3 |  0, 2, 1, 1, 0, 3, 2, 2, 0, 2,  1,  1,  0,  4,  3,  3,
   4 |  0, 0, 0, 0, 1, 1, 1, 1, 0, 0,  0,  0,  2,  2,  2,  2,
   5 |  0, 1, 0, 3, 1, 1, 1, 2, 0, 1,  0,  4,  2,  2,  2,  2,
   6 |  0, 0, 2, 2, 1, 1, 1, 1, 0, 0,  3,  3,  2,  2,  2,  2,
   7 |  0, 3, 2, 2, 1, 2, 1, 1, 0, 4,  3,  3,  2,  2,  2,  2,
   8 |  0, 0, 0, 0, 0, 0, 0, 0, 1, 1,  1,  1,  1,  1,  1,  1,
   9 |  0, 1, 0, 2, 0, 1, 0, 4, 1, 1,  1,  2,  1,  1,  1,  3,
  10 |  0, 0, 1, 1, 0, 0, 3, 3, 1, 1,  1,  1,  1,  1,  2,  2,
  11 |  0, 2, 1, 1, 0, 4, 3, 3, 1, 2,  1,  1,  1,  3,  2,  2,
  12 |  0, 0, 0, 0, 2, 2, 2, 2, 1, 1,  1,  1,  1,  1,  1,  1,
  13 |  0, 1, 0, 4, 2, 2, 2, 2, 1, 1,  1,  3,  1,  1,  1,  2,
  14 |  0, 0, 3, 3, 2, 2, 2, 2, 1, 1,  2,  2,  1,  1,  1,  1,
  15 |  0, 4, 3, 3, 2, 2, 2, 2, 1, 3,  2,  2,  1,  2,  1,  1,
etc.

Antti Karttunen, Table of n, a(n) for n = 0..33152; the first 257 antidiagonals, flattened
Beeler, M., Gosper, R. W. and Schroeppel, R., HAKMEM, ITEM 23 (Schroeppel) [(A AND B) + (A OR B) = A + B = (A XOR B) + 2 (A AND B).]
Nicholas Pippenger, Analysis of carry propagation in addition: an elementary approach, J. Algorithms 42 (2002), 317-333.
Index entries for sequences related to binary expansion of n

Row/Column 1: A007814, Row/Column 2: A050605, Row/Column 3: A050606. See also A372554 [A(n, 2n+1)].
Cf. A003056, A003987, A004198, A050600, A050601, A048720.
Cf. also A192054.
Cf. also A072030 (A285721) for similar arrays computed for an elementary Euclidean algorithm.

add3c := proc(a,b) option remember; if(0 = ANDnos(a,b)) then RETURN(0); else RETURN(1+add3c(XORnos(a,b),2*ANDnos(a,b))); fi; end;

a[n_, k_] := a[n, k] = If[0 == BitAnd[n, k], 0, 1 + a[BitXor[n, k], 2*BitAnd[n, k]]]; Table[a[n - k, k], {n, 0, 14}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 16 2014, updated Mar 06 2016 after Maple *)

up_to = 120;
A050602sq(x,y) = if(!bitand(x,y), 0, 1+A050602sq(bitxor(x,y),2*bitand(x,y)));
A050602list(up_to) = { my(v = vector(up_to), i=0); for(a=0, oo, for(col=0, a, i++; if(i > up_to, return(v)); v[i] = A050602sq(col, a-col))); (v); };
v050602 = A050602list(up_to);
A050602(n) = v050602[1+n]; \\ Antti Karttunen, Sep 04 2023

If A004198(x,y) = 0, then A(x,y) = 0, otherwise A(x,y) = 1 + A(A003987(x,y), 2*A004198(x,y)), where A004198 and A003987 are bitwise-AND and bitwise-XOR respectively.

Name edited by Antti Karttunen, Sep 04 2023

A285722 Square array A(n,k) read by antidiagonals, A(n,n) = 0, otherwise, if n > k, A(n,k) = T(n-k,k), else A(n,k) = T(n,k-n), where T(n,k) is sequence A000027 considered as a two-dimensional table.

Original entry on oeis.org

0, 1, 1, 2, 0, 3, 4, 3, 2, 6, 7, 5, 0, 5, 10, 11, 8, 6, 4, 9, 15, 16, 12, 9, 0, 8, 14, 21, 22, 17, 13, 10, 7, 13, 20, 28, 29, 23, 18, 14, 0, 12, 19, 27, 36, 37, 30, 24, 19, 15, 11, 18, 26, 35, 45, 46, 38, 31, 25, 20, 0, 17, 25, 34, 44, 55, 56, 47, 39, 32, 26, 21, 16, 24, 33, 43, 54, 66, 67, 57, 48, 40, 33, 27, 0, 23, 32, 42, 53, 65, 78, 79, 68, 58, 49, 41, 34, 28, 22, 31, 41, 52, 64, 77, 91

Offset: 1

Antti Karttunen, May 03 2017

The array is read by descending antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

			The top left 14 X 14 corner of the array:
   0,  1,  2,  4,  7, 11, 16, 22, 29, 37, 46, 56, 67, 79
   1,  0,  3,  5,  8, 12, 17, 23, 30, 38, 47, 57, 68, 80
   3,  2,  0,  6,  9, 13, 18, 24, 31, 39, 48, 58, 69, 81
   6,  5,  4,  0, 10, 14, 19, 25, 32, 40, 49, 59, 70, 82
  10,  9,  8,  7,  0, 15, 20, 26, 33, 41, 50, 60, 71, 83
  15, 14, 13, 12, 11,  0, 21, 27, 34, 42, 51, 61, 72, 84
  21, 20, 19, 18, 17, 16,  0, 28, 35, 43, 52, 62, 73, 85
  28, 27, 26, 25, 24, 23, 22,  0, 36, 44, 53, 63, 74, 86
  36, 35, 34, 33, 32, 31, 30, 29,  0, 45, 54, 64, 75, 87
  45, 44, 43, 42, 41, 40, 39, 38, 37,  0, 55, 65, 76, 88
  55, 54, 53, 52, 51, 50, 49, 48, 47, 46,  0, 66, 77, 89
  66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56,  0, 78, 90
  78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67,  0, 91
  91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79,  0

Antti Karttunen, Table of n, a(n) for n = 1..10585
MathWorld, Pairing Function

Transpose: A285723.
Cf. A000124 (row 1, from 1 onward), A000217 (column 1).
Cf. also A000027, A003989, A072030, A285721, A285732.

A[n_, n_] = 0;
A[n_, k_] /; k == n-1 := (k^2 - k + 2)/2;
A[1, k_] := (k^2 - 3k + 4)/2;
A[n_, k_] /; 1 <= k <= n-2 := A[n, k] = A[n, k+1] + 1;
A[n_, k_] /; k > n := A[n, k] = A[n-1, k] + 1;
Table[A[n-k+1, k], {n, 1, 14}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Nov 19 2019 *)

def T(n, m): return ((n + m)**2 - n - 3*m + 2)//2
def A(n, k): return 0 if n == k else T(n - k, k) if n>k else T(n, k - n)
for n in range(1, 21): print([A(k, n - k + 1) for k in range(1, n + 1)]) # Indranil Ghosh, May 03 2017

(define (A285722 n) (A285722bi (A002260 n) (A004736 n)))
(define (A285722bi row col) (cond ((= row col) 0) ((> row col) (A000027bi (- row col) col)) (else (A000027bi row (- col row)))))
(define (A000027bi row col) (* (/ 1 2) (+ (expt (+ row col) 2) (- row) (- (* 3 col)) 2)))

If n = k, A(n,k) = 0, if n > k, A(n,k) = T(n-k,k), otherwise [when n < k], A(n,k) = T(n,k-n), where T(n,k) is sequence A000027 considered as a two-dimensional table, that is, as a pairing function from N X N to N.

A285732 Square array A(n,k) read by antidiagonals, A(n,n) = -n, otherwise, if n > k, A(n,k) = T(n-k,k), else A(n,k) = T(n,k-n), where T(n,k) is sequence A000027 considered as a two-dimensional table.

Original entry on oeis.org

-1, 1, 1, 2, -2, 3, 4, 3, 2, 6, 7, 5, -3, 5, 10, 11, 8, 6, 4, 9, 15, 16, 12, 9, -4, 8, 14, 21, 22, 17, 13, 10, 7, 13, 20, 28, 29, 23, 18, 14, -5, 12, 19, 27, 36, 37, 30, 24, 19, 15, 11, 18, 26, 35, 45, 46, 38, 31, 25, 20, -6, 17, 25, 34, 44, 55, 56, 47, 39, 32, 26, 21, 16, 24, 33, 43, 54, 66, 67, 57, 48, 40, 33, 27, -7, 23, 32, 42, 53, 65, 78

Offset: 1

Antti Karttunen, May 03 2017

The array is read by descending antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

			The top left 14 X 14 corner of the array:
  -1,  1,  2,  4,  7, 11, 16, 22, 29,  37,  46,  56,  67,  79
   1, -2,  3,  5,  8, 12, 17, 23, 30,  38,  47,  57,  68,  80
   3,  2, -3,  6,  9, 13, 18, 24, 31,  39,  48,  58,  69,  81
   6,  5,  4, -4, 10, 14, 19, 25, 32,  40,  49,  59,  70,  82
  10,  9,  8,  7, -5, 15, 20, 26, 33,  41,  50,  60,  71,  83
  15, 14, 13, 12, 11, -6, 21, 27, 34,  42,  51,  61,  72,  84
  21, 20, 19, 18, 17, 16, -7, 28, 35,  43,  52,  62,  73,  85
  28, 27, 26, 25, 24, 23, 22, -8, 36,  44,  53,  63,  74,  86
  36, 35, 34, 33, 32, 31, 30, 29, -9,  45,  54,  64,  75,  87
  45, 44, 43, 42, 41, 40, 39, 38, 37, -10,  55,  65,  76,  88
  55, 54, 53, 52, 51, 50, 49, 48, 47,  46, -11,  66,  77,  89
  66, 65, 64, 63, 62, 61, 60, 59, 58,  57,  56, -12,  78,  90
  78, 77, 76, 75, 74, 73, 72, 71, 70,  69,  68,  67, -13,  91
  91, 90, 89, 88, 87, 86, 85, 84, 83,  82,  81,  80,  79, -14

Antti Karttunen, Table of n, a(n) for n = 1..10585; the first 145 antidiagonals of the array
MathWorld, Pairing Function

Transpose: A285733.
Cf. A000124 (row 1, after -1), A000217 (column 1, after -1).
Cf. also A000027, A003989, A072030, A285721, A285722, A286100.

def T(n, m): return ((n + m)**2 - n - 3*m + 2)//2
def A(n, k): return -n if n == k else T(n - k, k) if n>k else T(n, k - n)
for n in range(1, 21): print([A(k, n - k + 1) for k in range(1, n + 1)]) # Indranil Ghosh, May 03 2017

(define (A285732 n) (A285732bi (A002260 n) (A004736 n)))
(define (A285732bi row col) (cond ((= row col) (- row)) ((> row col) (A000027bi (- row col) col)) (else (A000027bi row (- col row)))))

If n = k, A(n,k) = -n, if n > k, A(n,k) = T(n-k,k), otherwise [when n < k], A(n,k) = T(n,k-n), where T(n,k) is sequence A000027 considered as a two-dimensional table, that is, as a pairing function from N X N to N.

A(n,k) = A285722(n,k) - A286100(n,k).

A286594 a(n) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k when starting with n = n and k = A000203(n).

Original entry on oeis.org

0, 2, 3, 4, 5, 1, 7, 8, 6, 5, 11, 4, 13, 5, 4, 16, 17, 7, 19, 11, 12, 6, 23, 3, 10, 6, 15, 1, 29, 5, 31, 32, 7, 7, 9, 13, 37, 7, 9, 5, 41, 6, 43, 11, 7, 8, 47, 7, 14, 14, 7, 11, 53, 7, 11, 8, 15, 9, 59, 6, 61, 9, 12, 64, 10, 8, 67, 11, 8, 20, 71, 9, 73, 10, 13, 9, 23, 9, 79, 17, 42, 11, 83, 4, 11, 11, 8, 23, 89, 5, 7, 9, 16, 12, 8, 6, 97, 17, 9, 16, 101, 11

Offset: 1

Antti Karttunen, May 21 2017

nonn

			For n = 1, sigma(1) = 1, and the arguments for gcd are equal at the start, thus a(1) = 0.
For n = 2, sigma(2) = 3, gcd(3,2) = gcd(2,1) = gcd(1,1), thus 2 steps were required to reach the termination condition, and a(2) = 2.
For n = 6, sigma(6) = 12, gcd(12,6) = gcd(6,6), thus a(6) = 1.
For n = 9, sigma(9) = 13, gcd(13,9) = gcd(9,4) = gcd(5,4) = gcd(4,1) = gcd(3,1) = gcd(2,1) = gcd(1,1), thus a(9) = 6.
Here the simple subtracting version of gcd-algorithm is used, where the new arguments will be the smaller argument and the smaller argument subtracted from the larger, and this is repeated until both are equal.

Antti Karttunen, Table of n, a(n) for n = 1..10000
Antti Karttunen, Scheme (Racket) program to compute this sequence

Cf. A000203, A009194, A285721.
Cf. A000396 (positions of 1's).
Cf. also A300227, A300228, A300234, A300237, A300238.

A285721(n,k) = if(n==k, 0, 1 + A285721(abs(n-k),min(n,k)));
A286594(n) = A285721(n,sigma(n)); \\ Antti Karttunen, Mar 02 2018

from sympy import divisor_sigma
def A(n, k): return 0 if n==k else 1 + A(abs(n - k), min(n, k))
def a(n): return A(n, divisor_sigma(n)) # Indranil Ghosh, May 22 2017

(define (A286594 n) (A285721bi n (A000203 n))) ;; Requires also code from A000203 and A285721.

a(n) = A285721(n, A000203(n)) = A285721(A000203(n), n).

a(n) = n - A300237(n). - Antti Karttunen, Mar 02 2018

A300227 a(n) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k when starting with n = n and k = sigma(n)-1, with a(1) = 1.

Original entry on oeis.org

1, 0, 0, 2, 0, 6, 0, 4, 3, 6, 0, 5, 0, 7, 9, 8, 0, 10, 0, 21, 12, 8, 0, 10, 5, 8, 6, 28, 0, 9, 0, 16, 9, 9, 14, 3, 0, 10, 9, 11, 0, 11, 0, 13, 11, 11, 0, 8, 7, 10, 10, 12, 0, 16, 10, 9, 10, 12, 0, 11, 0, 13, 11, 32, 10, 7, 0, 13, 13, 27, 0, 10, 0, 14, 8, 13, 11, 19, 0, 9, 15, 15, 0, 15, 13, 16, 11, 33, 0, 13, 12, 12, 11, 17, 27, 14, 0

Offset: 1

Antti Karttunen, Mar 02 2018

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537
Antti Karttunen, Scheme (Racket) program to compute this sequence

Cf. A000203, A285721.

Cf. also A286594, A300228, A300234, A300237, A300238.

A285721(n,k) = if(n==k, 0, 1 + A285721(abs(n-k),min(n,k)));
A300227(n) = if(1==n,n,A285721(n,sigma(n)-1));

a(1) = 1; for n > 1, a(n) = A285721(n,A000203(n)-1).

A300228 a(n) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k when starting with n = n and k = 1+phi(n).

Original entry on oeis.org

1, 0, 0, 3, 0, 1, 0, 4, 5, 1, 0, 5, 0, 1, 3, 6, 0, 6, 0, 7, 6, 1, 0, 4, 9, 1, 7, 9, 0, 5, 0, 10, 5, 1, 4, 8, 0, 1, 8, 9, 0, 9, 0, 13, 5, 1, 0, 9, 13, 8, 7, 15, 0, 10, 16, 11, 10, 1, 0, 12, 0, 1, 9, 18, 19, 9, 0, 19, 9, 6, 0, 12, 0, 1, 12, 21, 11, 13, 0, 10, 13, 1, 0, 10, 7, 1, 11, 13, 0, 6, 22, 25, 14, 1, 13, 12, 0, 10, 12, 10, 0, 13, 0, 15, 8

Offset: 1

Antti Karttunen, Mar 02 2018

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537
Antti Karttunen, Scheme (Racket) program to compute this sequence

Cf. A000010, A285721.

Cf. also A286594, A300227, A300234, A300237, A300238.

A285721(n,k) = if(n==k, 0, 1 + A285721(abs(n-k),min(n,k)));
A300228(n) = A285721(n,1+eulerphi(n));

a(n) = A285721(n,1+A000010(n)).

A300234 a(n) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k when starting with n = n and k = phi(n).

Original entry on oeis.org

0, 1, 2, 1, 4, 2, 6, 1, 2, 3, 10, 2, 12, 4, 8, 1, 16, 2, 18, 3, 4, 6, 22, 2, 4, 7, 2, 4, 28, 6, 30, 1, 9, 9, 9, 2, 36, 10, 5, 3, 40, 4, 42, 6, 8, 12, 46, 2, 6, 3, 10, 7, 52, 2, 5, 4, 6, 15, 58, 6, 60, 16, 4, 1, 10, 8, 66, 9, 11, 13, 70, 2, 72, 19, 8, 10, 13, 6, 78, 3, 2, 21, 82, 4, 24, 22, 12, 6, 88, 6, 11, 12, 8, 24, 13, 2, 96, 4, 9, 3, 100, 10, 102, 7, 9

Offset: 1

Antti Karttunen, Mar 02 2018

nonn

			For n = 1, phi(1) = 1, and the arguments for gcd are equal at the start, thus a(1) = 0.
For n = 2, eulerphi(2) = 1, gcd(2,1) = gcd(1,1), thus 1 step were required to reach the termination condition, and a(2) = 1.
For n = 5, eulerphi(5) = 4, gcd(5,4) = gcd(4,1) = gcd(3,1) = gcd(2,1) = gcd(1,1), four steps required, thus a(5) = 4.
For n = 6, eulerphi(6) = 2, gcd(6,2) = gcd(4,2) = gcd(2,2), two steps required, thus a(6) = 2.
Here a simple subtracting version of gcd-algorithm is used, where the new versions of two arguments will be the smaller argument and the smaller argument subtracted from the larger, and this is repeated until both are equal.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Antti Karttunen, Scheme (Racket) program to compute this sequence

Cf. A000010, A285721.

Cf. also A286594, A300227, A300228, A300237, A300238.

A285721(n,k) = if(n==k, 0, 1 + A285721(abs(n-k),min(n,k)));
A300234(n) = A285721(n,eulerphi(n));

a(n) = A285721(n,A000010(n)).

a(n) = n - A300238(n).

A377459 Square array T(n,k) read by ascending antidiagonals: number of steps for a certain Euclidean-style algorithm (see below) to find the GCD of n and k.

Original entry on oeis.org

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

Offset: 1

Thomas Anton, Jan 03 2025

The algorithm begins with the list n,k. Each step appends to the list the absolute difference of the last two items on the list. The algorithm terminates when the last two items are equal. These will share the value of the GCD of n and k.

			For T(5,2), the list of successive absolute differences is as follows and reaches equal values (1,1) after T(5,2) = 5 steps,
    5,2, 3, 1, 2, 1, 1
         \-----------/  steps
The array begins:
  n\k|  1  2  3  4  5  6   7   8  ...
  ---+-------------------------------
   1 |  0, 2, 3, 5, 6, 8,  9, 11, ...
   2 |  1, 0, 4, 2, 4, 3,  7,  5, ...
   3 |  3, 2, 0, 5, 6, 2,  6,  5, ...
   4 |  4, 1, 4, 0, 7, 4,  7,  2, ...
   5 |  6, 5, 3, 5, 0, 8,  6,  8, ...
   6 |  7, 3, 1, 2, 7, 0, 10,  5, ...
   7 |  9, 5, 6, 5, 6, 8,  0, 11, ...
   8 | 10, 4, 7, 1, 4, 4, 10,  0, ...
  ...

Cf. A072030, A285721.

def T(n,k):
    old = n
    new = k
    steps = 0
    while old != new:
        old, new, steps = new, abs(new-old), steps+1
    return steps

Uniquely determined by the following seven equations:
T(n,n) = 0,
T(n,2n) = 2,
T(2k,k) = 1,
T(n,n+k) = T(n,n-k)+3,
T(k+n,k) = T(k-n,k),
T(n,2n+k) = T(n,k)+3,
T(n+2k,k) = T(n,k)+3.

cp's OEIS Frontend

A300237 a(n) = n - A286594(n) = n - A285721(n, sigma(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A300238 a(n) = n - A300234(n) = n - A285721(n, phi(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A050602 Square array A(x,y), read by antidiagonals, where A(x,y) = 0 if (x AND y) = 0, otherwise A(x,y) = 1+A(x XOR y, 2*(x AND y)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A285722 Square array A(n,k) read by antidiagonals, A(n,n) = 0, otherwise, if n > k, A(n,k) = T(n-k,k), else A(n,k) = T(n,k-n), where T(n,k) is sequence A000027 considered as a two-dimensional table.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A285732 Square array A(n,k) read by antidiagonals, A(n,n) = -n, otherwise, if n > k, A(n,k) = T(n-k,k), else A(n,k) = T(n,k-n), where T(n,k) is sequence A000027 considered as a two-dimensional table.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Scheme

Formula

A286594 a(n) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k when starting with n = n and k = A000203(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Scheme

Formula

A300227 a(n) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k when starting with n = n and k = sigma(n)-1, with a(1) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A300228 a(n) = number of steps in simple Euclidean algorithm for gcd(n,k) to reach the termination test n=k when starting with n = n and k = 1+phi(n).