A341520 Square array A(n,k) = A156552(A005940(1+n)*A005940(1+k)), read by antidiagonals.

0, 1, 1, 2, 3, 2, 3, 5, 5, 3, 4, 7, 6, 7, 4, 5, 9, 11, 11, 9, 5, 6, 11, 10, 15, 10, 11, 6, 7, 13, 13, 19, 19, 13, 13, 7, 8, 15, 14, 23, 12, 23, 14, 15, 8, 9, 17, 23, 27, 21, 21, 27, 23, 17, 9, 10, 19, 18, 31, 22, 27, 22, 31, 18, 19, 10, 11, 21, 21, 35, 39, 29, 29, 39, 35, 21, 21, 11, 12, 23, 22, 39, 20, 47, 30, 47, 20, 39, 22, 23, 12

Offset: 0

Author

Antti Karttunen, Feb 13 2021

Keywords

• nonn
• tabl

Comments

The indices run as A(0,0), A(0,1), A(1,0), A(0,2), A(1,1), A(2,0), etc. The array is symmetric.

This array defines a binary operation on the nonnegative integers that matches up the zeros in the binary representation of each operand (starting from the right, and including as many leading zeros as necessary) and concatenates the two (possibly null) strings of ones to the right of each matched pair of zeros. See the examples. - Peter Munn, Feb 14 2021.

As such it could be useful for implementing multiplication, say, in Turing machines, with a "tape-like" unary-binary encoding of the prime factorization of n (A156552). However, such representation is not very useful if addition or subtraction is also needed.

Examples

			The top left {0..15} X {0..16} corner of the array:
   0,  1,  2,  3,  4,  5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,
   1,  3,  5,  7,  9, 11,  13,  15,  17,  19,  21,  23,  25,  27,  29,  31,
   2,  5,  6, 11, 10, 13,  14,  23,  18,  21,  22,  27,  26,  29,  30,  47,
   3,  7, 11, 15, 19, 23,  27,  31,  35,  39,  43,  47,  51,  55,  59,  63,
   4,  9, 10, 19, 12, 21,  22,  39,  20,  25,  26,  43,  28,  45,  46,  79,
   5, 11, 13, 23, 21, 27,  29,  47,  37,  43,  45,  55,  53,  59,  61,  95,
   6, 13, 14, 27, 22, 29,  30,  55,  38,  45,  46,  59,  54,  61,  62, 111,
   7, 15, 23, 31, 39, 47,  55,  63,  71,  79,  87,  95, 103, 111, 119, 127,
   8, 17, 18, 35, 20, 37,  38,  71,  24,  41,  42,  75,  44,  77,  78, 143,
   9, 19, 21, 39, 25, 43,  45,  79,  41,  51,  53,  87,  57,  91,  93, 159,
  10, 21, 22, 43, 26, 45,  46,  87,  42,  53,  54,  91,  58,  93,  94, 175,
  11, 23, 27, 47, 43, 55,  59,  95,  75,  87,  91, 111, 107, 119, 123, 191,
  12, 25, 26, 51, 28, 53,  54, 103,  44,  57,  58, 107,  60, 109, 110, 207,
  13, 27, 29, 55, 45, 59,  61, 111,  77,  91,  93, 119, 109, 123, 125, 223,
  14, 29, 30, 59, 46, 61,  62, 119,  78,  93,  94, 123, 110, 125, 126, 239,
  15, 31, 47, 63, 79, 95, 111, 127, 143, 159, 175, 191, 207, 223, 239, 255,
  16, 33, 34, 67, 36, 69,  70, 135,  40,  73,  74, 139,  76, 141, 142, 271,
...
From _Peter Munn_, Feb 24 2021: (Start)
We consider the case of n = 10, k = 41, following the procedure in the Feb 14 2021 comment.
First, write 10 and 41 in binary:
  10 = 1010_2
  41 = 101001_2
Add at least one leading zero to each number, equalizing number of zeros:
  0  0  1  0  1  0
  0  1  0  1  0  0  1
Align zeros, but separate ones:
  0     0  1     0  1  0
  |     |        |     |
  0  1  0     1  0     0  1
---------------------------
  0  1  0  1  1  0  1  0  1
Concatenating the ones, as shown above, we get 10110101_2 = 181.
So A(10, 41) = 181.
(End)
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..10439; the first 144 antidiagonals of the array
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A005940, A156552.

Cf. A088698 (main diagonal).

Rows/columns 0-3: A001477, A005408, A341522, A004767. Row/column 7: A004771.

Cf. A341521 (the lower triangular section).

Cf. also A003991, A268725, A297164, A331590, A341509, A341510, A351960, A351961, A351962

Programs

Mathematica

Block[{nn = 12, a = {1}}, Do[AppendTo[a, If[EvenQ[i], Times @@ Map[Prime[PrimePi[#1] + 1]^#2 & @@ # &, FactorInteger[#]] &@ a[[(i/2) + 1]], 2 a[[((i - 1)/2) + 1]]]], {i, nn}]; Table[Floor@ Total@ Flatten@ MapIndexed[#1 2^(#2 - 1) &, Flatten[Table[2^(PrimePi@ #1 - 1), {#2}] & @@@ FactorInteger@ #]] &[a[[1 + n - k]]*a[[1 + k]] ], {n, 0, nn}, {k, n, 0, -1}]] // Flatten (* Michael De Vlieger, Feb 24 2021 *)

PARI

up_to = 105;
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); (t); };
A156552(n) = { my(f = factor(n), p, p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res };
A341520sq(n,k) = A156552(A005940(1+n)*A005940(1+k));
A341520list(up_to) = { my(v = vector(1+up_to), i=0); for(a=0,oo, for(col=0,a, i++; if(i > #v, return(v)); v[i] = A341520sq(col,(a-(col))))); (v); };
v341520 = A341520list(up_to);
A341520(n) = v341520[1+n];

Formula

A(x, y) = A156552(A005940(1+x) * A005940(1+y)).

For all n>=0, A(0, n) = A(n, 0) = n.

For all x>=0, y>=0, A(x, y) = A(y, x).

For all x, y, z >= 0, A(x, A(y, z)) = A(A(x, y), z).

From Antti Karttunen, Feb 27 2022: (Start)

For all x, y >= 0, A(x, y) = A(A351961(x,y), A351962(x,y)).

For x >= 0, y > 0, A(x, y) = A351960(x, A(x, A297164(y))).

(End)