A259573 Number of distinct differences in row n of the reciprocity array of 0.

1, 2, 3, 4, 3, 4, 3, 6, 5, 6, 3, 8, 3, 6, 7, 8, 3, 8, 3, 8, 9, 6, 3, 12, 5, 6, 7, 10, 3, 14, 3, 10, 9, 6, 9, 14, 3, 6, 9, 12, 3, 12, 3, 12, 11, 6, 3, 18, 5, 10, 9, 12, 3, 12, 9, 14, 9, 6, 3, 22, 3, 6, 13, 12, 9, 14, 3, 12, 9, 14, 3, 18, 3, 6, 13, 12, 9, 16

Offset: 1

Author

Clark Kimberling, Jun 30 2015

Keywords

• nonn
• easy

Comments

The "reciprocity law" that Sum_{k=0..m} [(n*k+x)/m] = Sum_{k=0..n} [(m*k+x)/n] where x is a real number and m and n are positive integers, is proved in Section 3.5 of Concrete Mathematics (see References).

Examples

			In the array at A259572, row 4 is (0,2,3,6,6,8,9,12,12,14,15,...), with differences (2,1,3,0,2,1,3,0,2,1,3,0, ...), and distinct differences {0,1,2,3}, so that a(4) = 4. Example corrected by _Antti Karttunen_, Nov 30 2021
		

References

• R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989, pages 90-94.

Links

• Antti Karttunen, Table of n, a(n) for n = 1..20000

Crossrefs

Cf. A249572, A259574.

Programs

Mathematica

x = 0;  s[m_, n_] := Sum[Floor[(n*k + x)/m], {k, 0, m - 1}];
t[m_] := Table[s[m, n], {n, 1, 1000}];
u = Table[Length[Union[Differences[t[m]]]], {m, 1, 120}]  (* A259573 *)

PARI

A259572(m,n) = ((m*n - m - n + gcd(m,n))/2); \\ After Witold Dlugosz's formula for A259572.
A259573(n) = #Set(vector(n,k,A259572(n,1+k)-A259572(n,k))); \\ Antti Karttunen, Nov 30 2021