Το Interview Puzzle «Count the Divisors»: ο μικρότερος αριθμός με 104 διαιρέτες — και ο μικρότερος περιττός

Βρείτε:
I. Τον μικρότερο θετικό ακέραιο που έχει ακριβώς 104 διαιρέτες, με τον κανόνα: μετράμε τον ίδιο τον αριθμό ως διαιρέτη, αλλά όχι το 1.
II. Τον μικρότερο περιττό ακέραιο με τον ίδιο ακριβώς αριθμό διαιρετών.

(Παράδειγμα: το 24 έχει 7 τέτοιους διαιρέτες — 2, 3, 4, 6, 8, 12, 24 — γιατί δεν μετράμε το 1.)

---

Λύση – ιδέα σε μία γραμμή

Με τον παραπάνω κανόνα ζητάμε αριθμούς με συνολικό πλήθος διαιρετών

$$\tau (n)=104+1=\mathrm{105..}$$

Για παραγοντοποίηση $n=\prod p_i^{a_i}$ ισχύει:

$$\tau (n)=\prod (a_i+1)\mathrm{.}$$

Επομένως θέλουμε:

$$(a_i+1)(a_j+1)(a_k+1)=105=3\cdot 5\cdot 7.$$

Για ελάχιστο $n$, τοποθετούμε τους μεγαλύτερους εκθέτες στα μικρότερα πρώτα.

---

I. Μικρότερος θετικός με 104 (δηλ. $\tau=105$)

Διαλέγουμε εκθέτες:

$$a_1=6,a_2=4,a_3=2$$

στα πρώτα $2,3,5$.

Άρα:

$$n_{\min }=2^6\cdot 3^4\cdot 5^2=64\cdot 81\cdot 25=\mathrm{129,600..}$$

Έλεγχος:

$$\tau (n)=(6+1)(4+1)(2+1)=7\cdot 5\cdot 3=105\Rightarrow 104\mathrm{ \delta }\iota \alpha \iota \rho \acute{\epsilon }\tau \epsilon \varsigma \mathrm{ \mu }\epsilon \mathrm{ \tau }o\nu \mathrm{ \kappa }\alpha \nu \acute{o}\nu \alpha \mathrm{.}$$

---

II. Μικρότερος περιττός με 104 (δηλ. $\tau=105$)

Αποκλείουμε τον 2 και παίρνουμε τους εκθέτες $6,4,2$ στα πρώτα $3,5,7$.

$$n_{\min ,\text{odd}}=3^6\cdot 5^4\cdot 7^2=729\cdot 625\cdot 49=\mathrm{22,325,625.}$$

Έλεγχος:

$$\tau (n)=(6+1)(4+1)(2+1)=105\Rightarrow 104\mathrm{ \delta }\iota \alpha \iota \rho \acute{\epsilon }\tau \epsilon \varsigma \mathrm{ \mu }\mathrm{\epsilon }\tau o\nu \mathrm{ \kappa }\alpha \nu \acute{o}\nu \alpha \mathrm{.}$$

---

Σημείωση

Αν μετρούσαμε και το 1, τότε θα ζητούσαμε $\tau(n)=104$ αντί για $105$.