cp's OEIS Frontend

A023105 Number of distinct quadratic residues mod 2^n.

%I A023105 #101 Apr 24 2025 10:46:27
%S A023105 1,2,2,3,4,7,12,23,44,87,172,343,684,1367,2732,5463,10924,21847,43692,
%T A023105 87383,174764,349527,699052,1398103,2796204,5592407,11184812,22369623,
%U A023105 44739244,89478487,178956972,357913943,715827884,1431655767,2863311532
%N A023105 Number of distinct quadratic residues mod 2^n.
%C A023105 Number of distinct n-digit suffixes of base 2 squares.
%C A023105 a(n) counts the elements of A234000 smaller than 2^n plus the zero: a(7)=23 counts the elements of {0, 1, 4, 9, ..., 113, 121}, for example. - _R. J. Mathar_, Oct 11 2014
%C A023105 Conjecture: a(n) = 2 + (the number of A004215 entries < 2^n), for n>0. - _Tilman Neumann_, Sep 20 2020
%H A023105 Vincenzo Librandi, <a href="/A023105/b023105.txt">Table of n, a(n) for n = 0..1000</a>
%H A023105 John Greene and James A. Sellers, <a href="https://math.colgate.edu/~integers/z32/z32.pdf">Extending recent parity results of Nyirenda and Mugwangwavari for partitions with initial repetitions</a>, Integers (2025), Vol. 25, Art. No. A32. See p. 5.
%H A023105 Lee Hae-hwang, <a href="/A023105/a023105.pdf">Sequences of Growing Networks</a>
%H A023105 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 A023105 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2).
%F A023105 a(n) = floor( (2^n+10)/6 ).
%F A023105 a(n) = (2^n + 9 - (-1)^n)/6 for n > 0. - _David S. Dodson_, Jan 06 2013
%F A023105 G.f.: (1-3*x^2-x^3)/((1-x)*(1+x)*(1-2*x)). - _Colin Barker_, Mar 08 2012
%F A023105 a(0)=1, a(1)=2. a(n) = 2*a(n-1)-2 if n is even, a(n) = 2*a(n-1)-1 if n is odd. - _Vincenzo Librandi_, Apr 21 2012
%F A023105 a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) for n > 0. - _Joerg Arndt_, Apr 21 2012
%F A023105 a(0)=1, a(1)=2, a(n+2) = a(n+1) + A001045(n) for n >= 1. - _Lee Hae-hwang_, Jun 16 2014
%F A023105 a(n) = A000224(2^n). - _R. J. Mathar_, Oct 10 2014
%F A023105 a(n) = A005578(n-1) + 1, n > 0. - _Carl Joshua Quines_, Jul 17 2019
%F A023105 E.g.f.: (exp(2*x) + 9*exp(x) - 3 - exp(-x))/6. - _G. C. Greubel_, Aug 10 2022
%t A023105 CoefficientList[Series[(1-3*x^2-x^3)/((1-x)*(1+x)*(1-2*x)),{x,0,35}],x] (* _Vincenzo Librandi_, Apr 21 2012 *)
%t A023105 LinearRecurrence[{2,1,-2},{1,2,2,3},40] (* _Harvey P. Dale_, Mar 05 2016 *)
%o A023105 (Magma) [Floor((2^n+10)/6): n in [0..30]]; // _Vincenzo Librandi_, Apr 21 2012
%o A023105 (PARI) a(n)=(2^n+10)\6 \\ _Charles R Greathouse IV_, Apr 21 2012
%o A023105 (Haskell)
%o A023105 a 0 = 1
%o A023105 a 1 = 2
%o A023105 a n | even n = 2*a(n-1)-2
%o A023105 a n | odd  n = 2*a(n-1)-1
%o A023105 -- _James Spahlinger_, Oct 07 2012
%o A023105 (SageMath) [(2^n +9 -(-1)^n -3*bool(n==0))/6 for n in (0..30)] # _G. C. Greubel_, Aug 10 2022
%o A023105 (Python)
%o A023105 def A023105(n): return ((1<<n-1)+5)//3 if n else 1 # _Chai Wah Wu_, Aug 22 2023
%Y A023105 Cf. A000224, A001045, A004315, A005578, A234000.
%K A023105 nonn,easy
%O A023105 0,2
%A A023105 _David W. Wilson_