It's February and we'd love to help you find the right course plan!

G
Topic
First Poster
Last Poster
k a February Highlights and 2025 AoPS Online Class Information
jlacosta   0
Feb 2, 2025
We love to share what you can look forward to this month! The AIME I and AIME II competitions are happening on February 6th and 12th, respectively. Join our Math Jams the day after each competition where we will go over all the problems and the useful strategies to solve them!

2025 AIME I Math Jam: Difficulty Level: 8* (Advanced math)
February 7th (Friday), 4:30pm PT/7:30 pm ET

2025 AIME II Math Jam: Difficulty Level: 8* (Advanced math)
February 13th (Thursday), 4:30pm PT/7:30 pm ET

The F=ma exam will be held on February 12th. Check out our F=ma Problem Series course that begins February 19th if you are interested in participating next year! The course will prepare you to take the F=ma exam, the first test in a series of contests that determines the members of the US team for the International Physics Olympiad. You'll learn the classical mechanics needed for the F=ma exam as well as how to solve problems taken from past exams, strategies to succeed, and you’ll take a practice F=ma test of brand-new problems.

Mark your calendars for all our upcoming events:
[list][*]Feb 7, 4:30 pm PT/7:30pm ET, 2025 AIME I Math Jam
[*]Feb 12, 4pm PT/7pm ET, Mastering Language Arts Through Problem-Solving: The AoPS Method
[*]Feb 13, 4:30 pm PT/7:30pm ET, 2025 AIME II Math Jam
[*]Feb 20, 4pm PT/7pm ET, The Virtual Campus Spring Experience[/list]
AoPS Spring classes are open for enrollment. Get a jump on 2025 and enroll in our math, contest prep, coding, and science classes today! Need help finding the right plan for your goals? Check out our recommendations page!

Don’t forget: Highlight your AoPS Education on LinkedIn!
Many of you are beginning to build your education and achievements history on LinkedIn. Now, you can showcase your courses from Art of Problem Solving (AoPS) directly on your LinkedIn profile! Don't miss this opportunity to stand out and connect with fellow problem-solvers in the professional world and be sure to follow us at: https://www.linkedin.com/school/art-of-problem-solving/mycompany/ Check out our job postings, too, if you are interested in either full-time, part-time, or internship opportunities!

Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1
Monday, Feb 3 - May 19
Sunday, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10

Prealgebra 1 Self-Paced

Prealgebra 2
Sunday, Feb 16 - Jun 8
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10

Prealgebra 2 Self-Paced

Introduction to Algebra A
Sunday, Feb 16 - Jun 8 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)
Sunday, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28

Introduction to Algebra A Self-Paced

Introduction to Counting & Probability
Sunday, Feb 9 - Apr 27 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2

Introduction to Counting & Probability Self-Paced

Introduction to Number Theory
Sunday, Feb 16 - May 4
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3

Introduction to Algebra B
Thursday, Feb 13 - May 29
Sunday, Mar 2 - Jun 22
Monday, Mar 17 - Jul 7
Wednesday, Apr 16 - Jul 30

Introduction to Algebra B Self-Paced

Introduction to Geometry
Friday, Feb 14 - Aug 1
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1

Intermediate: Grades 8-12

Intermediate Algebra
Wednesday, Feb 12 - Jul 23
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13

Intermediate Counting & Probability
Monday, Feb 10 - Jun 16
Sunday, Mar 23 - Aug 3

Intermediate Number Theory
Thursday, Feb 20 - May 8
Friday, Apr 11 - Jun 27

Precalculus
Tuesday, Feb 25 - Jul 22
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21

Calculus
Friday, Feb 28 - Aug 22
Sunday, Mar 30 - Oct 5

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Tuesday, Feb 4 - Apr 22
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2

MATHCOUNTS/AMC 8 Advanced
Sunday, Feb 16 - May 4
Friday, Apr 11 - Jun 27

AMC 10 Problem Series
Sunday, Feb 9 - Apr 27
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23

AMC 10 Final Fives
Sunday, Feb 9 - Mar 2 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)

