IMO Shortlist 2011, Number Theory 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Jul 11, 2012, 10:25 PM • 12 Y

Y by Davi-8191, nhusanboev, anantmudgal09, samrocksnature, megarnie, jhu08, JarJarBinks, ImSh95, Resolut1on07, Adventure10, Mango247, Sedro

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ropro01

62 posts

ropro01

#2 h Jul 12, 2012, 10:36 AM • 4 Y

Y by jhu08, ImSh95, kamatadu, Adventure10

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

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

daniel73

253 posts

daniel73

#3 h Jul 12, 2012, 10:43 AM • 3 Y

Y by jhu08, ImSh95, Adventure10

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:

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jgnr

1343 posts

jgnr

#4 h Jul 12, 2012, 4:41 PM • 3 Y

Y by jhu08, ImSh95, Adventure10

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}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

siddigss

224 posts

siddigss

#5 h Jul 12, 2012, 4:56 PM • 5 Y

Y by jhu08, ImSh95, Adventure10, Mango247, and 1 other user

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\}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

daniel73

253 posts

daniel73

#6 h Jul 12, 2012, 10:01 PM • 17 Y

Y by yiwen, Imayormaynotknowcalculus, qubatae, hakN, jhu08, Kobayashi, ImSh95, ThisNameIsNotAvailable, maths_arka, Adventure10, Mango247, ihatemath123, and 5 other users

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ardentedu

4 posts

ardentedu

#7 h Jul 22, 2012, 5:57 PM • 30 Y

Y by iarnab_kundu, thunderz28, mkhayech, anantmudgal09, FISHMJ25, veehz, AlastorMoody, Imayormaynotknowcalculus, SnowPanda, Aimingformygoal, hakN, Pratik12, tigerzhang, jhu08, Wizard0001, Kobayashi, ImSh95, ike.chen, Adventure10, Mango247, Sedro, ihatemath123, and 8 other users

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

leader

339 posts

leader

#8 h Apr 21, 2014, 1:17 PM • 6 Y

Y by PRO2000, MathbugAOPS, jhu08, ImSh95, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SmartClown

82 posts

SmartClown

#9 h Sep 9, 2014, 6:44 PM • 5 Y

Y by Carnivore, GammaBetaAlpha, jhu08, ImSh95, Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sayantanchakraborty

505 posts

sayantanchakraborty

#10 h Jan 6, 2015, 3:45 PM • 4 Y

Y by Carnivore, jhu08, ImSh95, Adventure10

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}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kezer

986 posts

Kezer

#12 h Aug 21, 2016, 11:53 AM • 4 Y

Y by jhu08, ImSh95, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathemator_13

42 posts

Mathemator_13

#13 h May 9, 2017, 10:20 AM • 3 Y

Y by jhu08, ImSh95, Adventure10

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

This post has been edited 1 time. Last edited by Mathemator_13, May 9, 2017, 10:21 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

omarius

91 posts

omarius

#14 h Nov 5, 2017, 6:07 AM • 4 Y

Y by jhu08, ImSh95, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

abbosjon2002

114 posts

abbosjon2002

#15 h Jan 18, 2018, 6:56 AM • 4 Y

Y by jhu08, ImSh95, Adventure10, Mango247

who has easier solution?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ThE-dArK-lOrD

4071 posts

ThE-dArK-lOrD

#16 h Jan 18, 2018, 4:29 PM • 4 Y

Y by jhu08, ImSh95, Adventure10, Mango247

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.

This post has been edited 1 time. Last edited by ThE-dArK-lOrD, Apr 12, 2019, 11:30 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomehuman

496 posts

awesomehuman

#42 h May 1, 2022, 1:22 AM • 2 Y

Y by ImSh95, Mango247

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.

This post has been edited 4 times. Last edited by awesomehuman, May 1, 2022, 1:52 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7586 posts

asdf334

#43 h Jun 30, 2022, 5:32 PM • 1 Y

Y by Sagnik123Biswas

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ETS1331

107 posts

ETS1331

#44 h Jul 5, 2022, 10:30 PM • 1 Y

Y by pokpokben

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)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lrjr24

966 posts

lrjr24

#45 h Jul 9, 2022, 4:03 PM

Y by

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.

This post has been edited 1 time. Last edited by lrjr24, Jul 20, 2022, 10:46 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1683 posts

awesomeming327.

#46 h Jul 14, 2022, 4:08 AM • 2 Y

Y by Mango247, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

brainfertilzer

1831 posts

brainfertilzer

#47 h Jul 20, 2022, 9:15 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Hayabusa1

478 posts

Hayabusa1

#48 h Jul 26, 2022, 12:58 AM • 2 Y

