A006694 -id:A006694 - cp's OEIS frontend

A137576 a(n) = A002326(n) * A006694(n) + 1.

1, 3, 5, 7, 13, 11, 13, 17, 17, 19, 31, 23, 41, 55, 29, 31, 41, 61, 37, 49, 41, 43, 85, 47, 85, 57, 53, 81, 73, 59, 61, 73, 73, 67, 111, 71, 73, 141, 151, 79, 217, 83, 89, 113, 89, 109, 131, 145, 97, 211, 101, 103, 169, 107, 109, 145, 113, 221, 133, 193, 221, 141, 301, 127

Offset: 0

Vladimir Shevelev, Apr 26 2008, Apr 28 2008, May 03 2008, Jun 12 2008

nonn

Composite numbers n for which a((n-1)/2)=n are called overpseudoprimes to base 2 (A141232).
Theorem. If p and q are odd primes then the equality a((pq-1)/2)=pq is valid if and only if A002326((p-1)/2)=A002326((q-1)/2). Example: A002326(11) = A002326(44). Since 23 and 89 are primes then a((23*89-1)/2)=23*89.
A generalization: If p_1A002326((p_1-1)/2)= A002326((p_2-1)/2)=...=A002326((p_m-1)/2).
Moreover, if n is an odd squarefree number and a((n-1)/2)=n then also all divisors d of n satisfy a((d-1)/2)=d and d divides 2^d-2. Thus the sequence of such n is a subsequence of A050217.

Ray Chandler, Table of n, a(n) for n = 0..10000
Vladimir Shevelev, Exact exponent of remainder term of Gelfond's digit theorem in binary case, arXiv:0804.3682 [math.NT], 2008.
Vladimir Shevelev, Exact exponent in the remainder term of Gelfond's digit theorem in the binary case, Acta Arithmetica 136 (2009), 91-100.

Cf. A002326, A006694, A138193, A138217, A138227, A141232, A195468.

a[n_] := (t = MultiplicativeOrder[2, 2n+1])*DivisorSum[2n+1, EulerPhi[#] / MultiplicativeOrder[2, #]&]-t+1; Table[a[n], {n, 0, 70}] (* Jean-François Alcover, Dec 04 2015, adapted from PARI *)

a(n)=my(t);sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1 \\ Charles R Greathouse IV, Feb 20 2013

It can be shown that if p is an odd prime then a((p^k-1)/2)=1+k*phi(p^k).

a(n) = ord(2,2*n+1) * ((Sum_{d|(2n+1)} phi(d)/ord(2,d)) - 1) + 1, where phi = A000010 and ord(2,d) is the multiplicative order of 2 modulo d. - Jianing Song, Nov 13 2021

Edited and extended by Ray Chandler, May 08 2008

A160266 Let f and its k-fold iteration f^k be defined as in A159885. a(n) is the least k for which A006694( (f^k(2n+1)-1)/2 ) < A006694(n).

Original entry on oeis.org

2, 1, 1, 2, 4, 2, 1, 1, 6, 1, 2, 1, 1, 5, 1, 1, 1, 6, 1, 4, 3, 1, 2, 1, 1, 2, 1, 1, 10, 5, 1, 1, 8, 1, 1, 1, 1, 1, 2, 1, 40, 1, 1, 1, 1, 1, 6, 3, 1, 7, 17, 1, 36, 1, 1, 2, 1, 1, 1, 20, 1, 1, 1, 1, 8, 1, 1, 18, 13, 1, 5, 1, 2, 6, 1, 1, 1, 1, 1, 1, 6, 1, 9, 11, 2, 9, 1, 2, 9, 4, 6, 1, 1, 1, 9, 7, 1, 7, 29, 2, 2, 1

Offset: 1

Vladimir Shevelev, May 07 2009

Conjecture. For every n>=1, there exists a finite value of a(n). It is easy to see that this conjecture is equivalent to the well known Collatz 3n+1 conjecture.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006694, A159885, A159945, A160198, A122458, A160267.

A006519 := proc(n) local i ; for i in ifactors(n)[2] do if op(1,i) = 2 then return op(1,i)^op(2,i) ; fi ; od: return 1 ; end proc:
f := proc(twon1) local threen2 ; threen2 := 3*twon1/2+1/2 ; threen2/A006519(threen2) ; end proc:
A160266 := proc(n) local ref,k,fk ; ref := A006694(n) ; k := 1 ; fk := f(2*n+1) ; while true do if A006694( (fk-1)/2 ) < ref then return k; end if; fk := f(fk) ; k := k+1 ; end do ; end proc:
seq(A160266(n),n=1..120) ; # R. J. Mathar, Feb 02 2010

A006519[n_] := Do[If[fi[[1]] == 2, Return[2^fi[[2]]], Return[1]], {fi, FactorInteger[n]}];
f[n_] := With[{n2 = 3 n/2 + 1/2}, n2/A006519[n2]];
A006694[n_] := Sum[EulerPhi[d]/MultiplicativeOrder[2, d], {d, Divisors[2n + 1]}] - 1;
a[n_] := Module[{ref, k, fk}, ref = A006694[n]; k = 1; fk = f[2n + 1]; While[True, If[A006694[(fk - 1)/2] < ref, Return[k]]; fk = f[fk]; k++]];
Table[a[n], {n, 1, 105}] (* Jean-François Alcover, Aug 28 2024, after R. J. Mathar *)

f(n) = ((3*((n-1)/2))+2)/A006519((3*((n-1)/2))+2);
A006519(n) = (1<A006694(n) = (sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d))) - 1); \\ From A006694
A160266(n) = { my(w=A006694(n), n = (n+n+1), k=0); while(A006694((n-1)/2) >= w, k++; n = f(n)); (k); }; \\ Antti Karttunen, Sep 22 2018

