login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)
31
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,3

COMMENTS

Also number of cycles in permutations constructed from siteswap juggling pattern 1234...p.

Also A006694((p_n-1)/2) where p_n is the n-th odd prime. Conjecture: A006694(((p_n)^k-1)/2)=ka(n). - Vladimir Shevelev, May 26 2008

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.

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

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

(PARI) forprime(p=3, 800, print1(matsize(factormod((x^p+1)/(x+1), 2, 1))[1], ", ")) /* V. Raman, Oct 04 2012 */

CROSSREFS

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

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

Sequence in context: A013632 A080121 A122901 * A240545 A091591 A227796

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 03:24 EDT 2019. Contains 328211 sequences. (Running on oeis4.)