login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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)

REFERENCES

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

LINKS

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

FORMULA

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).

EXAMPLE

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.

MATHEMATICA

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 *)

CROSSREFS

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

Sequence in context: A319563 A201912 A201908 * A256184 A120855 A193737

Adjacent sequences:  A337709 A337710 A337711 * A337713 A337714 A337715

KEYWORD

nonn,tabf,easy

AUTHOR

Gary W. Adamson and Wolfdieter Lang, Oct 14 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 23 14:40 EDT 2021. Contains 347618 sequences. (Running on oeis4.)