A053446 Multiplicative order of 3 mod m, where gcd(m, 3) = 1.

1, 1, 2, 4, 6, 2, 4, 5, 3, 6, 4, 16, 18, 4, 5, 11, 20, 3, 6, 28, 30, 8, 16, 12, 18, 18, 4, 8, 42, 10, 11, 23, 42, 20, 6, 52, 20, 6, 28, 29, 10, 30, 16, 12, 22, 16, 12, 35, 12, 18, 18, 30, 78, 4, 8, 41, 16, 42, 10, 88, 6, 22, 23, 36, 48, 42, 20, 100, 34, 6, 52, 53, 27, 20, 12, 112, 44

Offset: 1

Author

David W. Wilson

Keywords

• nonn

Comments

Essentially the same as A050975. - R. J. Mathar, Oct 13 2008

Let k, m be any positive numbers not divisible by 3. Let k <+> m denote that of the two numbers k + m, k + 2*m which is divisible by 3. Finally, for a number t divisible by 3, let t* = t/3^s where s is the 3-adic order of t. Let u = u(n) be the n-th number which is not divisible by 3. Consider the following algorithm of the calculating a(n), similar to the algorithm in A002326: Compute successively r_1 = (1 <+> u)*, r_2 = (r_1 <+> u)*, ..., r_h = (r_(h-1) <+> u)* and finish as soon as r_h = 1. Then a(n) = s(1 <+> u) + s(r_1 <+> u) + ... + s(r_(h-1) <+> u). Note that by a similar algorithm one can compute an arbitrary multiplicative order of a mod b, where gcd(a, b) = 1. - Vladimir Shevelev, Oct 06 2017

Examples

			From _Vladimir Shevelev_, Oct 06 2017: (Start)
7 is the fifth number not divisible by 3. According to the algorithm in the comment we have in the form of a "finite continued fraction"
    1 + 14
    ------ + 7
       3
    ---------- + 14
          3
    ----------------- + 7
            3^2
    ---------------------- = 1
               3^2
Summing the exponents of 3 in the denominators, we obtain a(5) = 1 + 1 + 2 + 2 = 6. (End)
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A001651, A002326, A050975.

Programs

GAP

List(Filtered([1..130],n->Gcd(n,3)=1),n->OrderMod(3,n)); # Muniru A Asiru, Feb 26 2019

Mathematica

MultiplicativeOrder[3, #] & /@ Select[ Range@ 115, GCD[3, #] == 1 &] (* Robert G. Wilson v, Apr 05 2011 *)

PARI

lista(nn) = {for (n=1, nn, if (gcd(n,3) == 1, print1(znorder(Mod(3, n)), ", ")););} \\ Michel Marcus, Feb 06 2015

Sage

[Mod(3,n).multiplicative_order() for n in (1..115) if gcd(n,3) == 1] # Peter Luschny, Oct 07 2017

Formula

a(n) = multiplicative order of 3 modulo floor((3*n-1)/2) = A001651(n), for n >= 1. - Wolfdieter Lang, Sep 28 2020