cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A002326 Multiplicative order of 2 mod 2n+1.

Original entry on oeis.org

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
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

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) 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.
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 an algorithm of calculation of a(n) see author's comment in 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).
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).
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)
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
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
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

Examples

			From _Vladimir Shevelev_, Oct 03 2017: (Start)
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
    1 + 17
    ------- + 17
       2
    ------------- + 17
           2
    ------------------- + 17
              2
    -------------------------- = 1
                 32
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)

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.
  • 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

Crossrefs

Cf. A003571, A003573, A217469, A070667-A070683, A053447, A053451, A292239, A292265.
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. A000010, A000225, A005420, A006519, A007733, A025192, A048675, A056239, A179680.
Bisections give A274298, A274299.
Partial sums: A359147.

Programs

  • GAP
    List([0..100],n->OrderMod(2,2*n+1)); # Muniru A Asiru, Feb 01 2019
  • 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
  • Magma
    [ 1 ] cat [ Modorder(2, 2*n+1): n in [1..72] ]; // Klaus Brockhaus, Dec 03 2008
  • Maple
    a := n -> `if`(n=0, 1, numtheory:-order(2, 2*n+1)):
seq(a(n), n=0..72);
  • Mathematica
    Table[MultiplicativeOrder[2, 2*n + 1], {n, 0, 100}] (* Robert G. Wilson v, Apr 05 2011 *)
  • PARI
    a(n)=if(n<0,0,znorder(Mod(2,2*n+1))) /* Michael Somos, Mar 31 2005 */
  • Python
    from sympy import n_order
[n_order(2, 2*n+1) for n in range(73)] # Hermann Stamm-Wilbrandt, Jul 27 2021
  • Sage
    # From Peter Luschny, Oct 06 2017: (Start)
[Mod(2,n).multiplicative_order() for n in (0..145) if gcd(n,2) == 1]
# Algorithm from Vladimir Shevelev as described in A179680 and presented in Example.
def A002326VS(n):
    s, m, N = 0, 1, 2*n + 1
    while True:
        k = N + m
        v = valuation(k, 2)
        s += v
        m = k >> v
        if m == 1: break
    return s
[A002326VS(n) for n in (0..72)] # (End)

Formula

a((3^n-1)/2) = A025192(n). - Vladimir Shevelev, May 09 2008
Bisection of A007733: a(n) = A007733(2*n+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
a(n) = A056239(A292239(n)) = A048675(A292265(n)). - Antti Karttunen, Oct 04 2017

Extensions

More terms from David W. Wilson, Jan 13 2000
More terms from Benoit Cloitre, Apr 11 2003

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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