A292239 -id:A292239 - cp's OEIS frontend

A002326 Multiplicative order of 2 mod 2n+1.

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

N. J. A. Sloane

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

			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)

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

T. D. Noe, Table of n, a(n) for n = 0..10000
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
M. Baake, U. Grimm and J. Nilsson, Scaling of the Thue-Morse diffraction measure, arXiv preprint arXiv:1311.4371 [math-ph], 2013.
D. Bayer and P. Diaconis, Trailing the dovetail shuffle to its lair, Ann. Appl. Prob. 2 (2) (1992) 294-313.
Matthew Brand, Choosing 1 of N with and without lucky numbers, arXiv:1808.07994 [math.NT], 2018.
J. Brillhart, J. S. Lomont and P. Morton, Cyclotomic properties of the Rudin-Shapiro polynomials, J. Reine Angew. Math.288 (1976), 37--65. See Table 2. MR0498479 (58 #16589).
Steve Butler, Persi Diaconis and R. L. Graham, The mathematics of the flip and horseshoe shuffles, arXiv:1412.8533 [math.CO], 2014.
Steve Butler, Persi Diaconis and R. L. Graham, The mathematics of the flip and horseshoe shuffles, The American Mathematical Monthly 123.6 (2016): 542-556.
A. J. C. Cunningham, On Binal Fractions, Math. Gaz., 4 (71) (1908), circa p. 266.
P. Diaconis, R. L. Graham, and 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.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
Torleiv Klove, On covering sets for limited-magnitude errors, Cryptogr. Commun. 8 (3) (2016) 415-433
V. I. Levenshtein, Conflict-avoiding codes and cyclic triple systems [in Russian], Problemy Peredachi Informatsii, 43 (No. 3, 2007), 39-53.
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)
Yuan-Hsun Lo, Kenneth W. Shum, Wing Shing Wong and Yijin Zhang, Multichannel Conflict-Avoiding Codes of Weights Three and Four, arXiv:2009.11754 [cs.IT], 2020.
Jarkko Peltomäki and Aleksi Saarela, Standard words and solutions of the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2, Journal of Combinatorial Theory, Series A (2021) Vol. 178, 105340. See also arXiv:2004.14657 [cs.FL], 2020.
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 [math.NT], 2012.
Vladimir Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers, J. Integer Seq. 15 (2012) Article 12.7.7.
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

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.

List([0..100],n->OrderMod(2,2*n+1)); # Muniru A Asiru, Feb 01 2019

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

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

a := n -> `if`(n=0, 1, numtheory:-order(2, 2*n+1)):
seq(a(n), n=0..72);

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

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

from sympy import n_order
[n_order(2, 2*n+1) for n in range(73)] # Hermann Stamm-Wilbrandt, Jul 27 2021

# 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)

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

More terms from David W. Wilson, Jan 13 2000

More terms from Benoit Cloitre, Apr 11 2003

A179382 a(n) is the smallest period of pseudo-arithmetic progression with initial term 1 and difference 2n-1.

Original entry on oeis.org

1, 1, 2, 1, 3, 5, 6, 1, 4, 9, 2, 4, 10, 9, 14, 1, 5, 5, 18, 4, 10, 7, 5, 9, 10, 2, 26, 8, 9, 29, 30, 1, 6, 33, 11, 14, 3, 9, 15, 17, 27, 41, 2, 11, 4, 4, 3, 14, 24, 15, 50, 23, 4, 53, 18, 14, 14, 19, 3, 9, 55, 6, 50, 1, 7, 65, 8, 17, 34, 69, 23, 25, 14, 20, 74, 5, 10, 8, 26, 21

Offset: 1

Vladimir Shevelev, Jul 12 2010

nonn

Let x,y be odd numbers. Denote <+> the following binary operation: x<+>y=A000265(x+y). Let a and d be odd numbers. We call a sequence of the form b, b<+>d, (b<+>d)<+>d,... a pseudo-arithmetic progression with the initial term b and the difference d. It is not difficult to prove that every pseudo-arithmetic progression is periodic sequence. This sequence lists smallest periods of pseudo-arithmetic progressions with initial term 1 and difference 2n-1, n=1,2,...

a(n) is the number of distinct odd residues contained in set {1,2,...,2^(2*n-2)} modulo 2*n-1. Thus 2*n-1 is in A001122 iff a(n)=n-1. - Vladimir Shevelev, Jul 18 2010

			For n=5, we have 1<+>9=5, 5<+>9=7, 7<+>9=1. Thus a(5)=3.

