|
| |
|
|
A340670
|
|
Number of complex base i-1 points which can be represented within n bits and negated within those n bits.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
