A340670 Number of complex base i-1 points which can be represented within n bits and negated within those n bits.

1, 1, 1, 3, 5, 15, 29, 47, 101, 199, 413, 847, 1621, 3255, 6541, 13087, 26373, 52423, 104637, 209711, 419253, 839511, 1678317, 3353919, 6710629, 13421287, 26845213, 53693007, 107366933, 214742391, 429498701, 858994271, 1718023109, 3435955975, 6871883645

Offset: 0

Author

Kevin Ryde, Jan 15 2021

Keywords

• nonn
• easy

Comments

Complex base i-1 of Khmelnik and Penney uses an integer m to represent a complex integer point z(m) = A318438(m) + A318439(m)*i. A340669(m) is the negation of z in this representation. a(n) is how many n-bit m are negatable within those n bits, i.e., how many m in the range 0 <= m < 2^n have also 0 <= A340669(m) < 2^n.

A geometric interpretation of a(n) is to draw a unit square around each point z(0) to z(2^n-1), rotate a copy by 180 degrees about the origin, and measure its area of intersection with the original.

The bit-flip rule in A340669 gives the recurrence formula below. A low 0-bit of m has a(n-1) negatables above it, or low 11 is one arbitrary bit then negatables above so 2*a(n-3), or low 01 is three arbitrary so 8*a(n-5). This can be thought of the number of compositions of n (partitions with order) into parts 1,3,5 with 2 types of part 3 and 8 types of part 5.

Examples

			For n=3, the a(3)=3 points of n bits are m = 0,3,7 < 2^n, which negate to A340669(0,3,7) = 0,7,3 < 2^n.  These m are located at z = 0,i,-i,
               negate        intersection
  z(0..7)    (rotate 180)   a(3) = 3 points
                * *
   * *            * *             *
     o *        * o               o
   * *            * *             *
     * *
		

Links

• Kevin Ryde, Table of n, a(n) for n = 0..700
• Kevin Ryde, Iterations of the Dragon Curve, see index MinusNegA.
• Index entries for linear recurrences with constant coefficients, signature (1,0,2,0,8).

Crossrefs

Cf. A340669, A107920, A078069.

Programs

PARI

{ my(table=[4,-2,-2,6, -4,2,2,-6], p=Mod('x,2-'x+'x^2));
a(n) = (6<
				

Formula

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

a(n) = (2/5)*2^n + (h/15)*2^floor(n/2) + (2/3)*Im((1/2 + i*sqrt(7)/2)^(n+1)) where h = 4,-2,-2,6, -4,2,2,-6 according as n == 0 to 7 (mod 8) respectively.

a(n) = (2/5)*2^n + (1/3)*A107920(n+1) + (1/15)*A078069(n+2).

G.f.: 1/(1 - x - 2*x^3 - 8*x^5).

G.f.: (2/5)/(1-2*x) + (1/3)/(1-x+2*x^2) + (2/15)*(2+3*x)/(1+2*x+2*x^2).