|
| |
|
|
A002326
|
|
Multiplicative order of 2 mod 2n+1.
(Formerly M0936 N0350)
|
|
74
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| In other words, least m 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 (shevelev(AT)bgu.ac.il), May 09 2008
For a conjectural algorithm of calculation of a(n) see A179680. [From Vladimir Shevelev (shevelev(AT)bgu.ac.il), Jul 21 2010]
|
|
|
REFERENCES
| E. Bach and J. O. Shallit, Algorithmic Number Theory, I.
A. J. C. Cunningham, On Binal Fractions, Math. Gaz., 4 (1908), circa p. 266.
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.
M. J. Gardner and C. A. McMahan, Riffling casino checks, Math. Mag., 50 (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 [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
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
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
|
|
|
FORMULA
| a((3^n-1)/2)=A025192(n) - Vladimir Shevelev (shevelev(AT)bgu.ac.il), May 09 2008
Bisection of A007733: a(n) = A007733(2n+1) [From Max Alekseyev (maxale(AT)gmail.com), 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] ]; [From Klaus Brockhaus (klaus-brockhaus(AT)t-online.de), Dec 03 2008]
|
|
|
CROSSREFS
| Cf. A070667-A070675, A070676, A053447, A070677, A070681, A070678, A053451, A070679, A070682, A070680, A070683.
Cf. A024222, A006694 (number of cyclotomic cosets), A014664 (order of 2 mod n-th prime).
Sequence in context: A083673 A131388 A131393 * A064273 A134561 A120947
Adjacent sequences: A002323 A002324 A002325 * A002327 A002328 A002329
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from David W. Wilson (davidwwilson(AT)comcast.net), Jan 13, 2000.
More terms from Benoit Cloitre (benoit7848c(AT)orange.fr), Apr 11 2003
|
| |
|
|
