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

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,3

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

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)

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

Prog

(Magma) [ (p-1)/Modorder(2, p) where p is NthPrime(n): n in [2..100] ]; // Klaus Brockhaus, Dec 09 2008
(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

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.

Sequence in context: A013632 A080121 A122901 * A240545 A091591 A337633

Adjacent sequences: A001914 A001915 A001916 * A001918 A001919 A001920

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

Additional comments from Antti Karttunen, Jan 05 2000

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

Status

approved