A087289 a(n) = 2^(2*n+1) + 1.

3, 9, 33, 129, 513, 2049, 8193, 32769, 131073, 524289, 2097153, 8388609, 33554433, 134217729, 536870913, 2147483649, 8589934593, 34359738369, 137438953473, 549755813889, 2199023255553

Offset

0,1

Comments

Number of pairs of polynomials (f,g) in GF(2)[x] satisfying deg(f) <= n, deg(g) <= n and gcd(f,g) = 1.

An unpublished result due to Stephen Suen, David desJardins, and W. Edwin Clark. This is the case k = 2, q = 2 of their formula q^((n+1)*k) * (1 - 1/q^(k-1) + (q-1)/q^((n+1)*k)) for the number of ordered k-tuples (f_1, ..., f_k) of polynomials in GF(q)[x] such that deg(f_i) <= n for all i and gcd((f_1, ..., f_k) = 1.

Apparently the same as A084508 shifted left.

Terms in binary are palindromes of the form 1x1 where x is a string of 2*n zeros (A152577). - Brad Clardy, Sep 01 2011

For n > 0, a(n) is the number k such that the number of iterations of the map k -> (3k +1)/8 == 4 (mod 8) until reaching (3k +1)/8 <> 4 (mod 8) equals n. (see the Collatz problem: the start of the parity trajectory of a(n) is n times {100} = 100100100100...100abcd...). - Michel Lagneau, Jan 23 2012

An Engel expansion of 2 to the base 4 as defined in A181565, with the associated series expansion 2 = 4/3 + 4^2/(3*9) + 4^3/(3*9*33) + 4^4/(3*9*33*129) + .... Cf. A199561 and A207262. - Peter Bala, Oct 29 2013

For x = A083420(n), y = A000079(n+1), z = a(n) then x^2 + 2*y^2 = z^2. - Vincenzo Librandi, Jun 09 2014

A254046(n+1) is the 3-adic valuation of a(n). - Fred Daniel Kline, Jan 11 2017

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

K. Morrison, Random polynomials over finite fields

Index entries for linear recurrences with constant coefficients, signature (5,-4).

Formula

G.f.: (3-6*x)/((1-x)*(1-4*x)).

a(n) = 3 *A007583(n).

a(n) = 4*a(n-1) - 3. - Lekraj Beedassy, Apr 29 2005

a(n) = A099393(n+1) - 2*A099393(n). - Brad Clardy, Sep 01 2011

a(n) = 2^(2*n + 1) * a(-1-n) for all n in Z. - Michael Somos, Jan 11 2017

a(n) = A283070(n) - 1. - Peter M. Chema, Mar 02 2017

Example

a(0) = 3 since there are three pairs, (0,1), (1,0) and (1,1) of polynomials (f,g) in GF(2)[x] of degree at most 0 such that gcd(f,g) = 1.

Mathematica

Table[2^(2 n + 1) + 1, {n, 0, 20}] (* or *) 3 NestList[4 # - 1 &, 1, 20]
(* or *) CoefficientList[Series[(3 - 6 x)/((1 - x) (1 - 4 x)), {x, 0, 20}], x] (* Michael De Vlieger, Mar 03 2017 *)

Prog

(Magma) [2^(2*n+1) + 1: n in [0..30]]; // Vincenzo Librandi, May 16 2011
(PARI) a(n)=2^(2*n+1)+1 \\ Charles R Greathouse IV, Sep 24 2015

Crossrefs

Cf. A087290, A087291, A087292, A099393.

Equals A004171 + 1.

Cf. also A181565, A199561, A207262, A007583, A283070, A254046.

Sequence in context: A151040 A151041 A151042 * A084508 A151043 A151044

Adjacent sequences: A087286 A087287 A087288 * A087290 A087291 A087292

Keyword

easy,nonn

Author

W. Edwin Clark, Aug 29 2003

Status

approved