cp's OEIS Frontend

A039306 Number of distinct quadratic residues mod 9^n.

%I A039306 #33 Sep 08 2022 08:44:53
%S A039306 1,4,31,274,2461,22144,199291,1793614,16142521,145282684,1307544151,
%T A039306 11767897354,105911076181,953199685624,8578797170611,77209174535494,
%U A039306 694882570819441,6253943137374964,56285488236374671,506569394127372034
%N A039306 Number of distinct quadratic residues mod 9^n.
%C A039306 Number of distinct n-digit suffixes of base 9 squares.
%C A039306 From _Danny Rorabaugh_, Dec 15 2015: (Start)
%C A039306 Construct the word y_n as follows: y_0 = a; y_{n+1} is three concatenated copies of y_n, except that the middle copy is written with letters not used in y_n. For example:
%C A039306 y_0 = a;
%C A039306 y_1 = aba;
%C A039306 y_2 = abacdcaba;
%C A039306 y_3 = abacdcabaefeghgefeabacdcaba.
%C A039306 a(n) is the number of nonempty subwords of y_n that occur as a subword exactly once.
%C A039306 Let s(n, k) be the number of subwords of y_n that occur exactly 2^k times. One can show that s(n, 0) = a(n) using s(n+1, k+1) = s(n, k) + s(n, k+1), binomial(3^n+1, 2) = Sum_{k=0..n) s(n, k)*2^k, and the formulas for a(n) below.
%C A039306 (End)
%H A039306 Vincenzo Librandi, <a href="/A039306/b039306.txt">Table of n, a(n) for n = 0..1000</a>
%H A039306 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (10,-9).
%F A039306 a(n) = floor((9^n+3)*3/8).
%F A039306 G.f.: (1-6*x)/((1-x)*(1-9*x)). - _Colin Barker, Mar 14 2012
%F A039306 a(n) = 9*a(n-1) +a(n-2) -9*a(n-3). - _Vincenzo Librandi_, Apr 22 2012
%F A039306 a(n) = (5+3^(2n+1))/8 = a(n-1) + 3^(2n-1). - _Danny Rorabaugh_, Dec 15 2015
%e A039306 From _Danny Rorabaugh_, Dec 15 2015: (Start)
%e A039306 The squares of the numbers 0..8 are [0, 1, 4, 9, 16, 25, 36, 49, 64]. Modulo 9, these are [0, 1, 4, 0, 7, 7, 0, 4, 1]. Thus there are a(1) = 4 distinct quadratic residues module 9^1 = 9: 0, 1, 4, and 7.
%e A039306 There are a(2) = 31 subwords of y_2 = abacdcaba which occur in y_2 exactly once: [abac, abacd, abacdc, abacdca, abacdcab, abacdcaba, bac, bacd, bacdc, bacdca, bacdcab, bacdcaba, ac, acd, acdc, acdca, acdcab, acdcaba, cd, cdc, cdca, cdcab, cdcaba, d, dc, dca, dcab, dcaba, ca, cab, caba].
%e A039306 (End)
%t A039306 CoefficientList[Series[(1-6*x)/((1-x)*(1-9*x)),{x,0,30}],x] (* _Vincenzo Librandi_, Apr 22 2012 *)
%o A039306 (Magma) I:=[1, 4, 31]; [n le 3 select I[n] else 9*Self(n-1)+Self(n-2)-9*Self(n-3): n in [1..30]]; // _Vincenzo Librandi_, Apr 22 2012
%Y A039306 Quadratic residues modulo k^n: A023105 (k=2), A039300 (k=3), A039301 (k=4), A039302 (k=5), A039303 (k=6), A039304 (k=7), A039305 (k=8), this sequence (k=9), A000993 (k=10).
%K A039306 nonn,easy
%O A039306 0,2
%A A039306 _David W. Wilson_