cp's OEIS Frontend

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

%I A001917 M0069 N0022 #81 Aug 21 2023 13:58:48
%S A001917 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,
%T A001917 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,
%U A001917 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
%N A001917 (p-1)/x, where p = prime(n) and x = ord(2,p), the smallest positive integer such that 2^x == 1 (mod p).
%C A001917 Also number of cycles in permutations constructed from siteswap juggling pattern 1234...p.
%C A001917 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
%C A001917 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
%D A001917 M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 1, p. 131.
%D A001917 D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, pp. 7-10.
%D A001917 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.
%D A001917 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001917 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001917 T. D. Noe, <a href="/A001917/b001917.txt">Table of n, a(n) for n = 2..10000</a>
%H A001917 I. Anderson and D. A. Preece, <a href="http://dx.doi.org/10.1016/j.disc.2008.09.046">Combinatorially fruitful properties of 3*2^(-1) and 3*2^(-2) modulo p</a>, Discr. Math., 310 (2010), 312-324.
%H A001917 Keith Conrad, <a href="https://kconrad.math.uconn.edu/blurbs/ugradnumthy/wieferich-primes.pdf">Wieferich primes</a>, Univ. Conn. (2023).
%H A001917 W. Meissner, <a href="/A001917/a001917.pdf">Über die Teilbarkeit von 2^p-2 durch das Quadrat der Primzahl p = 1093</a>, Sitzungsberichte Königlich Preussischen Akadamie Wissenschaften Berlin, 35 (1913), 663-667. [Annotated scanned copy]
%H A001917 V. Papadimitriou, <a href="http://users.sch.gr/bpapa/morder/morder2.htm">The l_2^(p) and the ... ratio of the first hundred million primes</a>
%H A001917 David Speyer, <a href="http://math.stackexchange.com/questions/384097/can-the-order-of-2-mod-p-be-arbitrarily-small-relative-to-p-1/384406#384406">Can the order of 2 mod p be arbitrarily small (relative to p-1)?</a>
%F A001917 From _Vladimir Shevelev_, May 26 2008: (Start)
%F A001917 a(n) = A006694((p_n-1)/2) where p_n is the n-th odd prime.
%F A001917 Conjecture: k*a(n) = A006694(((p_n)^k-1)/2). (End)
%p A001917 with(numtheory); [seq((ithprime(n)-1)/order(2,ithprime(n)),n=2..130)];
%p A001917 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..)];
%t A001917 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_ *)
%t A001917 Table[p = Prime[n]; (p - 1)/MultiplicativeOrder[2, p], {n, 2, 100}] (* _T. D. Noe_, Apr 11 2012 *)
%t A001917 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 *)
%o A001917 (Magma) [ (p-1)/Modorder(2, p) where p is NthPrime(n): n in [2..100] ]; // _Klaus Brockhaus_, Dec 09 2008
%o A001917 (PARI) {for(n=2, 100, p=prime(n); print1((p-1)/znorder(Mod(2, p)), ","))} \\ _Klaus Brockhaus_, Dec 09 2008
%o A001917 (Python)
%o A001917 from sympy import prime, n_order
%o A001917 def A001917(n):
%o A001917     p = prime(n)
%o A001917     return 1 if n == 2 else (p-1)//n_order(2,p) # _Chai Wah Wu_, Jan 15 2020
%Y A001917 Cf. A006694 gives cycle counts of such permutations constructed for all odd numbers.
%Y A001917 Cf. A002323, A001122, A115591, A001133, A001134, A001135, A001136, A101208.
%Y A001917 Cf. A014664.
%K A001917 nonn,easy,nice
%O A001917 2,3
%A A001917 _N. J. A. Sloane_
%E A001917 Additional comments from _Antti Karttunen_, Jan 05 2000
%E A001917 More terms from _N. J. A. Sloane_, Dec 24 2009