login
Number of distinct quadratic residues mod 10^n; also number of distinct n-digit endings of base-10 squares.
(Formerly M4155 N1727)
7

%I M4155 N1727 #56 Mar 11 2024 04:14:28

%S 1,6,22,159,1044,9121,78132,748719,7161484,70800861,699869892,

%T 6978353179,69580078524,695292156201,6947835288052,69465637212039,

%U 694529215501164,6944974263529141,69446563720728612,694457689921141299,6944497426351013404

%N Number of distinct quadratic residues mod 10^n; also number of distinct n-digit endings of base-10 squares.

%D Albert H. Beiler, Recreations in the Theory of Numbers, Dover Publ., 2nd Ed., NY, 1966, Chapter XV, 'On The Square', p. 139.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

%H W. Penney, <a href="http://www.jstor.org/stable/2309232">On the final digits of squares</a>, Amer. Math. Monthly, 67 (1960), 1000-1002.

%H <a href="/index/Fi#final">Index entries for sequences related to final digits of numbers</a>

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (10,30,-300,-129,1290,100,-1000).

%F a(n) = floor( (83 - (-1)^n*(27 + 2^(n+1) + 5^(n+1)) + 9*2^n + (9 + 2^n)*5^(n+1)) / 72 ).

%F a(n+8) = 130 a(n+6) - 3129 a(n+4) + 13000 a(n+2) - 10000 a(n) for n >= 1.

%F G.f.: (1 - 4*x - 68*x^2 + 59*x^3 + 723*x^4 - 5*x^5 - 1700*x^6 - 500*x^7)/(1 - 10*x - 30*x^2 + 300*x^3 + 129*x^4 - 1290*x^5 - 100*x^6 + 1000*x^7).

%e Any square ends with one of 0, 1, 4, 5, 6, 9, so a(1) = 6.

%e A square may end with 22 different two-digit combinations: 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96. E.g., no number ending with 14 can be square, etc. See also A075821, A075823.

%e The finite sequence A122986 has a(3) = 159 terms. - _Reinhard Zumkeller_, Mar 21 2010

%p -(-6+38*z+241*z^2-594*z^3-1285*z^4+1600*z^5+1500*z^6)/((-1+z)*(5*z-1)*(2*z+1)*(2*z-1)*(5*z+1)*(10*z-1)*(z+1)); # Bruno Salvy

%t a[n_] := (83 - 27*(-1)^n + 9*2^(n) - (-1)^n*2^(1 + n) + 9*5^(1 + n) - (-1)^n*5^(1 + n) + 2^(n)*5^(1 + n))/72; Table[ Floor[ a[n]], {n, 0, 20}]

%t (* Or *) a[0] = 1; a[1] = 6; a[2] = 22; a[3] = 159; a[4] = 1044; a[5] = 9121; a[6] = 78132; a[7] = 748719; a[8] = 7161484; a[n_] := 130 a[n - 2] - 3129 a[n - 4] + 13000 a[n - 6] - 10000 a[n - 8]; Table[ a[n], {n, 0, 20}]

%t (* Or *) CoefficientList[ Series[(1 - 4*x - 68*x^2 + 59*x^3 + 723*x^4 - 5*x^5 - 1700*x^6 - 500*x^7)/(1 - 10*x - 30*x^2 + 300*x^3 + 129*x^4 - 1290*x^5 - 100*x^6 + 1000*x^7), {x, 0, 20}], x] (* _Robert G. Wilson v_, Nov 27 2004 *)

%t LinearRecurrence[{10,30,-300,-129,1290,100,-1000},{1,6,22,159,1044,9121,78132,748719},20] (* _Harvey P. Dale_, Dec 17 2017 *)

%o (Magma) [1] cat [(83 + 27*(-1)^n + 9*2^(1 + n) + (-1)^n*2^(2 + n) + 9*5^(2 + n) + (-1)^n*5^(2 + n) + 2^(1 + n)*5^(2 + n))/ 72: n in [0..20]] // _Vincenzo Librandi_, Mar 29 2012

%o (Python)

%o print([(2 + 2**n // 6) * (1 + 5**(n+1) // 12) if n else 1 for n in range(21)]) # _Nick Hobson_, Mar 10 2024

%Y Cf. A036688, A023105, A039300-A039306, A075821, A075823.

%K nonn,easy,nice,base

%O 0,2

%A _N. J. A. Sloane_