|
| |
|
|
A039300
|
|
Number of distinct quadratic residues mod 3^n.
|
|
4
|
|
|
|
1, 2, 4, 11, 31, 92, 274, 821, 2461, 7382, 22144, 66431, 199291, 597872, 1793614, 5380841, 16142521, 48427562, 145282684, 435848051, 1307544151, 3922632452, 11767897354, 35303692061, 105911076181, 317733228542, 953199685624
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Number of distinct n-digit suffixes of base 3 squares.
In general, for any odd prime p>=3, the number s of quadratic residues mod p^n is given by s=(p^(n+1) + p + 2)/2*(p+1) for even n and s=(p^(n+1) + 2*p + 1)/2*(p+1) for odd n. - Lekraj Beedassy, Jan 07 2005
|
|
|
REFERENCES
|
W. D. Stangl, "Counting Squares in Z_n", Mathematics Magazine pp. 285-9 Vol. 69 No. Oct 04 1996.
|
|
|
LINKS
|
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index to sequences with linear recurrences with constant coefficients, signature (3,1,-3).
|
|
|
FORMULA
|
a(n) = floor((3^n+3)*3/8).
a(n) = (3^(n+1) + 6 + (-1)^(n+1))/8- - Lekraj Beedassy, Jan 07 2005
G.f.: (1-x-3x^2)/((1-x)(1+x)(1-3x)).
a(n) = 2*a(n-1)+3*a(n-2)-3 with n>1, a(0)=1, a(1)=1. [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 14 2008]
a(n) = 3*a(n-1)+ a(n-2) -3*a(n-3). Vincenzo Librandi, Apr 21 2012
|
|
|
MAPLE
|
a[0]:=1:a[1]:=1:for n from 2 to 50 do a[n]:=2*a[n-1]+3*a[n-2]-3 od: seq(a[n], n=1..29); # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 14 2008]
|
|
|
MATHEMATICA
|
CoefficientList[Series[(1-x-3x^2)/((1-x)(1+x)(1-3x)), {x, 0, 35}], x] (* Vincenzo Librandi, Apr 21 2012 *)
Table[Floor((3^n+3)*3/8), {n, 0, 26}] (* Bruno Berselli, Apr 21 2012 *)
|
|
|
PROG
|
(PARI) a(n)=if(n<0, 0, 3^n*3\8+1)
(PARI) a(n)=if(n<1, n==0, 3*a(n-1)-2+n%2)
(MAGMA) [(3^(n+1) + 6 + (-1)^(n+1))/8: n in [0..30]]; // Vincenzo Librandi, Apr 21 2012
|
|
|
CROSSREFS
|
Equals A033113 + 1. Cf. A015518, A023105.
Sequence in context: A148161 A148162 A148163 * A118974 A119020 A073191
Adjacent sequences: A039297 A039298 A039299 * A039301 A039302 A039303
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
David W. Wilson
|
|
|
STATUS
|
approved
|
| |
|
|
