A337936 -id:A337936 - cp's OEIS frontend

A337712 Irregular triangle read by rows: row n gives the complete system of cycles of the doubling sequences modulo N = 2*n+1, for n >= 0.

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

Offset: 0

Gary W. Adamson and Wolfdieter Lang, Oct 14 2020

The length of row n is A037225(n), for n >= 0.
The doubling sequence modulo N = 2*n+1, for n >= 0, has entries DS(N, s(N,i), j) = s(N,i)*2^j (mod N), with j >= 0, and certain positive odd integer seeds s(N, i), for i = 1, 2, ..., S(N) = A037226((N-1)/2), where gcd(s(N, i), N) = 1 (restricted seeds modulo N). These doubling sequences are periodic with period length P(N) = A002326((N-1)/2) (order of 2 modulo N). Only the periods (cycles) {DS(N, s(N, i), j)}_{j=0..P(N)-1}, for i = 1, 2, ..., S(N), are listed.
N = 1 (n=0) is special: one takes here the restricted residue system modulo N not as [0] but as [1]. The order of 2 modulo 1 is 1, because 2^1 == 1 (mod 1) (== 0 (mod 1)).
In order to obtain the complete system of doubling sequences one starts with seed s(N, 1) = 1, and if all numbers from the smallest positive reduced residue system modulo N (called RRS(N), given in row N of A038566) are obtained, i.e., if P(N) = #RRS(N) = phi(N) = A000010(N), then the system is complete. Otherwise the smallest missing number from RRS(N) is taken as new seed s(N, 2), etc. until the system is complete. This means that the number of seeds needed is S(N) = phi(N)/P(N) = A037226((N-1)/2)).
The irregular subtriangle where only seed s(N, 1) = 1 has been used is given in A201908. But there 0 (not 1) for N = 1 has been used.
From Gary W. Adamson and Wolfdieter Lang, Dec 15 2020: (Start)
The cycles in row n, for N = 2*n + 1, of period length P(N) = A002326((N-1)/2) give the periods of the iterated doubling function D(x) = frac(2*x) with seeds x = s(N, i)/N, for i = 1, 2, ..., S(N) = A037226((N-1)/2), after multiplication with N. This is the doubling function used in the Devaney reference, pp. 24-25, 27, 125. 132, 171,289.
Each cycle in row n can also be used to find from the base 2 version of its first entry (the seed s = s(N, i)) divided by N the other entries by repeated application of a cyclic left shift by one step (called sigma operation) to the period of the base 2 expression of s/N. E.g., n = 7, N = 15, P(N) = 4, s = 1: (1/15){10->2} = .repeat(0001), then (.repeat(0010)){2->10} = 2/10, (.repeat(0100)){2->10} = 4/10 and (.repeat(1000)){2->10} = 8/15. Similarly for s = 7: from (7/15)_{10->2} = .repeat(0111) one obtains by repeated sigma operations 14/15, 13/15 and 11/15. The proof uses the elementary formulas for the conversion from base 10 to base 2, and the reverse one, from base 2 to base 10. See also a comment on the period length P(N) given in A002326. (End)

			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 18 19 20 21 22 ...
0,  1:    1
1,  3:    1 2
2,  5:    1 2 4 3
3,  7:    1 2 4|3  6  5
4,  9:    1 2 4 8  7  5
5,  11:   1 2 4 8  5 10  9  7  3  6
6,  13:   1 2 4 8  3  6 12 11  9  5 10  7
7,  15:   1 2 4 8| 7 14 13 11
8,  17:   1 2 4 8 16 15 13  9| 7 14 11  5 10  3  6 12
9,  19:   1 2 4 8 16 13  7 14  9 18 17 15 11  3  6 12 5 10
10, 21:   1 2 4 8 16 11| 5 10 20 19 17 13
11, 23:   1 2 4 8 16  9 18 13  3  6 12| 5 10 20 17 11 22 21 19 15  7 14
12, 25:   1 2 4 8 16  7 14  3  6 12 24 23 21 17  9 18 11 22 19 13
13, 27:   1 2 4 8 16  5 10 20 13 26 25 23 19 11 22 17  7 14
...
n = 14, N = 29:  1 2 4 8 16  3  6 12 24 19  9 18  7 14 28 27 25 21 13 26 23 17  5 10 20 11 22 15,
n = 15, N = 31: 1 2 4 8 16|3 6 12 24 17|5 10 20 9 18|7 14 28 25 19|11 22 13 26 21|15 30 29 27 23.

Robert L. Devaney, A First Course in Chaotic Dynamical Systems, Addison-Wesley., 1992. pp. 24-25, 27, 125, 132, 171, 289. Second edition 2020.

Michael De Vlieger, Table of n, a(n) for n = 0..11921 (rows 0 <= n <= 120, flattened)

