cp's OEIS Frontend

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.

%I A332435 #18 May 29 2025 06:05:37
%S A332435 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,
%T A332435 10,12,17,10,18,18,10,14,20,13,21,16,14,22,18,14,18,24,16,25,26,12,27,
%U A332435 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
%N 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.
%C A332435 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.
%C A332435 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.
%C A332435 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.
%C A332435 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.
%D A332435 Peter Hilton and Jean Pedersen, A Mathematical Tapestry: Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, 2010, (3rd printing 2012) pp. 261-281.
%F A332435 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.
%e A332435 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.
%e A332435 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.
%Y A332435 Cf. A000010, A055034, A109613, A332434, A332436 (complement if a(0) = 0).
%K A332435 nonn,easy
%O A332435 1,3
%A A332435 _Wolfdieter Lang_, Feb 26 2020