A332435 Row sums of the irregular triangle A332434. a(n) equals the number of odd numbers <= n, of the smallest nonnegative reduced residue system modulo (2*n + 1), for n >= 1.

1, 1, 2, 1, 3, 3, 2, 4, 5, 2, 6, 5, 5, 7, 8, 4, 6, 9, 6, 10, 11, 6, 12, 10, 8, 13, 10, 8, 15, 15, 10, 12, 17, 10, 18, 18, 10, 14, 20, 13, 21, 16, 14, 22, 18, 14, 18, 24, 16, 25, 26, 12, 27, 27, 18, 28, 22, 18, 24, 27, 20, 25, 32, 20, 33, 26, 18, 34, 35, 22, 30, 28, 22, 37, 38, 24, 30, 39, 26, 32, 41, 20

Offset: 1

Author

Wolfdieter Lang, Feb 26 2020

Keywords

• nonn
• easy

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.

Examples

			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.
		

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.

Crossrefs

Cf. A000010, A055034, A109613, A332434, A332436 (complement if a(0) = 0).

Formula

a(n) = Sum_{j=1..c(2*n+1)} A332434(n, j), where the coach number c(2*n+1) = A135303(n), for n >= 1.