A334430 Irregular triangle read by rows. Row n gives the cycles of positive integers of the complete modified doubling sequence MDS(b) for b = 2*n + 1, for n >= 1.

1, 2, 1, 2, 3, 1, 2, 4, 1, 2, 4, 3, 5, 1, 2, 4, 5, 3, 6, 1, 2, 4, 7, 1, 2, 4, 8, 1, 6, 5, 7, 3, 2, 4, 8, 3, 6, 7, 5, 9, 1, 2, 4, 8, 5, 10, 1, 2, 4, 8, 7, 9, 5, 10, 3, 6, 11, 1, 2, 4, 8, 9, 7, 11, 3, 6, 12, 1, 2, 4, 8, 11, 5, 10, 7, 13, 1, 2, 4, 8, 13, 3, 6, 12, 5, 10, 9, 11, 7, 14, 1

Offset: 1

Author

Gary W. Adamson and Wolfdieter Lang, Aug 11 2020

Keywords

• nonn
• tabf

Comments

The length of row n is phi(2*n+1)/2 with phi = A000010, for n > = 1.

There are c(2*n+1) = A135303(n) cycles in row n, and the length of each cycle is k(2*n+1) = A003558(n). c(2*n+1)*k(2*n+1) = phi(n)/2 (in Hilton and Pedersen [HP], the coach theorem, p. 262).

In the construction of the cycles a modified modular equivalence relation, called mod* b, for b = 2*n + 1, with n >= 1, proposed in the Brändli and Beyne [BB] paper, is used. It is defined as mod*(a, b) = mod(a, b) (with values in I(b) = {0, 1, ..., b-1}) for integer numbers a, if mod(a, b) <= (b-1)/2 and mod*(a, b) = mod(-a, b) if mod(a, b) > (b-1)/2. The equivalence relation k ~ m if mod*(k, b) = mod*(m,b) is multiplicative (not additive).

The MDS(b) cycles are obtained from the doubling sequence {a(b,i)*2^j}A003558(n)%20for%20each%20odd%20a(b,%20i)%20with%20gcd(a(b,%20i),%20b)%20=%201%20and%20a(b,%20i)%20%3C=%20(b-1)/2.%20The%20first%20cycle%20is%20Cy*(b,1)%20obtained%20for%20a(b,%201)%20=%201.%20If%20not%20all%20odd%20numbers%20relatively%20prime%20to%20b%20and%20%3C=%20(b-1)/2%20are%20present,%20the%20next%20cycle%20Cy*(b,2)%20uses%20the%20smallest%20missing%20reduced%20odd%20number,%20etc.%20The%20number%20of%20such%20inputs%20a(b,%20i),%20hence%20cycles,%20is%20c*(b),%20coinciding%20with%20c(2*n+1)%20=%20A135303(n),%20and%20all%20odd%20and%20even%20positive%20numbers%20with%20gcd(m,%20b)%20=%201%20and%20m%20%3C=%20(b-1)/2%20appear%20just%20once%20in%20the%20complete%20cycle%20system%20for%20b,%20called%20Cy*(b)%20=%20%7BCy*(b,i)%7D">{j=1..P(b)} evaluated mod*b: Cy*(b,i)_j = mod*(a(b,i)*2^j, b), with certain inputs (seeds) a(b, i). P(b), the length of the period independent, coincides with k(2*n+1) = A003558(n) for each odd a(b, i) with gcd(a(b, i), b) = 1 and a(b, i) <= (b-1)/2. The first cycle is Cy*(b,1) obtained for a(b, 1) = 1. If not all odd numbers relatively prime to b and <= (b-1)/2 are present, the next cycle Cy*(b,2) uses the smallest missing reduced odd number, etc. The number of such inputs a(b, i), hence cycles, is c*(b), coinciding with c(2*n+1) = A135303(n), and all odd and even positive numbers with gcd(m, b) = 1 and m <= (b-1)/2 appear just once in the complete cycle system for b, called Cy*(b) = {Cy*(b,i)}{i=1..c(b)}.

Such modified doubling sequences have been considered in the Kappraff-Adamson paper using iterations of x^2 - 2, and also in comments and examples by Adamson like the Aug 25 2019 comment in A065941, where it is named "r-t table" (for roots trajectory).

The recurrence relation for the cycle Cy*(b,i) with elements {c_j(b,i)} is

c(b, i)j = mod*(2*c(b, i){j-1}, b), for j = 2, 3, ..., P(b), and input c(b, i)1, for i = 1, 2, ..., c(b). This input is here not a(b, i) but 2*a(b, i) if a(b, i) <= floor((b-1)/4) and b - 2*a(b, i) otherwise. Observe that c(b, i){P(b)} = a(b, i).

