cp's OEIS Frontend

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

%I A340670 #13 Jan 23 2021 03:02:46
%S A340670 1,1,1,3,5,15,29,47,101,199,413,847,1621,3255,6541,13087,26373,52423,
%T A340670 104637,209711,419253,839511,1678317,3353919,6710629,13421287,
%U A340670 26845213,53693007,107366933,214742391,429498701,858994271,1718023109,3435955975,6871883645
%N A340670 Number of complex base i-1 points which can be represented within n bits and negated within those n bits.
%C A340670 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.
%C A340670 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.
%C A340670 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.
%H A340670 Kevin Ryde, <a href="/A340670/b340670.txt">Table of n, a(n) for n = 0..700</a>
%H A340670 Kevin Ryde, <a href="http://user42.tuxfamily.org/dragon/index.html">Iterations of the Dragon Curve</a>, see index MinusNegA.
%H A340670 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,2,0,8).
%F A340670 a(n) = a(n-1) + 2*a(n-3) + 8*a(n-5).
%F A340670 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.
%F A340670 a(n) = (2/5)*2^n + (1/3)*A107920(n+1) + (1/15)*A078069(n+2).
%F A340670 G.f.: 1/(1 - x - 2*x^3 - 8*x^5).
%F A340670 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).
%e A340670 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,
%e A340670                negate        intersection
%e A340670   z(0..7)    (rotate 180)   a(3) = 3 points
%e A340670                 * *
%e A340670    * *            * *             *
%e A340670      o *        * o               o
%e A340670    * *            * *             *
%e A340670      * *
%o A340670 (PARI) { my(table=[4,-2,-2,6, -4,2,2,-6], p=Mod('x,2-'x+'x^2));
%o A340670 a(n) = (6<<n + table[n%8+1]<<(n\2) + 5*vecsum(Vec(lift(p^n))))/15; }
%Y A340670 Cf. A340669, A107920, A078069.
%K A340670 nonn,easy
%O A340670 0,4
%A A340670 _Kevin Ryde_, Jan 15 2021