

A014664


Order of 2 modulo the nth 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^k1.
Concerning the complexity of computing this sequence, see for example Bach And Shallit, p. 115, exercise 8.
Also A002326((p_n1)/2). Conjecture: If p_n is not a Wieferich prime (1093, 3511, ...) then A002326(((p_n)^k1)/2) = a(n)*(p_n)^(k1).  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((N1)/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 nth 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^k1 (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", SpringerVerlag, 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. 455541 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), 175180.
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}] (* JeanFrançois Alcover, Dec 10 2015 *)


PROG

(PARI) a(n)=if(n<0, 0, k=1; while((2^k1)%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



