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
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
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
Comments