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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002326 Multiplicative order of 2 mod 2n+1.
(Formerly M0936 N0350)
102
1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21, 8, 52, 20, 18, 58, 60, 6, 12, 66, 22, 35, 9, 20, 30, 39, 54, 82, 8, 28, 11, 12, 10, 36, 48, 30, 100, 51, 12, 106, 36, 36, 28, 44, 12, 24, 110, 20, 100, 7, 14, 130, 18, 36, 68, 138, 46, 60, 28 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

In other words, least m>0 such that 2n+1 divides 2^m-1.

Number of riffle shuffles of 2n+2 cards required to return a deck to initial state. A riffle shuffle replaces a list s(1), s(2), ..., s(m) by s(1), s((i/2)+1), s(2), s((i/2)+2), ... a(1) = 2 because a riffle shuffle of [1, 2, 3, 4] requires 2 iterations [1, 2, 3, 4] -> [1, 3, 2, 4] -> [1, 2, 3, 4] to restore the original order.

Concerning the complexity of computing this sequence, see for example Bach And Shallit, p. 115, exercise 8.

It is not difficult to prove that if 2n+1 is a prime then 2n is a multiple of a(n). But the converse is not true. Indeed, one can prove that a(2^(2t-1))=4t. Thus if n=2^(2t-1), where, for any m>0, t=2^(m-1) then 2n is a multiple of a(n) while 2n+1 is a Fermat number which, as is well known, is not always a prime. It is an interesting problem to describe all composite numbers for which 2n is divisible by a(n). - Vladimir Shevelev, May 09 2008

For a conjectural algorithm of calculation of a(n) see A179680. - Vladimir Shevelev, Jul 21 2010

From V. Raman, Sep 18 2012, Dec 10 2012: (Start)

If 2n+1 is prime, then the polynomial (x^(2n+1)+1)/(x+1) factors into 2n/a(n) polynomials of the same degree a(n) over GF(2). For example, the polynomial (x^31+1)/(x+1) factors into six polynomials of degree 5 over GF(2). Thus if 2n+1 is prime then 2n will always be a multiple of a(n).

If 2n+1 is prime and the polynomial (x^(2n+1)+1)/(x+1) is reducible over GF(2), then 2 is not a primitive root (mod 2n+1) (cf. A216838). For these values of n, a(n) != 2n (but a divisor of 2n).

On the other hand, if (x^(2n+1)+1)/(x+1) is irreducible over GF(2), then 2n+1 is prime, and 2 is a primitive root (mod 2n+1) (cf. A001122). Then (x^(2n+1)+1)/(x+1) consists of a single irreducible factor of degree 2n. For these values of n, a(n) = 2n.

Also, for all n > 0, whether 2n+1 is prime or composite, a(n) is the degree of the largest irreducible polynomial factor for the polynomial (x^(2n+1)+1)/(x+1) over GF(2). (End)

a(n) is a factor of phi(2n+1) (A000010(2n+1)). - Douglas Boffey, Oct 21 2013

Conjecture: if p is an odd prime then a((p^3-1)/2) = p * a((p^2-1)/2). Because otherwise a((p^3-1)/2) < p * a((p^2-1)/2) iff a((p^3-1)/2) = a((p-1)/2) for a prime p. Equivalently p^3 divides 2^(p-1)-1, but no such prime p is known. - Thomas Ordowski, Feb 10 2014

REFERENCES

E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I.

T. Folger, "Shuffling Into Hyperspace," Discover, 1991 (vol 12, no 1), pages 66-67.

M. Gardner, "Card Shuffles," Mathematical Carnival chapter 10, pages 123-138. New York: Vintage Books, 1977.

V. I. Levenshtein, Conflict-avoiding codes and cyclic triple systems [in Russian], Problemy Peredachi Informatsii, 43 (No. 3, 2007), 39-53.

L. Lunelli and M. Lunelli, Tavola di congruenza a^n == 1 mod K per a=2,5,10, Atti Sem. Mat. Fis. Univ. Modena 10 (1960/61), 219-236 (1961).

J. H. Silverman, A Friendly Introduction to Number Theory, 3rd ed., Pearson Education, Inc, 2006, p. 146, Exer. 21.3

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

T. D. Noe, Table of n, a(n) for n = 0..10000

M. Baake, U. Grimm, J. Nilsson, Scaling of the Thue-Morse diffraction measure, arXiv preprint arXiv:1311.4371, 2013