Peter J. C. Moses, Table of n, a(n) for n = 1..4096

Cf. A000265, A001122, A179680, A292239.

pseuAprog := proc(a,b) A000265(a+b) ; end proc:
A179382 := proc(n) local p,k; p := [1] ; for k from 2 do a := pseuAprog( p[-1],2*n-1) ; if not a in p then p := [op(p),a] ; else return nops(p) ; end if; end do: end proc:
seq(A179382(n),n=1..80) ;
# R. J. Mathar, Jul 13 2010

oddres[n_] := n/2^IntegerExponent[n, 2];
a[n_] := Module[{d = 2n-1, k=1, t=1}, While[(t = oddres[t+d])>1, k++]; k];
Array[a, 80] (* Jean-François Alcover, Apr 13 2020, translated from PARI *)

oddres(n)=n>>valuation(n,2)
a(n)=my(d=2*n-1,k=1,t=1);while((t=oddres(t+d))>1,k++);k
\\ Charles R Greathouse IV, May 15 2013

def A179382(n):
    N, o, s = 2*n-1, 1, 0
    while True:
        o = (N + o) >> valuation(N + o, 2)
        s = s + 1
        if o == 1: break
    return s
print([A179382(n) for n in (1..72)]) # Peter Luschny, Oct 07 2017

a(n) = A001222(A292239(n-1)). - Antti Karttunen, Oct 04 2017

Corrected and extended by R. J. Mathar, Jul 13 2010

Duplicated database lines removed by R. J. Mathar, Jul 23 2010

A292270 Sum of all partial fractions in the algorithm used for calculation of A002326(n).

Original entry on oeis.org

1, 1, 4, 1, 13, 25, 36, 1, 38, 81, 12, 26, 124, 121, 196, 1, 103, 73, 324, 42, 224, 175, 91, 147, 232, 14, 676, 170, 303, 841, 900, 1, 264, 1089, 385, 364, 93, 301, 585, 563, 1093, 1681, 44, 355, 152, 118, 83, 484, 1254, 763, 2500, 1043, 156, 2809, 996, 564, 952, 931, 71, 387, 3325, 176, 3124, 1, 649, 4225, 554, 1081

Offset: 0

Vladimir Shevelev and Antti Karttunen, Oct 05 2017

nonn

This sequence gives important additional insight into the algorithm for the calculation of A002326 (see A179680 for its description). Let us estimate how many steps are required before (the first) 1 will appear. Note that all partial fractions (which are indeed, integers) are odd residues modulo 2*n+1 from the interval [1,2*n-1]. So, if there is no repetition, then the number of steps does not exceed n. Suppose then that there is a repetition before the appearance of 1. Then for an odd residue k from [1, 2*n-1], 2^m_1 == 2^m_2 == k (mod 2*n+1) such that m_2 > m_1. But then 2^(m_2-m_1) == 1 (mod 2*n+1). So, since m_2 - m_1 < m_2, it means that 1 should appear earlier than the repetition of k, which is a contradiction. So the number of steps <= n. For example, for n=9, 2*n+1 = 19, we have exactly 9 steps with all other odd residues <= 17 modulo 19 appearing before the final 1: 5, 3, 11, 15, 17, 9, 7, 13, 1.

A001122 gives the odd numbers k such that a((k-1)/2) = A000290((k-1)/2).

			Let n = 9. According to the comment, a(9) = 5 + 3 + 11 + 15 + 17 + 9 + 7 + 13 + 1 = 81.

Antti Karttunen, Table of n, a(n) for n = 0..10001

Cf. A000265, A000290, A001122, A001917, A002326, A006519, A163782, A179382, A179680, A292239, A292265, A292947, A293218, A293219.

Cf. A000225 (gives the positions of ones), A292938 (of squares), A292939 (and the corresponding odd numbers), A292940 (odd numbers corresponding to squares larger than one), A292379 (odd numbers corresponding to squares less than n^2).

A000265(n) = (n >> valuation(n, 2));
A006519(n) = 2^valuation(n, 2);
A292270(n) = { my(x = n+n+1, z = ((1+x)/A006519(1+x)), m = A000265(1+x)); while(m!=1, z += ((x+m)/A006519(x+m)); m = A000265(x+m)); z; };

(define (A292270 n) (let ((x (+ n n 1))) (let loop ((z (/ (+ 1 x) (A006519 (+ 1 x)))) (k 1)) (let ((m (A000265 (+ x k)))) (if (= 1 m) z (loop (+ z (/ (+ x m) (A006519 (+ x m)))) m))))))

