h1. Dicsi

Observăm că numerele de forma [1, 2, 4, 8, ..., 2^k^] necesită folosirea a $k + 1$ culori distincte. Putem obţine o astfel de colorare colorând numărul $i$ cu **suma exponenţilor din descompunerea în factori primi** a acestuia. Echivalent, putem folosi următoarea "euristică": $col[i] = 1 + max{col[d] | d divide pe i}$ (care dă, în final, acelaşi răspuns.

Observăm că numerele de forma [1, 2, 4, 8, ..., 2^k^] necesită folosirea a $k + 1$ culori distincte. Putem obţine o astfel de colorare colorând numărul $i$ cu **suma exponenţilor din descompunerea în factori primi** a acestuia. Echivalent, putem folosi următoarea "euristică": $col[i] = 1 + max{col[d] | d divide pe i}$ (care dă, în final, acelaşi răspuns). Calcularea se poate face în complexitate $O(n sqrt(n))$ cu divizori sau $O(n log(n))$ cu ciur.

h1. Blaturi