My brute force solution. Its highly likely that this is neither the shortest nor the most beautiful way to do it.

ropro01 wrote: My brute force solution. Its highly likely that this is neither the shortest nor the most beautiful way to do it. Well, do not sweat it, unless I am mistaken it works fine. Hint follows:

Let $p_i$ be the $i$-th prime and $a_i$ be the smallest integer such that $p_i^{2^{a_i}} > p_{i+1}$. My intuition strongly believes that $f(2^n)$ can be defined as follows: choose the largest $t$ such that $\sum_{i=1}^ta_i\le n$ and let $a_{t+1}=n-\sum_{i=1}^ta_i$, then $f(2^n)=\prod_{i=1}^{t+1}p_i^{2^{a_i}-1}$.

Let $p_i's$ be the prime numbers Let : $f({2^{k }}) = \prod\limits_{i = 1}^\infty {{p_i}^{{2^{{t_i}}} - 1}} $ By induction we'll prove that :$f({2^{k + 1}}) = f({2^k}) \cdot \min \left\{ {{p_i}^{{2^{{t_i}}}}} \right\}$ Assume that there exist $n \in \mathbb{Z_+}$ such that $\tau (n) = {2^{k + 1}},n < f({2^k}) \cdot \min \left\{ {{p_i}^{2^{t_i}}} \right\}$ Let : $n = \prod\limits_{i = 1}^\infty {{q_i}^{{2^{{r_i}}} - 1}} $ If : $\exists m \in \mathbb{Z}$ such that ${q_m}^{{2^{{r_m} - 1}}} \geqslant\min \left\{ {{p_i}^{{2^{{t_i}}}}} \right\}$ then :$f({2^k}) > {q_m}^{{2^{{r_m} - 1}} - 1} \cdot \prod\limits_{i = 1,i \ne m}^\infty {{q_i}^{{2^{{r_i}}} - 1}} $ but : $\tau \left( {{q^{{2^{{r_m} - 1}} - 1}}\prod\limits_\begin{subarray}{l} i = 1 \\ i \ne m \end{subarray} ^\infty {{p_i}^{{2^{{r_i}}} - 1}} } \right) = 2^k$ Which is impossible $\therefore {q_i}^{{2^{{r_i}}} - 1} < \min \left\{ {{p_i}^{{2^{{t_i}}}}} \right\}$ $\forall i \in \mathbb{N}$ but from induction hypothesis $ n \leqslant f({2^k})$ but clearly$ f(2^{k+1})>f(2^k)$ , contradiction !! $\therefore f({2^{k + 1}}) = f({2^k}) \cdot \min \left\{ {{p_i}^{{2^{{t_i}}}}} \right\}$

This is roughly what I was talking about. Define $\mathcal{P}$ as the set of all powers of primes such that the exponent is a power of $2$ (including exponent $2^0=1$), ie, $2^{2^0},2^{2^1},2^{2^2},\dots,3^{2^0},3^{2^1},\dots$. Now order them in increasing order, ie (if I did not accidentally leave any one out) $\mathcal{P}=\{2,3,4,5,7,9,11,13,16,17,19,23,25,29,\dots\}$. Denote by $p_i$ the $i$-th element in the set. Then any integer that has exactly $2^k$ divisors, is the product of exactly $k$ elements in $\mathcal{P}$, such that if $p^{2^u}$ appears in the product, then so do necessarily $p^{2^v}$ for $v=0,1,\dots,u$. Clearly, the product of the lowest $k$ elements in $\mathcal{P}$ satisfies this requirement, and is obviously the lowest product of $k$ elements in $\mathcal{P}$. Or $f(2^k)=p_1p_2\dots p_k$, and clearly $f(2^{k+1})=f(2^k)p_{k+1}$. The conclusion follows and we have an algorithm to build $f(2^k)$ for any positive integer $k$.

I proposed this problem as team leader of the Malaysia team to IMO 2011. Some generalizations can be found in Ramanujan's paper: "Highly Composite Numbers", Proc. of the LMS, 1916. Suhaimi Ramly, Malaysia

