For an integer $n$, $\sigma(n)$ denotes the sum of postitive divisors of $n$. A sequence of positive integers $(a_i)_{i=0}^{\infty}$ with $a_0 =1$ is defined as follows: For each $n>1$, $a_n$ is the smallest integer greater than $1$ that satisfies $$\sigma{(a_0a_1\dots a_{n-1})} \vert \sigma{(a_0a_1\dots a_{n})}.$$Determine the number of divisors of $2024^{2024}$ amongst the sequence.
Problem
Source: 2024 Turkey TST P8
Tags: number theory
BarisKoyuncu
19.03.2024 12:01
sketch: (will add the details later) Consider all the numbers in the form $p^{2^n}$ where $p$ is a prime number and $n$ is a nonnegative integer. Rearrange these in increasing order and show that this sequence is the same as $a_0, a_1, a_2, \cdots$. After this, you can see that there are $1+13+11+11=36$ numbers in the sequence $a_i$ dividing the number $2^{6072}\cdot 11^{2024}\cdot 13^{2024}=2024^{2024}$.
hakN
19.03.2024 12:08
It is easy to compute that $a_1=2, a_3=3,a_4=4$ and $a_5=5$. We prove by induction that all numbers appear at most once, and all terms are of the form $p^{2^m}$ where $p$ is a prime and $m\ge 0$, furthermore if $a_n=p^{2^m}$, then all numbers $p^{2^i}$ for $0\le i\le m-1$ occur among $a_0,a_1,\dots,a_{n-1}$.
Suppose it's true for values smaller than $n$. By induction hypothesis, we can let $a_0a_1\dots a_{n-1} = p_1^{2^{\alpha_1}-1}\cdots p_{\ell}^{2^{\alpha_{\ell}}-1}$ where $p_i$ are distinct primes and $\alpha_i\ge 1$.
If there exists a prime $p\mid a_n$ with $p\neq p_i$ for all $i$, then $a_n=p$ and claim holds.
Let $a_n=p_1^{\theta_1}\cdots p_t^{\theta_t}$ where $t\le \ell$ and $\theta_i\ge 1$. If $t=1$, we have $p_1^{2^{\alpha_1}}-1 \mid p_1^{2^{\alpha_1}+\theta_1}-1$, which implies $2^{\alpha_1} \mid \theta_1$, so $\theta_1\ge 2^{\alpha_1}$. Further, $\theta_1=2^{\alpha_1}$ satisfies, so $a_n=p_1^{2^{\alpha_1}}$ and claim holds.
Suppose $t\ge 2$. If there exists $\theta_i\ge 2^{\alpha_i}$, then $a_n=p_i^{2^{\alpha_i}}$ works, contradiction. Suppose $\theta_i<2^{\alpha_i}$ for all $i$. By the condition we have $(p_1^{2^{\alpha_1}}-1)\cdots (p_t^{2^{\alpha_t}}-1) \mid (p_1^{2^{\alpha_1}+\theta_1}-1)\cdots (p_t^{2^{\alpha_t}+\theta_t}-1)$. For all odd $x$ and $\theta\ge 1$, $v_2(x^{2^{\theta}}-1)=v_2(x-1)+v_2(x+1)+\theta-1$, comparing the $v_2$ on both sides, we obtain $v_2(2^{\alpha_i}+\theta_i)\ge \alpha_i$ for some $i$, thus $\theta_i\ge 2^{\alpha_i}$, contradiction, induction is complete.
If there exists a number of the form $p^{2^m}$ which does not occur in the sequence, let it be $k=p^{2^m}$ with $m$ minimal, so all $p^{2^i}$ with $0\le i\le m-1$ occur in the sequence. Since the sequence is unbounded, there exists large $n$ with $a_n>k$, but $a_n=k$ also satisfies the condition, contradiction.
Thus, our answer is $1+13+11+11=36$ since $2024^{2024}=2^{6072}\cdot 11^{2024}\cdot 23^{2024}$.
starchan
23.03.2024 04:11
very cute problem
We call a number nice if it is of the form \[p^{2^{i}}\]for a prime $p$ and nonnegative integer $i \geq 0$.
Claim: The sequence $a_1, a_2, \dots$ is precisely the nice numbers in increasing order.
Proof: We induct on $k$ to show that the numbers $a_1, a_2, \dots, a_k$ are precisely the first $k$ nice numbers in increasing order. We note that this is true for $k = 1$, as one has $a_1 = 2^{2^{0}}$, which is indeed the smallest nice number.
Suppose now that the result has been true for $k' < k$, and we would like to prove it for $k$. Suppose the $k$th smallest nice number is $p^{2^u}$ for some prime $p$ and $u \geq 0$. From the inductive hypotheses, we see that for all pairs $(q, m)$ with $q^{2^m} < p^{2^u}$ and $q$ prime with $m \geq 0$, the term $q^{2^m}$ is multiplied in the expression $a_0a_1\dots a_{n-1}$. In particular, for each prime $q$, there is a contigous list of numbers $m$ starting from $0$ to be considered in the product.
It follows that the product is of the following form, for some appropriate $p_1 < p_2 < \dots < p_v$ and $0 \leq m_1, m_2, \dots, m_v$: \[M \overset{\text{ def }}{=} a_0a_1\dots a_{k-1} = \prod \limits_{i = 1}^{v} p_i^{2^{m_i}-1}\]Suppose that $a_k \ne p^{2^u}$. There are two cases to consider:
Case 1: $a_k > p^{2^u}$
By minimality, this implies that $N = p^{2^u}$ does not fit as a valid $a_k$ in the $k$th step. If $p = p_i$ for some $i$, then we see that we necessarily have $m_i = u$ (from an earlier discussion). In particular, we have \[\frac{\sigma(MN)}{\sigma(M)} = \frac{\sigma(p_i^{2^{u+1}-1})}{\sigma(p_i^{2^{u}-1})} = p_i^{2^u}+1\]In particular, we have $\sigma(M) \mid \sigma(MN)$, contradicting the minimality of $a_k$. On the other hand, if $p \ne p_i$ for any $i$, then we must have $u = 0$ and $\gcd(p, N) = 1$. But then we again must have had $\sigma(M) \mid \sigma(MN)$ due to the multiplicativity of $\sigma$.
Case 2: $a_k < p^{2^u}$.
Write \[a_k = q_1^{e_1}q_2^{e_2}\dots q_x^{e_x}\]for primes $q_i$ and nonnegative integers $e_i$. Suppose there is some $q_j$ distinct from all the $p_i$. Then we have $\gcd(M, q_j) = 1$. In particular, $q_j$ satisfies the condition (from the multiplicativity of $\sigma$) and therefore we must have $a_k = q_j$. But now $a_k$ is a nice number. If it is less than $p^{2^u}$, and had yet not appeared in the $p_i$, it would have been the next nice number in order, instead of $p^{2^u}$; contradiction.
Thus each $q_j$ is part of the $p_i$. Note that primes $p_i$ not among the $q_j$ do not affect the $\sigma$ divisibility criterion (due to multiplicativity) and thus we can restrict $M$ to only the primes $q_j$. Suppose \[M' = \prod \limits_{i = 1}^{x} q_i^{2^{m_i}-1}\]From a similar argument as earlier, we can see that we must have $e_i \leq 2^{m_i}-1$ for all $i$. The condition that $\sigma(M') \mid \sigma(M'N)$ is the same as requiring \[\prod \limits_{i = 1}^{x} (q_i^{2^{m_i}}-1) \mid \prod \limits_{i = 1}^{x} (q_i^{2^{m_i}+e_i}-1) \qquad (1)\]There are two cases to consider here:
Case 1: There are odd primes among the $q_i$.
Proof: In this case, we compare the $\nu_2$ of both sides above. For a fixed $i$, we have \[\nu_2\left(q_i^{2_{m_i}}-1\right) = \nu_2\left(q_i^2-1\right) + m_i - 1\]On the other hand, $\nu_2\left(q^{2^{m_i}+e_i}-1\right)$ is equal to either \[\nu_2(q-1) \text{ or } \nu_2(q^2-1) + \nu_2(2^{m_i}+e_i) - 1\]In either case, we see that one has $\nu_2\left(q^{2^{m_i}+e_i}-1\right) < \nu_2\left(q_i^{2_{m_i}}-1\right)$. This is because $e_i < 2^{m_i}$.
Summing over all $i$, we see that the left hand side in $(1)$ has a greater $\nu_2$-valuation then the right side, contradiction.
Case 2: There is only one $q_i$, and it is equal to $2$.
In this case we have $2^{2^{m_1}}-1 \mid 2^{2^{m_1}+e_1}-1$. This implies that $2^{2^{m_1}-1} \mid 2^{e_1}-1$ and we get $e_1 \geq 2^{m_1}$ by size, impossible yet again.
Combining all that we have seen above, we see that $a_k$ must indeed be the next nice number. $\square$
The rest of the problem is merely answer extraction. We have \[2024^{2024} = 2^{6072} \cdot 11^{2024} \cdot 23^{2024}\]and hence the required count is \[1 + \left(\lfloor \log_2(6072) \rfloor + 1\right) + 2 \left(\lfloor \log_2(2024)\rfloor + 1\right) = 1+13+22 = 36\]which is the desired answer. $\square$
math_comb01
23.03.2024 12:38
cute!
We claim that the answer is $\boxed{36}$
The following algorithm to choose next number clearly works:
1. Say we are on $(1+2+4 \cdots 2^{a_1})(1+3+ \cdots 3^{a_2})\cdots(1+p_i+\cdots p^{a_i})$
2. Check the closest number such that it is of form $p_t^{2(a_t+1)}$ and the closest next prime
3. whichever is closer choose that and repeat
This shows that all numbers of the form $p^{2^m}$ are covered, now it is easy to calculate the answer.
The algorithm can be replaced with induction (as usual) + some standard $v_2$ LTE arguments are needed both to prove the algorithm works and the induction works.
alba_tross1867
30.10.2024 23:37
Computing first terms give $(2,3,4,5...)$. Motivated by the multiplicative proprety of $\sigma$ function, we find that at the rank $n$ multiplying by the smallest number coprime with $\prod a_{i}$ ( let that be $C$ ) will give $\sigma(\prod a_i) | \sigma(\prod a_i \cdot C )$. By minimality of $C$ it must be a prime number (look at divisors ). We conclude then that the set of primes in the sequence in a contiguous segment of primes. On another side when we add a power of prime we get $p^{\alpha_p}-1 | p^{\alpha_p + x}-1$ then $\alpha_p | x $ thus $x=\alpha_p$ is minimal which gives the sequence of $x$ (1,2,4... ) generally $2^t$ thus the motivation comes to prove that all terms of the sequence are of the form $p^{2^i}$.