MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Ideas. As there is a lot of discussion going on, I thought I share here my attempts as Ewan and Gowers took similar paths. First of all, if we denote the primes by $p_i$ and the largest prime not bigger than $n$ by $p_d$, then it is sufficient to color the numbers of the form $\Pi p_i^{\alpha_i}$. This is equivalent to coloring $\mathbb Z^d$ with n colors such that the translates of a special poliomino are all rainbow colored, meaning they contain all $n$ colors. This is also equivalent to tiling the space with translates of this poliomino. The easiest way to give a coloring is if we have some nice periodicity, eg. if n+1 is prime, then $\Pi p_i^{\alpha_i} \mod (n+1)$ is such, whenever we go in a direction, it corresponds to an authomorphism of $Z_{n+1}^*$. Another possibility is to give a "linear" coloring using the addition $\mod n$, for example for $n=5$, one can take $x+3y+4z \mod 5$. So far I could always find such a linear coloring but I cannot prove that it always exist, eg. we have too many constraints to use the combinatorial nullstellensatz.