A214734 Sum_{k=1..n} floor(k*p/q), where (p,q) are either coprime positive integers or q=1 or p=1, n*p>=q, ordered by (n + p + q) ascending, then n ascending, then p ascending.

1, 2, 3, 3, 1, 6, 6, 1, 4, 9, 2, 12, 10, 5, 1, 4, 12, 1, 18, 4, 20, 15, 1, 2, 6, 15, 3, 8, 24, 2, 30, 6, 30, 21, 1, 7, 1, 3, 7, 18, 30, 1, 5, 14, 40, 3, 45, 9, 42, 28, 1, 3, 8, 1, 4, 21, 1, 3, 7, 14, 36, 50, 2, 8, 21, 60, 5, 63, 12, 56, 36

Offset: 1

Author

Renzo Benedetti, Jul 27 2012

Keywords

• nonn

Comments

Since this is a sequence with 3 indexes (n,p,q), then the order proposed is an ordering by planes of 3D-discrete points (similar to a diagonal ordering of 2D-discrete points). It is not possible to order by rows, columns since n, p, q are boundless.

This sequence generalizes other sequences like A130518, A001840, A058937, A130519, A001972 and maybe others (most of those sequences are replica of each other up to an offset), by providing a closed formula (see formulas).

Examples

			a(n, 1, 3) = n*(n+1)/ 6 - floor(n/3) - Sum_{k=1..(n mod 3)} (k mod 3) = n*(n+1)/ 6 - floor(n/3) - (4 mod 3)/3 = A130518(n).
Example of the ordering (n,p,q): (1,1,1), (1,1,2), (1,2,1), (2,1,1), (1,1,3), (1,3,1), (2,1,2), (2,2,1), (3,1,1), (1,1,4), ...
		

Formula

a(n, p, q) = Sum_{k=1..n} floor(k*p/q) defines the sequence.

a(n, p, q) = n*(n+1)*p/q/2 - floor(n/q) * (q-1)/2 - Sum_{k=1...(n mod q)} (k*p mod q)/q (the remaining sum has at most q-1 terms, and can assume at most q values when n varies, i.e., that sum for n is equal to the sum for n+q, so the computation of a(n, p, q) requires adding at most (q+1) terms). [Renzo Benedetti, Jul 27 2012]