Number theoryDifficulty 5.6AIME, harderFind the answer
For positive integers a and b, let M(a,b)=gcd(a,b)lcm(a,b), and for each positive integer n≥2, define xn=M(1,M(2,M(3,…,M(n−2,M(n−1,n))…))) Compute the number of positive integers n such that 2≤n≤2021 and 5xn2+5xn+12=26xnxn+1.
A number or a short expression. Spacing and $ signs are ignored.
Solution
The desired condition is that xn=5xn+1 or xn+1=5xn. Note that for any prime p, we have νp(M(a,b))=∣νp(a)−νp(b)∣. Furthermore, νp(M(a,b))≡νp(a)+νp(b)mod2. So, we have that νp(xn)≡νp(1)+νp(2)+⋯+νp(n)mod2 Subtracting gives that νp(xn+1)−νp(xn)≡νp(n+1)mod2. In particular, for p=5,νp(n+1) must be even, and ν5(n+1) must be odd. So n+1 must be a 5 times a perfect square. There are ⌊52021⌋=20 such values of n in the interval [2, 2021]. Now we show that it is sufficient for n+1 to be 5 times a perfect square. The main claim is that if B>0 and a sequence a1,a2,…,aB of nonnegative real numbers satisfies an≤B+∑i<nai for all 1≤n≤N, then ∣a1−∣a2−∣⋯−∣aN−1−aN∣∣⋯∣∣≤B This can be proved by a straightforward induction on N. We then apply this claim, with B=1, to the sequence ai=νp(i); it is easy to verify that this sequence satisfies the condition. This gives νp(xn)=∣νp(1)−∣νp(2)−∣⋯−∣νp(n−1)−νp(n)∣∣⋯∣∣≤1 so νp(xn) must be equal to (νp(1)+⋯+νp(n))mod2. Now suppose n+1=5k2 for some k; then νp(n+1)≡0mod2 for p=5 and ν5(n+1)≡1mod2. Therefore νp(xn+1)=νp(xn) for p=5, and ν5(xn+1)=(ν5(xn)+1)mod2, and this implies xn+1/xn∈{1/5,5} as we wanted.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: Omni-MATH,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.