login
Number of distinct quadratic residues mod 4^n.
11

%I #28 Jun 15 2023 13:06:29

%S 1,2,4,12,44,172,684,2732,10924,43692,174764,699052,2796204,11184812,

%T 44739244,178956972,715827884,2863311532,11453246124,45812984492,

%U 183251937964,733007751852,2932031007404,11728124029612,46912496118444

%N Number of distinct quadratic residues mod 4^n.

%C Number of distinct n-digit suffixes of base 4 squares.

%H Vincenzo Librandi, <a href="/A039301/b039301.txt">Table of n, a(n) for n = 0..170</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (5, -4).

%F a(n) = floor((4^n+10)/6).

%F a(n) = A007583(n-1)+1 = A020988(n-2)+2 = A083584(n-2)+3. - _Ralf Stephan_, Jun 14 2003

%F Also, a(0)=1 and, for n>0, a(n) = (4^n+8)/6. - _Bruno Berselli_, Jul 27 2010

%F G.f.: (1-3*x-2*x^2)/((1-x)*(1-4*x)). - _Bruno Berselli_, Jul 27 2010

%F a(n)-5*a(n-1)+4*a(n-2) = 0 for n>1. - _Bruno Berselli_, Jul 27 2010

%o (Magma) [Floor((4^n+10)/6): n in [0..40] ]; // _Vincenzo Librandi_, Apr 28 2011

%K nonn,easy

%O 0,2

%A _David W. Wilson_