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

%I #25 Sep 08 2022 08:44:53

%S 1,3,11,53,261,1303,6511,32553,162761,813803,4069011,20345053,

%T 101725261,508626303,2543131511,12715657553,63578287761,317891438803,

%U 1589457194011,7947285970053,39736429850261,198682149251303,993410746256511

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

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

%D J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 324.

%H Vincenzo Librandi, <a href="/A039302/b039302.txt">Table of n, a(n) for n = 0..1000</a>

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

%F a(n) = floor((5^n+3)*5/12).

%F G.f.: (1-2*x-5*x^2)/((1-x)*(1+x)*(1-5*x)). [Colin Barker, Mar 14 2012]

%F a(n) = 5*a(n-1) +a(n-2) -5*a(n-3). _Vincenzo Librandi_, Apr 21 2012

%F a(n) = A000224(5^n). - _R. J. Mathar_, Sep 28 2017

%p A039302 := proc(n)

%p floor((5^n+3)*5/12) ;

%p end proc:

%p seq(A039302(n),n=0..10) ; # _R. J. Mathar_, Sep 28 2017

%t CoefficientList[Series[(1-2*x-5*x^2)/((1-x)*(1+x)*(1-5*x)),{x,0,30}],x] (* or *)LinearRecurrence[{5,1,-5},{1,3,11},30] (* _Vincenzo Librandi_, Apr 21 2012 *)

%o (Magma) I:=[1, 3, 11]; [n le 3 select I[n] else 5*Self(n-1)+Self(n-2)-5*Self(n-3): n in [1..30]]; // _Vincenzo Librandi_, Apr 21 2012

%K nonn,easy

%O 0,2

%A _David W. Wilson_