Coloring the \(n\)-smooth numbers with \(n\) colors (Q2227831)

The \(n\)-satisfactory coloring is a coloring of the set of natural numbers into \(n\) colors such that for any \(a\) the numbers \(a,2a,\ldots,na\) all have different colors. The existence of \(n\)-satisfactory colorings is an important combinatorial problem. It is also related to some conjectures of Graham and Pilz and with the properties of the \(n\)-smooth numbers (i.e. integers whose prime factorization only includes primes less than or equal to \(n\)). The paper discuss the known partial results and investigate a series of related matters attempting to understand the structure of these \(n\)-satisfactory colorings. For example, the existence of \(n\)-satysfactory colorings are established in the following cases: 1) \(n+1\) or \(2n+1\) is prime; 2) \(n=p^2-p\) for some prime \(p\); 3) \(n<195\). Generally, it is shown that the existence of \(n\)-satisfactory coloring follows from the existence an abelian group operation \(\oplus\) on the set \(\{1,2,\ldots,n\}\) such that if \(ij<n\) then \(i\oplus j=ij\).