Y by Mango247, Mango247

sol

This post has been edited 1 time. Last edited by Hayabusa1, Jul 26, 2022, 12:58 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bobthegod78

2982 posts

bobthegod78

#49 h Apr 27, 2023, 11:06 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

signifance

140 posts

signifance

#50 h Sep 18, 2023, 12:18 AM

Y by

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)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sagnik123Biswas

419 posts

Sagnik123Biswas

#51 h May 4, 2024, 8:45 AM

Y by

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})$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MELSSATIMOV40

29 posts

MELSSATIMOV40

#52 h Jun 18, 2024, 4:19 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pokpokben

17 posts

pokpokben

#53 h Jun 29, 2024, 1:38 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1251 posts

ezpotd

#54 h Aug 31, 2024, 6:37 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

smileapple

1010 posts

smileapple

#56 h Dec 25, 2024, 9:07 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Zany9998

10 posts

Zany9998

#57 h Mar 30, 2025, 3:59 PM

Y by

Let's begin by considering the following problem first .We have a list of $n$ positive reals $(x_1,x_2,\dots,x_n)$ and a non-negative integer $k$ . We have to multiply each $x_i$ with a number $2^{a_i}$ where $a_i \in \mathbb{N}_0$ and
$\sum_{i=1}^{i=n} a_i = k$ such that the resulting sum of the list is minimized.
Lemma:
In order to minimize the sum the simple greedy algorithm is followed $k$ times. Choose the smallest number in the list, let its index be $t$ , then multipy the number at index $t$ with 2. The list at the end is the list with minimum sum.

Proof:
WLOG sort the list first, then
first of all notice that for each $k$ there exists a solution with list of coefficients $(2^{a_1},2^{a_2},\dots,2^{a_n})$ with $a_1 \geq a_2 \geq a_3 \geq \dots \geq a_n$ . This is because if for some solution we have a $j$ s.t. $a_j < a_{j+1}$ then we can swap $a_j$ and $a_{j+1}$ and get a solution whose sum that's not greater than original sum, we can follow the given step until the list is sorted in descending order.

Now notice that the resulting list with this greedy algorithm will be a list where each number is multiplied with some $2^{\alpha_i}$ where $\sum_{i=1}^{i=n} \alpha_i = k$ . Let's prove it is the minimum such sum. First of all notice that if $k<2$ , then the following greedy algorithm results to the list with minimum sum. Now let's suppose for the sake of induction that the greedy algorithm always helps us find the list with minimum sum for all $k < m$ where $m \geq 2$ then the coefficient of $x_1$ in a solution will be $2^{a_1}$ where $a_1 \geq 1$ , $($ because there exists a solution with $a_1 \geq a_2 \geq a_3 \geq \dots \geq a_n)$ . This implies that if we have a list $(2x_1,x_2,\dots,x_n)$ and we need to find its minimum sum for $k=m-1$ then the resulting list's sum will be equal to the sum of our solution's list. But note that we can apply greedy algorithm here to form a list with minimum sum. But now note that in our first step we will convert our list to $(2x_1,x_2,\dots,x_n)$ and after that if we apply the greedy algo $k-1$ times we will get the same exact list with minimum sum. QED

Now for the original proof note that $f(2^k)$ can only have at most $k$ distinct prime factors, note that if it contains $t$ prime factors then these prime factors are exactly first $t$ primes (otherwise we can replace a bigger prime with a smaller prime and make the number smaller).
Hence for both $f(2^k)$ and $f(2^{k+1})$ we will have prime factors from first $k+1$ smallest primes $(p_0,p_1,\dots,p_k)$ . Now note that $f(2^t)$ for $t \leq k+1$ is the minimum number of form $\prod_{i=0}^{i=k}p_i^{ (2^{a_i})-1}$ such that $\sum_{i=0}^{i=k} a_i = t$ . This is equivalent to minimising $\prod_{i=0}^{i=k}p_i^{ 2^{a_i}}$ such that $\sum_{i=0}^{i=k} a_i = t$ . Now minimising it is equivalent to minimising $\sum_{i=0}^{i=k}2^{a_i}log(p_i)$ . Now note that considering the list $(log(p_1),log(p_2),\dots,log(p_n))$ in the lemma we get that greedy algorithm will minimize the following sum . Now note that $\sum_{i=0}^{i=k}2^{a_i}log(p_i)$ for $\sum_{i=0}^{i=k} a_i = t$ is minimized by the greedy algorithm and for $t+1$ our greedy algorithm will obviously have greater coefficients for each $p_i$ , this implies that $f(2^t)|f(2^{t+1})$ for all $t$ . QED

Z K Y