Here is my solution: Assume the contradictiory. Then there are primes $p,q$ such that $p^{2^c-1}q^{2^d-1}$ is a part of the factorisiation of $f(2^{k+1})$ and $p^{2^a-1}q^{2^b-1}$ is a part of the factorisation $f(2^k)$ such that $d<b$ and $c>a$. Then we have that by definition of $f$ and multiplying by $pq$ that $p^{2^{c-1}}q^{2^{d+1}}>p^{2^c}q^{2^d}$ giving $p^{2^{c-1}}<q^{2^d}$ Also $p^{2^{a+1}}q^{2^{b-1}}>p^{2^a}q^{2^b}$ which gives $p^{2^{a}}>q^{2^{b-1}}$ But now $p^{2^{c-1}}<q^{2^d}\le q^{2^{b-1}}<p^{2^a}\le p^{2^{c-1}}$ giving a contradiction.

Consider the following algorithm for obtaining $f(2^k)$.We do it in moves.We start from $2^1$.Now, in every move we consider the smallest prime number not contained in our current number.Let that number be $p_t$.Now, in each move we either add $p_t$ in our configuration or we increase the exponent of some of the already existing numbers(if their exponent is $2^l-1$ it will become $2^{l+1}-1$ or in other words we add $2^l$ to the exponent).So if there exists, in our configuration, some number $p_i<p_t$ such that $p_i^{2^l}<p_k$ we increase the exponent of $p_i$.We will obviously have $k$ moves and the algorithm obviously satisfies that the calculated number will be the smallest one satisfying condition so we have $f(2^{k+1})=f(2^k) \cdot p_t^j$ so the task is proven.

Note that $f(1)=1,f(2)=2,f(4)=6$ etc.It is not hard to guess that $f(2^k)$ is of form $\prod_{i=1}^{r}{{p_i}^{2^{\alpha_i}-1}}$ where $p_1,p_2,\cdots,p_r$ are the first $r$ prime numbers and the $\alpha_i$'s are decreasing from the start with each of them positive. I shall use strong induction on $k$. Base cases are trivial.Let's assume that the statement is true for all integers upto $k-1$. First I show that $f(2^{k+1})$ cannot have less than $r$ prime factors in its factorisation.Let $f(2^{k+1})=\prod_{i=1}^{s}{{p_i}^{2^{\beta_i}-1}}$ and assume to the contrary.Then if there exists $i$ such that $p_r < {p_i}^{2^{\beta_i-1}}$ then we could have removed $2^{\beta_i-1}$ from the power of $p_i$ and multiplied the term by $p_r$.This makes the number smaller but the number of divisors fixed.Contradiction!.Thus $p_r \ge {p_i}^{2^{\beta_i-1}} \forall i<r$. Now assume that ${p_r}^{2^{\alpha_{r-1}}}>{p_i}^{2^{\alpha_i}}$ for some $i$.Then multiplying $f(2^k)$ with $\frac{{p_i}^{2^{\alpha_i}}}{{p_r}^{2^{\alpha_{r-1}}}}$ we obtain a term smaller than $f(2^r)$ and with $2^r$ divisors which is again a contradiction.Therefore ${p_r}^{2^{\alpha_r}} \le {p_i}^{2^{\alpha_{i-1}}} \forall i<r$. Since $\sum{\beta_i}=2^{k+1}$ there exists $\beta_j$ s.t $\beta_j > \alpha_j$.For that $\beta_j$ we should have ${p_j}^{2^{{\beta_j}-1}} \le {p_r} \le {p_r}^{2^{\alpha_r}} \le {p_j}^{2^{{\alpha_j}-1}}$.Contradiction.Therefore $f(2^{k+1})$ has no less than $r$ distinct prime factors,as desired. Hence $f(2^{k+1})=\prod_{i=1}^{s}{{p_i}^{2^{\beta_s}-1}}$ where $s \ge r$.Let $r=s$.By similar argument as in the previous paragraph we may also show that ${p_j}^{2^{\alpha_j}} > {p_i}^{2^{\alpha_i-1}} \forall i,j$ and ${p_j}^{2^{{\beta_j}-1}} < {p_i}^{2^{\beta_i}} \forall i,j$.Also since $\sum{\beta_i}=k+1$ there exists $j$ s.t $\beta_j > \alpha_j$.Then applying these inequalities with $i,j$ fixed we get ${p_i}^{2^{\beta_i}} > {p_j}^{2^{{\beta_j}-1}} \ge {p_j}^{2^{\alpha_j}} > {p_i}^{2^{\alpha_i-1}}$.Thus we obtain $\beta_i \ge \alpha_i \forall i$.The case when $s=r+1$ is trivial by fixing $p_{r+1}$.

