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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A014664 Order of 2 modulo the n-th prime. 35
2, 4, 3, 10, 12, 8, 18, 11, 28, 5, 36, 20, 14, 23, 52, 58, 60, 66, 35, 9, 39, 82, 11, 48, 100, 51, 106, 36, 28, 7, 130, 68, 138, 148, 15, 52, 162, 83, 172, 178, 180, 95, 96, 196, 99, 210, 37, 226, 76, 29, 119, 24, 50, 16, 131, 268, 135, 92, 70, 94, 292, 102, 155, 156, 316 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,1

COMMENTS

In other words, a(n), n >= 2, is the least k such that prime(n) divides 2^k-1.

Concerning the complexity of computing this sequence, see for example Bach And Shallit, p. 115, exercise 8.

Also A002326((p_n-1)/2). Conjecture: If p_n is not a Wieferich prime (1093, 3511, ...) then A002326(((p_n)^k-1)/2) = a(n)*(p_n)^(k-1). - Vladimir Shevelev, May 26 2008

If for distinct i,j,...,k we have a(i)=a(j)=...=a(k) then the number N = p_i*p_j*...*p_k is in A001262 and moreover A137576((N-1)/2) = N. For example, a(16)=a(37)=a(255)=52. Therefore we could take N = p_16*p_37*p_255 = 53*157*1613 = 13421773. - Vladimir Shevelev, Jun 14 2008

Also degree of the 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

Is this the same as smallest k > 1 not already in the sequence such that p = prime(n) is a factor of 2^k-1 (A270600)? If the answer is yes, is the sequence a permutation of the positive integers > 1? - Felix Fröhlich, Feb 21 2016. Answer: No, it is easy to prove that 6 is missing and obviously 11 appears twice. - N. J. A. Sloane, Feb 21 2016

Sequence A112927 gives the index at which a given number n first appears in this sequence. - M. F. Hasler, Feb 21 2016

REFERENCES

E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I.

Albert H. Beiler, "Recreations in the Theory of Numbers", Dover, 1966; Table 48, page 98, "Exponents to Which a Belongs, MOD p and MOD p^n.

John H. Conway and Richard Guy, "The Book of Numbers", Springer-Verlag, 1996; p. 166: "How does the Cycle Length Change with the Base?". [From Gary W. Adamson, Aug 22 2009]

S. K. Sehgal, Group rings, pp. 455-541 in Handbook of Algebra, Vol. 3, Elsevier, 2003; see p. 493.

LINKS

Nick Hobson, Zak Seidov, and Michael De Vlieger, Table of n, a(n) for n = 2..10001 (first 5000 terms from Nick Hobson and Zak Seidov)

Gary W. Adamson, Further comments

O. N. Karpenkov, On examples of difference operators for {0,1}-valued functions over finite sets, Funct. Anal. Other Math. 1 (2006), 175-180.

O. N. Karpenkov, On examples of difference operators for {0,1}-valued functions over finite sets, arXiv:math/0611940 [math.CO], 2006.

FORMULA

a(n) = (A000040(n)-1)/A001917(n); a(A072190(n)) = A001122(n)-1. - Benoit Cloitre, Jun 06 2004

EXAMPLE

2^2 == 1 (mod 3) and so a(2) = 2; 2^4 == 1 (mod 5) and so a(3) = 4; 2^3 == 1 (mod 7) and so a(4) = 3; 2^10 == 1 (mod 11) and so a(5) = 10; etc.

[Conway & Guy, p. 166]: Referring to the work of Euler, 1/13 in base 2 = .000100111011...; (cycle length of 12). - Gary W. Adamson, Aug 22 2009

MAPLE

with(numtheory): [ seq(order(2, ithprime(n)), n=2..60) ];

MATHEMATICA

Reap[Do[p=Prime[i]; Do[If[PowerMod[2, k, p]==1, Print[{i, k}]; Sow[{i, k}]; Goto[ni]], {k, 1, 10^6}]; Label[ni], {i, 2, 5001}]][[2, 1]] (* Zak Seidov, Jan 26 2009 *)

Table[MultiplicativeOrder[2, Prime[n]], {n, 2, 70}] (* Jean-François Alcover, Dec 10 2015 *)

PROG

(PARI) a(n)=if(n<0, 0, k=1; while((2^k-1)%prime(n)>0, k++); k)

(PARI) A014664(n)=znorder(Mod(2, prime(n))) \\ Nick Hobson (nickh(AT)qbyte.org), Jan 08 2007, edited by M. F. Hasler, Feb 21 2016

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

(GAP) P:=Filtered([1..350], IsPrime);; a:=List([2..Length(P)], n->OrderMod(2, P[n]));; Print(a); # Muniru A Asiru, Jan 29 2019

CROSSREFS

Cf. A002326 (order of 2 mod 2n+1), A036116, A036117, A062117.

Cf. also A065941, A112927.

Sequence in context: A277416 A064691 A247071 * A270600 A180871 A305423

Adjacent sequences:  A014661 A014662 A014663 * A014665 A014666 A014667

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Benoit Cloitre, Apr 11 2003

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 August 20 05:25 EDT 2019. Contains 326139 sequences. (Running on oeis4.)