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,5

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.

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

Formula

T(n, 1) = 0.

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

Example

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

Prog

(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])

Crossrefs

See A295989 and A353174 for similar sequences.

Cf. A380272.

Sequence in context: A362110 A236138 A388307 * A363930 A361755 A362755

Adjacent sequences: A380270 A380271 A380272 * A380274 A380275 A380276

Keyword

nonn,base,tabf

Author

Rémy Sigrist, Jan 18 2025

Status

approved