|
|
A000993
|
|
Number of distinct quadratic residues mod 10^n; also number of distinct n-digit endings of base-10 squares.
(Formerly M4155 N1727)
|
|
7
|
|
|
1, 6, 22, 159, 1044, 9121, 78132, 748719, 7161484, 70800861, 699869892, 6978353179, 69580078524, 695292156201, 6947835288052, 69465637212039, 694529215501164, 6944974263529141, 69446563720728612, 694457689921141299, 6944497426351013404
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
W. Penney, On the final digits of squares, Amer. Math. Monthly, 67 (1960), 1000-1002.
Index entries for sequences related to final digits of numbers
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
|
|
CROSSREFS
|
Cf. A036688, A023105, A039300-A039306, A075821, A075823.
Sequence in context: A009361 A193445 A075759 * A028406 A090372 A009366
Adjacent sequences: A000990 A000991 A000992 * A000994 A000995 A000996
|
|
KEYWORD
|
nonn,easy,nice,base
|
|
AUTHOR
|
N. J. A. Sloane
|
|
STATUS
|
approved
|
|
|
|