Problem

Source: Philippine Mathematical Olympiad 2024 P4

Tags: function, combinatorics, number theory



Let $n$ be a positive integer. Suppose for any $\mathcal{S} \subseteq \{1, 2, \cdots, n\}$, $f(\mathcal{S})$ is the set containing all positive integers at most $n$ that have an odd number of factors in $\mathcal{S}$. How many subsets of $\{1, 2, \cdots, n\}$ can be turned into $\{1\}$ after finitely many (possibly zero) applications of $f$?