A046630 Number of cubic residues mod 2^n.

1, 2, 3, 5, 10, 19, 37, 74, 147, 293, 586, 1171, 2341, 4682, 9363, 18725, 37450, 74899, 149797, 299594, 599187, 1198373, 2396746, 4793491, 9586981, 19173962, 38347923, 76695845, 153391690, 306783379, 613566757, 1227133514, 2454267027

Offset

0,2

Links

Table of n, a(n) for n=0..32.

S. R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

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

Formula

a(n) = ceiling(2^(n+2)/7) [Finch-Sebah, page 12]. - N. J. A. Sloane, Sep 30 2018

G.f.: (-2*x^3-x^2+1)/((1-2*x)*(1-x^3)).

a(n) = A046530(2^n) = 2^(n+2)/7 + 2/3 - (5*A049347(n)+A049347(n-1))/21. - R. J. Mathar, Feb 27 2011

a(n) = 1 + A033138(n) for n >= 1. - John Keith, Mar 07 2022

Example

For n=3, the cubes 0^3, 1^3, 2^3, ..., 7^3 reduced mod 2^3 = 8 are 0,1,0,3,0,5,0,7, five different values, so a(3)=5. - N. J. A. Sloane, Sep 30 2018

Maple

A049347 := proc(n) op( (n mod 3)+1, [1, -1, 0]) ; end proc:
A046630 := proc(n) 2^(n+2)/7+2/3-(5*A049347(n)+A049347(n-1))/21 ; end proc: # R. J. Mathar, Feb 27 2011

Mathematica

LinearRecurrence[{2, 0, 1, -2}, {1, 2, 3, 5}, 33] (* Jean-François Alcover, Nov 17 2017 *)

Prog

(PARI) a(n)=(4<<n+6)\7 \\ Charles R Greathouse IV, Jan 03 2013

Crossrefs

Cf. A033138.

Sequence in context: A283314 A078715 A166874 * A177874 A293353 A293328

Adjacent sequences: A046627 A046628 A046629 * A046631 A046632 A046633

Keyword

nonn,easy

Author

David W. Wilson

Status

approved