How many different integers can be written as [n2/1998] for n = 1, 2, ... , 1997?
Solution
Answer: 1498.
Let f(k) = [k2/1998]. We have k2/1998 - (k - 1)2/1998 = (2k - 1)/1998 > 1 for k ≥ 1000. Hence for k > 1000, f(k) ≥ f(k - 1) + 1. So the 998 values k = 1000, 1001, ... , 1997 generate 998 distinct values of f(k) all at least f(1000) = [999·1000/1998 + 1·1000/1998] = [500 + 1000/1998] = 500.
If k < 1000, then k2/1998 - (k - 1)2/1998 < 1. So the real values 1/1998, 4/1998, 9/1998, ... , 9992/1998 are spaced at intervals of less than one and hence every integer from 1 to f(999) must lie between two of them. Thus for k = 1, 2, ... , 999, f(k) generates every integer from 0 to f(999) = [999·999/1998] = [999/2] = 499, a total of 500 integers.
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002