OFFSET
0,2
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).
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
EXAMPLE
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.
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); }
a(n) = sum(k = 0, n, ok(n-k, k))
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Jan 18 2025
STATUS
approved