AMC 12 Problem Series
Sunday, Feb 23 - May 11

AMC 12 Final Fives
Sunday, Feb 9 - Mar 2 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)

Special AIME Problem Seminar B
Sat & Sun, Feb 1 - Feb 2 (4:00 - 7:00 pm ET/1:00 - 4:00 pm PT)

F=ma Problem Series
Wednesday, Feb 19 - May 7

Programming

Introduction to Programming with Python
Sunday, Feb 16 - May 4
Monday, Mar 24 - Jun 16

Intermediate Programming with Python
Tuesday, Feb 25 - May 13

USACO Bronze Problem Series
Thursday, Feb 6 - Apr 24

Physics

Introduction to Physics
Friday, Feb 7 - Apr 25
Sunday, Mar 30 - Jun 22

Physics 1: Mechanics
Sunday, Feb 9 - Aug 3
Tuesday, Mar 25 - Sep 2

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
0 replies
jlacosta
Feb 2, 2025
0 replies
P6 Geo Finale
math_comb01   7
N 2 minutes ago by GuvercinciHoca
Source: XOOK 2025/6
Let $ABC$ be a triangle with incenter $I$ and excenters $I_A$, $I_B$, $I_C$ opposite to $A,B,C$ respectively. Suppose $BC$ meets the circumcircle of $I_AI_BI_C$ at points $D$ and $E$. $X$ and $Y$ lie on the incircle of $\triangle ABC$ so that $DX$ and $EY$ are tangents to the incircle (different from $BC$). Prove that the circumcircles of $\triangle AXY$ and $\triangle ABC$ are tangent.

Proposed by Anmol Tiwari
7 replies
math_comb01
Feb 10, 2025
GuvercinciHoca
2 minutes ago
A functional equation
super1978   1
N 13 minutes ago by pco
Source: Somewhere
Find all functions $f: \mathbb R \to \mathbb R$ such that:$$ f(f(y-x)-xf(y))+f(x)=y(1-f(x)) $$for all $x,y \in \mathbb R$
1 reply
super1978
an hour ago
pco
13 minutes ago
Sequences Handout
M11100111001Y1R   4
N 17 minutes ago by MR.1
Source: Own
Hi everyone, I wrote this handout about sequences in NT.
Hope you enjoy!
4 replies
+2 w
M11100111001Y1R
Oct 19, 2022
MR.1
17 minutes ago
[Handout] 50 non-traditional functional equations
gghx   2
N 44 minutes ago by GreekIdiot
Sup guys,

I'm retired. I love FEs. So here's 50 of them. Yea...

Functional equations have been one of the least enjoyed topics of math olympiads in recent times, mostly because so many techniques have been developed to just bulldoze through them. These chosen problems do not fall in that category - they require some combi-flavoured creativity to solve (to varying degrees).

For this reason, this handout is aimed at more advanced problem solvers who are bored of traditional FEs and are up for a little challenge!

In some sense, this is dedicated to the "covid FE community" on AoPS who got me addicted to FEs, people like EmilXM, hyay, IndoMathXdZ, Functional_equation, GorgonMathDota, BlazingMuddy, dangerousliri, Mr.C, TLP.39, among many others: thanks guys :). Lastly, thank you to rama1728 for suggestions and proofreading.

