A053446 -id:A053446 - cp's OEIS frontend

A337936 Irregular triangle read by rows: row n gives the complete system of tripling sequences modulo N = floor((3*n-1)/2), for n >= 1.

1, 1, 1, 3, 1, 3, 4, 2, 1, 3, 2, 6, 4, 5, 1, 3, 5, 7, 1, 3, 9, 7, 1, 3, 9, 5, 4, 2, 6, 7, 10, 8, 1, 3, 9, 2, 6, 5, 4, 12, 10, 7, 8, 11, 1, 3, 9, 13, 11, 5, 1, 3, 9, 11, 5, 15, 13, 7, 1, 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6, 1, 3, 9, 8, 5, 15, 7, 2, 6, 18, 16, 10, 11, 14, 4, 12, 17, 13, 1, 3, 9, 7, 11, 13, 19, 17, 1, 3, 9, 5, 15, 7, 21, 19, 13, 17

Offset: 1

Wolfdieter Lang, Oct 22 2020

The length of row n is A053446(n)*A337714(n) = phi(floor((3*n-1)/2)) = A337937(n), for n >= 1.
The tripling sequence modulo N(n), with N(n) = floor((3*n-1)/2) = A001651(n) (i.e., gcd(3, N(n)) = 1), for n >= 1, has entries TS(N, s(N,i), j) = s(N, i) 3^j (mod N), for j >= 0 and with certain positive odd integer seeds s(N, i), for i = 1, 2, ..., S(N(n)) = A337714(n), where gcd(s(N, i), N) = 1 (restricted seeds modulo N).
These tripling sequences are periodic with period length P(N(n)) = A053446(n) (order of 3 modulo N(n)). Only the periods (cycles) {TS(N, s(N, i), j)}_{j=0..P(N)-1}, for i = 1, 2, ..., S(N), are listed.
For n >= 2 the seeds start with s(N, 1) = 1 and if the first cycle does not cover all members of the restricted residue system modulo N = N(n) (RRS(N(n)) then the smallest missing member is chosen as second seed s(N, 2), etc., until all members of RRS(N(n)) have been reached. For N(1) = 1 one uses here RRS(1) = [1] (not [0]).
For the complete system of doubling sequences modulo 2*n + 1, for n >= 0, see A337712.
This entry generalizes A337712, given together with Gary W. Adamson. [added Dec 14 2020]

			The irregular triangle T(n, k) begins (cycles are separated by a vertical bar)
n,  N\ k 1 2 3  4   5  6  7  8  9 10 11 12 13 14 15 16 17 16 19 20 21 22 ...
1,  1:   1
2,  2:   1
3,  4:   1 3
4,  5:   1 3 4  2
5,  7:   1 3 2  6   4  5
6,  8:   1 3|5  7
7,  10:  1 3 9  7
8,  11:  1 3 9  5   4| 2  6  7 10  8
9,  13:  1 3 9| 2   6  5| 4 12 10| 7  8 11
10, 14:  1 3 9 13  11  5
11, 16:  1 3 9 11|  5 15 13  7
12, 17:  1 3 9 10  13  5 15 11 16 14  8  7  4 12  2  6
13, 19:  1 3 9  8   5 15  7  2  6 18 16 10 11 14  4 12 17 13
14, 20:  1 3 9  7| 11 13 19 17
15, 22:  1 3 9  5  15| 7 21 19 13 17
16, 23:  1 3 9  4  12 13 16  2  6 18  8| 5 15 22 20 14 19 11 10  7 21 17
17, 25:  1 3 9  2   6 18  4 12 11  8 24 22 16 23 19  7 21 13 14 17
18, 26:  1 3 9| 5  15 19| 7 21 11|17 25 23
19, 28:  1 3 9 27  25 19| 5 15 17 23 13 11
...
n = 20, N = 29:  1 3 9 27 23 11 4 12 7 21 5 15 16 19 28 26 20 2 6 18 25 17 22 8 24 14 13 10.
...

Cf. A001651, A053446, A337712 (doubling), A337714, A337937.

{1}~Join~Array[Block[{a = {}, k = 3, n = Floor[(3 # - 1)/2], m}, m = EulerPhi[n]; While[Length@ Flatten@ a < m, AppendTo[a, Most@ NestWhileList[Mod[3 #, n] &, If[Length@ a == 0, 1, k], UnsameQ, All]];
Set[k, SelectFirst[Complement[Range[n], Union@ Flatten@ a], GCD[#, n] == 1 &] ]]; a] &, 14, 2] // Flatten (* Michael De Vlieger, Nov 06 2020 *)

T(n, k) gives the k-th entry in the complete tripling system modulo N(n), with N(n) = floor((3*n-1)/2), for n >= 1, where the S(N(n)) = A337714(n) cycles of length P(N(n)) = A053446(n) are written in row n. See the comment above for TS(N, s(N,i), j), i = 1, 2, ..., S(N), and j = 0, 1, ..., P(N) - 1.

A059909 a(n) = |{m : multiplicative order of n mod m = 4}|.

Original entry on oeis.org

0, 2, 6, 4, 12, 4, 26, 18, 14, 6, 24, 12, 64, 8, 16, 8, 66, 20, 36, 8, 64, 24, 76, 6, 28, 12, 64, 24, 48, 12, 100, 40, 50, 48, 36, 8, 96, 40, 28, 8, 104, 12, 208, 36, 24, 36, 200, 18, 48, 36, 36, 24, 128, 8, 152, 16, 172, 24, 48, 12, 48, 36, 56, 72, 40, 8, 128, 56, 48, 40

Offset: 1

Vladeta Jovovic, Feb 08 2001

The multiplicative order of a mod m, gcd(a,m) = 1, is the smallest natural number d for which a^d = 1 (mod m).

			a(2) = |{5, 15}| = 2, a(3) = |{5, 10, 16, 20, 40, 80}| = 6, a(4) = |{17, 51, 85, 255}| = 4, a(5) = |{13, 16, 26, 39, 48, 52, 78, 104, 156, 208, 312, 624}| = 12, ...

Cf. A059907, A059908, A059910-A059911, A059499, A059885-A059892, A002326, A053446-A053452, A002329, A055205, A048691, A048785.

Table[DivisorSigma[0,n^4-1]-DivisorSigma[0,n^2-1],{n,70}] (* Harvey P. Dale, Nov 30 2011 *)

a(n) = if(n == 1, 0, numdiv(n^4-1) - numdiv(n^2-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = tau(n^4-1)-tau(n^2-1), where tau(n) = number of divisors of n A000005. More generally, if b(n, r) = |{m : multiplicative order of n mod m = r}| then b(n, r) = Sum_{d|r} mu(d)*tau(n^(r/d)-1), where mu(n) = Moebius function A008683.

A059910 a(n) = |{m : multiplicative order of n mod m = 5}|.

Original entry on oeis.org

0, 1, 4, 6, 9, 4, 4, 6, 20, 9, 8, 2, 6, 6, 12, 44, 5, 6, 18, 14, 12, 4, 4, 2, 56, 13, 20, 4, 6, 2, 40, 6, 18, 12, 12, 44, 63, 6, 28, 4, 16, 14, 8, 2, 18, 12, 28, 14, 70, 3, 42, 12, 42, 6, 24, 8, 56, 44, 60, 6, 60, 2, 4, 90, 21, 20, 24, 2, 18, 60, 88, 6, 12, 2, 28, 26, 6, 28, 8, 14, 170

Offset: 1

Vladeta Jovovic, Feb 08 2001

The multiplicative order of a mod m, gcd(a,m) = 1, is the smallest natural number d for which a^d = 1 (mod m).

Cf. A059907-A059909, A059911, A059499, A059885-A059892, A002326, A053446-A053452, A002329, A055205, A048691, A048785.

a[n_] := Subtract @@ DivisorSigma[0, {n^5-1, n-1}]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jan 25 2025 *)

a(n) = if(n == 1, 0, numdiv(n^5-1) - numdiv(n-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = tau(n^5-1)-tau(n-1), where tau(n) = number of divisors of n A000005. Generally, if b(n, r) = |{m : multiplicative order of n mod m = r}| then b(n, r) = Sum_{d|r} mu(d)*tau(n^(r/d)-1), where mu(n) = Moebius function A008683.

A053448 Multiplicative order of 5 mod m, where gcd(m, 5) = 1.

Original entry on oeis.org

1, 1, 2, 1, 2, 6, 2, 6, 5, 2, 4, 6, 4, 16, 6, 9, 6, 5, 22, 2, 4, 18, 6, 14, 3, 8, 10, 16, 6, 36, 9, 4, 20, 6, 42, 5, 22, 46, 4, 42, 16, 4, 52, 18, 6, 18, 14, 29, 30, 3, 6, 16, 10, 22, 16, 22, 5, 6, 72, 36, 9, 30, 4, 39, 54, 20, 82, 6, 42, 14, 10, 44, 12, 22, 6, 46, 8, 96, 42, 30, 25, 16

Offset: 1

David W. Wilson

nonn

Essentially the same as A050977. - R. J. Mathar, Oct 21 2012

Cf. A047201, A002326 (order of 2), A053446 (order of 3), A053447 (order of 4).

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

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

a(n) = multiplicative order of 5 modulo floor((5*n-1)/4), for n >= 1. This modulus is A047201(n). - Wolfdieter Lang, Sep 30 2020

A054711 Multiplicative order of 11 mod n, where gcd(n, 11) = 1.

Original entry on oeis.org

1, 1, 2, 2, 1, 2, 3, 2, 6, 1, 2, 12, 3, 2, 4, 16, 6, 3, 2, 6, 22, 2, 5, 12, 18, 6, 28, 2, 30, 8, 16, 3, 6, 6, 3, 12, 2, 40, 6, 7, 6, 22, 46, 4, 21, 5, 16, 12, 26, 18, 6, 6, 28, 58, 2, 4, 30, 6, 16, 12, 66, 16, 22, 3, 70, 6, 72, 6, 10, 6, 12, 39, 4, 54, 40, 41

Offset: 1

Henry Bottomley, Apr 20 2000

The original version "Number of powers of 11 modulo n" that was similar to A054703-A054717 is now in A351524. - Georg Fischer, Feb 13 2022

Cf. A053446 (of 3 mod n), A053448 (5), A053449 (6), A053450 (7), A053452 (9).

Cf. A351524.

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

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

Corrected by Michel Marcus, Feb 11 2015

A165783 a(n) = A002326(n-1) + A000120(A165781(n-1)).

Original entry on oeis.org

2, 3, 6, 4, 9, 15, 18, 5, 12, 27, 8, 15, 30, 27, 42, 6, 15, 17, 54, 16, 30, 21, 17, 32, 31, 10, 78, 28, 27, 87, 90, 7, 18, 99, 33, 49, 12, 29, 45, 56, 81, 123, 10, 39, 15, 16, 13, 50, 72, 45, 150, 74, 16, 159, 54, 50, 42, 63, 15, 33, 165, 26, 150, 8, 21, 195, 26, 53, 102, 207

Offset: 1

Ctibor O. Zizka, Sep 26 2009

Given a shift register : r(k)=r(k-1)+ X if r(k-1) is not divisible Y, else r(k)=r(k-1)/Y.
Gcd(r(0), X))=1, Gcd(X, Y)=1.
Then the length of the period orbit of such a register is L + digitsum (r(L)*(Y^L-1)/ X). Digitsum(z)in base X.
r(L) a point from period orbit, L minimal possible exponent such that (Y^L-1)/X)is a positive integer.
Number of period orbits is the order of the cyclic group connected to the register.
a(n) is the period length for Y=2, X=2*n-1, r(L)=1. [Ctibor O. Zizka, Nov 24 2009]

			n=1, a(1)=1 + digitsum(1)= 2.
n=2, a(2)=2 + digitsum(1)=3.
n=3, a(3)= 4 + digitsum(3) = 6.
n=4, a(4)= 3 + digitsum(1)=4.
n=5, a(5)= 6 + digitsum(7)=9. [_Ctibor O. Zizka_, Nov 24 2009]

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A002326, A053446.

A002326 := proc(n) if n = 0 then 1; else numtheory[order](2,2*n+1) ; end if ; end proc:
A165781 := proc(n) (2^A002326(n)-1)/(2*n+1) ; end proc:
read("transforms") ; A165783 := proc(n) A002326(n-1)+wt(A165781(n-1) ) ; end proc:
seq(A165783(n),n=1..80) ; # R. J. Mathar, Nov 26 2009

Table[(b = MultiplicativeOrder[2, 2 n - 1]) + Plus @@ IntegerDigits[(2^b - 1)/(2 n - 1), 2], {n, 1, 70}] (* Ivan Neretin, May 09 2015 *)

hamming(n)=my(v=binary(n));sum(i=1,#v,v[i])
a(n)=my(x=2*n+1,m=znorder(Mod(2,x)));m+hamming((1<

a(n) = L + digitsum((2^L -1)/(2*n-1)). Digitsum(z)in base 2. [Ctibor O. Zizka, Nov 24 2009]

Program and extension by Charles R Greathouse IV, Nov 24 2009

Definition corrected and comments merged by R. J. Mathar, Nov 26 2009

A297363 Numbers k such that (3^ord(3, k) - 1)/k is prime, where ord(3, k) is the multiplicative order of 3 (mod k).

Original entry on oeis.org

1, 4, 13, 16, 22, 40, 46, 56, 94, 104, 121, 160, 364, 526, 862, 968, 1093, 1312, 1514, 3146, 3194, 3280, 3742, 4376, 5368, 7280, 7702, 8744, 9841, 28418, 29524, 40880, 69022, 75920, 88573, 106288, 157394

Offset: 1

Amiram Eldar, Dec 29 2017

The corresponding primes are 2, 2, 2, 5, 11, 2, 3851, 13, 1001523179, 7, 2, 41, 2, 605199588591144003100881306574406851660288427740394885828171, ...

			46 is in the sequence since ord(3, 46) = 11 and (3^11 - 1)/46 = 3851 is prime.

Cf. A050975, A053446.

aQ[n_] := PrimeQ[(3^MultiplicativeOrder[3, n] - 1)/n]; Select[ Range[10000], aQ ]

isok(n) = (gcd(n,3) == 1) && isprime((3^znorder(Mod(3, n)) - 1)/n); \\ Michel Marcus, Dec 30 2017

A337714 Euler totient function phi(N) divided by the multiplicative order of 3 modulo N, with N = N(n) = floor((3*n-1)/2), for n >= 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 4, 1, 2, 1, 1, 2, 2, 2, 1, 4, 2, 1, 1, 2, 1, 2, 2, 1, 4, 5, 1, 2, 2, 2, 1, 1, 4, 1, 2, 4, 1, 2, 6, 1, 2, 4, 3, 2, 2, 2, 6, 2, 2, 2, 1, 8, 5, 2, 4, 1, 4, 1, 12, 2, 2, 2, 2, 1, 2, 1, 3, 8, 1, 2, 4, 2, 4, 1

Offset: 1

Wolfdieter Lang, Oct 22 2020

For the multiplicative order of 3 modulo N = N(n), with N(n) = floor((3*n-1)/2) = A001651(n), see A053446(n), for n >= 1.
For n >= 2 this sequence gives also the number of seeds s(N(n), i) needed to cover all numbers of the smallest positive restricted residue system (called RRS(N(n))) from the cycles obtained from s(N(n), i)*3^k (mod(N(n)), for k = 0..(P(N(n))-1), and certain s(N(n), i) chosen from RRS(N(n)). See A337936 for the choice of these seeds s(N, i). The cycles have period length P(N(n)) = A053446(n). For n = 1, N = 1, RRS(1) = [1] (not [0])
For the complete system of tripling sequences modulo N(n), for n >= 1, see A337936.

			The pairs [N(n),a(n)] begin, for n >= 1:
[1, 1], [2, 1], [4, 1], [5, 1], [7, 1], [8, 2], [10, 1], [11, 2], [13, 4], [14, 1], [16, 2], [17, 1], [19, 1], [20, 2], [22, 2], [23, 2], [25, 1], [26, 4], [28, 2], [29, 1], [31, 1], [32, 2], [34, 1], [35, 2], [37, 2], [38, 1], [40, 4], [41, 5], [43, 1], [44, 2], ...
The pairs [N(n)= floor((3*n-1)/2), P(N(n)) = A053446(n)] begin, for n >= 1:
[1, 1], [2, 1], [4, 2], [5, 4], [7, 6], [8, 2], [10, 4], [11, 5], [13, 3], [14, 6], [16, 4], [17, 16], [19, 18], [20, 4], [22, 5], [23, 11], [25, 20], [26, 3], [28, 6], [29, 28], [31, 30], [32, 8], [34, 16], [35, 12], [37, 18], [38, 18], [40, 4], [41, 8], [43, 42], [44, 10], ...

Cf. A000010, A001651, A053446, A337936.

a[n_] := EulerPhi[(f = Floor[(3*n - 1)/2])] / MultiplicativeOrder[3, f]; Array[a, 100] (* Amiram Eldar, Oct 22 2020 *)

a(n) = my(N=(3*n-1)\2); eulerphi(N)/znorder(Mod(3, N)); \\ Michel Marcus, Oct 22 2020

Bisection: a(2*k+1) = phi(3*k+1)/A053446(2*k+1), a(2*k+2) = phi(3*k+2)/A053446(2*k+2), for k >= 0, where phi = A000010.

cp's OEIS Frontend

A337936 Irregular triangle read by rows: row n gives the complete system of tripling sequences modulo N = floor((3*n-1)/2), for n >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A059909 a(n) = |{m : multiplicative order of n mod m = 4}|.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A059910 a(n) = |{m : multiplicative order of n mod m = 5}|.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A053448 Multiplicative order of 5 mod m, where gcd(m, 5) = 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A054711 Multiplicative order of 11 mod n, where gcd(n, 11) = 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions

A165783 a(n) = A002326(n-1) + A000120(A165781(n-1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A297363 Numbers k such that (3^ord(3, k) - 1)/k is prime, where ord(3, k) is the multiplicative order of 3 (mod k).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A337714 Euler totient function phi(N) divided by the multiplicative order of 3 modulo N, with N = N(n) = floor((3*n-1)/2), for n >= 1.

Views

Author

Keywords