|
%I M0936 N0350 #353 Mar 09 2024 16:43:59
%S 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,
%T 52,20,18,58,60,6,12,66,22,35,9,20,30,39,54,82,8,28,11,12,10,36,48,30,
%U 100,51,12,106,36,36,28,44,12,24,110,20,100,7,14,130,18,36,68,138,46,60,28
%N Multiplicative order of 2 mod 2n+1.
%C In other words, least m > 0 such that 2n+1 divides 2^m-1.
%C 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) with 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.
%C Concerning the complexity of computing this sequence, see for example Bach and Shallit, p. 115, exercise 8.
%C 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
%C For an algorithm of calculation of a(n) see author's comment in A179680. - _Vladimir Shevelev_, Jul 21 2010
%C From _V. Raman_, Sep 18 2012, Dec 10 2012: (Start)
%C 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).
%C 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).
%C For all n > 0, a(n) is the degree of the largest irreducible polynomial factor for the polynomial (x^(2n+1)+1)/(x+1) over GF(2). (End)
%C a(n) is a factor of phi(2n+1) (A000010(2n+1)). - _Douglas Boffey_, Oct 21 2013
%C 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
%C A generalization of the previous conjecture: For each k>=2, if p is an odd prime then a(((p^(k+1))-1)/2) = p * a((p^k-1)/2). Computer testing of this generalized conjecture shows that there is no counterexample for k and p both up to 1000. - _Ahmad J. Masad_, Oct 17 2020
%C a(n) = a((N-1)/2), with odd N = 2*n+1 >= 3 (n >= 1), is also the primitive period length of (1/N) in binary notation: (1/N)_2 = 0.repeat(a[1]a[2]...a[P(N)]), and P(N) = a((N-1)/2). E.g., N = 11 (n = 5), (1/11)_2 = 0.repeat(0001011101), with P(11) = 10 = a(5). Proof: Use a cyclic shift operation sigma (1 step to the left) on the cycle: sigma((1/N)_2) = .repeat(a[2]...a[P(N)]a[1]). Then one can prove for the composition sigma^[k] (k=0 is the identity map) written back in decimal notation the result (sigma^[k]((1/N)_2))_10 = (1/N)*2^k (mod N). E.g. N = 11, sigma^[2]((1/11)_2) = .repeat(0101110100), written in base 10 as 4/11, etc. Hence P(N) and the order of 2 modulo N coincide. - _Gary W. Adamson_ and _Wolfdieter Lang_, Oct 14 2020
%D E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I.
%D T. Folger, "Shuffling Into Hyperspace," Discover, 1991 (vol 12, no 1), pages 66-67.
%D M. Gardner, "Card Shuffles," Mathematical Carnival chapter 10, pages 123-138. New York: Vintage Books, 1977.
%D 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).
%D J. H. Silverman, A Friendly Introduction to Number Theory, 3rd ed., Pearson Education, Inc, 2006, p. 146, Exer. 21.3
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A002326/b002326.txt">Table of n, a(n) for n = 0..10000</a>
%H M. Baake, U. Grimm and J. Nilsson, <a href="https://arxiv.org/abs/1311.4371">Scaling of the Thue-Morse diffraction measure</a>, arXiv preprint arXiv:1311.4371 [math-ph], 2013.
%H D. Bayer and P. Diaconis, <a href="http://dx.oi.org/10.1214/aoap/1177005705">Trailing the dovetail shuffle to its lair</a>, Ann. Appl. Prob. 2 (2) (1992) 294-313.
%H Matthew Brand, <a href="https://arxiv.org/abs/1808.07994">Choosing 1 of N with and without lucky numbers</a>, arXiv:1808.07994 [math.NT], 2018.
%H J. Brillhart, J. S. Lomont and P. Morton, <a href="http://resolver.sub.uni-goettingen.de/purl?GDZPPN002192802">Cyclotomic properties of the Rudin-Shapiro polynomials</a>, J. Reine Angew. Math.288 (1976), 37--65. See Table 2. MR0498479 (58 #16589).
%H Steve Butler, Persi Diaconis and R. L. Graham, <a href="https://arxiv.org/abs/1412.8533">The mathematics of the flip and horseshoe shuffles</a>, arXiv:1412.8533 [math.CO], 2014.
%H Steve Butler, Persi Diaconis and R. L. Graham, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.123.6.542">The mathematics of the flip and horseshoe shuffles</a>, The American Mathematical Monthly 123.6 (2016): 542-556.
%H A. J. C. Cunningham, <a href="http://www.jstor.org/stable/3602595">On Binal Fractions</a>, Math. Gaz., 4 (71) (1908), circa p. 266.
%H P. Diaconis, R. L. Graham, and W. M. Kantor, <a href="http://dx.doi.org/10.1016/0196-8858(83)90009-X">The mathematics of perfect shuffles</a>, Adv. Appl. Math. 4 (2) (1983) 175-196
%H M. J. Gardner and C. A. McMahan, <a href="http://www.jstor.org/stable/2689753">Riffling casino checks</a>, Math. Mag., 50 (1) (1977), 38-41.
%H S. W. Golomb, <a href="http://dx.doi.org/10.1137/1003059">Permutations by cutting and shuffling</a>, SIAM Rev., 3 (1961), 293-297.
%H Jonas Kaiser, <a href="https://arxiv.org/abs/1608.00862">On the relationship between the Collatz conjecture and Mersenne prime numbers</a>, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
%H Torleiv Klove, <a href="https://doi.org/10.1007/s12095-015-0154-5">On covering sets for limited-magnitude errors</a>, Cryptogr. Commun. 8 (3) (2016) 415-433
%H V. I. Levenshtein, <a href="http://mi.mathnet.ru/eng/ppi17">Conflict-avoiding codes and cyclic triple systems</a> [in Russian], Problemy Peredachi Informatsii, 43 (No. 3, 2007), 39-53.
%H V. I. Levenshtein, <a href="http://dx.doi.org/10.1134/S0032946007030039">Conflict-avoiding codes and cyclic triple systems</a>, Problems of Information Transmission, September 2007, Volume 43, Issue 3, pp 199-212 (translated from Russian)
%H Yuan-Hsun Lo, Kenneth W. Shum, Wing Shing Wong and Yijin Zhang, <a href="https://arxiv.org/abs/2009.11754">Multichannel Conflict-Avoiding Codes of Weights Three and Four</a>, arXiv:2009.11754 [cs.IT], 2020.
%H Jarkko Peltomäki and Aleksi Saarela, <a href="https://doi.org/10.1016/j.jcta.2020.105340">Standard words and solutions of the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2</a>, Journal of Combinatorial Theory, Series A (2021) Vol. 178, 105340. See also <a href="https://arxiv.org/abs/2004.14657">arXiv:2004.14657</a> [cs.FL], 2020.
%H Vladimir Shevelev, Gilberto Garcia-Pulgarin, Juan Miguel Velasquez-Soto and John H. Castillo, <a href="https://arxiv.org/abs/1206.0606">Overpseudoprimes, and Mersenne and Fermat numbers as primover numbers</a>, arXiv preprint arXiv:1206:0606 [math.NT], 2012.
%H Vladimir Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL15/Shevelev/shevelev19.html">Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers</a>, J. Integer Seq. 15 (2012) Article 12.7.7.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RiffleShuffle.html">Riffle Shuffle</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/In-Shuffle.html">In-Shuffle</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Out-Shuffle.html">Out-Shuffle</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MultiplicativeOrder.html">Multiplicative Order</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Riffle_shuffle#Riffle">Riffle Shuffle</a>
%F a((3^n-1)/2) = A025192(n). - _Vladimir Shevelev_, May 09 2008
%F Bisection of A007733: a(n) = A007733(2*n+1). - _Max Alekseyev_, Jun 11 2009
%F 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
%F Note that a(2^n-1) = n+1 and a(2^n) = 2*(n+1). - _Thomas Ordowski_, Jan 16 2014
%F a(n) = A056239(A292239(n)) = A048675(A292265(n)). - _Antti Karttunen_, Oct 04 2017
%e From _Vladimir Shevelev_, Oct 03 2017: (Start)
%e Our algorithm for the calculation of a(n) in the author's comment in A179680 (see also the Sage program below) could be represented in the form of a "finite continued fraction". For example let n = 8, 2*n+1 = 17. We have
%e 1 + 17
%e ------- + 17
%e 2
%e ------------- + 17
%e 2
%e ------------------- + 17
%e 2
%e -------------------------- = 1
%e 32
%e Here the denominators are the A006519 of the numerators: A006519(1+17) = 2, A006519(9+17) = 2, A006519(13+17) = 2, A006519(15+17) = 32. Summing the exponents of these powers of 2, we obtain the required result: a(8) = 1 + 1 + 1 + 5 = 8. Indeed, we have (((1*32 - 17)*2 - 17)*2 - 17)*2 - 17 = 1. So 32*2*2*2 - 1 == 0 (mod 17), 2^8 - 1 == 0 (mod 17). In the general case, note that all "partial fractions" (which indeed are integers) are odd residues modulo 2*n+1 in the interval [1, 2*n-1]. It is easy to prove that the first 1 appears not later than in the n-th step. (End)
%p a := n -> `if`(n=0, 1, numtheory:-order(2, 2*n+1)):
%p seq(a(n), n=0..72);
%t Table[MultiplicativeOrder[2, 2*n + 1], {n, 0, 100}] (* _Robert G. Wilson v_, Apr 05 2011 *)
%o (PARI) a(n)=if(n<0,0,znorder(Mod(2,2*n+1))) /* _Michael Somos_, Mar 31 2005 */
%o (Magma) [ 1 ] cat [ Modorder(2, 2*n+1): n in [1..72] ]; // _Klaus Brockhaus_, Dec 03 2008
%o (Haskell)
%o import Data.List (findIndex)
%o import Data.Maybe (fromJust)
%o a002326 n = (+ 1) $ fromJust $
%o findIndex ((== 0) . (`mod` (2 * n + 1))) $ tail a000225_list
%o -- _Reinhard Zumkeller_, Apr 22 2013
%o (Sage)
%o # From _Peter Luschny_, Oct 06 2017: (Start)
%o [Mod(2,n).multiplicative_order() for n in (0..145) if gcd(n,2) == 1]
%o # Algorithm from _Vladimir Shevelev_ as described in A179680 and presented in Example.
%o def A002326VS(n):
%o s, m, N = 0, 1, 2*n + 1
%o while True:
%o k = N + m
%o v = valuation(k, 2)
%o s += v
%o m = k >> v
%o if m == 1: break
%o return s
%o [A002326VS(n) for n in (0..72)] # (End)
%o (GAP) List([0..100],n->OrderMod(2,2*n+1)); # _Muniru A Asiru_, Feb 01 2019
%o (Python)
%o from sympy import n_order
%o [n_order(2, 2*n+1) for n in range(73)] # _Hermann Stamm-Wilbrandt_, Jul 27 2021
%Y Cf. A003571, A003573, A217469, A070667-A070683, A053447, A053451, A292239, A292265.
%Y Cf. A024222, A006694 (number of cyclotomic cosets).
%Y Cf. A014664 (order of 2 mod n-th prime).
%Y Cf. A001122 (primes for which 2 is a primitive root).
%Y Cf. A216838 (primes for which 2 is not a primitive root).
%Y Cf. A000010, A000225, A005420, A006519, A007733, A025192, A048675, A056239, A179680.
%Y Bisections give A274298, A274299.
%Y Partial sums: A359147.
%K nonn,easy,nice
%O 0,2
%A _N. J. A. Sloane_
%E More terms from _David W. Wilson_, Jan 13 2000
%E More terms from _Benoit Cloitre_, Apr 11 2003
|