Anyways...
2 replies
gghx
Sep 23, 2023
GreekIdiot
44 minutes ago
No more topics!
NT from Ukrainian TST
mshtand1   20
N Jan 9, 2025 by math004
Source: Ukrainian TST for IMO 2021 P4
Initially, some positive integer greater than 1 is written on the board. Every second one erases number $n$ written on the board at this moment and writes number $n + \dfrac{n}{p}$ where $p$ is some prime divisor of $n$ and this process lasts indefinitely. Prove that number $3$ was chosen as a prime number $p$ infinitely many times.
Proposed by Mykhailo Shtandenko
20 replies
mshtand1
May 2, 2021
math004
Jan 9, 2025
NT from Ukrainian TST
G H J
G H BBookmark kLocked kLocked NReply
Source: Ukrainian TST for IMO 2021 P4
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mshtand1
44 posts
#1 • 5 Y
Y by HWenslawski, Didier, megarnie, PRMOisTheHardestExam, Aryan-23
Initially, some positive integer greater than 1 is written on the board. Every second one erases number $n$ written on the board at this moment and writes number $n + \dfrac{n}{p}$ where $p$ is some prime divisor of $n$ and this process lasts indefinitely. Prove that number $3$ was chosen as a prime number $p$ infinitely many times.
Proposed by Mykhailo Shtandenko
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cadaeibf
700 posts
#2 • 5 Y
Y by HWenslawski, Mango247, Mango247, Mango247, PRMOisTheHardestExam
Let the sequence of the numbers be $x_n$, and define $x_n=3^{k_n}2^{l_n}y_n=3^{k_n}a_nb_n$ where if $p$ is prime and it divides $a_n$ it is $\equiv 1\pmod 3$ and if it divides $b_n$ then it is $\equiv 2\pmod 3$(and $p>2$). We want to prove that from any starting point eventually $y_n=1$. Since $2|p+1$ for any odd primes and the primes we divide by are all $\geq 5$, $y_n$ is multiplied by a factor $\leq \frac{1}{2}\left(1+\frac{1}{5}\right)=\frac{3}{5}<1$. Therefore eventually $y_n=1$. At this point, if we choose $p=2$, we have $k_{n+1}=k_n+1$ and $l_{n+1}=l_n-1$ so eventually $l_n=3^{k_n}$. At this point we are forced to choose $p=3$, and in fact it will always remain from here a number with $y_n=1$, since we can only multiply by $\frac{4}{3}$ or $\frac{3}{2}$, which don't have any prime factors other than $2$ or $3$. So repeating the same procedure we will use $3$ infinitely many times.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
naman12
1358 posts
#3
Y by
Note that if the greatest prime divisor of $n$ is at least 5, then it is non-increasing. In particular, we multiply $n$ by $\frac{p+1}p$, so indeed if $p\geq 5$, $p+1$ is even and $p>\frac{p+1}2$.

Now, this means that we can only use a given prime $p$ a finite number of times. As the primes on the board can not exceed $\min(p,3)$ where $p$ is the smallest divisor of $n$, one of 2 and 3 is repeated infinitely. However, note if $\nu_2(n)=k$, we can apply $p=2$ at most $k$ times, after which we are forced to apply $p=3$ (after depleting all other numbers). This process endlessly repeats, as what we wanted to prove.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Nofancyname
102 posts
#4
Y by
naman12 wrote:
Note that if the greatest prime divisor of $n$ is at least 5, then it is non-increasing. In particular, we multiply $n$ by $\frac{p+1}p$, so indeed if $p\geq 5$, $p+1$ is even and $p>\frac{p+1}2$.

Doesn't it hold for all $p\ge 3$ ? Also I don't quite get the proof in general
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
naman12
1358 posts
#5 • 2 Y
Y by Mango247, Mango247
Nofancyname wrote:
naman12 wrote:
Note that if the greatest prime divisor of $n$ is at least 5, then it is non-increasing. In particular, we multiply $n$ by $\frac{p+1}p$, so indeed if $p\geq 5$, $p+1$ is even and $p>\frac{p+1}2$.

Doesn't it hold for all $p\ge 3$ ? Also I don't quite get the proof in general

