A348042 Square array A(n,k) = the nearest common ancestor of n, k and n*k in Doudna tree (A005940).

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 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, 2, 2, 2, 3, 2, 1, 1, 2, 2, 2, 3, 3, 2, 2, 2, 1, 1, 2, 2, 4, 3, 2, 3, 4, 2, 2, 1, 1, 2, 3, 4, 2, 3, 3, 2, 4, 3, 2, 1, 1, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1

Offset: 1

Author

Antti Karttunen, Sep 27 2021

Keywords

• nonn
• tabl

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), ...

Examples

			The top left 17x17 corner of the array:
  n/k |  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17
------+-------------------------------------------------------------
    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,
    3 |  1, 2, 2, 2, 3, 2, 3, 2, 2,  3,  3,  2,  3,  3,  3,  2,  3,
    4 |  1, 2, 2, 4, 2, 2, 2, 4, 4,  2,  2,  2,  2,  2,  2,  4,  2,
    5 |  1, 2, 3, 2, 2, 3, 3, 2, 2,  2,  5,  3,  5,  3,  2,  2,  5,
    6 |  1, 2, 2, 2, 3, 2, 3, 2, 2,  3,  3,  2,  3,  3,  6,  2,  3,
    7 |  1, 2, 3, 2, 3, 3, 2, 2, 2,  3,  3,  3,  5,  2,  3,  2,  7,
    8 |  1, 2, 2, 4, 2, 2, 2, 8, 4,  2,  2,  2,  2,  2,  2,  8,  2,
    9 |  1, 2, 2, 4, 2, 2, 2, 4, 4,  2,  2,  2,  2,  2,  2,  4,  2,
   10 |  1, 2, 3, 2, 2, 3, 3, 2, 2,  2,  5,  3,  5,  3,  2,  2,  5,
   11 |  1, 2, 3, 2, 5, 3, 3, 2, 2,  5,  2,  3,  3,  3,  3,  2,  5,
   12 |  1, 2, 2, 2, 3, 2, 3, 2, 2,  3,  3,  2,  3,  3,  6,  2,  3,
   13 |  1, 2, 3, 2, 5, 3, 5, 2, 2,  5,  3,  3,  2,  5,  3,  2,  3,
   14 |  1, 2, 3, 2, 3, 3, 2, 2, 2,  3,  3,  3,  5,  2,  3,  2,  7,
   15 |  1, 2, 3, 2, 2, 6, 3, 2, 2,  2,  3,  6,  3,  3,  2,  2,  3,
   16 |  1, 2, 2, 4, 2, 2, 2, 8, 4,  2,  2,  2,  2,  2,  2, 16,  2,
   17 |  1, 2, 3, 2, 5, 3, 7, 2, 2,  5,  5,  3,  3,  7,  3,  2,  2,
		

Links

• Index entries for sequences computed from indices in prime factorization

Crossrefs

Cf. A005940, A156552, A348041, A348043, A348044 (main diagonal).

Programs

PARI

\\ Needs also code from A348041:
up_to = 105;
A348042sq(row,col) = A348041sq(row*col,A348041sq(row,col));
A348042list(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] = A348042sq(col,(a-(col-1))))); (v); };
v348042 = A348042list(up_to);
A348042(n) = v348042[n];

Formula

A(n, k) = A(k, n).

A(n, k) = A348041(n*k, A348041(n, k)).

A(n, k) = A348041(n, A348043(k, n)) = A348041(k, A348043(n, k)).

For any two squares s=u^2 and t=v^2, A(s, t) is a square also.