OFFSET
0,4
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.
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).
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.
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).
EXAMPLE
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
* * * * *
* *
PROG
(PARI) { my(table=[4, -2, -2, 6, -4, 2, 2, -6], p=Mod('x, 2-'x+'x^2));
a(n) = (6<<n + table[n%8+1]<<(n\2) + 5*vecsum(Vec(lift(p^n))))/15; }
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Kevin Ryde, Jan 15 2021
STATUS
approved