More terms from R. J. Mathar, Feb 02 2010

A141229 Odd numbers k for which A006694((k-1)/2) = 3.

Original entry on oeis.org

27, 43, 109, 125, 157, 229, 277, 283, 307, 499, 643, 691, 733, 739, 811, 997, 1021, 1051, 1069, 1093, 1331, 1459, 1579, 1597, 1627, 1699, 1723, 1789, 1933, 2179, 2197, 2203, 2251, 2341, 2347, 2749, 2917, 3163, 3181, 3229, 3259, 3373, 4027, 4339, 4549, 4597, 4651, 4909

Offset: 1

Vladimir Shevelev, Jun 15 2008

nonn

Conjecture. The terms of the sequence have only one prime divisor; moreover, p^3 is in the sequence if and only if p is in A001122.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A006694, A002326, A001122, A001133.

r[n_] := EulerPhi[n]/MultiplicativeOrder[2, n]; Select[Range[5000], Total@(r /@ Divisors[#]) - 1 == 3 &] (* Amiram Eldar, Sep 12 2019 *)

a006694(n)=sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d))) - 1;
isok(n) = (n % 2) && (a006694((n-1)/2) == 3); \\ Michel Marcus, Feb 08 2016

More terms from Michel Marcus, Feb 08 2016

A064285 Duplicate of A006694.

Original entry on oeis.org

1, 1, 2, 2, 1, 1, 4, 2, 1, 5, 2, 2, 3, 1, 6, 4, 5, 1, 4, 2, 3, 7, 2, 4, 7, 1, 4, 4, 1, 1, 12, 6, 1, 5, 2

Offset: 0

dead

A139208 Numbers 2*k+1 for which numbers A006694(k) are record values for A006694.

Original entry on oeis.org

1, 3, 7, 15, 21, 31, 45, 63, 93, 105, 127, 189, 217, 255, 315, 341, 455, 511, 819, 1023, 1365, 2047, 3591, 3855, 4095, 5461, 8191, 12483, 13107, 16383, 21845, 29127, 32767, 53261, 55831, 60787, 65535, 87381, 131071, 178481, 182361, 209715, 258111, 262143, 349525, 430185, 479349, 524287

Offset: 1

Vladimir Shevelev, Jun 06 2008

nonn

Question. Is it true that all primes in this sequence are Mersenne primes?

178481 is a prime term, but is not a Mersenne prime. - Michel Marcus, Dec 18 2018

Cf. A006694, A000668.

a006694(n)=sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d))) - 1;
lista(nn) = {my(m = -1, newm); for(n=0, nn, newm = a006694(n); if (newm > m, m = newm; print1(2*n+1, ", ")););} \\ Michel Marcus, Dec 18 2018

Offset 1, missing term 819 and more terms from Michel Marcus, Dec 18 2018

A141230 Odd numbers n for which A006694((n-1)/2)=4.

Original entry on oeis.org

