VOOZH about

URL: https://oeis.org/A000993

⇱ A000993 - OEIS

login
A000993
Number of distinct quadratic residues mod 10^n; also number of distinct n-digit endings of base-10 squares.
7
1, 6, 22, 159, 1044, 9121, 78132, 748719, 7161484, 70800861, 699869892, 6978353179, 69580078524, 695292156201, 6947835288052, 69465637212039, 694529215501164, 6944974263529141, 69446563720728612, 694457689921141299, 6944497426351013404
OFFSET
0,2
REFERENCES
Albert H. Beiler, Recreations in the Theory of Numbers, Dover Publ., 2nd Ed., NY, 1966, Chapter XV, 'On The Square', p. 139.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Shyam Sunder Gupta, Elegance of Squares, Cubes, and Higher Powers, Exploring the Beauty of Fascinating Numbers, Springer (2025) Ch. 2, 29-81.
Walter Penney, On the final digits of squares, Amer. Math. Monthly, 67 (1960), 1000-1002.
Index entries for linear recurrences with constant coefficients, signature (10,30,-300,-129,1290,100,-1000).
FORMULA
a(n) = floor( (83 - (-1)^n*(27 + 2^(n+1) + 5^(n+1)) + 9*2^n + (9 + 2^n)*5^(n+1)) / 72 ).
a(n+8) = 130 a(n+6) - 3129 a(n+4) + 13000 a(n+2) - 10000 a(n) for n >= 1.
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).
EXAMPLE
Any square ends with one of 0, 1, 4, 5, 6, 9, so a(1) = 6.
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.
The finite sequence A122986 has a(3) = 159 terms. - Reinhard Zumkeller, Mar 21 2010
MAPLE
-(-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
MATHEMATICA
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}]
(* 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}]
(* 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 *)
LinearRecurrence[{10, 30, -300, -129, 1290, 100, -1000}, {1, 6, 22, 159, 1044, 9121, 78132, 748719}, 20] (* Harvey P. Dale, Dec 17 2017 *)
PROG
(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
(Python)
print([(2 + 2**n // 6) * (1 + 5**(n+1) // 12) if n else 1 for n in range(21)]) # Nick Hobson, Mar 10 2024
KEYWORD
nonn,easy,nice,base
STATUS
approved