cp's OEIS Frontend

A039300 Number of distinct quadratic residues mod 3^n.

%I A039300 #52 Apr 06 2025 19:54:08
%S A039300 1,2,4,11,31,92,274,821,2461,7382,22144,66431,199291,597872,1793614,
%T A039300 5380841,16142521,48427562,145282684,435848051,1307544151,3922632452,
%U A039300 11767897354,35303692061,105911076181,317733228542,953199685624
%N A039300 Number of distinct quadratic residues mod 3^n.
%C A039300 Number of distinct n-digit suffixes of base 3 squares.
%C A039300 In general, for any odd prime p, the number s of quadratic residues mod p^n is given by s = (p^(n+1) + p + 2)/(2p + 2) for even n and s = (p^(n+1) + 2*p + 1)/(2p + 2) for odd n, see A000224. - _Lekraj Beedassy_, Jan 07 2005
%D A039300 J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 324.
%H A039300 Vincenzo Librandi, <a href="/A039300/b039300.txt">Table of n, a(n) for n = 0..1000</a>
%H A039300 W. D. Stangl, <a href="http://www.maa.org/programs/faculty-and-departments/classroom-capsules-and-notes/counting-squares-in-zn">Counting Squares in Z_n</a>, Mathematics Magazine, pp. 285-289, Vol. 69 No. 4 (October 1996).
%H A039300 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,1,-3).
%F A039300 a(n) = floor(3*(3^n + 3)/8).
%F A039300 a(n) = A033113(n) + 1.
%F A039300 a(n) = (3^(n+1) + 6 + (-1)^(n+1))/8. - _Lekraj Beedassy_, Jan 07 2005
%F A039300 G.f.: (1 - x - 3*x^2)/((1 - x)*(1 + x)*(1 - 3*x)). - _Michael Somos_, Mar 27 2005
%F A039300 a(n) = 2*a(n-1) + 3*a(n-2) - 3 with n > 1, a(0) = 1, a(1) = 1. - _Zerinvary Lajos_, Dec 14 2008
%F A039300 a(n) = 3*a(n-1) + a(n-2) - 3*a(n-3). _Vincenzo Librandi_, Apr 21 2012
%F A039300 a(n) = A000224(3^n). - _R. J. Mathar_, Sep 28 2017
%F A039300 E.g.f.: (1/8)*exp(-x)*(-1+6*exp(2*x)+3*exp(4*x)). - _Stefano Spezia_, Sep 04 2018
%p A039300 A039300 := proc(n)
%p A039300     floor((3^n+3)*3/8) ;
%p A039300 end proc:
%p A039300 seq(A039300(n),n=0..30) ; # _R. J. Mathar_, Sep 28 2017
%t A039300 CoefficientList[Series[(1-x-3x^2)/((1-x)(1+x)(1-3x)),{x,0,30}],x] (* _Vincenzo Librandi_, Apr 21 2012 *)
%t A039300 Table[Floor((3^n+3)*3/8),{n,0,30}] (* _Bruno Berselli_, Apr 21 2012 *)
%t A039300 CoefficientList[Series[1/8 E^-x (-1 + 6 E^(2 x) + 3 E^(4 x)), {x, 0, 30}], x]*Table[k!, {k, 0, 30}] (* _Stefano Spezia_, Sep 04 2018 *)
%o A039300 (PARI) {a(n) = if(n<0, 0, 3^n*3\8 + 1)}; /* _Michael Somos_,Mar 27 2005 */
%o A039300 (PARI) {a(n) = if(n<1, n==0, 3*a(n-1) - 2 + n%2)}; /* _Michael Somos_, Mar 27 2005 */
%o A039300 (Magma) [(3^(n+1) + 6 + (-1)^(n+1))/8: n in [0..30]]; // _Vincenzo Librandi_, Apr 21 2012
%o A039300 (Sage) [(3^(n+1) +6 -(-1)^n)/8 for n in (0..30)] # _G. C. Greubel_, Jul 14 2019
%o A039300 (GAP) List([0..30], n-> (3^(n+1) +6 -(-1)^n)/8); # _G. C. Greubel_, Jul 14 2019
%Y A039300 Cf. A033113, A000224, A015518, A023105.
%K A039300 nonn,easy
%O A039300 0,2
%A A039300 _David W. Wilson_