A380272 a(n) is the number of integers k in 0..n such that the nonadjacent forms for n-k and k can be added without carries (see Comments section for exact definition).

1, 2, 2, 2, 4, 4, 2, 2, 6, 4, 4, 2, 4, 4, 2, 6, 12, 8, 4, 6, 10, 8, 2, 2, 6, 4, 4, 2, 4, 4, 6, 10, 22, 12, 8, 6, 10, 8, 6, 6, 16, 8, 8, 2, 4, 4, 2, 6, 12, 8, 4, 6, 10, 8, 2, 2, 6, 4, 4, 10, 16, 12, 10, 22, 44, 24, 12, 14, 22, 16, 6, 6, 16, 8, 8, 10, 16, 12, 6

Offset: 0

Author

Rémy Sigrist, Jan 18 2025

Keywords

• nonn
• base

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.

For symmetry reasons, all terms, except the initial a(0) = 1, are even.

The set of pairs of integers whose nonadjacent forms can be added without carries, when plotted on a hexagonal lattice, has interesting graphical features (see illustration in Links section).

Examples

			For n = 9: we have:
  k  naf(9-k)  naf(k)  can be added without carries?
  -  --------  ------  -----------------------------
  0      1001       0  yes
  1      1000       1  yes
  2      100T      10  no
  3      10T0     10T  no
  4       101     100  no
  5       100     101  no
  6       10T    10T0  no
  7        10    100T  no
  8         1    1000  yes
  9         0    1001  yes
So a(9) = 4.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8192
• Joerg Arndt, Matters Computational (The Fxtbook), pages 61-62.
• Rémy Sigrist, Scatterplot of (x, y) such that the nonadjacent forms for x and y can be added without carries (represented in a hexagonal lattice, around the origin)
• Wikipedia, Non-adjacent form

Crossrefs

See A001316 and A352502 for similar sequences.

Cf. A380273.

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); }
a(n) = sum(k = 0, n, ok(n-k, k))