For an integer n, σ(n) denotes the sum of postitive divisors of n. A sequence of positive integers (ai)∞i=0 with a0=1 is defined as follows: For each n>1, an is the smallest integer greater than 1 that satisfies σ(a0a1…an−1)|σ(a0a1…an).Determine the number of divisors of 20242024 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 p2n 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 a0,a1,a2,⋯. After this, you can see that there are 1+13+11+11=36 numbers in the sequence ai dividing the number 26072⋅112024⋅132024=20242024.
hakN
19.03.2024 12:08
It is easy to compute that a1=2,a3=3,a4=4 and a5=5. We prove by induction that all numbers appear at most once, and all terms are of the form p2m where p is a prime and m≥0, furthermore if an=p2m, then all numbers p2i for 0≤i≤m−1 occur among a0,a1,…,an−1.
Suppose it's true for values smaller than n. By induction hypothesis, we can let a0a1…an−1=p2α1−11⋯p2αℓ−1ℓ where pi are distinct primes and αi≥1.
If there exists a prime p∣an with p≠pi for all i, then an=p and claim holds.
Let an=pθ11⋯pθtt where t≤ℓ and θi≥1. If t=1, we have p2α11−1∣p2α1+θ11−1, which implies 2α1∣θ1, so θ1≥2α1. Further, θ1=2α1 satisfies, so an=p2α11 and claim holds.
Suppose t≥2. If there exists θi≥2αi, then an=p2αii works, contradiction. Suppose θi<2αi for all i. By the condition we have (p2α11−1)⋯(p2αtt−1)∣(p2α1+θ11−1)⋯(p2αt+θtt−1). For all odd x and θ≥1, v2(x2θ−1)=v2(x−1)+v2(x+1)+θ−1, comparing the v2 on both sides, we obtain v2(2αi+θi)≥αi for some i, thus θi≥2αi, contradiction, induction is complete.
If there exists a number of the form p2m which does not occur in the sequence, let it be k=p2m with m minimal, so all p2i with 0≤i≤m−1 occur in the sequence. Since the sequence is unbounded, there exists large n with an>k, but an=k also satisfies the condition, contradiction.
Thus, our answer is 1+13+11+11=36 since 20242024=26072⋅112024⋅232024.
starchan
23.03.2024 04:11
very cute problem
We call a number nice if it is of the form p2ifor a prime p and nonnegative integer i≥0.
Claim: The sequence a1,a2,… is precisely the nice numbers in increasing order.
Proof: We induct on k to show that the numbers a1,a2,…,ak are precisely the first k nice numbers in increasing order. We note that this is true for k=1, as one has a1=220, 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 kth smallest nice number is p2u for some prime p and u≥0. From the inductive hypotheses, we see that for all pairs (q,m) with q2m<p2u and q prime with m≥0, the term q2m is multiplied in the expression a0a1…an−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 p1<p2<⋯<pv and 0≤m1,m2,…,mv: M def =a0a1…ak−1=v∏i=1p2mi−1iSuppose that ak≠p2u. There are two cases to consider:
Case 1: ak>p2u
By minimality, this implies that N=p2u does not fit as a valid ak in the kth step. If p=pi for some i, then we see that we necessarily have mi=u (from an earlier discussion). In particular, we have σ(MN)σ(M)=σ(p2u+1−1i)σ(p2u−1i)=p2ui+1In particular, we have σ(M)∣σ(MN), contradicting the minimality of ak. On the other hand, if p≠pi for any i, then we must have u=0 and gcd. 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 - 1On 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) - 1In 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 = 36which 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}.