%I #128 May 13 2024 09:16:00
%S 2,4,3,10,12,8,18,11,28,5,36,20,14,23,52,58,60,66,35,9,39,82,11,48,
%T 100,51,106,36,28,7,130,68,138,148,15,52,162,83,172,178,180,95,96,196,
%U 99,210,37,226,76,29,119,24,50,16,131,268,135,92,70,94,292,102,155,156,316
%N Order of 2 modulo the n-th prime.
%C In other words, a(n), n >= 2, is the least k such that prime(n) divides 2^k-1.
%C Concerning the complexity of computing this sequence, see for example Bach and Shallit, p. 115, exercise 8.
%C 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
%C 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
%C 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
%C Is this the same as the 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
%C pi(A112927(m)) is the index at which a given number m first appears in this sequence. - _M. F. Hasler_, Feb 21 2016
%D E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I.
%D 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.
%D 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]
%D S. K. Sehgal, Group rings, pp. 455-541 in Handbook of Algebra, Vol. 3, Elsevier, 2003; see p. 493.
%H Michael De Vlieger, <a href="/A014664/b014664.txt">Table of n, a(n) for n = 2..10001</a> (terms 2..1001 from Nick Hobson, terms 1002..5001 from Zak Seidov)
%H Gary W. Adamson, <a href="/A014664/a014664.txt">Further comments</a>.
%H O. N. Karpenkov, <a href="http://dx.doi.org/10.1007/s11853-007-0010-z">On examples of difference operators for {0,1}-valued functions over finite sets</a>, Funct. Anal. Other Math. 1 (2006), 175-180.
%H O. N. Karpenkov, <a href="http://arxiv.org/abs/math/0611940">On examples of difference operators for {0,1}-valued functions over finite sets</a>, arXiv:math/0611940 [math.CO], 2006.
%F a(n) = (A000040(n)-1)/A001917(n); a(A072190(n)) = A001122(n) - 1. - _Benoit Cloitre_, Jun 06 2004
%e 2^2 == 1 (mod 3) and so a(2) = 2;
%e 2^4 == 1 (mod 5) and so a(3) = 4;
%e 2^3 == 1 (mod 7) and so a(4) = 3;
%e 2^10 == 1 (mod 11) and so a(5) = 10; etc.
%e [Conway & Guy, p. 166]: Referring to the work of Euler, 1/13 in base 2 = 0.000100111011...; (cycle length of 12). - _Gary W. Adamson_, Aug 22 2009
%p with(numtheory): [ seq(order(2,ithprime(n)), n=2..60) ];
%t 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 *)
%t Table[MultiplicativeOrder[2, Prime[n]], {n, 2, 70}] (* _Jean-François Alcover_, Dec 10 2015 *)
%o (PARI) a(n)=if(n<0,0,k=1;while((2^k-1)%prime(n)>0,k++);k)
%o (PARI) A014664(n)=znorder(Mod(2, prime(n))) \\ _Nick Hobson_, Jan 08 2007, edited by _M. F. Hasler_, Feb 21 2016
%o (PARI) forprime(p=3, 800, print(factormod((x^p+1)/(x+1), 2, 1)[1, 1])) \\ _V. Raman_, Oct 04 2012
%o (GAP) P:=Filtered([1..350],IsPrime);; a:=List([2..Length(P)],n->OrderMod(2,P[n]));; Print(a); # _Muniru A Asiru_, Jan 29 2019
%o (Python)
%o from sympy import n_order, prime
%o def A014664(n): return n_order(2,prime(n)) # _Chai Wah Wu_, Nov 09 2023
%Y Cf. A002326 (order of 2 mod 2n+1), A001122 (full reptend primes in base 2), A065941, A112927.
%Y In other bases: A062117, A082654, A211241, A211242, A211243, A211244, A211245, A002371.
%K nonn,easy
%O 2,1
%A _N. J. A. Sloane_
%E More terms from _Benoit Cloitre_, Apr 11 2003