cp's OEIS Frontend

A380273 Irregular table T(n, k), n >= 0, k = 1..A380272(n), read by rows; the n-th row lists the integers m in 0..n such that the nonadjacent forms for m-n and m can be added without carries.

%I A380273 #7 Jan 19 2025 09:28:52
%S A380273 0,0,1,0,2,0,3,0,1,3,4,0,1,4,5,0,6,0,7,0,1,2,6,7,8,0,1,8,9,0,2,8,10,0,
%T A380273 11,0,1,11,12,0,1,12,13,0,14,0,3,4,11,12,15,0,1,2,3,4,5,11,12,13,14,
%U A380273 15,16,0,1,4,5,12,13,16,17,0,2,16,18,0,3,4,15,16,19
%N A380273 Irregular table T(n, k), n >= 0, k = 1..A380272(n), read by rows; the n-th row lists the integers m in 0..n such that the nonadjacent forms for m-n and m can be added without carries.
%C A380273 The nonadjacent forms for two integers, say Sum_{i >= 0} x_i * 2^i and Sum_{i >= 0} y_i * 2^i, can be added without carries iff for any i >= 0:
%C A380273 - abs(x_i + y_i) <= 1,
%C A380273 - (x_i + y_i) * (x_{i+1} + y_{i+1}) = 0.
%H A380273 Rémy Sigrist, <a href="/A380273/b380273.txt">Table of n, a(n) for n = 0..10524</a>
%H A380273 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pages 61-62.
%H A380273 Rémy Sigrist, <a href="/A380273/a380273.png">Scatterplot of (n, T(n, k)) for n = 0..2^9</a> (in a hexagonal lattice)
%H A380273 Wikipedia, <a href="https://en.wikipedia.org/wiki/Non-adjacent_form">Non-adjacent form</a>
%F A380273 T(n, 1) = 0.
%F A380273 T(n, A380272(n)) = n.
%e A380273 Table T(n, k) begins:
%e A380273   n   n-th row
%e A380273   --  ----------------------------------------
%e A380273    0  0
%e A380273    1  0, 1
%e A380273    2  0, 2
%e A380273    3  0, 3
%e A380273    4  0, 1, 3, 4
%e A380273    5  0, 1, 4, 5
%e A380273    6  0, 6
%e A380273    7  0, 7
%e A380273    8  0, 1, 2, 6, 7, 8
%e A380273    9  0, 1, 8, 9
%e A380273   10  0, 2, 8, 10
%e A380273   11  0, 11
%e A380273   12  0, 1, 11, 12
%e A380273   13  0, 1, 12, 13
%e A380273   14  0, 14
%e A380273   15  0, 3, 4, 11, 12, 15
%e A380273   16  0, 1, 2, 3, 4, 5, 11, 12, 13, 14, 15, 16
%o A380273 (PARI) ok(x, y) = { my (dx, dy, p = 0, q); while (x || y, if (x % 2, x -= dx = 2 - (x%4), dx = 0); if (y % 2, y -= dy = 2 - (y%4), dy = 0); if (dx && dx==dy, return (0);); q = dx + dy; if (p && q, return (0);); x /= 2; y /= 2; p = q;); return (1); }
%o A380273 row(n) = select(k -> ok(n-k, k), [0..n])
%Y A380273 See A295989 and A353174 for similar sequences.
%Y A380273 Cf. A380272.
%K A380273 nonn,base,tabf
%O A380273 0,5
%A A380273 _Rémy Sigrist_, Jan 18 2025