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

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

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

References

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

Links

• 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)?

Crossrefs

Cf. A006694 gives cycle counts of such permutations constructed for all odd numbers.

Cf. A002323, A001122, A115591, A001133, A001134, A001135, A001136, A101208.

Cf. A014664.

Programs

Magma

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

Maple

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

Mathematica

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

PARI

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

Python

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

Formula

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)

Extensions

Additional comments from Antti Karttunen, Jan 05 2000

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