[seqfan] Re: (no subject) (lattice points)

Richard Mathar mathar at strw.leidenuniv.nl
Sat Apr 24 20:06:14 CEST 2010


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


More information about the SeqFan mailing list