MathDB

1

Part of 2024 Brazil National Olympiad

Problems(2)

Find all a_1 that make the sequence eventually periodic, and all periods

Source: Brazilian Mathematical Olympiad 2024, Level 3, Problem 1

10/12/2024
Let a1 a_1 be an integer greater than or equal to 2. Consider the sequence such that its first term is a1 a_1 , and for an a_n , the n n -th term of the sequence, we have an+1=anpkek−1+1, a_{n+1} = \frac{a_n}{p_k^{e_k - 1}} + 1, where p1e1p2e2⋯pkek p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} is the prime factorization of an a_n , with 1<p1<p2<⋯<pk 1 < p_1 < p_2 < \cdots < p_k , and e1,e2,…,ek e_1, e_2, \dots, e_k positive integers.
For example, if a1=2024=23⋅11⋅23 a_1 = 2024 = 2^3 \cdot 11 \cdot 23 , the next two terms of the sequence are a2=a123−1+1=20244+1=2025=34⋅52; a_2 = \frac{a_1}{2^{3-1}} + 1 = \frac{2024}{4} + 1 = 2025 = 3^4 \cdot 5^2; a3=a252−1+1=20255+1=406. a_3 = \frac{a_2}{5^{2-1}} + 1 = \frac{2025}{5} + 1 = 406.
Determine for which values of a1 a_1 the sequence is eventually periodic and what all the possible periods are.
Note: Let p p be a positive integer. A sequence x1,x2,… x_1, x_2, \dots is eventually periodic with period p p if p p is the smallest positive integer such that there exists an N≥0 N \geq 0 satisfying xn+p=xn x_{n+p} = x_n for all n>N n > N .
SequencePeriodic sequenceprime factorizationnumber theory
sequence with prime factors

Source: Brazilian Mathematical Olympiad 2024, Level 2, Problem 1

10/12/2024
Consider a sequence whose first term is a given positive integer N>1 N > 1 . Consider the prime factorization of N N . If N N is a power of 2, the sequence consists of a single term: N N . Otherwise, the second term of the sequence is obtained by replacing the largest prime factor p p of N N with p+1 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=22⋅3⋅52 N = 300 = 2^2 \cdot 3 \cdot 5^2 , since its largest prime factor is p=5 p = 5 , the second term is 22⋅3⋅(5+1)2=24⋅33 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 p = 3 , so the third term is 24⋅(3+1)3=210 2^4 \cdot (3 + 1)^3 = 2^{10} . Since we obtained a power of 2, the sequence has 3 terms: 22⋅3⋅52 2^2 \cdot 3 \cdot 5^2 , 24⋅33 2^4 \cdot 3^3 , and 210 2^{10} .
a) How many terms does the sequence have if the first term is N=2⋅3⋅5⋅7⋅11⋅13⋅17⋅19⋅23 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 p leaves a remainder of 1 when divided by 3, then p+12 \frac{p+1}{2} is an integer that also leaves a remainder of 1 when divided by 3. c) Present an initial term N N less than 1,000,000 (one million) such that the sequence starting from N N has exactly 11 terms.
number theoryprime factorizationSequence