Cf. A000010, A002326, A037225, A037226, A201908, A038566, A334430 (modified doubling), A337936 (tripling), A339046 (quadrupling).

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

T(n, k) gives the k-th entry in the complete doubling system modulo N = 2*n+1, for n >= 0, with the S(N) = A037226((N-1)/2) cycles of length A002326((N-1)/2) written in row n. See the comment above for DS(N,s(N,i)), i = 1, 2, ..., S(N).

A337937 a(n) = Euler totient function phi = A000010 evaluated at N(n) = floor((3*n-1)/2) = A001651(n), for n >= 1.

Original entry on oeis.org

1, 1, 2, 4, 6, 4, 4, 10, 12, 6, 8, 16, 18, 8, 10, 22, 20, 12, 12, 28, 30, 16, 16, 24, 36, 18, 16, 40, 42, 20, 22, 46, 42, 20, 24, 52, 40, 24, 28, 58, 60, 30, 32, 48, 66, 32, 24, 70, 72, 36, 36, 60, 78, 32, 40, 82, 64, 42, 40, 88

Offset: 1

Wolfdieter Lang, Oct 22 2020

This sequence gives the row length of the irregular triangle A337936 (complete system of tripling sequences modulo N(n)).

			The pairs [n, N(n)], n >= 1, begin:
[1, 1], [2, 2], [3, 4], [4, 5], [5, 7], [6, 8], [7, 10], [8, 11], [9, 13], [10, 14], [11, 16], [12, 17], [13, 19], [14, 20], [15, 22], [16, 23], [17, 25], [18, 26], [19, 28], [20, 29], ...

Amiram Eldar, Table of n, a(n) for n = 1..10000
Lv Chuan, On the Mean Value of an Arithmetical Function, in Zhang Wenpeng (ed.), Research on Smarandache Problems in Number Theory (collected papers), 2004, pp. 89-92.

Cf. A000010, A001651, A337936.

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

a(n) = eulerphi((3*n-1)\2); \\ Michel Marcus, Oct 22 2020

a(n) = A000010(A001651(n)) = phi(floor((3*n-1)/2)), for n >= 1.

a(n) ~ (9/(4*Pi^2))*n^2 + O(n^(3/2+eps)) (Lv Chuan, 2004). - Amiram Eldar, Aug 02 2022

A339046 Irregular triangle read by rows: row n gives the complete quadrupling system modulo N = 2*n + 1, for n >= 0.

Original entry on oeis.org

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

Offset: 0

Wolfdieter Lang, Dec 13 2020

The length of row n is given by phi(2*n + 1), with phi = A000010, for n >= 0.
The quadrupling sequence modulo N = 2*n + 1, for n >= 0, has entries QS(N, s(N,i), j) = s(N,i)*4^j (mod N), with j >= 0, and certain positive integer seeds s(N, i), for i = 1, 2, ..., S(N) = A339049((N-1)/2), where gcd(s(N, i), N) = 1 (restricted seeds modulo N). These quadrupling sequences are periodic with period length P(N) = A053447((N-1)/2) (order of 4 modulo N). Only the periods (cycles) QS(N, s(N,i)) = {QS(N, s(N, i), j)}_{j=0..P(N)-1}, for i = 1, 2, ..., S(N), are listed.
N = 1 (n = 0) is special: one takes here the restricted residue system modulo N not as [0] but as [1]. The order of 4 modulo 1 is 1, because 4^1 == 1 (mod 1) (== 0 (mod 1)).
In order to obtain the complete system of quadrupling sequences one starts with seed s(N, 1) = 1, and if all numbers from the smallest positive reduced residue system modulo N (called RRS(N), given in row N of A038566) are obtained, i.e., if P(N) = #RRS(N) = phi(N) = A000010(N), then the system is complete. Otherwise the smallest missing number from RRS(N) is taken as new seed s(N, 2), etc. until the system is complete. This means that the number of seeds needed is S(N) given above.
This entry generalizes A337712, given together with Gary W. Adamson. See also A337936.

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

Cf. A000010, A053447, A337712 (doubling), A337936 (tripling), A339049.

T(n, k) gives the k-th entry in the complete quadrupling system modulo N = 2*n + 1, for n >= 0, with the S(N) = A339049((N-1)/2) cycles of length A053447((N-1)/2) written in row n. See the comment above for QS(N,s(N,i)), i = 1, 2, ..., S(N).

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

A337712 Irregular triangle read by rows: row n gives the complete system of cycles of the doubling sequences modulo N = 2*n+1, for n >= 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A337937 a(n) = Euler totient function phi = A000010 evaluated at N(n) = floor((3*n-1)/2) = A001651(n), for n >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A339046 Irregular triangle read by rows: row n gives the complete quadrupling system modulo N = 2*n + 1, for n >= 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula