A039302 Number of distinct quadratic residues mod 5^n.

1, 3, 11, 53, 261, 1303, 6511, 32553, 162761, 813803, 4069011, 20345053, 101725261, 508626303, 2543131511, 12715657553, 63578287761, 317891438803, 1589457194011, 7947285970053, 39736429850261, 198682149251303, 993410746256511, 4967053731282553

Offset: 0

Author

David W. Wilson

Keywords

• nonn
• easy

Comments

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

References

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

Links

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

Programs

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

Maple

A039302 := proc(n)
    floor((5^n+3)*5/12) ;
end proc:
seq(A039302(n),n=0..10) ; # R. J. Mathar, Sep 28 2017

Mathematica

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 *)

Formula

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

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

a(n) = 5*a(n-1) +a(n-2) -5*a(n-3). - Vincenzo Librandi, Apr 21 2012

a(n) = A000224(5^n). - R. J. Mathar, Sep 28 2017