VOOZH about

URL: https://oeis.org/A023105

⇱ A023105 - OEIS

login
A023105
Number of distinct quadratic residues mod 2^n.
16
1, 2, 2, 3, 4, 7, 12, 23, 44, 87, 172, 343, 684, 1367, 2732, 5463, 10924, 21847, 43692, 87383, 174764, 349527, 699052, 1398103, 2796204, 5592407, 11184812, 22369623, 44739244, 89478487, 178956972, 357913943, 715827884, 1431655767, 2863311532
OFFSET
0,2
COMMENTS
Number of distinct n-digit suffixes of base 2 squares.
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
Conjecture: a(n) = 2 + (the number of A004215 entries < 2^n), for n>0. - Tilman Neumann, Sep 20 2020
LINKS
John Greene and James A. Sellers, Extending recent parity results of Nyirenda and Mugwangwavari for partitions with initial repetitions, Integers (2025), Vol. 25, Art. No. A32. See p. 5.
W. D. Stangl, Counting Squares in Z_n, Mathematics Magazine, pp. 285-289, Vol. 69 No. 4 (October 1996).
FORMULA
a(n) = floor( (2^n+10)/6 ).
a(n) = (2^n + 9 - (-1)^n)/6 for n > 0. - David S. Dodson, Jan 06 2013
G.f.: (1-3*x^2-x^3)/((1-x)*(1+x)*(1-2*x)). - Colin Barker, Mar 08 2012
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
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) for n > 0. - Joerg Arndt, Apr 21 2012
a(0)=1, a(1)=2, a(n+2) = a(n+1) + A001045(n) for n >= 1. - Lee Hae-hwang, Jun 16 2014
a(n) = A000224(2^n). - R. J. Mathar, Oct 10 2014
a(n) = A005578(n-1) + 1, n > 0. - Carl Joshua Quines, Jul 17 2019
E.g.f.: (exp(2*x) + 9*exp(x) - 3 - exp(-x))/6. - G. C. Greubel, Aug 10 2022
MATHEMATICA
CoefficientList[Series[(1-3*x^2-x^3)/((1-x)*(1+x)*(1-2*x)), {x, 0, 35}], x] (* Vincenzo Librandi, Apr 21 2012 *)
LinearRecurrence[{2, 1, -2}, {1, 2, 2, 3}, 40] (* Harvey P. Dale, Mar 05 2016 *)
PROG
(Magma) [Floor((2^n+10)/6): n in [0..30]]; // Vincenzo Librandi, Apr 21 2012
(PARI) a(n)=(2^n+10)\6 \\ Charles R Greathouse IV, Apr 21 2012
(Haskell)
a 0 = 1
a 1 = 2
a n | even n = 2*a(n-1)-2
a n | odd n = 2*a(n-1)-1
-- James Spahlinger, Oct 07 2012
(SageMath) [(2^n +9 -(-1)^n -3*bool(n==0))/6 for n in (0..30)] # G. C. Greubel, Aug 10 2022
(Python)
def A023105(n): return ((1<<n-1)+5)//3 if n else 1 # Chai Wah Wu, Aug 22 2023
CROSSREFS
KEYWORD
nonn,easy
STATUS
approved