A039305 Number of distinct quadratic residues mod 8^n.

1, 3, 12, 87, 684, 5463, 43692, 349527, 2796204, 22369623, 178956972, 1431655767, 11453246124, 91625968983, 733007751852, 5864062014807, 46912496118444, 375299968947543, 3002399751580332, 24019198012642647, 192153584101141164

Offset: 0

Author

David W. Wilson

Keywords

• nonn
• easy

Comments

Number of distinct n-digit suffixes of base 8 squares.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (8,1,-8).

Crossrefs

Cf. A001018.

Programs

Magma

I:=[1, 3, 12, 87]; [n le 4 select I[n] else 8*Self(n-1)+Self(n-2)-8*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Apr 22 2012

Mathematica

CoefficientList[Series[(1-5*x-13*x^2-4*x^3)/((1-x)*(1+x)*(1-8*x)),{x,0,30}],x] (* Vincenzo Librandi, Apr 22 2012 *)
Join[{1},LinearRecurrence[{8,1,-8},{3,12,87},30]] (* Harvey P. Dale, Feb 10 2015 *)

Formula

a(n) = floor((8^n+10)/6).

G.f.: (1-5*x-13*x^2-4*x^3)/((1-x)*(1+x)*(1-8*x)). - Colin Barker, Mar 14 2012

a(n) = 8*a(n-1) + a(n-2) - 8*a(n-3) for n>0, a(0)=1. - Vincenzo Librandi, Apr 22 2012