login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
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 (list; graph; refs; listen; history; text; internal format)
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.
LINKS
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.
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
Cf. A000010, A055034, A109613, A332434, A332436 (complement if a(0) = 0).
Sequence in context: A032434 A002347 A006642 * A361744 A324751 A210595
KEYWORD
nonn,easy
AUTHOR
Wolfdieter Lang, Feb 26 2020
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 14:38 EDT 2024. Contains 371254 sequences. (Running on oeis4.)