The complete cycle system Cy*(b) is equivalent to the complete coach system of Hilton and Pedersen [HP], with the coach number c(b) = c*(b) and k(b) = P(b). The odd numbers of each cycle Cy*(b,i), read backwards (anticyclically), give the first row of the coach; and the number of steps to go from one odd number to the next odd number, ending with the starting number, gives the second row of the coach with sum k(b). See [HP] pp. 102-103 for the modified coach system and the extended list, eq. (7. 12), in the proof of their quasi-order theorem.

The complete cycle system of Schick (unsigned) and Brändli-Beyne SBB(b) is also equivalent to Cy*(b). Each cycle Cy*(b,i) gives the SBB(b,i) cycle (q(b, i)j) with elements obtained from q(b, i)_j = b - 2*c(b,i){P(b)-1+j}, for j = 0, 1, 2, ..., P(b)-1. Cyclicity is used: c(b,i){P(b)+k} = c(b,i){k}.

For more details and proofs see the arxiv paper by W. Lang.

Examples

			The irregular triangle a(n,m) begins (cycles are enclosed by brackets; blanks are used to fit the index m):
n,   b \ m 1 2 3  4  5   6  7  8  9 10  11 12 13 14 15 16 17 18 19 20 ...
1,   3:   (1)
2,   5:   (2 1)
3,   7:   (2 3 1)
4,   9:   (2 4 1)
5,  11:   (2 4 3  5  1)
6,  13:   (2 4 5  3  6   1)
7,  15:   (2 4 7  1)
8,  17:   (2 4 8  1)(6   5  7  3)
9,  19:   (2 4 8  3  6   7  5  9  1)
10, 21:   (2 4 8  5 10   1)
11, 23:   (2 4 8  7  9   5 10  3  6 11  1)
12, 25:   (2 4 8  9  7  11  3  6 12  1)
13, 27:   (2 4 8 11  5  10  7 13  1)
14, 29:   (2 4 8 13  3   6 12  5 10  9  11  7 14  1)
15, 31:   (2 4 8 15  1) (6 12  7 14  3)(10 11  9 13  5)
16, 33:   (2 4 8 16  1)(10 13  7 14  5)
17, 35:   (2 4 8 16  3   6 12 11 13  9  17  1)
18, 37:   (2 4 8 16  5  10 17  3  6 12  13 11 15  7 14  9 18  1)
19, 39:   (2 4 8 16  7  14 11 17  5 10  19  1)
20, 41:   (2 4 8 16  9  18  5 10 20  1) (6 12 17  7 14 13 15 11 19  3)
...
-------------------------------------------------------------------------
n = 8, b = 17: (2, 4, 8, 16) = (2, 4, 8, 16) (mod(17)) = (2, 4, 8, 1) (mod*(17), and the first odd (reduced) number missing is 3, with cycle (3*2, 3*4, 3*8, 3*16) = (6, 12, 7, 14) (mod(17)) = (6, 5, 7, 3) (mod*(17).
From this the complete coach system Sigma(17) becomes {[[1], [4]]; [[3 7 5], [1 1 2]]]}.
The complete SBB(17) cycle systen is (unsigned, offset 0) {(1 15 13 9); (3 11 5 7)}, from  17 - 2*8 = 1, 17 - 2*1 = 15, 17 - 2*2 = 13,  17 - 2*4 = 9, and from  17 - 2*7 = 3, 17 - 2*3 = 11, 17 - 2*6 = 5, 17 - 2*5 = 7.
		

References

• Peter Hilton and Jean Pederson, A Mathematical Tapestry, 2010 (3rd printing 2012), Cambridge University Press, pp. 102-103, 260-264.
• Carl Schick, Trigonometrie und unterhaltsame Zahlentheorie, Bokos Druck, Zürich, 2003 (ISBN 3-9522917-0-6). Tables 3.1 to 3.10, for odd p = 3 to 113 (with some gaps), pp. 158-166.

Links

• Gerold Brändli and Tim Beyne, Modified Congruence Modulo n with Half the Amount of Residues, arXiv:1504.02757 [math.NT], 2015-2016.
• Jay Kappraff and Gary W. Adamson, Polygons and Chaos, Journal of Dynamical Systems and Geometric Theories, Vol 2 (2004), pp. 67-80.
• Wolfdieter Lang, On the Equivalence of Three Complete Cyclic Systems of Integers, arXiv:2008.04300 [math.NT], 2020.

Crossrefs

Cf. A000010, A003558, A135303, A332434, A332435, A332436.

Formula

See the above given recurrence relation for the cycles Cy*(b, i), i = 1, 2, ..., c(b) = A135303((b-1)/2), for b = 2*n + 1 >= 3, and the procedure to choose the inputs a(b, i).