login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A023105 Number of distinct quadratic residues mod 2^n. 9
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 (list; graph; refs; listen; history; text; internal format)
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

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Lee Hae-hwang, Sequences of Growing Networks

W. D. Stangl, Counting Squares in Z_n, Mathematics Magazine, pp. 285-289, Vol. 69 No. 4 (October 1996).

Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

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

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

CROSSREFS

Sequence in context: A053638 A051920 A286350 * A281723 A011784 A302487

Adjacent sequences:  A023102 A023103 A023104 * A023106 A023107 A023108

KEYWORD

nonn,easy

AUTHOR

David W. Wilson

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 20 05:07 EST 2019. Contains 329323 sequences. (Running on oeis4.)