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,2

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).

Links

Table of n, a(n) for n=1..71.

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]

Example

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), ...

Crossrefs

Sequence in context: A364957 A076239 A019798 * A120653 A323850 A236937

Adjacent sequences: A214731 A214732 A214733 * A214735 A214736 A214737

Keyword

nonn

Author

Renzo Benedetti, Jul 27 2012

Status

approved