D. Bayer, P. Diaconis, Trailing the dovetail shuffle to its lair, Ann. Appl. Prob. 2 (2) (1992) 294-313

Brillhart, John; Lomont, J. S.; Morton, Patrick. Cyclotomic properties of the Rudin-Shapiro polynomials, J. Reine Angew. Math.288 (1976), 37--65. See Table 2. MR0498479 (58 #16589). - From N. J. A. Sloane, Jun 06 2012

A. J. C. Cunningham, On Binal Fractions, Math. Gaz., 4 (71) (1908), circa p. 266.

P. Diaconis, R. L. Graham, W. M. Kantor, The mathematics of perfect shuffles, Adv. Appl. Math. 4 (2) (1983) 175-196

M. J. Gardner and C. A. McMahan, Riffling casino checks, Math. Mag., 50 (1) (1977), 38-41.

S. W. Golomb, Permutations by cutting and shuffling, SIAM Rev., 3 (1961), 293-297.

V. I. Levenshtein, Conflict-avoiding codes and cyclic triple systems, Problems of Information Transmission, September 2007, Volume 43, Issue 3, pp 199-212 (translated from Russian)

Vladimir Shevelev, Gilberto Garcia-Pulgarin, Juan Miguel Velasquez-Soto and John H. Castillo, Overpseudoprimes, and Mersenne and Fermat numbers as primover numbers, Arxiv preprint arXiv:1206:0606, 2012. - From N. J. A. Sloane, Oct 28 2012

Eric Weisstein's World of Mathematics, Riffle Shuffle

Eric Weisstein's World of Mathematics, In-Shuffle

Eric Weisstein's World of Mathematics, Out-Shuffle

Eric Weisstein's World of Mathematics, Multiplicative Order

Wikipedia, Riffle Shuffle

FORMULA

a((3^n-1)/2)=A025192(n). - Vladimir Shevelev, May 09 2008

Bisection of A007733: a(n) = A007733(2n+1). - Max Alekseyev, Jun 11 2009

a((b(n)-1)/2) = n for odd n and even n such that b(n/2) != b(n), where b(n) = A005420(n). - Thomas Ordowski, Jan 11 2014

Note that a(2^n-1) = n+1 and a(2^n) = 2(n+1). - Thomas Ordowski, Jan 16 2014

MAPLE

with(numtheory): f := n->order(2, 2*n+1);

MATHEMATICA

Table[MultiplicativeOrder[2, 2*n + 1], {n, 0, 100}] (* Robert G. Wilson v, Apr 05 2011 *)

PROG

(PARI) a(n)=if(n<0, 0, znorder(Mod(2, 2*n+1))) /* Michael Somos, Mar 31 2005 */

(MAGMA) [ 1 ] cat [ Modorder(2, 2*n+1): n in [1..72] ]; // Klaus Brockhaus, Dec 03 2008

(PARI) vector(100, p, factormod((x^(2*p+1)+1)/(x+1), 2, 1)[matsize(factormod((x^(2*p+1)+1)/(x+1), 2, 1))[1], 1]) \\ V. Raman, Sep 18 2012

(PARI) for(i=0, 200, i++; if(i%5==0, print1(0", "), print1(znorder(Mod(2, i))", "))) \\ V. Raman, Nov 22 2012

(PARI) for(i=0, 200, i++; m=0; for(x=1, i, if(((2^x-1))%i==0, m=x; break)); print1(m", ")) \\ V. Raman, Nov 22 2012

(Haskell)

import Data.List (findIndex)

import Data.Maybe (fromJust)

a002326 n = (+ 1) $ fromJust $

            findIndex ((== 0) . (`mod` (2 * n + 1))) $ tail a000225_list

-- Reinhard Zumkeller, Apr 22 2013

CROSSREFS

Cf. A003571, A003573, A217469, A070667-A070683, A053447, A053451.

Cf. A024222, A006694 (number of cyclotomic cosets).

Cf. A014664 (order of 2 mod n-th prime).

Cf. A001122 (primes for which 2 is a primitive root).

Cf. A216838 (primes for which 2 is not a primitive root).

Cf. A000225.

Sequence in context: A131388 A131393 A216476 * A064273 A232564 A134561

Adjacent sequences:  A002323 A002324 A002325 * A002327 A002328 A002329

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from David W. Wilson, Jan 13 2000

More terms from Benoit Cloitre, Apr 11 2003

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified August 21 04:26 EDT 2014. Contains 245837 sequences.