15, 33, 39, 49, 55, 57, 81, 87, 95, 111, 113, 143, 159, 177, 183, 201, 209, 249, 281, 289, 295, 303, 319, 321, 335, 353, 393, 407, 415, 417, 447, 489, 519, 529, 535, 537, 543, 551, 577, 583, 591, 593, 617, 625, 633, 649, 655, 681, 695, 737, 767, 807, 815, 879, 895, 913, 951

Offset: 1

Vladimir Shevelev, Jun 16 2008

nonn

If p>3 is a prime then 3p is in this sequence if and only if p is in A001122.

Cf. A006694, A001122, A001134.

a006694(n)=sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d))) - 1;
isok(n) = (n % 2) && (a006694((n-1)/2)== 4); \\ Michel Marcus, Dec 18 2018

More terms from Michel Marcus, Dec 18 2018

A160268 Odd numbers k for which A006694( (k-1)/2 )< A006694( (A000265(3k+1)-1)/2 ) .

Original entry on oeis.org

11, 23, 37, 41, 43, 59, 61, 79, 83, 97, 103, 107, 113, 121, 139, 143, 147, 149, 163, 167, 169, 171, 173, 177, 181, 183, 191, 193, 199, 201, 203, 227, 237, 243, 249, 251, 263, 271, 283, 287, 289, 293, 303, 313, 317, 321, 323, 347, 351, 353, 355, 359, 363, 367, 373, 379

Offset: 1

Vladimir Shevelev, May 07 2009

nonn

Conjecture: For every k in the sequence, the number k^2 is in the sequence as well.

Composite numbers in the sequence which are not perfect squares are 143, 147, 171, 183 etc. [R. J. Mathar, May 16 2009]

A006694, A160198, A122458, A159885, A159945, A160266, A160267.

Edited and extended by R. J. Mathar, May 16 2009

A160364 Let f be defined as in A159885 and f^k be the k-th iteration of f. Then a(n) is the least k for which either {A000120(f^k(2n+1)) < A000120(2n+1)}&{A006694((f^k(2n+1)-1)/2)<=A006694(n)} or {A000120(f^k(2n+1))<=A000120(2n+1)}&{A006694((f^k(2n+1)-1)/2) < A006694(n)}.

Original entry on oeis.org

2, 1, 1, 5, 3, 1, 1, 2, 5, 1, 2, 1, 1, 1, 1, 5, 2, 5, 3, 33, 3, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 5, 7, 1, 5, 10, 1, 1, 2, 5, 5, 1, 1

Offset: 1

Vladimir Shevelev, May 11 2009

Using induction, one can prove that the Collatz (3x+1)-conjecture follows from the finiteness of a(n) for every n.

			Beginning with n=1, we have f(2n+1)=f(3)=5. Here A000120(3)=A000120(5)=2 and A006694((3-1)/2)= A006694((5-1)/2)=1. None of values did not become less than. Therefore a(1)>1. Since f(5)=1 and A000120(1)=1 and A006694(0)=0, then a(2)=2.

A000120 A006694 A160267 A006694 A122458 A160266 A159885 A159945 A160198

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

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

A001917 (p-1)/x, where p = prime(n) and x = ord(2,p), the smallest positive integer such that 2^x == 1 (mod p).

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 1, 2, 1, 6, 1, 2, 3, 2, 1, 1, 1, 1, 2, 8, 2, 1, 8, 2, 1, 2, 1, 3, 4, 18, 1, 2, 1, 1, 10, 3, 1, 2, 1, 1, 1, 2, 2, 1, 2, 1, 6, 1, 3, 8, 2, 10, 5, 16, 2, 1, 2, 3, 4, 3, 1, 3, 2, 2, 1, 11, 16, 1, 1, 4, 2, 2, 1, 1, 2, 1, 9, 2, 2, 1, 1, 10, 6, 6, 1, 2, 6, 1, 2, 1, 2, 2, 1, 3, 2, 1, 2, 1, 1, 1, 1, 1, 2

Offset: 2

N. J. A. Sloane

Also number of cycles in permutations constructed from siteswap juggling pattern 1234...p.
Also the number of irreducible polynomial factors for the polynomial (x^p-1)/(x-1) over GF(2), where p is the n-th prime. - V. Raman, Oct 04 2012
The sequence is unbounded: for any value of M, there exists an element of the sequence divisible by M. See the proof by David Speyer below. - Shreevatsa R, May 24 2013

