[seqfan] Re: (no subject) (lattice points)
Richard Mathar
mathar at strw.leidenuniv.nl
Sat Apr 24 20:06:14 CEST 2010
http://list.seqfan.eu/pipermail/seqfan/2010-April/004437.html
This counts the numbers in the triangle
underneath s = n/q- p*t/q in the first
quadrant. Clearly equals
sum_{t=0..floor(n/p)} 1+floor[ (n-p*t)/q].
or
sum_{s=0..floor(n/q)} 1+floor[ (n-q*s)/p].
by direct counting.
A lower bound seems to be
1 + ( 1+floor(n/q) )*( 1+floor(n/q) ) / 2 .
There must be some positive correction term which by p<->q symmetry of the
problem is some combination (sum, product) of symmetric functions like
gcd(p,q), lcm(p,q), floor(n^2/pq), floor(n/q)+floor(n/p), (n mod p)+(n mod q),
floor(n/q)*floor(n/p) etc.
I am unable to figure out what this functional actually is.
RJM
More information about the SeqFan
mailing list