Very nice problem! Here's an algorithmic solution. I'm sure that could be done quicker and clearer, but here we go. Let $(p_1,p_2,p_3,p_4,\dots)=(2,3,5,7,\dots)$ be the list of prime numbers and let $\tau(\cdot)$ be the function to determine the number of divisors. Note that \[ 2^k = \tau \left( f \left( 2^k \right) \right) = (\alpha_1+1)(\alpha_2+1)\dots(\alpha_h+1), \]if $f \left(2^k \right) = p_1^{\alpha_1}p_2^{\alpha_2} \dots p_h^{\alpha_h}$ is its canonial representation. Note that $\alpha_i = 2^{e_i}-1$ for some $e_i$. Thus \[ f \left(2^k \right) = \prod_{1 \leq i, \ 0 \leq e_i} p_i^{2^{e_i}-1}. \]Note that obviously $e_1 \geq e_2 \geq e_3 \geq \dots$. Now let $n$ be a positive integer, such that $\tau(n) = 2^k$. Then we also have \[ n = \prod_{1 \leq i, \ 0 \leq f_i} p_i^{2^{f_i}-1}. \]It's easy to see that we have to multiply $n$ by $p_{\ell}^{2^{f_{\ell}}}$ for some $j$ to create some number with $2^{k+1}$ divisors. Analogously for $f \left(2^k \right)$ we have to multiply it by some $p_j^{2^{e_j}}$. Now let $f \left(2^k \right) \cdot p_j^{2^{e_j}}$ be optimal, that is, using an other factor is always at least as large as that number and let $n \cdot p_{\ell}^{2^{f_{\ell}}}$ be arbitrary. We want to show \[ f \left(2^{k+1} \right) = f \left(2^k \right) \cdot p_j^{2^{e_j}}. \]Note that with $n \cdot p_{\ell}^{2^{f_{\ell}}}$ we can produce all numbers with exactly $2^{k+1}$ divisors. It thus suffices to show $ f \left(2^k \right) \cdot p_j^{2^{e_j}} \leq n \cdot p_{\ell}^{2^{f_{\ell}}}$. WLOG let $f_1 \geq f_2 \geq f_3 \geq \dots$. Therefore, we only have a finite number of numbers $n$ to consider. Case 1: Suppose $f_{\ell} \geq e_{\ell}$. Then just note \[ f \left(2^k \right) \cdot p_j^{2^{e_j}} \leq f \left(2^k \right) \cdot p_{\ell}^{2^{e_{\ell}}} \leq n \cdot p_{\ell}^{2^{f_{\ell}}}, \]as $j$ is chosen optimally. Case 2: Suppose $f_{\ell} < e_{\ell}$. That case is a bit tougher (and especially tougher to explain). Let $\sigma_i(\cdot)$ and $\delta_i(\cdot)$ be operations that multiply some numbers by some $p_x^{2^{e_x}}$ or $p_y^{2^{f_y}}$. Note that \[ f \left( 2^k \right) = \sigma_s \circ \sigma_{s-1} \circ \dots \circ \sigma_1(1) \ \text{and } \ n= \delta_s \circ \delta_{s-1} \circ \dots \circ \delta_1(1). \]Let $\sigma_{s+1}$ denote a multiplication by $p_j^{2^{e_j}}$ and $\delta_{s+1}$ denote a multiplication by $p_{\ell}^{2^{p_{\ell}}}$. Note that $\sigma_1,\sigma_2,\dots,\sigma_{s+1}$ are pairwise distinct. As are their $\delta$ counterparts. As $f_{\ell} < e_{\ell}$, there is a $\sigma_m$ that operates a multiplication by $p_{\ell}^{2^{f_{\ell}}}$. Thus, there is a operation $\delta_r$ with $1 \leq r \leq s$ that isn't included in the set of operations $\{\sigma_1,\sigma_2,\dots,\sigma_s \}$ by the Pigeonhole Principle. Now note that \[ f \left(2^k \right) = \sigma_1 \circ \sigma_2 \circ \dots \circ \sigma_s(1) \]and \[ u := \delta_1 \circ \dots \circ \delta_{r-1} \circ \delta_{r+1} \circ \delta_{r+2} \circ \dots \circ \delta_{s+1}(1) \]is some number with exaclty $2^k$ divisors. Obviously $f \left(2^k \right) \leq u$ due to the optimality criterion. But \[ f \left( 2^{k+1} \right) = \sigma_{s+1} \left(f \left(2^k \right) \right) \ \text{and} \ n \cdot p_{\ell}^{2^{f_{\ell}}} = \delta_r(u).\]But $\delta_r$ denotes a multiplication by $p_t^{2^{f_t}}$ for some $t$. And since $\delta_r$ is not an element of $\{ \sigma_1,\sigma_2,\dots,\sigma_{s+1} \}$, it follows that $f_t \geq e_t$. Thus, we can proceed as in Case 1. Done.

