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.

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, 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, 15, 16, 0, 1, 4, 5, 12, 13, 16, 17, 0, 2, 16, 18, 0, 3, 4, 15, 16, 19

Offset: 0

Author

Rémy Sigrist, Jan 18 2025

Keywords

• nonn
• base
• tabf

Comments

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:

- abs(x_i + y_i) <= 1,

- (x_i + y_i) * (x_{i+1} + y_{i+1}) = 0.

Examples

			Table T(n, k) begins:
  n   n-th row
  --  ----------------------------------------
   0  0
   1  0, 1
   2  0, 2
   3  0, 3
   4  0, 1, 3, 4
   5  0, 1, 4, 5
   6  0, 6
   7  0, 7
   8  0, 1, 2, 6, 7, 8
   9  0, 1, 8, 9
  10  0, 2, 8, 10
  11  0, 11
  12  0, 1, 11, 12
  13  0, 1, 12, 13
  14  0, 14
  15  0, 3, 4, 11, 12, 15
  16  0, 1, 2, 3, 4, 5, 11, 12, 13, 14, 15, 16
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..10524
• Joerg Arndt, Matters Computational (The Fxtbook), pages 61-62.
• Rémy Sigrist, Scatterplot of (n, T(n, k)) for n = 0..2^9 (in a hexagonal lattice)
• Wikipedia, Non-adjacent form

Crossrefs

See A295989 and A353174 for similar sequences.

Cf. A380272.

Programs

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); }
row(n) = select(k -> ok(n-k, k), [0..n])

Formula

T(n, 1) = 0.

T(n, A380272(n)) = n.