Basically the idea is that primes not of the form 2 and 3 will never get "regenerated" if you go below - suppose $n=p_1^{e_1}\cdots p_k^{e_k}$ where $p_1<p_2<\cdots<p_k$. Then, you can't get $p\mid n$ after many steps if $p>\min(3,p_k)$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
hakN
428 posts
#6
Y by
Let $n = 2^x \cdot 3^y \cdot p_1^{\alpha_1} \dots \cdot p_k^{\alpha_k}$ where $p_1 < p_2 < \dots < p_k$ are distinct primes greater than $3$.
If at any time we are forced to select $p=3$, then we will be done since we can repeat this procedure on any $n$. So lets assume we do not select $p=3$ if we have other options.
Note that every time we do an operation with any of the $p_i$'s, $v_{p_i}(n)$ decreases and the sum of the exponents of the primes which are smaller than $p_i$ increases. If we do an operation with $p=2$, then $v_2(n)$ decreases and $v_3(n)$ increases. Thus, after doing this operations finitely many times with not selecting $3$, we will be left with $n=2^u \cdot 3^v$ for $u,v \in \mathbb{Z}^+$. And so we will have to select $2$ exactly $u$ times and then we will be left with $n=3^{u+v}$. So now we are forced to select $p=3$ and we are done. $\square$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
third_one_is_jerk
36 posts
#7 • 1 Y
Y by HyperDunteR
Suppose $n = 3^km, k \in \mathbb{Z}_{\geq 0}$. We prove that eventually we must have $p = 3$.

Claim The size of the prime factors of $m$ is decreasing.
Proof. Suppose $m = m'p$. Then $n+ \frac{n}{p} = 3^k m'(p+1),$ and the prime factors of $p+1$ are less than $p$. $\square$

By the above claim we must eventually have $m = 2^\ell, \ell \in \mathbb{Z}_{> 0}$. Now if we choose $p = 2$ then \[n+ \frac{n}{p} = 2^\ell \cdot 3^k + 2^{\ell - 1}\cdot 3^k = 3^{k+1} \cdot 2^{\ell - 1}.\]Therefore, we must have $n$ a power of $3$ after some steps.
This post has been edited 3 times. Last edited by third_one_is_jerk, Oct 9, 2021, 9:07 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
DottedCaculator
7282 posts
#8
Y by
For each prime $p$, define $f(p)=p$ if $p\neq3$, and $f(3)=1$. Then, let $f(n)$ be the largest possible value of $f(p)$ for some prime $p$ dividing $n$. We will prove that $3$ must eventually be chosen. We will prove this by strong induction on $f(n)$.

Base Case: $f(n)=1$
Then, $n=3^k$, which means that $3$ must be chosen, which is a contradiction.

Inductive Step:
Then, for every prime $p\neq3$, we have $f(p)>f(p+1)$. Let $q$ satisfy $f(q)=f(n)$. Then, by the inductive hypothesis, any sequence of moves starting from $\frac n{q^{\nu_q(n)}}$ must eventually pick $3$, so if $3$ is not eventually chosen, then $q$ must be chosen eventually. However, since $f(q)>f(q+1)$, we have that $q$ must be chosen $\nu_q(n)$ times, but then this decreases the value of $f(n)$, so by the inductive hypothesis, $3$ must be chosen eventually.

Therefore, if $3$ is chosen finitely many times, then there exists a number $x$ such that starting from $x$, the number $3$ is not chosen at all. However, this is a contradiction. Therefore, $3$ was chosen infinitely many times.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pikapika007
294 posts
#9
Y by
2 = 3

It suffices to show that $n$ will be a power of $3$ infinitely often. Note first that picking $3$ changes our $3$ to two $2$'s in the prime factorization, and that picking $2$ changes our prime to a $3$.

Consider picking a prime $p \ge 5$, and note that after a move, $\nu_p(n)$ decreases by exactly one, as all prime factors of $p+1$ are less than $n$. Therefore, at some point we will have $n = 2^a3^b$ - with our observation above we are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
OronSH
1688 posts
#10 • 1 Y
Y by megarnie
Notice that the operation is equivalent to replacing some prime factor $p$ of $n$ with the prime factors (with multiplicity) of $p+1.$ The key to this problem is the following:

The sum of the prime factors not equal to $3$ decreases unless $p=3.$

Proof: For small primes we can manually check. For large enough primes we have $\frac{p+1}{2}+2<p,$ and the sum of the prime factors of any $k$ is less than or equal to $k.$ This is because multiplying by a prime $p$ increases any number $n \ne 1$ by at least $p.$

To finish, if $p=3$ was never chosen from some point on, then after that point, the sum of the prime factors not equal to $3$ would decrease indefinitely, which is impossible, finishing the proof.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Sanjana42
17 posts
#11 • 1 Y
Y by kamatadu
Notice that the new number we get is $n(\frac{p+1}{p})$. So we are basically multiplying the number by $\frac{p+1}{p}$. Assume FTSOC that after a point, we don't choose 3 anymore. Call numbers which are neither divisible by 2 nor 3 slick numbers.

If we use 2, then the power of 2 decreases by 1 and the power of 3 increases by 1. If we use a slick prime $p$, then $n$ gets multiplied by by $\frac{p+1}{p}$. Now $2 \mid p+1$, so if we consider the slick part of the number, it has been divided by $p$ and multiplied by maximum $\frac{p+1}{2}$ (less if this is divisible by 3). Since $\frac{p+1}{2} < p$ as long as $p>1$, the slick part reduces.

Now at any point, we cannot go on using 2's forever since eventually $\mathcal{V}_2(n)$ will become 0. So a slick prime must be used infinitely many times, which causes the slick part to reduce, so eventually it must become 1. Now $n$ has only 2 and 3 as prime factors, so it must keep on using 2, but then $\mathcal{V}_2(n)$ again becomes 0, so we have to use 3, contradiction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Math4Life7
1697 posts
#12
Y by
We prove the result by induction on the largest prime $p\geq 5$ that divides $n$.

We have two base cases of $2^n$, and $2^n3^m$. Notice that when we simply have to prove the second and the first comes automatically. Notice that we can either change our number to $2^{n+2}3^m-1$ or $2^{n-1}3^{m+1}$. Notice, therefore that we must always have the number of the form $2^n3^m$. We obviously must have the amount of times we chose $3$ as our primes to be infinite because $n$ is always finite.

Now for the inductive step. We claim that the given works when our largest prime is $p$. Let the next largest prime be $q$. Notice that when we can only pick $q$ as our prime a finite number of times. When we choose $q$, we multiply our number by $\frac{q+1}{q}$. Notice that $2|q+1$ thus we will decrease the power of $q$ and it will not contribute to the power of any greater prime. Thus if the power of $q$ is $n$ then if we choose $q$ as our prime $n$ times then our number will be a number with largest prime $p$ or less. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
thdnder
191 posts
#13
Y by
We only need to prove that for all $n$, number $3$ will eventually be chosen. Let $p$ be the largest prime divisor of $n$. Then if $p$ is not chosen, then we can replace $n \to \frac{n}{p}$. Thus, we may assume that $p$ will be eventually chosen. Therefore, the largest prime divisor of $n$ is decreasing, so at some moment, we may suppose that we reached number $3^a2^b$ for some $a, b \ge 0$. From this, number $3$ will be eventually chosen, or we'll reach to $3^{a + b}$. Hence we're done. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
john0512
4167 posts
#14
Y by
The main idea of this problem is that when a prime $p\geq 3$ is selected, only smaller prime factors are produced, as all prime divisors of $p+1$ are smaller than $p$.

In particular, consider primes $p\geq 5$. Each time, only smaller primes are gained, so e.g. by considering an ordinal, there can only be finitely many moves on primes $p\geq 5$. Thus, eventually all moves are either $p=2$ or $p=3$. In a $p=2$ move we lose a 2 and gain a 3, in a $p=3$ move we lose a 3 and gain two 2s. Thus, clearly the $p=3$ move must happen infinitely often so that we don't run out of 2s.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
RedFireTruck
4184 posts
#15
Y by
FTSOC, assume that the number $3$ is only chosen a finite number of times.

Let $P$ be the largest prime dividing $n$.

then consider the tuple $(v_{\max(11, P)}(n), \dots, v_{7}(n), v_{5}(n), v_2(n), v_3(n))$

every second, some number in the tuple decrease and some numbers later in the tuple increase

