Consider a sequence whose first term is a given positive integer \( N > 1 \). Consider the prime factorization of \( N \). If \( N \) is a power of 2, the sequence consists of a single term: \( N \). Otherwise, the second term of the sequence is obtained by replacing the largest prime factor \( p \) of \( N \) with \( p + 1 \) in the prime factorization. If the new number is not a power of 2, we repeat the same procedure with it, remembering to factor it again into primes. If it is a power of 2, the numerical sequence ends. And so on. For example, if the first term of the sequence is \( N = 300 = 2^2 \cdot 3 \cdot 5^2 \), since its largest prime factor is \( p = 5 \), the second term is \( 2^2 \cdot 3 \cdot (5 + 1)^2 = 2^4 \cdot 3^3 \). Repeating the procedure, the largest prime factor of the second term is \( p = 3 \), so the third term is \( 2^4 \cdot (3 + 1)^3 = 2^{10} \). Since we obtained a power of 2, the sequence has 3 terms: \( 2^2 \cdot 3 \cdot 5^2 \), \( 2^4 \cdot 3^3 \), and \( 2^{10} \). a) How many terms does the sequence have if the first term is \( N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \)? b) Show that if a prime factor \( p \) leaves a remainder of 1 when divided by 3, then \( \frac{p+1}{2} \) is an integer that also leaves a remainder of 1 when divided by 3. c) Present an initial term \( N \) less than 1,000,000 (one million) such that the sequence starting from \( N \) has exactly 11 terms.
Problem
Source: Brazilian Mathematical Olympiad 2024, Level 2, Problem 1
Tags: number theory, prime factorization, Sequence
13.10.2024 00:10
a) Operating with the sequence: $2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23 \rightarrow 2^4\cdot3^2\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19 \rightarrow 2^6\cdot3^2\cdot5^2\cdot7\cdot11\cdot13\cdot17 \rightarrow 2^7\cdot3^4\cdot5^2\cdot7\cdot11\cdot13 \rightarrow 2^8\cdot3^4\cdot5^2\cdot7^2\cdot11 \rightarrow 2^{10}\cdot3^5\cdot5^2\cdot7^2 \rightarrow 2^{16}\cdot3^5\cdot5^2 \rightarrow 2^{18}\cdot3^7 \rightarrow 2^{32}.$ Totalizing $9$ terms. b) First, we rule out the possibility that $p$ is even, since $2$ is the only even prime and $2$ doesn´t leave $1$ when divided by $3$. Therefore, let $p=2q-1$, $q\in \mathcal{Z}$. But, $p=2q-1\equiv1$(mod $3$)$ \Rightarrow 2q\equiv2$(mod $3$). So, as $mdc(2,3)=1$, $\frac{p+1}{2}=q\equiv1$(mod $3$), Q.E.D. c) The number $N=636.779$ satisfies the statement, since $636.779<1.000.000$ and the sequence for this value of $N$ is: $11\cdot13\cdot61\cdot73 \rightarrow 2\cdot11\cdot13\cdot37\cdot61 \rightarrow 2^2\cdot11\cdot13\cdot31\cdot37 \rightarrow 2^3\cdot11\cdot13\cdot19\cdot31 \rightarrow 2^8\cdot11\cdot13\cdot19 \rightarrow 2^{10}\cdot5\cdot11\cdot13 \rightarrow 2^{11}\cdot5\cdot7\cdot11 \rightarrow 2^{13}\cdot3\cdot5\cdot7 \rightarrow 2^{16}\cdot3\cdot5 \rightarrow 2^{17}\cdot3^2 \rightarrow 2^{21}$ Totalizing 11 terms.
13.10.2024 06:30
the original b) asked for $\frac{p+1}{2}$
13.10.2024 14:14
lksb wrote: the original b) asked for $\frac{p+1}{2}$ Fixed