|
| |
|
|
A002326
|
|
Multiplicative order of 2 mod 2n+1.
(Formerly M0936 N0350)
|
|
96
|
|
|
|
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]
Contribution 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)
|
|
|
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
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.
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
|
|
|
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 A134561 A225055
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
|
| |
|
|