can someone prove that $f(2^k)=p_1p_2\dots p_k$ $?$

Mathemator_13 wrote: can someone prove that $f(2^k)=p_1p_2\dots p_k$ $?$ Not always true, take n any power of 2 greater than 8

who has easier solution?

Order countable infinite numbers of the form $p^{2^{\ell}}$ where $p$ be any prime number and $\ell$ be any non-negative integer in increasing order. Not hard to show that, for any positive integer $n$, $f(2^n)$ is equal to the product of first $n$ numbers in the ordered sequence.

daniel73 wrote: Then any integer that has exactly $2^k$ divisors, is the product of exactly $k$ elements in $\mathcal{P}$, such that if $p^{2^u}$ appears in the product, then so do necessarily $p^{2^v}$ for $v=0,1,\dots,u$. Can someone elaborate this part?

I wrote it late at night with "You say run" stuck in my head so it may have some errors. Please let me know, if so orl wrote: For any integer $d > 0,$ let $f(d)$ be the smallest possible integer that has exactly $d$ positive divisors (so for example we have $f(1)=1, f(5)=16,$ and $f(6)=12$). Prove that for every integer $k \geq 0$ the number $f\left(2^k\right)$ divides $f\left(2^{k+1}\right).$ Proposed by Suhaimi Ramly, Malaysia Let $a_k=f(2^k)$ for all $k \ge 0$. Check base cases $k \le 2$ by hand. Let $k>2$ be the least integer for which the claim is false. Let $a_k=\prod^{s}_{j=1} p_j^{2^{x_j}-1}$ and $a_{k+1}=\prod^{r}_{i=1} p_i^{2^{y_i}-1}$. Lemma: $x_1 \ge \dots \ge x_s=1$ and $p_1<\dots <p_s$ are the first $s$ primes. (Proof) Replacing the base of a prime power dividing $a_k$ with a smaller prime will contradict the minimality of $a_k$. Thus, $p_i$'s make up the first $s$ primes. Now if for $i<j$ we have $x_i<x_j$ then switch the exponents of $p_i, p_j$ to get a number $a_k'<a_k$ with $d(a_k')=2^k$, again not possible. Finally, $x_s=1$ else $p_s^{2^{x_s}-1} \mapsto p_s^{2^{x_s-1}-1}$ and append $p_{s+1}<2p_s$. Minimality is again contradicted. $\blacksquare$ Lemma: $y_i \le x_i$ for all $1 \le i \le s$ and $r>s$. (Proof) Suppose $y_{\ell}>x_{\ell}$. Then $d\left(\frac{a_{k+1}}{p_{\ell}^{2^{y_{\ell}-1}}}\right)=k$ hence $a_{k+1} \ge p_{\ell}^{2^{y_{\ell}-1}}a_k$. However $d(a_kp_{\ell}^{2^{x_{\ell}}})=k+1$ hence $a_{k+1} \le a_kp_{\ell}^{2^{x_{\ell}}}$ thus $a_k \mid a_{k+1}$ and we get a contradiction! Hence $y_i \le x_i$ for all $i \le s$. Since $y_s \le x_s=1$ we get $y_{s+1}=\dots=y_r=1$ and $x_1+\dots+x_s=k$ while $$(k+1)=y_1+\dots+y_r=(y_1+\dots+y_s)+(r-s) \le (x_1+\dots+x_s)+(r-s)=k+(r-s)$$hence $r \ge s+1$. $\blacksquare$ Now $d(a_kp_{s+1})=2^{k+1}$ hence $a_kp_{s+1} \ge a_{k+1}$. Meanwhile, $d\left(\frac{a_{k+1}}{p_{s+1}}\right)=k$ hence $a_{k+1} \ge p_{s+1}a_k$ and so $a_{k+1}=p_{s+1}a_k$ again a contradiction. Hence no integer $k$ dares to oppose the given proposition. $\blacksquare$

I wrote it late afternoon with "You say mo" stuck in my head so it may have some errors. Please let me know, if so Fix $k \ge 0$, and let $g(k) = f(2^k)$ for all $k \ge 0$; we want to prove $g(k) \mid g(k+1)$. Because $g(k+1)$ has more factors than $g(k)$, $g(k+1)$ does not divide $g(k)$, so $v_p (g(k+1)) > v_p (g(k))$ for some prime $p$. Let $v_p (g(k)) = a$; then $a+1$ divides the number of divisors $2^k$, so $a = 2^b - 1$ for some $b \ge 0$. Since $v_p (g(k+1))$ is also one less than a power of $2$ and is greater than $a$, we have $v_p (g(k+1)) = 2^c - 1$ for some $c \ge b+1$. Hence, $g(k+1) \cdot p^{-2^{c-1}}$ has $2^k$ factors, so $g(k+1) \cdot p^{-2^{c-1}} \ge g(k)$. But $g(k) \cdot p^{2^b}$ has $2^{k+1}$ factors, and is at least $g(k+1)$. Hence, $$g(k+1) g(k) \cdot p^{2^b} \ge g(k+1) g(k) p^{2^{c-1}}.$$Since $g(k)$ and $g(k+1)$ are nonzero, we have $b \ge c-1$. Thus all equalities hold, $b = c-1$, and $g(k+1) = g(k) \cdot p^{2^b}$, so $g(k) \mid g(k+1)$.

anantmudgal09 wrote: I wrote it late at night with "You say run" stuck in my head so it may have some errors. Please let me know, if so orl wrote: For any integer $d > 0,$ let $f(d)$ be the smallest possible integer that has exactly $d$ positive divisors (so for example we have $f(1)=1, f(5)=16,$ and $f(6)=12$). Prove that for every integer $k \geq 0$ the number $f\left(2^k\right)$ divides $f\left(2^{k+1}\right).$ Proposed by Suhaimi Ramly, Malaysia Let $a_k=f(2^k)$ for all $k \ge 0$. Check base cases $k \le 2$ by hand. Let $k>2$ be the least integer for which the claim is false. Let $a_k=\prod^{s}_{j=1} p_j^{2^{x_j}-1}$ and $a_{k+1}=\prod^{r}_{i=1} p_i^{2^{y_i}-1}$. Lemma: $x_1 \ge \dots \ge x_s=1$ and $p_1<\dots <p_s$ are the first $s$ primes. (Proof) Replacing the base of a prime power dividing $a_k$ with a smaller prime will contradict the minimality of $a_k$. Thus, $p_i$'s make up the first $s$ primes. Now if for $i<j$ we have $x_i<x_j$ then switch the exponents of $p_i, p_j$ to get a number $a_k'<a_k$ with $d(a_k')=2^k$, again not possible. Finally, $x_s=1$ else $p_s^{2^{x_s}-1} \mapsto p_s^{2^{x_s-1}-1}$ and append $p_{s+1}<2p_s$. Minimality is again contradicted. $\blacksquare$ Lemma: $y_i \le x_i$ for all $1 \le i \le s$ and $r>s$. Nope: $f(4) = 2 \cdot 3$ and $f(8) = 2^3 \cdot 3$ if I am not mistaken. Hence $r > s$ is false.

Notice $f(2^k)$ is in the form $\prod p_i^{2^{a_i}-1}$ where $p_i$ are prime divisors of $f(2^k),$ $a_i\ge 1,$ and $\sum a_i=k.$ Similarly, let $f(2^{k+1})=\prod q_i^{2^{b_i}-1}$ with $\sum b_i=k+1.$ Claim: $f(2^{k+1})$ cannot have $b_i<a_i$ for any $i.$ Proof. Suppose FTSOC that $b_i=a_i+\epsilon_i,$ with $\sum\epsilon_i=1$ and $\epsilon_j<0.$ Notice we must have at least one positive $\epsilon,$ call that $\epsilon_k.$ Consider $\ell=\prod r_i^{2^{c_i}-1}$ where $c_i=a_i$ for all $i\neq k$ and $c_k=a_k+1.$ Since $\tau(\ell)=2f(2^k)=2^{k+1},$ we know $\ell>f(2^{k+1}).$ But as $2^{a_k}\le 2^{a_k+\epsilon_k-1}$ and $\left(p^{2^{a_k+\epsilon_k-1}}\right)\left(p^{2^{a_k+\epsilon_k-1}-1}\right)=2^{2^{a_k+\epsilon_k}-1},$ we know $$f(2^k)=\frac{\ell}{p^{2^{a_k}}}>\frac{f(2^{k+1})}{p^{2^{a_k+\epsilon_k-1}}}=p^{2^{a_k+\epsilon_k-1}-1}\prod_{i\neq k}{p^{2^{b_i}-1}}.$$Since $$\tau\left(p^{2^{a_k+\epsilon_k-1}-1}\prod_{i\neq k}{p^{2^{b_i}-1}}\right)=2^{a_k+\epsilon_k-1}\cdot 2^{\sum_{i\neq k} b_i}=2^k,$$we have a contradiction because $f(2^k)$ is not the smallest number with $2^k$ divisors. $\blacksquare$ Thus, $b_i\ge a_i$ for all $i$ and so $f(2^k)\mid f(2^{k+1}).$ $\square$

Can someone check my solution, thanks We will prove the following claim using induction: $f(2^k)$ is the unique number $p_1^{2^{a_1}-1}\cdots p_n^{2^{a_n}-1}$ with $p_1,\ldots,p_n$ prime and $a_1,\ldots a_n$ positive integers satisfying the following properties: 1. $a_1+\cdots+a_n=k$ 2. For all $1\leq i, j\leq n$, $p_i^{2^{a_i}}>p_j^{2^{a_j-1}}$ 3. For all prime $q$ not equal to any $p_i$, for all $1\leq i\leq n$, $q>p_i^{2^{a_i-1}}$ 4. It is divisible by $f(2^{k-1})$. Proof: First we will show that properties 1, 2, and 3 are true. Property 1 must be true since $f(2^k)$ has $2^k$ divisors. Property 2 must be true because otherwise you could multiply $f(2^k)$ by $\frac{p_i^{2^{a_i}}}{p_j^{2^{a_j-1}}}$ and get a smaller number with $2^k$ divisors. Similarly, property 3 must be true because otherwise you could multiply $f(2^k)$ by $\frac{q}{p_i^{2^{a_i-1}}}$ and get a smaller number with $2^k$ divisors. Now, we will show that there is a unique number satisfying properties 1, 2, 3, and that property 4 holds. We will prove this using induction. As the base case, we have $k=1$ and $f(2)=2$ where we can check that each statement is true and that this is the unique number satisfying these properties. Inductive step: Assume that $f(2^{k-1})$ is the unique number satisfying properties 1, 2, 3 for $k-1$. Let $p_1^{2^{a_1}-1}\cdots p_n^{2^{a_n}-1}$ be a number satisfying properties 1, 2, 3 for $k$. Assume WLOG that $p_1^{2^{a_1-1}}>p_x^{2^{a_x-1}}$ for all $1\leq x\leq n$. Then, it can be shown that $p_1^{2^{a_1-1}-1}p_2^{2^{a_2}-1}\cdots p_n^{2^{a_n}-1}$ satisfies properties 1, 2, 3, for $k-1$ and therefore is equal to $f(2^{k-1})$. So, we have $f(2^{k-1})|X$ for all $X$ satisfying properties 1, 2, 3 for $k$. Let $f(2^{k-1})=p_1^{2^{a_1}-1}\cdots p_n^{2^{a_n}-1}$. We claim that there is a unique $X$ satisfying the three properties for $k$. Assume towards a contradiction that $X$ and $Y$ both satisfy the properties. Then, assume WLOG $X<Y$. We have $\frac{X}{f(2^{k-1})}<\frac{Y}{f(2^{k-1})}$. The LHS is equal to either $p_i^{2^{a_i}}$ for some $1\leq i\leq n$ or $q$ for some prime $q$ not equal to any $p_i$. And, for some term $p^{2^a-1}$ of $Y$'s prime factorization with $p$ prime, then the RHS is equal to $p^{2^{a-1}}$. So, this contradicts the fact that $Y$ satisfies properties 2 and 3. So, there is a unique $X$ satisfying properties 1, 2, 3, and it is divisible by $f(2^{k-1})$. This completes the proof.

consider the list 2^1, 2^2, 2^4, 2^8, ..., 3^1, 3^2, 3^4, 3^8, ..., 5^1, 5^2, 5^4, 5^8, ... in sorted order then to get f(2^k) just pick the first k numbers (in sorted order) and multiply those obviously this works + immediately implies the conclusion

Actually, we claim that we can characterize the exact value of $f(2^k)$. Consider the set of integers \[ S = \bigcup_{p \text{ prime}} \{p, p^2, p^4, \ldots\} \]i.e., the set of integers that start with $2,3,4,5,7,9,\ldots$. Claim: Any integer with $2^k$ divisors must be the product of exactly $k$ distinct integers in $s$. Proof. Write the integer $n$ as $n = \prod_{i=1}^{l} p_{i}^{2^{a_i}-1}$ where $p_i$ are all prime, $a_i$ are all integers, and $\sum\limits_{i=1}^{l} a_i = k$. Then, write \[ n = \prod_{i=1}^{l} p_{i}^{2^{a_i}-1} = \prod_{i=1}^{l} \left(\prod_{j = 0}^{a_i-1} p_i^{2^j}\right) \]and each of the $p_i^{2^{j}}$ terms are distinct numbers in $S$, and there are a total of $\sum\limits_{i=1}^{l} a_i = k$ of these terms, which finishes. $\blacksquare$ Now, to finish note that $f(2^k)$ is simply the product of the $k$ smallest numbers in $S$ (and it is easy to see that this does actually work), and $f(2^{k+1})$ is the product of the $k+1$ smallest numbers in $S$, clearly a multiple of $f(2^k)$.

Let $$S = \bigcup_{p \text{ prime}} \{p, p^2, p^4, \ldots\}$$with the first integers being $2,3,4,5,7,9, \cdots$. Claim: Any integer with $2^k$ divisors is the product of $k$ elements in $S$. Proof: Let $n=p_1^{e_1} p_2^{e_2} \cdots p_i^{e_i}$. We have $e_j+1 | 2^k$, so $e_j+1=2^{f_j}$ with $\sum_{j=1}^{i}f_j=k$. Using this new definition, we get that $$n=p_1^{2^{f_1}-1}p_2^{2^{f_2}-1} \cdots p_i^{2^{f_i}-1} = (p_1^1 \cdot p_1^2 \cdots p_1^{2^{f_1-1}}) \cdots (p_i^1 \cdot p_i^2 \cdots p_i^{2^{f_i-1}}),$$of which there is obviously $k$ terms by the fact that $\sum_{j=1}^{i}f_j=k$. This proves the claim. Thus obviously $f(2^k)$ is the product of the $k$ smallest elements in $S$, so $\frac{f(2^{k+1})}{f(2^k)}$ is the $k+1$th smallest integer in $S$, which is obviously an integer so we are done.

Note that if a number has $2^k$ divisors, then it's of the form $\prod_{i=1}^{\infty}{p_i^{2^{e_i}-1}}$ where $e_i$ is a nonnegative integer and $p_i$ is the $p$th prime. Additionally, $k=\sum_{i=1}^{\infty}{e_i}.$ Thus, each number with $2^k$ divisors is a product of some $k$ values of the form ${p_i}^{2^j}$ for some prime $p_i$ and nonnegative integer $2^j.$ The minimal such number, therefore, will be the product of the least values in this form. Only problem is that we cannot multiply ${p_i}^{2^j}$ before ${p_i}^{2^k}$ if $j>k$ but this never happens because we are multiplying the minimal values.

Make a set with $p^{2^i}$, for primes $p$ and nonnegative $i$. It is easy to see that $f(2^k)$ is just the product of the first $k$ elements in this, so we have the desired.

Actually, compared to the N3-5s I've done with bashy diophantines, this one seems rather trivial. f(2^k) has the form \prod p_i^{2^{e_i}-1}=\prod_i (\prod_{j=0}^{e_i-1}p_i^{2^j}), with sum of all e_i=k; this is precisely the k smallest elements in the set S={p_i,p_i^2,p_i^4,...} over all i, which is obviously an integer when you take f(2^{k+1})/f(2^k). (I'll start posting latex one this stuff stops saying i am a new user because i delicately spent like 2 hours learning how to latex)

Denote $p_i$ as the $i$th largest prime number. Let $s_i = \{ p_i^{2^k-1} | k \in \mathbb{N} \}$. Consider the set $S = \cup_{i=1}^{\infty}s_i$. Note that $f(2^k)$ will be the product of the $k$ smallest numbers in the set $S$. Moreover, $f(2^{k+1})$ will be the product of the $k+1$ smallest numbers in the set $S$. So clearly $f(2^k) | f(2^{k+1})$.

Sagnik123Biswas wrote: Denote $p_i$ as the $i$th largest prime number. Let $s_i = \{ p_i^{2^k-1} | k \in \mathbb{N} \}$. Consider the set $S = \cup_{i=1}^{\infty}s_i$. Note that $f(2^k)$ will be the product of the $k$ smallest numbers in the set $S$. Moreover, $f(2^{k+1})$ will be the product of the $k+1$ smallest numbers in the set $S$. So clearly $f(2^k) | f(2^{k+1})$. What about exponent of primes

@Hayabusa1, why is $f(2^{k+1})=f(2^k)*p?$

We describe an algorithm to get $f(2^k)$. Algorithm: Consider the set $p^{2^i}$ over all primes $p$ and nonnegative integers $i$. We sort this set, and take the product of the first $k$ elements. Claim: This procedure results in something with $2^k$ factors. Proof: Consider adding a prime power $p^{2^i}$. If $i = 0$, we obviously multiply the number of divisors by $2$. Otherwise, the power of $p$ we have in the current product is $p^{2^i - 1}$, since we must have already added $p^{2^{i - 1}} \cdots p^{2^0}$, so the product after is $p^{2^{i + 1} - 1}$, so we multiplied the number of divisors by $2$. Claim: This results in the smallest number with $2^k$ factors. Proof: Assume there is something more optimal, we can write it as $\prod p_i^{2^{e_i} - 1} = \prod \prod_{0 \le j \le e_{i} - 1} p_i^{2^j}$, where there are necessarily $k$ elements in the final product since each one multiplies the number of divisors by $2$. Now each element of the product is part of the set described earlier, so we require each element to be the minimal one not taken yet, which just gives the same procedure as before. Now clearly going from $f(2^k)$ to $f(2^{k + 1})$ is just multiplying $f(2^k)$ by another element of the set, so we are done.

For any nonnegative integer $k$, note that there exist some positive integer $n$ and nonnegative integers $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$ for which \[f(2^k)=\prod_{i=1}^np_i^{2^{a_i}-1}\]and \[f(2^{k+1})=\prod_{i=1}^np_i^{2^{b_i}-1}.\]For all $m$, note that $g_{m,k}=f(2^{k+1})p_m^{-2^{b_m-1}}$ and $g_{m,k+1}=f(2^k)p_m^{2^{a_m}}$ respectively have $2^k$ and $2^{k+1}$ factors. Then by minimality $g_{m,k}g_{m,k+1}\ge f(2^k)f(2^{k+1})$, implying that $a_m\ge b_m-1$ for all $m$. In fact, as $\sum_{i=1}^n(b_i-a_i)=1$, there must exist some $m$ such that $a_m=b_m-1$ and thus $g_{m,k}g_{m,k+1}=f(2^k)f(2^{k+1})$. Again by minimality we have $g_{m,k}=f(2^k)$ and $g_{m,k+1}=f(2^{k+1})$, which implies that $f(2^k)\mid f(2^{k+1})$ as desired. $\blacksquare$