cp's OEIS Frontend

If a_{max} is the maximal entry of all first rows of the complete coach system Sigma(b) (the a-numbers, and b = 2*n+1) of Hilton and Pedersen [HP] then a(n) is given by the number of elements in the smallest positive reduced residue system with only odd numbers (call it RRSodd(b)) which are <= a_{max}. This is because all odd numbers reduced modulo b and <= (b-1)/2 appear in the first rows precisely once [see the [HP] proof of the quasi-order theorem, a remark on p. 263]. E.g., for n = 16, a_{max}(33) = 13 from the two coaches with top rows [1] and [5, 7, 13], and RRSodd(33) = {1, 5, 7, 13, 17, 19, 23, 25, 29, 31}, hence a(16) = 4 from #{1, 5, 7, 13} = 4. The cardinality #RRSodd(b) = A055034(b) = A000010(b)/2 = phi(b)/2.

Instead of this upper bound n = (b-1)/2 one can use the odd number a_{up}(b) = (b - (4-q))/2, where q = 1 or 3 if b = 1 or 3 (mod 4), respectively. See also a comment in A109613.

If b = 2*n+1 is a prime p then the upper bound a_{up}(p) = a_{max}(p) of Sigma(p). E.g., b = 5, a_{max}(5) = 1, and b = 7, a_{max}(7) = 3. For primes p1 == 1 (mod 4) (A002144) one has a_{max}(p1) = (p1-3)/2, and for primes p1 == 3 (mod 4) (A002145) a_{max}(p3) = (p3-1)/2.

If b is composite and a_{up}(b) is prime then a_{up}(b) = a_{max}(b). If a_{up}(b) is composite, and one of its factors divides b, then if a_{up}(b) - 2 is prime this is the maximum, otherwise one has to continue this procedure. E.g., a_{up}(33) = 15 = 3*5 and 3 | 33, then 15-2 = 13 is prime, therefore a_{max}(33) = 13.

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.