A356300 Square array read by antidiagonals. A(n,k) is the nearest common ancestor of n and k in the binary tree depicted in A253563.

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 2, 2, 2, 2, 1, 1, 2, 3, 4, 3, 2, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 4, 5, 4, 3, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 3, 4, 3, 4, 7, 4, 3, 4, 3, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1

Offset

1,5

Comments

Array is symmetric and is read by antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ... .

Also the nearest common ancestor of n and k in the tree depicted in A253565 (the mirror image of the A253563-tree).

Links

Table of n, a(n) for n=1..105.

Index entries for sequences computed from indices in prime factorization

Example

The top left 21x21 corner of the array:
n/k  |  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21
-----+----------------------------------------------------------------------------
   1 |  1, 1, 1, 1, 1, 1, 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   2 |  1, 2, 2, 2, 2, 2, 2, 2, 2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
   3 |  1, 2, 3, 2, 3, 2, 3, 2, 3,  2,  3,  2,  3,  2,  3,  2,  3,  2,  3,  2,  3,
   4 |  1, 2, 2, 4, 2, 4, 2, 4, 2,  4,  2,  4,  2,  4,  2,  4,  2,  4,  2,  4,  2,
   5 |  1, 2, 3, 2, 5, 2, 5, 2, 3,  2,  5,  2,  5,  2,  3,  2,  5,  2,  5,  2,  3,
   6 |  1, 2, 2, 4, 2, 6, 2, 4, 2,  6,  2,  4,  2,  6,  2,  4,  2,  6,  2,  4,  2,
   7 |  1, 2, 3, 2, 5, 2, 7, 2, 3,  2,  7,  2,  7,  2,  3,  2,  7,  2,  7,  2,  3,
   8 |  1, 2, 2, 4, 2, 4, 2, 8, 2,  4,  2,  8,  2,  4,  2,  8,  2,  4,  2,  8,  2,
   9 |  1, 2, 3, 2, 3, 2, 3, 2, 9,  2,  3,  2,  3,  2,  9,  2,  3,  2,  3,  2,  9,
  10 |  1, 2, 2, 4, 2, 6, 2, 4, 2, 10,  2,  4,  2, 10,  2,  4,  2,  6,  2,  4,  2,
  11 |  1, 2, 3, 2, 5, 2, 7, 2, 3,  2, 11,  2, 11,  2,  3,  2, 11,  2, 11,  2,  3,
  12 |  1, 2, 2, 4, 2, 4, 2, 8, 2,  4,  2, 12,  2,  4,  2,  8,  2,  4,  2, 12,  2,
  13 |  1, 2, 3, 2, 5, 2, 7, 2, 3,  2, 11,  2, 13,  2,  3,  2, 13,  2, 13,  2,  3,
  14 |  1, 2, 2, 4, 2, 6, 2, 4, 2, 10,  2,  4,  2, 14,  2,  4,  2,  6,  2,  4,  2,
  15 |  1, 2, 3, 2, 3, 2, 3, 2, 9,  2,  3,  2,  3,  2, 15,  2,  3,  2,  3,  2, 15,
  16 |  1, 2, 2, 4, 2, 4, 2, 8, 2,  4,  2,  8,  2,  4,  2, 16,  2,  4,  2,  8,  2,
  17 |  1, 2, 3, 2, 5, 2, 7, 2, 3,  2, 11,  2, 13,  2,  3,  2, 17,  2, 17,  2,  3,
  18 |  1, 2, 2, 4, 2, 6, 2, 4, 2,  6,  2,  4,  2,  6,  2,  4,  2, 18,  2,  4,  2,
  19 |  1, 2, 3, 2, 5, 2, 7, 2, 3,  2, 11,  2, 13,  2,  3,  2, 17,  2, 19,  2,  3,
  20 |  1, 2, 2, 4, 2, 4, 2, 8, 2,  4,  2, 12,  2,  4,  2,  8,  2,  4,  2, 20,  2,
  21 |  1, 2, 3, 2, 3, 2, 3, 2, 9,  2,  3,  2,  3,  2, 15,  2,  3,  2,  3,  2, 21,
.
A(3,6) = A(6,3) = 2 because the nearest common ancestor of 3 and 6 in the tree described in A253563 (and in A253565) is 2.
A(4,6) = A(6,4) = 4 because 6 occurs as a descendant of 4 in A253563-tree, thus their nearest common ancestor is 4 itself.

Prog

(PARI)
up_to = 105;
A253553(n) = if(n<=2, 1, my(f=factor(n), k=#f~); if(f[k, 2]>1, f[k, 2]--, f[k, 1] = precprime(f[k, 1]-1)); factorback(f));
A356300sq(x, y) = if(1==x||1==y, 1, my(lista=List([]), i, k=x, stemvec, stemlen, h=y); while(k>1, listput(lista, k); k = A253553(k)); stemvec = Vecrev(Vec(lista)); stemlen = #stemvec; while(1, if((i=vecsearch(stemvec, h))>0, return(stemvec[i])); h = A253553(h)));
A356300list(up_to) = { my(v = vector(up_to), i=0); for(a=1, oo, for(col=1, a, i++; if(i > up_to, return(v)); v[i] = A356300sq(col, (a-(col-1))))); (v); };
v356300 = A356300list(up_to);
A356300(n) = v356300[n];

Crossrefs

Cf. A253553, A253563, A253565, A356301.

Cf. also A348041.

Sequence in context: A230596 A307079 A330190 * A348041 A003983 A087062

Adjacent sequences: A356297 A356298 A356299 * A356301 A356302 A356303

Keyword

nonn,tabl

Author

Antti Karttunen, Aug 03 2022

Status

approved