A352502 a(n) is the number of integers k in the interval 0..n such that k and n-k can be added without carries in balanced ternary.

1, 2, 2, 4, 4, 2, 4, 4, 6, 10, 8, 6, 10, 8, 2, 4, 4, 6, 10, 8, 6, 10, 8, 10, 16, 12, 18, 28, 20, 14, 22, 16, 10, 16, 12, 18, 28, 20, 14, 22, 16, 2, 4, 4, 6, 10, 8, 6, 10, 8, 10, 16, 12, 18, 28, 20, 14, 22, 16, 10, 16, 12, 18, 28, 20, 14, 22, 16, 18, 28, 20, 30

Offset: 0

Author

Rémy Sigrist, Apr 28 2022

Keywords

• nonn
• base

Comments

Two integers can be added without carries in balanced ternary if they have no equal nonzero digit at the same position.

This sequence has connections with Gould's sequence (A001316); here we work with balanced ternary, there with binary.

Examples

			For n = 8:
- we consider the following cases:
              k|    0    1    2    3    4    5    6    7    8
      ---------+---------------------------------------------
        bter(k)|    0    1   1T   10   11  1TT  1T0  1T1  10T
      bter(8-k)|  10T  1T1  1T0  1TT   11   10   1T    1    0
       carries?|  no   yes  no   no   yes  no   no   yes  no
- so a(8) = 6.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..6561
• Wikipedia, Balanced ternary

Crossrefs

Cf. A001316, A059095, A140429, A353174 (corresponding k's).

Programs

PARI

ok(u,v) = { while (u && v, my (uu=[0,+1,-1][1+u%3], vv=[0,+1,-1][1+v%3]); if (abs(uu+vv)>1, return (0)); u=(u-uu)/3; v=(v-vv)/3); return (1) }
a(n) = sum(k=0, n, ok(n-k, k))

Formula

a(n) <= n+1 with equality iff n belongs to A140429.

a(3*n) = 3*a(n) - 2.

a(3*n+1) = a(3*n-1) + 2.