%I #38 Feb 28 2022 07:56:25
%S 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,
%T 13,19,19,13,13,7,8,15,14,23,12,23,14,15,8,9,17,23,27,21,21,27,23,17,
%U 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
%N Square array A(n,k) = A156552(A005940(1+n)*A005940(1+k)), read by antidiagonals.
%C 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.
%C 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.
%C 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.
%H Antti Karttunen, <a href="/A341520/b341520.txt">Table of n, a(n) for n = 0..10439; the first 144 antidiagonals of the array</a>
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A(x, y) = A156552(A005940(1+x) * A005940(1+y)).
%F For all n>=0, A(0, n) = A(n, 0) = n.
%F For all x>=0, y>=0, A(x, y) = A(y, x).
%F For all x, y, z >= 0, A(x, A(y, z)) = A(A(x, y), z).
%F From _Antti Karttunen_, Feb 27 2022: (Start)
%F For all x, y >= 0, A(x, y) = A(A351961(x,y), A351962(x,y)).
%F For x >= 0, y > 0, A(x, y) = A351960(x, A(x, A297164(y))).
%F (End)
%e The top left {0..15} X {0..16} corner of the array:
%e 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
%e 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31,
%e 2, 5, 6, 11, 10, 13, 14, 23, 18, 21, 22, 27, 26, 29, 30, 47,
%e 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63,
%e 4, 9, 10, 19, 12, 21, 22, 39, 20, 25, 26, 43, 28, 45, 46, 79,
%e 5, 11, 13, 23, 21, 27, 29, 47, 37, 43, 45, 55, 53, 59, 61, 95,
%e 6, 13, 14, 27, 22, 29, 30, 55, 38, 45, 46, 59, 54, 61, 62, 111,
%e 7, 15, 23, 31, 39, 47, 55, 63, 71, 79, 87, 95, 103, 111, 119, 127,
%e 8, 17, 18, 35, 20, 37, 38, 71, 24, 41, 42, 75, 44, 77, 78, 143,
%e 9, 19, 21, 39, 25, 43, 45, 79, 41, 51, 53, 87, 57, 91, 93, 159,
%e 10, 21, 22, 43, 26, 45, 46, 87, 42, 53, 54, 91, 58, 93, 94, 175,
%e 11, 23, 27, 47, 43, 55, 59, 95, 75, 87, 91, 111, 107, 119, 123, 191,
%e 12, 25, 26, 51, 28, 53, 54, 103, 44, 57, 58, 107, 60, 109, 110, 207,
%e 13, 27, 29, 55, 45, 59, 61, 111, 77, 91, 93, 119, 109, 123, 125, 223,
%e 14, 29, 30, 59, 46, 61, 62, 119, 78, 93, 94, 123, 110, 125, 126, 239,
%e 15, 31, 47, 63, 79, 95, 111, 127, 143, 159, 175, 191, 207, 223, 239, 255,
%e 16, 33, 34, 67, 36, 69, 70, 135, 40, 73, 74, 139, 76, 141, 142, 271,
%e ...
%e From _Peter Munn_, Feb 24 2021: (Start)
%e We consider the case of n = 10, k = 41, following the procedure in the Feb 14 2021 comment.
%e First, write 10 and 41 in binary:
%e 10 = 1010_2
%e 41 = 101001_2
%e Add at least one leading zero to each number, equalizing number of zeros:
%e 0 0 1 0 1 0
%e 0 1 0 1 0 0 1
%e Align zeros, but separate ones:
%e 0 0 1 0 1 0
%e | | | |
%e 0 1 0 1 0 0 1
%e ---------------------------
%e 0 1 0 1 1 0 1 0 1
%e Concatenating the ones, as shown above, we get 10110101_2 = 181.
%e So A(10, 41) = 181.
%e (End)
%t 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 *)
%o (PARI)
%o up_to = 105;
%o A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); (t); };
%o 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 };
%o A341520sq(n,k) = A156552(A005940(1+n)*A005940(1+k));
%o 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); };
%o v341520 = A341520list(up_to);
%o A341520(n) = v341520[1+n];
%Y Cf. A005940, A156552.
%Y Cf. A088698 (main diagonal).
%Y Rows/columns 0-3: A001477, A005408, A341522, A004767. Row/column 7: A004771.
%Y Cf. A341521 (the lower triangular section).
%Y Cf. also A003991, A268725, A297164, A331590, A341509, A341510, A351960, A351961, A351962
%K nonn,tabl
%O 0,4
%A _Antti Karttunen_, Feb 13 2021