For all n >= 1, A000196(a((A001122(1+n)-1)/2)) = (A001122(1+n)-1)/2, in other words, a(A163782(n)) = A000290(A163782(n)).

A179680 The number of exponents >1 in a recursive reduction of 2n-1 until reaching an odd part equal to 1.

Original entry on oeis.org

0, 1, 1, 1, 1, 3, 3, 1, 1, 5, 1, 3, 5, 5, 7, 1, 1, 3, 9, 3, 3, 3, 3, 6, 5, 2, 13, 5, 3, 15, 15, 1, 1, 17, 5, 9, 1, 5, 7, 10, 13, 21, 1, 7, 2, 3, 2, 9, 11, 9, 25, 13, 2, 27, 9, 9, 5, 11, 2, 6, 27, 5, 25, 1, 1, 33, 3, 9, 15, 35, 11, 15, 3, 11, 37, 3, 6, 5, 13, 13

Offset: 1

Vladimir Shevelev, Jul 24 2010

nonn

Let N = 2n-1. Then consider the following algorithm of updating pairs (v,m) indicating highest exponent of 2 (2-adic valuation) and odd part: Initialize at step 1 by v(1) = A007814(N+1) and m(1) = A000265(N+1). Iterate over steps i>=2: v(i) = A007814(N+m(i-1)), m(i) = A000265(N+m(i-1)) using the previous odd part m(i-1) until some m(k) = 1. a(n) is defined as the count of the v(i) which are larger than 1.
This is an algorithm to compute A002326 because the sum v(1)+v(2)+ ... +v(k) of the exponents is A002326(n-1).
A179382(n) = 1 + the number of iterations taken by the algorithm when starting from N = 2n-1. - Antti Karttunen, Oct 02 2017

			For n = 9, 2*n-1 = 17, we have v_1 = v_2 = v_3 = 1, v_4 = 5. Thus a(9) = 1.
For n = 10, 2*n-1 = 19, we have v_1 = 2, v_2 = 3, v_3 = v_4 = v_5 = 1, v_6 = v_7 = 2, v_8 = 1, v_9 = 5. Thus a(10) = 5.

Antti Karttunen, Table of n, a(n) for n = 1..8192

Cf. A179676, A179460, A007814, A002326, A179382, A292239, A292265, A292266.

A179680 := proc(n) local l,m,a ,N ; N := 2*n-1 ; a := 0 ; l := A007814(N+1) ; m := A000265(N+1) ; if l > 1 then a := a+1 ; end if; while m <> 1 do l := A007814(N+m) ; if l > 1 then a := a+1 ; end if; m := A000265(N+m) ; end do: a ; end proc:
seq(A179680(n),n=1..80) ; # R. J. Mathar, Apr 05 2011

a7814[n_] := IntegerExponent[n, 2];
a265[n_] := n/2^IntegerExponent[n, 2];
a[n_] := Module[{l, m, k, nn}, nn = 2n-1; k = 0; l = a7814[nn+1]; m = a265[nn+1]; If[l>1, k++]; While[m != 1, l = a7814[nn+m]; If[l>1, k++]; m = a265[nn+m]]; k];
Array[a, 80] (* Jean-François Alcover, Jul 30 2018, after R. J. Mathar *)

def A179680(n):
    s, m, N = 0, 1, 2*n - 1
    while True:
        k = N + m
        v = valuation(k, 2)
        if v > 1: s += 1
        m = k >> v
        if m == 1: break
    return s
print([A179680(n) for n in (1..80)]) # Peter Luschny, Oct 07 2017

(define (A179680 n) (let ((x (+ n n -1))) (let loop ((s (- 1 (A000035 n))) (k 1)) (let ((m (A000265 (+ x k)))) (if (= 1 m) s (loop (+ s (if (> (A007814 (+ x m)) 1) 1 0)) m)))))) ;; Antti Karttunen, Oct 02 2017

cp's OEIS Frontend

A002326 Multiplicative order of 2 mod 2n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A179382 a(n) is the smallest period of pseudo-arithmetic progression with initial term 1 and difference 2n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A292270 Sum of all partial fractions in the algorithm used for calculation of A002326(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Scheme

Formula

A179680 The number of exponents >1 in a recursive reduction of 2n-1 until reaching an odd part equal to 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Scheme

A292265 A multiplicative encoding (compressed) for the exponents of 2 obtained when using Shevelev's algorithm for computing A002326.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

A292266 Restricted growth sequence transform of A292265; a filter related to Shevelev's algorithm for computing A002326.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs