A053446 -id:A053446 - cp's OEIS frontend

A293445 A multiplicative encoding (base-2 compressed) for the exponents of 3 obtained when using Shevelev's algorithm for computing A053446.

2, 2, 3, 12, 36, 3, 12, 24, 6, 48, 12, 20736, 82944, 12, 18, 864, 248832, 6, 20, 19906560, 59719680, 80, 8640, 720, 25920, 34560, 5, 80, 103195607040, 240, 480, 622080, 137594142720, 138240, 20, 59440669655040, 138240, 20, 14929920, 29859840, 240, 59719680, 8640, 720, 414720, 8640, 540, 447897600, 960, 46080, 34560, 59719680, 295814814232058265600, 5, 80

Offset: 1

Antti Karttunen, Oct 09 2017

nonn

			A001651(5) = 7 as 7 is the fifth number not divisible by 3. According to the algorithm described in the comment of A053446 we have in the form of a "finite continued fraction"
    1 + 14
    ------ + 7
       3^1
    ---------- + 14
          3^1
    ----------------- + 7
            3^2
    ---------------------- = 1
               3^2
Cumulatively multiplying (with A019565) together the prime-numbers corresponding to 1-bits in the binary expansions of the exponents of 3 in the denominators (that are 1, 1, 2, 2, in binary 1, 1, 10, 10, with 1's in bit-positions 0 and 1), yields prime(0+1) * prime(0+1) * prime(1+1) * prime(1+1) = 2^2 * 3^2 = 36, thus a(5) = 36.
(Adapted from _Vladimir Shevelev_'s explanation in A053446.)
Another example: A001651(19) = 28 as 28 is the 19th number not divisible by 3. (1 + 28) is not a multiple of 3, so we start with (1 + 2*28) = 1+56 = 57 and proceed as:
    1 + 56
    ------ + 56                     [that is, (57/3) + 56 = 75]
       3^1
    ---------- + 56                 [that is, (75/3) + 56 = 81]
          3^1
    -----------------  = 1          [that is, (81/81) = 1]
            3^4
So we obtained exponents 1, 1, 4 (in binary "1", "1" and "100") where the 1-bits are in positions 0, 0 and 2. We form a product prime(0+1) * prime(0+1) * prime(2+1) = 2*2*5, thus a(19) = 20.

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

Cf. A001651, A007949, A019565, A038502, A053446, A293220.
Cf. A293446 (restricted growth transform of this sequence).
Cf. also A292265.

(define (A293445 n) (define (next_one k m) (if (zero? (modulo (+ k m) 3)) (+ k m) (+ k m m))) (let* ((u (A001651 n)) (x_init (next_one 1 u))) (let loop ((x x_init) (z (A019565 (A007949 x_init)))) (let ((r (A038502 x))) (if (= 1 r) z (let ((x_next (next_one r u))) (loop x_next (* z (A019565 (A007949 x_next))))))))))
(define (A001651 n) (let ((x (- n 1))) (if (even? x) (+ 1 (* 3 (/ x 2))) (- (* 3 (/ (+ x 1) 2)) 1))))
(define (A038500 n) (A000244 (A007949 n)))
(define (A038502 n) (/ n (A038500 n)))

A048675(a(n)) = A053446(n).

A293446 Restricted growth sequence transform of A293445, related to Shevelev's algorithm for computing A053446.

Original entry on oeis.org

1, 1, 2, 3, 4, 2, 3, 5, 6, 7, 3, 8, 9, 3, 10, 11, 12, 6, 13, 14, 15, 16, 17, 18, 19, 20, 21, 16, 22, 23, 24, 25, 26, 27, 13, 28, 27, 13, 29, 30, 23, 15, 17, 18, 31, 17, 32, 33, 34, 35, 20, 15, 36, 21, 16, 37, 17, 26, 23, 38, 13, 39, 40, 41, 42, 22, 27, 43, 44, 13, 28, 45, 46, 47, 18, 48, 49, 29, 50, 51, 52, 53, 54, 55, 56, 57, 34, 58, 35, 39, 59, 60, 61, 34

Offset: 1

Antti Karttunen, Oct 09 2017

nonn

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

Cf. A053446, A293445.

Cf. also A292266.

For all i, j: a(i) = a(j) => A053446(i) = A053446(j).

A293220 Sum of all partial fractions in the algorithm used for calculation of A053446(n).

Original entry on oeis.org

1, 1, 1, 7, 12, 1, 8, 10, 1, 30, 12, 91, 108, 8, 6, 44, 157, 1, 45, 271, 300, 73, 164, 91, 162, 234, 1, 125, 588, 122, 175, 225, 684, 368, 65, 919, 373, 45, 512, 443, 206, 630, 300, 196, 506, 213, 118, 550, 303, 510, 459, 679, 2028, 1, 208, 941, 286, 1218, 201, 2611, 62, 691, 751, 724, 1575, 1374, 540, 3367, 1004, 36

Offset: 1

Vladimir Shevelev and Antti Karttunen, Oct 08 2017

nonn

This sequence gives an additional insight (cf. A292270) into the algorithm for the calculation of A053446(m), where m=A001651(n). Let us estimate how many steps are required before (the first) 1 will appear. Note that all partial fractions (which are indeed, integers) are residues modulo A001651(n) not divisible by 3 from the interval [1, A001651(n)-1]. So, if there is no repetition, then the number of steps does not exceed n-1. Suppose then that there is a repetition before the appearance of 1. Then for a not divisible by 3 residue k from [1, A001651(n)-1], 3^m_1 == 3^m_2 == k (mod A001651(n)) such that m_2 > m_1. But then 3^(m_2-m_1) == 1 (mod A001651(n)). So, since m_2 - m_1 < m_2, it means that 1 should appear earlier than the repetition of k, which is a contradiction. So the number of steps <= n-1. For example, for n=12, A001651(12) = 17, we have exactly n-1 = 11 steps with all other not divisible by 3 residues <= 17 - 1 = 16 modulo 17 appearing before the final 1: 2, 4, 7, 8, 14, 16, 11, 5, 13, 10 , 1.

Antti Karttunen, Table of n, a(n) for n = 1..13122
Antti Karttunen, Scheme-program for computing this sequence and A053446

Cf. A001651, A053446, A292270, A293445, A293446.

Cf. A038754 (seems to give the positions of ones).

Let n = 12. According to the comment, a(12) = 2 + 4 + 7 + 8 + 14 + 16 + 11 + 5 + 13 + 10 + 1 = 91.

A165781 a(n) = (2^A002326(n)-1)/(2*n+1).

Original entry on oeis.org

1, 1, 3, 1, 7, 93, 315, 1, 15, 13797, 3, 89, 41943, 9709, 9256395, 1, 31, 117, 1857283155, 105, 25575, 381, 91, 178481, 42799, 5, 84973577874915, 19065, 4599, 4885260612740877, 18900352534538475, 1, 63, 1101298153654301589

Offset: 0

Ctibor O. Zizka, Sep 26 2009

a(n) = 1 <=> n is in A000225 <=> n = 2^k - 1 with k = 0, 1, 2, ... - M. F. Hasler, Sep 20 2017

Robert Israel, Table of n, a(n) for n = 0..1672

Cf. A002326, A053446, A000225.

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:
seq(A165781(n),n=0..60) ; # R. J. Mathar, Nov 16 2009

a[n_] := (2^MultiplicativeOrder[2, 2n+1]-1)/(2n+1);
a /@ Range[0, 40] (* Jean-François Alcover, Jun 04 2020 *)

a(n)=(2^znorder(Mod(2,n=2*n+1))-1)/n \\ M. F. Hasler, Sep 20 2017

Sign in definition and offset corrected by R. J. Mathar, Nov 16 2009

A212906 Triangle T(n,k) of orders of degree-n irreducible polynomials over GF(3) listed in ascending order.

Original entry on oeis.org

1, 2, 4, 8, 13, 26, 5, 10, 16, 20, 40, 80, 11, 22, 121, 242, 7, 14, 28, 52, 56, 91, 104, 182, 364, 728, 1093, 2186, 32, 41, 82, 160, 164, 205, 328, 410, 656, 820, 1312, 1640, 3280, 6560, 757, 1514, 9841, 19682, 44, 61, 88, 122, 244, 484, 488, 671, 968, 1342

Offset: 1

Boris Putievskiy, May 29 2012

The elements m of row n, are also solutions to the equation: multiplicative order of 3 mod m = n, with gcd(m,3) = 1, cf. A053446.

			Triangle T(n,k) begins:
1,   2;
4,   8;
13, 26;
5,  10,  16,  20, 40, 80;
11, 22, 121, 242;
7,  14,  28,  52, 56, 91, 104, 182, 364, 728;

R. Lidl and H. Niederreiter, Finite Fields, 2nd ed., Cambridge Univ. Press, 1997, Table C, pp. 555-557.
V. I. Arnol'd, Topology and statistics of formulas of arithmetics, Uspekhi Mat. Nauk, 58:4(352) (2003), 3-28

Alois P. Heinz, Rows n = 1..47, flattened (first 13 rows from Boris Putievskiy)
Eric Weisstein's World of Mathematics, Irreducible Polynomial
XIAO, Polynomial order (computes the order of an irreducible polynomial over a finite field GF(p))

Cf. A053446, A059912, A059885, A058944, A059499, A059886-A059892.
Column k=2 of A212737.
Column k=1 gives: A218356.

with(numtheory):
M:= proc(n) option remember;
      divisors(3^n-1) minus U(n-1)
    end:
U:= proc(n) option remember;
      `if`(n=0, {}, M(n) union U(n-1))
    end:
T:= n-> sort([M(n)[]])[]:
seq(T(n), n=1..15);  # Alois P. Heinz, Jun 02 2012

M[n_] := M[n] = Divisors[3^n - 1] ~Complement~ U[n - 1];
U[n_] := U[n] = If[n == 0, {}, M[n] ~Union~ U[n - 1]];
T[n_] := Sort[M[n]]; Array[T, 15] // Flatten (* Jean-François Alcover, Jun 10 2018, after Alois P. Heinz *)

T(n,k) = k-th smallest element of M(n) with M(n) = {d : d | (3^n-1)} \ (M(1) U M(2) U ... U M(i-1)) for n>1, M(1) = {1,2}.

|M(n)| = Sum_{d|n} mu(n/d)*tau(3^d-1) = A059885(n).

A059907 a(n) = |{m : multiplicative order of n mod m = 2}|.

Original entry on oeis.org

0, 1, 2, 2, 5, 2, 6, 4, 6, 3, 12, 2, 10, 6, 8, 4, 13, 2, 18, 6, 10, 4, 16, 4, 12, 9, 12, 4, 26, 2, 20, 6, 8, 12, 20, 4, 15, 6, 16, 4, 32, 2, 24, 10, 10, 6, 20, 4, 26, 9, 18, 4, 26, 6, 32, 12, 12, 4, 28, 2, 20, 10, 12, 18, 25, 4, 24, 6, 26, 4, 52, 2, 18, 10, 12, 18, 26, 4, 40, 8, 14, 5, 28

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) = |{3}| = 1, a(3) = |{4,8}| = 2, a(4) = |{5,15}| = 2, a(5) = |{3,6,8,12,24}| = 5, a(6) = |{7,35}| = 2, a(7) = |{4,8,12,16,24,48}| = 6,...

Alois P. Heinz, Table of n, a(n) for n = 1..10000

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

Row n=2 of A212957. - Alois P. Heinz, Oct 24 2012

with(numtheory):f := n->tau(n^2-1)-tau(n-1):for n from 1 to 100 do printf(`%d,`,f(n)) od:

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

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

a(n) = tau(n^2-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.

A212486 Triangle T(n,k) of orders of degree-n irreducible polynomials over GF(7) listed in ascending order.

Original entry on oeis.org

1, 2, 3, 6, 4, 8, 12, 16, 24, 48, 9, 18, 19, 38, 57, 114, 171, 342, 5, 10, 15, 20, 25, 30, 32, 40, 50, 60, 75, 80, 96, 100, 120, 150, 160, 200, 240, 300, 400, 480, 600, 800, 1200, 2400, 2801, 5602, 8403, 16806, 36, 43, 72, 76, 86, 129, 144, 152, 172, 228, 258

Offset: 1

Boris Putievskiy, Jun 02 2012

The elements m of row n, are also solutions to the equation: multiplicative order of 7 mod m = n, with gcd(m,7) = 1, cf. A053450.

			Triangle T(n,k) begins:
  1,  2,  3,  6;
  4,  8, 12, 16, 24,  48;
  9, 18, 19, 38, 57, 114, 171, 342;
  5, 10, 15, 20, 25,  30,  32,  40, 50, 60, 75, 80, 96, 100, 120, 150, 160, 200, 240, 300, 400, 480, 600, 800, 1200, 2400;
  ...

R. Lidl and H. Niederreiter, Finite Fields, 2nd ed., Cambridge Univ. Press, 1997, Table C, pp. 560-562.
V. I. Arnol'd, Topology and statistics of formulas of arithmetics, Uspekhi Mat. Nauk, 58:4(352) (2003), 3-28

Boris Putievskiy, Table of n, a(n) for n = 1..102
Eric Weisstein's World of Mathematics, Irreducible Polynomial
Gang Xiao, (computes the order of an irreducible polynomial over a finite field GF(p))

Cf. A053446, A059912, A059885, A058944, A059499, A059886-A059892.
Column k=4 of A212737.
Column k=1 gives: A218358.

with(numtheory):
M:= proc(n) option remember;
      `if`(n=1, {1, 2, 3, 6}, divisors(7^n-1) minus U(n-1))
    end:
U:= proc(n) option remember;
      `if`(n=0, {}, M(n) union U(n-1))
    end:
T:= n-> sort([M(n)[]])[]:
seq(T(n), n=1..7);

M[n_] := M[n] = If[n == 1, {1, 2, 3, 6}, Divisors[7^n - 1] ~Complement~ U[n - 1]];
U[n_] := U[n] = If[n == 0, {}, M[n] ~Union~ U[n - 1]];
T[n_] := Sort[M[n]];
Table[T[n], {n, 1, 7}] // Flatten (* Jean-François Alcover, Sep 24 2022, from Maple code *)

T(n,k) = k-th smallest element of M(n) with M(n) = {d : d | (7^n-1)} \ (M(1) U M(2) U ... U M(i-1)) for n>1, M(1) = {1,2,3,6}.

|M(n)| = Sum_{d|n} mu(n/d)*tau(7^d-1) = A059889(n).

A059911 a(n) = |{m : multiplicative order of n mod m = 6}|.

Original entry on oeis.org

0, 3, 10, 16, 37, 10, 42, 24, 58, 53, 164, 26, 68, 38, 32, 68, 169, 22, 222, 38, 42, 50, 328, 40, 180, 219, 108, 26, 334, 82, 460, 82, 92, 72, 220, 108, 449, 86, 128, 80, 192, 22, 336, 110, 222, 218, 540, 84, 778, 129, 150, 80, 270, 54, 328, 356, 132, 68, 348, 22

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) = |{9,21,63}| = 3, a(3) = |{7,14,28,52,56,91,104,182,364,728}| = 10, a(4) = |{13,35,39,45,65,91,105,117,195,273,315,455,585,819,1365,4095}| = 16,...

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

a[n_] := Total[{1, -1, -1, 1} * DivisorSigma[0, n^{6, 3, 2, 1} - 1]]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jan 25 2025*)

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

a(n) = tau(n^6-1)-tau(n^3-1)-tau(n^2-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.

A050975 Haupt-exponents of 3 modulo integers relatively prime to 3.

Original entry on oeis.org

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

Offset: 1

Eric W. Weisstein

nonn

R. J. Mathar, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Multiplicative Order

Cf. A002326, A002329, A053446.

A001651 := proc(n)
        (3*(2*n-1)-(-1)^n)/4 ;
end proc:
A050975 := proc(n)
        local gcd3 ;
        gcd3 := A001651(n+1);
        numtheory[order](3,gcd3) ;
end proc: # R. J. Mathar, Oct 21 2012

A059908 a(n) = |{m : multiplicative order of n mod m = 3}|.

Original entry on oeis.org

0, 1, 2, 4, 3, 2, 8, 2, 12, 5, 12, 2, 12, 2, 4, 20, 5, 6, 10, 2, 6, 14, 12, 2, 40, 9, 4, 6, 18, 10, 16, 6, 6, 8, 12, 12, 39, 2, 12, 8, 8, 6, 16, 6, 18, 26, 12, 6, 50, 3, 18, 8, 18, 2, 32, 12, 8, 20, 4, 6, 60, 2, 12, 26, 21, 4, 64, 10, 6, 8, 8, 6, 20, 14, 4, 12, 6, 4, 64, 2, 70, 7, 12, 6, 24

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) = |{7}| = 1, a(3) = |{13,26}| = 2, a(4) = |{7,9,21,63}| = 4, a(5) = |{31,62,124}| = 3, a(6) = |{43,215}| = 2, a(7) = |{9,18,19,38,57,114,171,342}| = 8,...

Alois P. Heinz, Table of n, a(n) for n = 1..10000

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

Row n=3 of A212957. - Alois P. Heinz, Oct 24 2012

Table[DivisorSigma[0,n^3-1]-DivisorSigma[0,n-1],{n,90}] (* Harvey P. Dale, Feb 03 2015 *)

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

a(n) = tau(n^3-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.

cp's OEIS Frontend

A293445 A multiplicative encoding (base-2 compressed) for the exponents of 3 obtained when using Shevelev's algorithm for computing A053446.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Scheme

Formula

A293446 Restricted growth sequence transform of A293445, related to Shevelev's algorithm for computing A053446.

Views

Author

Keywords

Links

Crossrefs

Formula

A293220 Sum of all partial fractions in the algorithm used for calculation of A053446(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A165781 a(n) = (2^A002326(n)-1)/(2*n+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A212906 Triangle T(n,k) of orders of degree-n irreducible polynomials over GF(3) listed in ascending order.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A059907 a(n) = |{m : multiplicative order of n mod m = 2}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A212486 Triangle T(n,k) of orders of degree-n irreducible polynomials over GF(7) listed in ascending order.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A059911 a(n) = |{m : multiplicative order of n mod m = 6}|.

Views

Author