OFFSET
1,3
COMMENTS
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.
REFERENCES
Peter Hilton and Jean Pedersen, A Mathematical Tapestry: Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, 2010, (3rd printing 2012) pp. 261-281.
FORMULA
EXAMPLE
n = 3, b = 7, c(7) = 1, k(7) = 4, a_{up}(7) = 3 = a_{max}(7): Sigma(7) = [[1,3; 1,2]], hence a(3) = 2.
n = 16, b = 33, c(33) = 2, k(33) = 5, Sigma(33) = [[1; 5], [5, 7, 13; 2, 1, 2]], a(16) = 1 + 3 = 4.
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Wolfdieter Lang, Feb 26 2020
STATUS
approved