clearly, only a finite number of seconds pass before we end up with a tuple of the form $(0, \dots, 0, X)$, as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Martin2001
126 posts
#16
Y by
The problem is equivalent to, after each step of the process, adding one to a prime factor of the current number. As the only consecutive prime numbers are $2,3,$ after every step the prime will have been split into several smaller prime numbers if and only if the prime numbers isn't $2.$ Continuing splitting the prime numbers until all are $2,$ now note that $2+1=3$ and $3+1=2^2,$ so $3$ will be chosen infinitely thereafter, so we're done$.\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dolphinday
1301 posts
#17
Y by
WLOG we are not forced to choose $p = 3$.
Note that since $n + \frac np = \frac np(p + 1)$ and the prime divisors of $p + 1$ are all smaller than $p$, so clearly we will continue this process until all prime factors of the number on the board are $2$ or $3$.
If $p = 2$ then we get $\frac n2(3)$ so we repeat this process until there are no prime factors of $2$ left, so we are forced to choose $p = 3$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
InterLoop
226 posts
#18
Y by
solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shendrew7
774 posts
#19
Y by
It suffices to show that $n$ will always become a power of 3 if we don't choose $p=3$ (which would force $p=3$). Letting $n=pk$, we see our process changes $pk \rightarrow (p+1)k$.

Notice that choosing $p=2$ takes one factor of 2 from $n$ and replaces it with a factor of 3. Otherwise, the prime factors of $p+1$ are strictly smaller than $p$, and thus we eventually are left with only factors of 2 and 3, from which we are eventually left with a power of 3. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AshAuktober
871 posts
#20
Y by
Tfw the writeup is so weird I'm on the verge of running out of good-looking variables...


Note that if we eventually reach a number of the form $2^a3^b$ then we're done, so assume otherwise. Further assume we never choose $3$ as a prime, as we can just skip to the point where we never choose it.
Let the numbers be $n_1, \dots,$ and let $$n_i = 2^{a_i}3^{b_i}\prod_{j = 1}^{\infty}p_j^{k_{(j, i)}},$$where $5 = p_1 < p_2 < \dots$ are the primes greater than $3$.
Let $j_i$ be the largest number $j$ such that $k_{(j, i)} > 0$. Note that $$\nu_{p_{j_i}}(n_l)$$is nonincreasing as we increase $l > i$. We claim that, in fact, this quantity eventually strictly decreases.
Indeed, this implies that we eventually reach a number of the form $2^a3^b$, so we'd be done. We prove this by induction on $j_i$.
Indeed, the base case is obvious: if the number is of the form $2^a3^b5^c$, then we have to keep choosing 2, else we choose 5 and $\nu_5$ decreases. But then 2's get transferred into 3's, so eventually we choose 5 as desired.
Now assume that this is true for $j_i = k$. We prove it for $j_i = k+1$.
Consider $n_1 = p_{k+1}^a \times m_1$ WLOG (else if it's $n_q$ then we shift the sequence by $q-1$ terms to the left). Then we have $n_r = p_{k+1}^a \times m_r$, where we perform similar operations on the $m_r$. Note that from previous cases $m_i$ eventually becomes a power of 3, so we have a number of the form $3^x \times p_{k+1}^a$, at which point we either choose $3$ and lose, or choose $p_{k+1}$ and the $\nu_{p_{k+1}}$ decreases. This completes the proof. $\square$
From here we of course eventually reach to a number of the form $2^a3^b$, and thus we reach a power of $3$, qed. :cool:
This post has been edited 5 times. Last edited by AshAuktober, Jan 4, 2025, 5:19 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math004
23 posts
#21
Y by
The main idea is to see that the new primes added to $n+\frac{n}{p}$ are less than $p$ and that the $p-adic$ valuation decreases when you choose $p$ as the divisor. That is, the sequence of the $p-adic$ valuations of the number written on the board i.e $(v_5(n),v_7(n),\cdots)$ decreases lexicographically and hence constant after some point. That implies that we have to choose $p\in\{2,3\}$ as a divisor infinitely many often. Obviously, we cannot choose $2$ every time since the $2-adic$ valuation decreases.
Z K Y
N Quick Reply
G
H
=
a