The function f is defined on the positive integers and f(m) ≠ f(n) if m - n is prime. What is the smallest possible size of the image of f.
Solution
Answer: 4.
f(1), f(3), f(6), f(8) must all be different. So the image must contain at least 4 elements. But the example f(n) = residue of n mod 4 shows that 4 is sufficient.
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002