M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 1, p. 131.
D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, pp. 7-10.
W. Meissner, Über die Teilbarkeit von 2^p-2 durch das Quadrat der Primzahl p = 1093, Sitzungsberichte Königlich Preussischen Akadamie Wissenschaften Berlin, 35 (1913), 663-667.
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 = 2..10000
I. Anderson and D. A. Preece, Combinatorially fruitful properties of 3*2^(-1) and 3*2^(-2) modulo p, Discr. Math., 310 (2010), 312-324.
Keith Conrad, Wieferich primes, Univ. Conn. (2023).
W. Meissner, Über die Teilbarkeit von 2^p-2 durch das Quadrat der Primzahl p = 1093, Sitzungsberichte Königlich Preussischen Akadamie Wissenschaften Berlin, 35 (1913), 663-667. [Annotated scanned copy]
V. Papadimitriou, The l_2^(p) and the ... ratio of the first hundred million primes
David Speyer, Can the order of 2 mod p be arbitrarily small (relative to p-1)?

Cf. A006694 gives cycle counts of such permutations constructed for all odd numbers.
Cf. A002323, A001122, A115591, A001133, A001134, A001135, A001136, A101208.
Cf. A014664.

[ (p-1)/Modorder(2, p) where p is NthPrime(n): n in [2..100] ]; // Klaus Brockhaus, Dec 09 2008

with(numtheory); [seq((ithprime(n)-1)/order(2,ithprime(n)),n=2..130)];
with(group); with(numtheory); gen_rss_perm := proc(n) local a, i; a := []; for i from 1 to n do a := [op(a), ((2*i) mod (n+1))]; od; RETURN(a); end; count_of_disjcyc_seq := [seq(nops(convert(gen_rss_perm(ithprime(j)-1),'disjcyc')),j=2..)];

a6694[n_] := Sum[ EulerPhi[d] / MultiplicativeOrder[2, d], {d, Divisors[2n + 1]}] - 1; a[n_] := a6694[(Prime[n]-1)/2]; Table[ a[n], {n, 2, 104}] (* Jean-François Alcover, Dec 14 2011, after Vladimir Shevelev *)
Table[p = Prime[n]; (p - 1)/MultiplicativeOrder[2, p], {n, 2, 100}] (* T. D. Noe, Apr 11 2012 *)
ord[n_]:=Module[{x=1},While[PowerMod[2,x,n]!=1,x++];(n-1)/x]; ord/@ Prime[ Range[ 2,110]] (* Harvey P. Dale, Jun 25 2014 *)

{for(n=2, 100, p=prime(n); print1((p-1)/znorder(Mod(2, p)), ","))} \\ Klaus Brockhaus, Dec 09 2008

from sympy import prime, n_order
def A001917(n):
    p = prime(n)
    return 1 if n == 2 else (p-1)//n_order(2,p) # Chai Wah Wu, Jan 15 2020

From Vladimir Shevelev, May 26 2008: (Start)
a(n) = A006694((p_n-1)/2) where p_n is the n-th odd prime.
Conjecture: k*a(n) = A006694(((p_n)^k-1)/2). (End)

Additional comments from Antti Karttunen, Jan 05 2000

More terms from N. J. A. Sloane, Dec 24 2009

cp's OEIS Frontend

A137576 a(n) = A002326(n) * A006694(n) + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A160266 Let f and its k-fold iteration f^k be defined as in A159885. a(n) is the least k for which A006694( (f^k(2n+1)-1)/2 ) < A006694(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A141229 Odd numbers k for which A006694((k-1)/2) = 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A064285 Duplicate of A006694.

Views

Author

Keywords

A139208 Numbers 2*k+1 for which numbers A006694(k) are record values for A006694.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A141230 Odd numbers n for which A006694((n-1)/2)=4.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A160268 Odd numbers k for which A006694( (k-1)/2 )< A006694( (A000265(3k+1)-1)/2 ) .

Views

Author

Keywords

Comments

Crossrefs

Extensions

A160364 Let f be defined as in A159885 and f^k be the k-th iteration of f. Then a(n) is the least k for which either {A000120(f^k(2n+1)) < A000120(2n+1)}&{A006694((f^k(2n+1)-1)/2)<=A006694(n)} or {A000120(f^k(2n+1))<=A000120(2n+1)}&{A006694((f^k(2n+1)-1)/2) < A006694(n)}.

Views

Author

Keywords

Comments

Examples

Crossrefs

A002326 Multiplicative order of 2 mod 2n+1.

Views

Author

Keywords

Comments

Examples

References

Links