Plan ahead for the next school year. Schedule your class today!

G
Topic
First Poster
Last Poster
k a July Highlights and 2025 AoPS Online Class Information
jwelsh   0
Jul 1, 2025
We are halfway through summer, so be sure to carve out some time to keep your skills sharp and explore challenging topics at AoPS Online and our AoPS Academies (including the Virtual Campus)!

[list][*]Over 60 summer classes are starting at the Virtual Campus on July 7th - check out the math and language arts options for middle through high school levels.
[*]At AoPS Online, we have accelerated sections where you can complete a course in half the time by meeting twice/week instead of once/week, starting on July 8th:
[list][*]MATHCOUNTS/AMC 8 Basics
[*]MATHCOUNTS/AMC 8 Advanced
[*]AMC Problem Series[/list]
[*]Plus, AoPS Online has a special seminar July 14 - 17 that is outside the standard fare: Paradoxes and Infinity
[*]We are expanding our in-person AoPS Academy locations - are you looking for a strong community of problem solvers, exemplary instruction, and math and language arts options? Look to see if we have a location near you and enroll in summer camps or academic year classes today! New locations include campuses in California, Georgia, New York, Illinois, and Oregon and more coming soon![/list]

MOP (Math Olympiad Summer Program) just ended and the IMO (International Mathematical Olympiad) is right around the corner! This year’s IMO will be held in Australia, July 10th - 20th. Congratulations to all the MOP students for reaching this incredible level and best of luck to all selected to represent their countries at this year’s IMO! Did you know that, in the last 10 years, 59 USA International Math Olympiad team members have medaled and have taken over 360 AoPS Online courses. Take advantage of our Worldwide Online Olympiad Training (WOOT) courses
and train with the best! Please note that early bird pricing ends August 19th!
Are you tired of the heat and thinking about Fall? You can plan your Fall schedule now with classes at either AoPS Online, AoPS Academy Virtual Campus, or one of our AoPS Academies around the US.

Our full course list for upcoming classes is below:
All classes start 7:30pm ET/4:30pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Wednesday, Jul 16 - Oct 29
Sunday, Aug 17 - Dec 14
Tuesday, Aug 26 - Dec 16
Friday, Sep 5 - Jan 16
Monday, Sep 8 - Jan 12
Tuesday, Sep 16 - Jan 20 (4:30 - 5:45 pm ET/1:30 - 2:45 pm PT)
Sunday, Sep 21 - Jan 25
Thursday, Sep 25 - Jan 29
Wednesday, Oct 22 - Feb 25
Tuesday, Nov 4 - Mar 10
Friday, Dec 12 - Apr 10

Prealgebra 2 Self-Paced

Prealgebra 2
Friday, Jul 25 - Nov 21
Sunday, Aug 17 - Dec 14
Tuesday, Sep 9 - Jan 13
Thursday, Sep 25 - Jan 29
Sunday, Oct 19 - Feb 22
Monday, Oct 27 - Mar 2
Wednesday, Nov 12 - Mar 18

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Tuesday, Jul 15 - Oct 28
Sunday, Aug 17 - Dec 14
Wednesday, Aug 27 - Dec 17
Friday, Sep 5 - Jan 16
Thursday, Sep 11 - Jan 15
Sunday, Sep 28 - Feb 1
Monday, Oct 6 - Feb 9
Tuesday, Oct 21 - Feb 24
Sunday, Nov 9 - Mar 15
Friday, Dec 5 - Apr 3

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Wednesday, Jul 2 - Sep 17
Sunday, Jul 27 - Oct 19
Monday, Aug 11 - Nov 3
Wednesday, Sep 3 - Nov 19
Sunday, Sep 21 - Dec 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Friday, Oct 3 - Jan 16
Sunday, Oct 19 - Jan 25
Tuesday, Nov 4 - Feb 10
Sunday, Dec 7 - Mar 8

Introduction to Number Theory
Tuesday, Jul 15 - Sep 30
Wednesday, Aug 13 - Oct 29
Friday, Sep 12 - Dec 12
Sunday, Oct 26 - Feb 1
Monday, Dec 1 - Mar 2

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Friday, Jul 18 - Nov 14
Thursday, Aug 7 - Nov 20
Monday, Aug 18 - Dec 15
Sunday, Sep 7 - Jan 11
Thursday, Sep 11 - Jan 15
Wednesday, Sep 24 - Jan 28
Sunday, Oct 26 - Mar 1
Tuesday, Nov 4 - Mar 10
Monday, Dec 1 - Mar 30

Introduction to Geometry
Monday, Jul 14 - Jan 19
Wednesday, Aug 13 - Feb 11
Tuesday, Aug 26 - Feb 24
Sunday, Sep 7 - Mar 8
Thursday, Sep 11 - Mar 12
Wednesday, Sep 24 - Mar 25
Sunday, Oct 26 - Apr 26
Monday, Nov 3 - May 4
Friday, Dec 5 - May 29

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)
Sat & Sun, Sep 13 - Sep 14 (1:00 - 4:00 PM PT/4:00 - 7:00 PM ET)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22
Friday, Aug 8 - Feb 20
Tuesday, Aug 26 - Feb 24
Sunday, Sep 28 - Mar 29
Wednesday, Oct 8 - Mar 8
Sunday, Nov 16 - May 17
Thursday, Dec 11 - Jun 4

Intermediate Counting & Probability
Sunday, Sep 28 - Feb 15
Tuesday, Nov 4 - Mar 24

Intermediate Number Theory
Wednesday, Sep 24 - Dec 17

Precalculus
Wednesday, Aug 6 - Jan 21
Tuesday, Sep 9 - Feb 24
Sunday, Sep 21 - Mar 8
Monday, Oct 20 - Apr 6
Sunday, Dec 14 - May 31

Advanced: Grades 9-12

Calculus
Sunday, Sep 7 - Mar 15
Wednesday, Sep 24 - Apr 1
Friday, Nov 14 - May 22

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)
Sunday, Aug 17 - Nov 9
Wednesday, Sep 3 - Nov 19
Tuesday, Sep 16 - Dec 9
Sunday, Sep 21 - Dec 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Oct 6 - Jan 12
Thursday, Oct 16 - Jan 22
Tues, Thurs & Sun, Dec 9 - Jan 18 (meets three times a week!)

MATHCOUNTS/AMC 8 Advanced
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)
Sunday, Aug 17 - Nov 9
Tuesday, Aug 26 - Nov 11
Thursday, Sep 4 - Nov 20
Friday, Sep 12 - Dec 12
Monday, Sep 15 - Dec 8
Sunday, Oct 5 - Jan 11
Tues, Thurs & Sun, Dec 2 - Jan 11 (meets three times a week!)
Mon, Wed & Fri, Dec 8 - Jan 16 (meets three times a week!)

AMC 10 Problem Series
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)
Sunday, Aug 10 - Nov 2
Thursday, Aug 14 - Oct 30
Tuesday, Aug 19 - Nov 4
Mon & Wed, Sep 15 - Oct 22 (meets twice a week!)
Mon, Wed & Fri, Oct 6 - Nov 3 (meets three times a week!)
Tue, Thurs & Sun, Oct 7 - Nov 2 (meets three times a week!)

AMC 10 Final Fives
Friday, Aug 15 - Sep 12
Sunday, Sep 7 - Sep 28
Tuesday, Sep 9 - Sep 30
Monday, Sep 22 - Oct 13
Sunday, Sep 28 - Oct 19 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, Oct 8 - Oct 29
Thursday, Oct 9 - Oct 30

AMC 12 Problem Series
Wednesday, Aug 6 - Oct 22
Sunday, Aug 10 - Nov 2
Monday, Aug 18 - Nov 10
Mon & Wed, Sep 15 - Oct 22 (meets twice a week!)
Tues, Thurs & Sun, Oct 7 - Nov 2 (meets three times a week!)

AMC 12 Final Fives
Thursday, Sep 4 - Sep 25
Sunday, Sep 28 - Oct 19
Tuesday, Oct 7 - Oct 28

AIME Problem Series A
Thursday, Oct 23 - Jan 29

AIME Problem Series B
Tuesday, Sep 2 - Nov 18

F=ma Problem Series
Tuesday, Sep 16 - Dec 9
Friday, Oct 17 - Jan 30

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT


Programming

Introduction to Programming with Python
Thursday, Aug 14 - Oct 30
Sunday, Sep 7 - Nov 23
Tuesday, Dec 2 - Mar 3

Intermediate Programming with Python
Friday, Oct 3 - Jan 16

USACO Bronze Problem Series
Wednesday, Sep 3 - Dec 3
Thursday, Oct 30 - Feb 5
Tuesday, Dec 2 - Mar 3

Physics

Introduction to Physics
Tuesday, Sep 2 - Nov 18
Sunday, Oct 5 - Jan 11
Wednesday, Dec 10 - Mar 11

Physics 1: Mechanics
Sunday, Sep 21 - Mar 22
Sunday, Oct 26 - Apr 26
0 replies
jwelsh
Jul 1, 2025
0 replies
thanks u!
Ruji2018252   0
10 minutes ago
$f:\mathbb{R}\to\mathbb{R}$ and
\[f(2f(xy)+xf(y)+f(x))=3yf(x)+x,\forall x,y\in\mathbb{R}\]
0 replies
Ruji2018252
10 minutes ago
0 replies
Number theory
truongngochieu   3
N 19 minutes ago by Schintalpati
Prove that \[\tau\big(\varphi(n)\big) \geq \varphi\big(\tau(n)\big)\]with all integer n.
3 replies
truongngochieu
Wednesday at 5:06 AM
Schintalpati
19 minutes ago
Peru IMO TST 2022
diegoca1   1
N 27 minutes ago by TUAN2k8
Source: Peru IMO TST 2022 D1P2
Find all functions $f: \mathbb{R}\rightarrow \mathbb{R}$ such that:
\[ f(xy + f(x))+f(y) = xf(y)+f(x+y) \]for all real numbers $x,y$
1 reply
diegoca1
5 hours ago
TUAN2k8
27 minutes ago
Find the minimum value
sqing   3
N 39 minutes ago by sqing
Source: 2025 China Mathematical Olympiad Hope Alliance Summer Camp
Let $ a,b,c> 0, abc=\frac{1}{1024} .$ Find the minimum value of $ a^2+2b^2 +4c^2+\frac{2ac}{a+2c}.$
3 replies
sqing
2 hours ago
sqing
39 minutes ago
No more topics!
Integer FE Again
popcorn1   45
N Jul 3, 2025 by monval
Source: ISL 2020 N5
Determine all functions $f$ defined on the set of all positive integers and taking non-negative integer values, satisfying the three conditions:
[list]
[*] $(i)$ $f(n) \neq 0$ for at least one $n$;
[*] $(ii)$ $f(x y)=f(x)+f(y)$ for every positive integers $x$ and $y$;
[*] $(iii)$ there are infinitely many positive integers $n$ such that $f(k)=f(n-k)$ for all $k<n$.
[/list]
45 replies
popcorn1
Jul 20, 2021
monval
Jul 3, 2025
Source: ISL 2020 N5
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Spectator
657 posts
#37
Y by
We claim that $f(x) = cv_{p}(x)$ for some constant $c$ and some prime $p$.

Let $p$ be the smallest integer such that $f(p)> 0$. Clearly, $p$ is a prime, because otherwise, we could write it in its prime factorization and must have one of the terms be $> 0$, which is a contradiction by minimality.

Let $n$ be a sufficiently large integer that satisfies the second condition. We claim that we must have $p \mid n$.

For the sake of contradiction, let $n \equiv k \neq 0 \pmod{p}$. Thus, \[f(k) = f(n-k) = f(p)+f(\cdots) > 0\]but $k< p$, so $f(k) = 0$, contradiction.

We claim that there doesn't exist any other prime $q$ such that $f(q) > 0$. For the sake of contradiction, let $q$ be the second smallest prime such that $f(q) > 0$. We claim that $q \mid n$ as well.

Let $l = \lfloor\log_{p}(q)\rfloor$. Note that $p^{l} \mid n$ by the same logic that $p\mid n$ except if $p\mid k$, we'll have a greater exponent of $p$, contradiction. Thus, for the sake of contradiction let $n \equiv k \pmod{q}$. If $p \nmid k$, then $f(k) = 0 = f(n-k) = f(q)+f(\cdots) > 0$. If $p \mid k$, then we get
$f(k) = f(p^{v_{p}(k)}) = f(p^{v_{p}(k)})+f(q) + f(\cdots)$, because $v_{p}(k) \leq l$. Thus, we must have $q \mid n$.

However, if $n = aq\cdot p^{b}$, such that $v_{p}(a) = 0$. Note that $aq = cp+k$ for some $k < p$. Thus, we can just take $f(cp^{b+1}) = f(kp^{b})$, which is a contradiction.

From here, it is clear that $f(x) = cv_{p}(x)$ for some constant $c$ and some prime $p$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
huashiliao2020
1292 posts
#38
Y by
$      $
Attachments:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Wave_dude
15 posts
#39
Y by
MatBoy-123 wrote:
Aryan-23 wrote:
Hence for all large enough good $n$, we have that $p \not \vert \tbinom {n-1}{k}$. By Lucas's theorem we have that $n=a\cdot p^b$ for some $a<p$.
I am quite confused, how did u apply Lucas, can someone plz explain..

Claim: For a prime number $p$ and a positive integer $n$ if $p\nmid \tbinom{n-1}{k}, \forall 0\leq k\leq n-1$ then $n=a\cdot p^b$ for some $1\leq a<p$ and $b$ non negative.
Proof: Let $n-1=\sum_{i=0}^{s} n_i p^{i}$ for some non negative integer $s$ and $0\leq n_i<p$ for all $0\leq i\leq  s$. The case $s=0$ is trivial, so we can assume $s\geq 1$. Take $0\leq j\leq s-1$ and assume BWOC that $n_j<p-1$ so that the $j$th digit base $p$ of $(n_j+1)p^j$ is still just $n_j+1$. Note that $\tbinom{a}{b}=0$ if $b>a$. We can now apply Luca's theorem in the following way:
\[
\binom{n-1}{(n_j+1)p^j}\equiv \prod_{i=0}^{s} \binom{n_i}{\delta_{ij} (n_j+1)}\equiv \binom{n_j}{n_j+1}\equiv 0 \pmod p
\]Here $\delta_{ij}$ is the Kronecker delta symbol (=1 if $i=j$ and =0 otherwise). Now since $(n_j+1)p^j<n$ we know that $p$ can't divide $\tbinom{n-1}{(n_j+1)p^j}$ which is a contradiction. So $n_j=p-1, \forall 0\leq j\leq s-1$. Now it easily follows:
\[n=1+n_s p^s+\sum_{i=0}^{s-1} (p-1) p^{i}=(n_s+1)p^s\]Which is of the form $a\cdot p^b$ for $1\leq a<p$ and we are done $\blacksquare$.
I hope this helped :-D.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
BlazingMuddy
284 posts
#40 • 5 Y
Y by mathmax12, IAmTheHazard, square_root_of_3, megarnie, mathhotspot
Let's forget for a moment that $\mathbb{N}_0$ has a nice total order (which is used in the official solution). We will only use the fact that $\mathbb{N}_0$ is
  • an integral monoid (commutative, and addition can be cancelled out, i.e., $a + c = b + c$ implies $a = b$);
  • torsion-free (for any $k \in \mathbb{N}_0$, if $n \cdot k = 0$ for some positive integer $n$, then $k = 0$).
Quote:
Let $\mathbb{N}$ denote the set of positive integers. Let $M$ be a torsion-free integral monoid.
Determine all functions $f : \mathbb{N} \to M$ such that
  • $f$ is additive: $f(xy) = f(x) + f(y)$ for every $x, y \in \mathbb{N}$,
  • there are infinitely many positive integers $n$ such that $f(k) = f(n - k)$ for all $k \in \mathbb{N}$ such that $k < n$.

Answer.
$n \mapsto \nu_p(n) \cdot c$ for some prime $p$ and $c \in M$.

More generally, if $M$ is not torsion-free, then any function of the form $p^k x \mapsto kc + \chi(x)$ for some monoid homomorphism $\chi : (\mathbb{Z}/p\mathbb{Z})^{\times} \to M$ works. However, we may have pathological solutions as well, for example, using Legendre symbols when $M = \mathbb{Z}/2\mathbb{Z}$. See the solution below for more detail.


We will not assume that $M$ is torsion-free, unless necessary.

We say that a positive integer $n$ is $f$-nice if $f(k) = f(n - k)$ for all $k \in \mathbb{N}$ such that $k < n$. For any positive integers $c$ and $d$, if $cd$ is $f$-nice, then $f(ck) = f(cd - ck) \implies f(c) + f(k) = f(c) + f(d - k) \implies f(k) = f(d - k)$ for any $k < n$, so $d$ is $f$-nice as well. That is, the set of $f$-nice positive integers is divisor-closed. Since this set is assumed to be infinite, either
  • (1). there exists a prime $p$ such that $p^k$ is $f$-nice for any $k \geq 0$;
  • (2). there exists infinitely many $f$-nice primes.
The following lemma is crucial in both cases.

Lemma. Let $p$ be an $f$-nice prime. Then $f(km \bmod{p}) = f(k) + f(m)$ for any positive integers $k, m < p$, where $km \bmod{p}$ denote the remainder of $km$ under division by $p$.
Proof

The lemma tells us that $f$, when restricted over $\{1, 2, \ldots, p - 1\}$, is essentially a monoid homomorphism $(\mathbb{Z}/p\mathbb{Z})^{\times} \to M$. In particular, when $M$ is torsion-free, $f$ would necessarily restrict to the zero map on $(\mathbb{Z}/p\mathbb{Z})^{\times}$.

Case 1. There exists a prime $p$ such that $p^k$ is $f$-nice for any $k \geq 0$.

We claim that $f(x) = f(x \bmod{p})$ for any positive integer $x$ coprime with $p$. The claim is the bulk of the solution in Case 1.
Proof

Now let $\chi : (\mathbb{Z}/p\mathbb{Z})^{\times} \to M$ be the restriction of $f$ to $(\mathbb{Z}/p\mathbb{Z})^{\times}$. Recall by the above lemma that $\chi$ is a monoid homomorphism. The above claim yields that $f(x) = \chi(x \bmod{p}) = \chi(x)$ for any $x \in \mathbb{N}$ coprime with $p$. As a result, $f(p^k x) = k f(p) + \chi(x)$ for any $k \geq 0$ and $x \in \mathbb{N}$ coprime with $p$.

Note that if $M$ is torsion-free, then $\chi$ is necessarily zero, since $(p - 1) \chi(x) = \chi(x^{p - 1}) = \chi(1) = 0$ for any $x \in (\mathbb{Z}/p\mathbb{Z})^{\times}$. In this case, we have $f(p^k x) = k f(p) = \nu_p(p^k x) f(p)$. That is, $f(n) = \nu_p(n) f(p)$ for any $n \in \mathbb{N}$.

Case 2. There exists infinitely many $f$-nice primes.

Assuming that $M$ is torsion-free, this case has a short solution as follows.
By the above lemma and the same argument as in the final paragraph in Case 1, for any $f$-nice prime $p$, we have $f(n) = 0$ for any $n < p$. Now for any $n \in \mathbb{N}$, there must be an $f$-nice prime greater than $n$ since there are infinitely many $f$-nice primes. Thus we get $f(n) = 0$ for any $n \in \mathbb{N}$.

However, if $M$ is not torsion-free, then there exists a prime $q$ such that there exists an injective homomorphism $\mathbb{Z}/q\mathbb{Z} \hookrightarrow M$. If we can construct a weird function $f : \mathbb{N} \to \mathbb{Z}/q\mathbb{Z}$ with infinitely many $f$-nice primes, then the same holds for $\mathbb{N} \to M$ just by composing with that homomorphism. Such construction exists for $q = 2$; we construct it below.

Non-torsion-free case, q equals 2

In the case where $q$ is odd, it suffices to find a sequence of primes $p_1 < p_2 < \ldots$ and compatible non-zero homomorphisms $f_k : (\mathbb{Z}/p_k \mathbb{Z})^{\times} \to \mathbb{Z}/q\mathbb{Z}$ and leave it there. By compatible, we mean that $f_k(n) = f_m(n)$ whenever $n < \min\{p_k, p_m\}$. Then we can set $f(n) = f_n(n)$, and check that since $q$ is odd, the equality $f(n) = f(p_k - n)$ always holds whenever $n < p_k$. Unfortunately, finding such sequence looks like an open problem on itself...

Edit on April 14: It turns out that Chebotarev density theorem alone is enough to prove that such sequence exists, and it works without much extra work. View $\mathbb{Z}/q\mathbb{Z}$ as being isomorphic to the subgroup $\langle \zeta_q \rangle$ of $\mathbb{Q}(\zeta_q)^{\times}$. The homomorphisms $f_k$ are chosen to be the $q^{\text{th}}$ power symbol on $\mathbb{Q}(\zeta_q)$, and the primes $p_1, p_2, \ldots$ are chosen inductively using Chebotarev density theorem on a suitable abelian extension of $\mathbb{Q}(\zeta_q)$ at each step.
This post has been edited 2 times. Last edited by BlazingMuddy, Apr 14, 2024, 5:41 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Shreyasharma
688 posts
#41
Y by
Amazing problem, but had to use ARCH hint to solve.
$\rule{25cm}{0.5pt}$

We claim $\boxed{f(x) = \nu_p(x) \cdot c}$ for some prime $p$ and some constant $c$.

Let $S$ denote the set of all integers $n$ satisfying for $f(n-k) = f(k)$ for all $k < n$.

$\color{blue} \textbf{Claim}$: For any $n \in S$, any divisor $d$ of $n$ must be in $S$.

Proof . Assume some $n \in S$. Then take some divisor of $n$, say $d$. Let $k$ be such that $dk = n$. Then note for any $\ell < d$ that we have,
\begin{align*}
f(\ell k) &= f(n - \ell k)\\
f(\ell ) + f(k) &= f(k) + f(d - \ell)\\
f(\ell) &= f(d- \ell )
\end{align*}which is sufficient. $\blacksquare$

Now assuming that $f$ is not the zero function, take the smallest $p$ such that $f(p) > 0$. Clearly $p$ is prime from our previous claim. Also we find that $p \in S$, as for any $\ell < p$ we have,
\begin{align*}
f(\ell) = f(p-\ell) = 0.
\end{align*}
$\color{red} \textbf{Claim}$: For any $n \in S$, with $n > p$, we must have $p \mid n$.

Proof. Assume otherwise and let $n = pm + r$. Then we find,
\begin{align*}
f(n - r) &= f(r)\\
f(pm) &= f(r)\\
f(p) + f(m) &= f(r)
\end{align*}However this implies that $f(r) \geq f(p) > 0$, with $r < p$, a contradiction. $\blacksquare$

In fact we can slightly strengthen our claim.

$\color{blue} \textbf{Claim}$: Any $n \in S$ must be of the form $kp^e$ for some $k \in (1, 2, \dots, p-1)$.

Proof. Assume otherwise. Then there exists some element $n \in S$ of the form $tp^e$, with $t > p - 1$. Note by our first claim we find that $ t \in S$. However then from our second claim as if $t > p - 1$, we find $p \mid t$, a contradiction to our assumption. $\blacksquare$

Finally from the infinite size of $S$, we must have that for any $e$ we have $p^e \in S$.

$\color{red} \textbf{Claim}$: For all other primes $q \neq p$, we have $f(q) = 0$.

Proof. Assume that there is some prime $q > p$ such that $f(q) > 0$. Then noting that $q \mid p^{q-1}-1$ we find,
\begin{align*}
f(p^{q-1}-1) = f(q) + f(k)
\end{align*}where $k$ is such that $qk = p^{q-1}-1$. Note that from our previous claim, namely that all powers of $p$ lie in $S$, we have $f(p^{q-1}-1) = f(1) = 0$. Then we must have $f(q) = 0$, a contradiction. $\blacksquare$

Now we are almost finished. Note that from the additivity of $f$, for any $n = p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ we have,
\begin{align*}
f(n) = \sum_{i=1}^{k} e_i \cdot f(p_i)
\end{align*}Now from the condition that for any prime $q \neq p$ we have $f(q) = 0$, we find that for any $n$ we must have,
\begin{align*}
f(n) = \nu_p(n) \cdot f(p)
\end{align*}Letting $f(p)$ be some integer constant greater than or equal to $0$, we can conclude that $f$ is indeed the claimed function.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shendrew7
818 posts
#42
Y by
Our answer is $\boxed{f(x) = c \cdot v_p(x)}$ for a nonnegative constant $c$ and a prime $p$, which can be tested to work. Note that $f(x)=0$ is obviously valid, so from here we assume $f$ is not the zero function. Define $N$ as the infinite set of integers $n$ satisfying the second condition.

Claim 1: If $d \mid n$ and $n \in N$, then $d \in N$.

Choose an arbitrary positive integer $k < d$. Since $\frac nd \in \mathbb{Z}$, we get
\[f(k) = f(d-k) \iff f\left(\frac{nk}{d}\right) = f\left(\frac nd (d-k)\right) = f\left(n - \frac{nk}{d}\right),\]
which is true by definition of $n$. ${\color{blue} \Box}$

Claim 2: If $p$ is the smallest positive integer with $f(p)>0$, $p$ must be prime and $p \in N$.

The first part is clear from our first condition and the second part is clear from our second condition along with the minimality of $p$. ${\color{blue} \Box}$

Claim 3: Each element of $N$ greater than $p$ is of the form $p^eq$ for $1 \leq q < p$, and every power of $p$ is in $N$.

Assume FTSOC there exists an element $ap+b$, where $1 \leq b \leq p-1$. This tells us
\[f(b) = f(ap) = f(a)+f(p) > 0,\]
contradicting the minimality of $p$. Now assume FTSOC there exists an element $p^er$, where $p \nmid r$ and $r > p$. Claim 1 tells us $r \in N$, but our previous results then says $p \mid r$, contradiction.

Finally, the infinite size of $N$ along with Claim 1 grants us the final portion of our claim. ${\color{blue} \Box}$

Claim 4: For all primes $q \ne p$, we have $f(q)=0$.

By construction all $q<p$ already satisfy this condition. For $q>p$, Claim 3 tells us
\[f \left(\frac{p^{\operatorname{ord}_q(p)}-1}{q}\right) + f(q) = f \left(p^{\operatorname{ord}_q(p)}-1\right) = f(1) = 0. \quad {\color{blue} \Box}\]
The first condition finally gives us the desired expression of $f(x)$ through its prime factorization:
\[f(x) = \sum_{k \text{ prime}} f(k) \cdot v_k(x) = f(p) \cdot v_p(x). \quad \blacksquare\]
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
vsamc
3814 posts
#43
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.
awesomeming327.
1784 posts
#44
Y by
Denote $S=\{n\mid f(k)=f(n-k)\forall 1<k<n\}$. Let $n\in S$ then if $d\mid n$ then let $a+b=d$. We have $\tfrac{an}{d}+\tfrac{bn}{d}=n$ so
\[f(a)+f\left(\frac{n}{d}\right)=f\left(\frac{an}{d}\right)=f(b)+f\left(\frac{n}{d}\right)\]which implies that $d\in S$.

Let $p$ be the smallest number such that $f(p)\neq 0$. If $p=ab$ where $a,b$ are positive integers less than $p$ then $f(p)=f(a)+f(b)=0$ which is a contradiction. Thus, $p$ is prime. Suppose $n\in S$ and $n\ge p$ then $f(n-1)=f(n-2)=\dots=f(n-(p-1))=0$. Let $n=kp+m$ where $m\in \{1,2,\dots,p-1\}$ then \[0=f(n-m)=f(kp)=f(k)+f(p)=f(p)\]which is another contradiction. Thus, $p\mid n$. Now let $n=bp^a$ where $p\nmid b$ then since $b\mid n$, $b\in S$ which means $b<p$. If $p^k\not\in S$ for some $k$ then all multiples of $k$ are not in $S$. Thus, $S\setminus \{1,2,\dots,p-1\} \subseteq \{bp^a\mid a<k, b<p\}$, so $S$ is not infinite, contradiction. Therefore, $p^k\in S\forall k$.

Supposed $f(q)\neq 0$ for some $q\neq p$ then note that
\[0=f(p^{q-1}-1)=f(q)+f\left(\frac{p^{q-1}-1}{q}\right)>0\]which is a contradiction. Thus, $f(q)=0$ for all $q\neq p$. After prime factorizing $x$ we can easily see that $f(x)=c\nu_p(x)$ for some $c$, $p$. This function clearly satisfies all three properties.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ezpotd
1358 posts
#45
Y by
I claim the answer is only $f(x) = k\nu_p(x)$, which obviously works for all positive integer $k$ and primes $p$.

Call all integers satisfying the third property good. If an integer $n$ is good, so is any divisor of it $d$: observe $f(x) = f(y)$ is true iff $f(x) + f(\frac nd) = f(y) + f(\frac nd)$ which is true iff $f(\frac{xn}{d}) = f(\frac{yn}{d})$. Clearly, for any $x,y$ chosen such that $x + y =d$, the last statement holds, thus so does the first one and $d$ is good. In addition, if $n$ is a root, so is every divisor of it $d$, this is trivial by assuming otherwise and then forcing $f(n) > 0$.

Observe $f(x)  = f(x) + f(1)$, so $f(1) = 0$. Now consider the first value of $x$ with $f(x) > 0$. If $x$ is not prime, we can write it as $f(x) = f(a) + f(b)$, with $ab = n$, $a$,$b$ $< n$. Then since $f(a) = f(b) = 0$, we also have $f(x) = 0$, contradiction. Thus there exists some $p$ with $p$ prime that is the smallest solution to $f(x) = 0$. Clearly $p$ is good, since $f(k) = f(p - k) = 0$. Now we prove there are no good numbers above $p$ not dividing $p$. Assume there exists another good prime, called $q$. Then we have $f(x) = f(q - x)$, so for $1 \le x \le p - 1$ this shows that $f(q - 1) \cdots f(q - p + 1) = 0$. Now since $q, \cdots q - p + 1$ is a complete residue set mod $p$, we must have one of those numbers is divisible by $p$, and its not $q$ by definition of $q$. Let that number be $a$, we have $f(a) = 0$, but also $f(a) = f(p) + f(\frac pa) \ge f(p) > 0$, contradiction.

Now any good number cannot have a divisor greater than $p$ that is not divisible by $p$, this means that they all must be of the form $cp^x$ for $1 \le c \le p - 1$, so since there are a finite number of elements of the form $cp^x$ for $x \ge N$, we can conclude the set of good numbers has unbounded $\nu_p$. Now there always exists $x > N$ for all $N$ such that $p^x$ is good. Then since $p^N \mid p^x$, we have $p^N$ is good for all $N$. To finish, we have $0 = f(1) = f(p^k - 1)$. Now all divisors of $p^k - 1$ also must be a root of $f$. Indeed, $p^k \equiv 1 \mod m$ always has a solution, this is well known as long as $\gcd(p , m) = 1$, which is true, so all numbers relatively prime to $p$ divide some expression of the form $p^k - 1$, meaning all numbers relatively prime to $p$ are roots of $f$. Let $f(p) = k$, then we can easily show $f(p^x) = kx$ by using $f(p^x) = f(p^{x-  1}) + f(p)$ and induction, then if $\nu_p(x) = c$, we can write $f(x) = f(p^c) + f(\frac{x}{p^c}) = kc + f(\frac{x}{p^c})$, since $\frac{x}{p^c}$ is relatively prime to $p$ by definition of $c$, we have $f(x) = kc = f(p^c) = k\nu_p(p^c) = k\nu_p(x)$, so we have $f(x) = k\nu_p(x)$

Remark: putting actual effort into writeups is so boring. why would anyone do this.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
numbertheory97
56 posts
#46
Y by
Solved with a hint motivating the first lemma ($n$ good implies $d \mid n$ good). After that it still took me a while, but in hindsight I realized I was expecting something a little more $\nu_p$-flavored (the only use of $\nu_p$ in the solution is to actually show that the functions work).

Solution. The only solutions are $f(n) = c\nu_p(n)$ for some prime $p$ and positive integer $c$.

Claim: All such functions work.

Proof. The zero function trivially satisfies the equation. For $f(n) = c\nu_p(n)$, take $n = p^\ell$ for any positive integer $\ell$; we have \[f(n - k) = c\nu_p(p^\ell - k) = c\nu_p(-k) = f(k)\]since $\nu_p(k) < \ell$ for each $k < n$, as desired. $\square$

Let $p$ be the smallest positive integer for which $f(p)$ is nonzero. Clearly $p$ is prime, since otherwise $p = ab$ for $a, b < p$ and then one of $f(a)$ and $f(b)$ is nonzero. Our goal is to show that this is the only such prime, from which it easily follows that $f(n) = f(p)\nu_p(n)$ for all $n$.

Suppose to the contradiction that there exists a prime $q > p$ for which $f(q) > 0$. Call a positive integer $n$ good if it satisfies the third condition. We begin with the following:

Claim: If $n$ is good, any divisor $d \mid n$ is good.

Proof. Write $n = md$. Take an integer $k \in [1, d - 1]$; it suffices to show that $f(k) = f(d - k)$. Indeed, we have \[f(m) + f(k) = f(mk) = f(md - mk) = f(m) + f(d - k),\]and subtracting $f(m)$ yields the desired. $\square$

Claim: All good positive integers are of the form $ap^k$, where $a < p$ and $k$ is a nonnegative integer.

Proof. Let $n > p$ be a good integer, and write $n = mp + r$ for some $m \geq 1$ and $r < p$. If $r \neq 0$, we have $f(r) = f(mp) = f(m) + f(p) > 0$, a contradiction, so $r = 0$ and $n = mp$. By the previous claim, $m$ is good and so we can repeat this until $m < p$, completing the proof. $\square$

Claim: $p^k$ is good for every positive integer $k$.

Proof. There are infinitely many good integers, so we can find arbitrarily large $k$ for which $ap^k$ is good for some $a < p$. Since any divisor of $ap^k$ is good, we deduce the desired result. $\square$

Now we can finish as follows: since $p^{q - 1}$ is good, we have \[0 = f(1) = f(p^{q - 1} - 1) = f(q) + f\left(\frac{p^{q - 1} - 1}{q}\right) > 0,\]by Fermat, a contradiction. Thus $p$ is the only prime for which $f(p) > 0$, which completes the proof. $\square$
This post has been edited 3 times. Last edited by numbertheory97, Oct 5, 2024, 5:11 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathwiz_1207
105 posts
#47
Y by
We claim the only such functions that work are $f(n) = c \cdot v_p(n)$ for some prime $p$. We will proceed by showing that any function must be of this form, and then at the end we will show that all such functions work. $f \equiv 0 $ works trivially, so assume $f \not\equiv 0$. Furthermore, let $S$ be the set of all numbers $n$ satisfying $f(k) = f(n-k)$ for all $k < n$.


If $d \mid n$ and $n \in S$, then $d \in S$.

Proof. Note that for all $k < d$, we have
\[f(k \cdot \frac{n}{d}) = f((d-k) \cdot \frac{n}{d}) \implies f(k) = f(d-k)\]thus, $d \in S$.


Now, note that $f(1) = 2f(1)$, so $f(1) = 0$. Let $n$ be the first integer such that $f(n) \neq 0$. Then, $n$ must be a prime as otherwise
\[f(n) = f(p_1^{e_1}\cdots p_k^{e_k}) = e_1f(p_1) + \cdots + e_kf(p_k) > 0\]implies that there is a prime $p_i < n$ such that $f(p_i) > n$, a contradiction.


If $n > p$ and $n \in S$, $p \mid n$

Proof. Let $n = pm + r$, for $0 < r < p$, then
\[f(r) = f(pm) = f(p) + f(m) > 0\]a contradictions, so $r = 0$ and $p \mid n$.


Note that the above implies that over all $n$ in $S$, $\text{max}\{v_q(n)\}$ is bounded otherwise there would exist a $k$ such that $q^k > p \in S$, and $p \nmid q$. Since there are infinitely many integers in $S$, this implies that $\text{max}\{v_p(n)\}$ is unbounded, therefore
\[\{p, p^2, p^3, \cdots \}\]are in fact all elements of $S$. Now, let $q$ be a prime such that $q \neq p$. Then,
\[0 = f(1) = f(p - 1) = f(p^{q- 1} - 1)\]However, since $ q \mid p^{q-1} -1$, we have $f(q) = 0$. This is enough to imply that $f(n) = c \cdot v_p(n)$. To show that this works, consider
\[v_p(n - k) = v_p(k)\]If $p \nmid n$, then $n < p$, so it is true, and if $p \mid n$, then $n = a \cdot p^l$ for some $a < p$, so the above is true.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bin_sherlo
755 posts
#48
Y by
Answer is $f(n)=c.v_q(n)$ which holds. If $f(k)=f(n-k)$ for all $k<n$, then call $n$ special. If $nm $ is special, $f(m)+f(n-k)=f(nm-mk)=f(mk)=f(m)+f(k)$ for $k<n$ so $n$ is also special. Also note that $f(1)=0$.

Claim: The prime divisor set of all special numbers' has finitely many elements.
Proof: Assume otherwise. There must be infinitely many special primes. Since $f$ is unbounded, there exists $f(a)>\max\{f(1),\dots,f(a-1)\}$. Pick a sufficiently large special prime $q$. We have $f(q-ak)=f(ak)\geq f(a)$ but since $q\not \equiv 0(mod \ a)$ we choose $k=\lfloor\frac{q}{a}\rfloor$ so $f(a)\leq f(q-ak)\in \{f(1),\dots,f(a-1)\}$ which is impossible.

Let $\{q_1,\dots,q_k\}$ be the prime divisor set of special numbers'. Since there are infinitely many special numbers, there exists some $q_i$ such that $\nu_{q_i}'$s of special numbers are unbounded. Let that prime be $q$. Any divisor of a special number is also a special number thus, $q^m$ is special for each positive integer $m$. Pick $m\equiv 0(mod \ p-1)$ and $k=\lfloor\frac{q^m}{p}\rfloor$. We have $0=f(1)=f(q^m-pk)=f(pk)\geq f(p)$ so $f(p)=0$ for $p\neq q$. Since $f(p_1^{m_1}\dots p_k^{m_k})=m_1f(p_1)+\dots+m_kf(p_k)$ and $f(q)>0,f(p)=0$ for $p\neq 0$ we observe that $f(q^km)=kf(q)$ where $(q,m)=1$. Thus, the only function is $f(n)=c.v_q(n)$ for a constant prime $q$ and $c\in \mathbb{Z}^+$ as desired.$\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
DeathIsAwe
33 posts
#49
Y by
Answer is $f(n) = c \cdot v_p(n)$. Clearly this works since 69420 other people on this thread has the same answer :)

Let $A$ be the set of primes $p$ where $f(p) > 0$.

It is easy to notice that $f(n) = \sum_{p \in A}f(p)v_p(n)$.

Let $a$ be a prime and $b$ be a natural such that $a^b = \min(p^{v_p(n) + 1}, p \in A)$. Let $m$ be a natural smaller than $a^b$ such that $a^b | n - m$.

Notice that $v_a(n - m) \geq b > n$, thus $v_a(m) = v_a(n) < v_a(n - m)$

Also notice that for any other prime $p \in A$, we cannot have $v_p(m) > v_p(n)$ since $m < a^b \leq p^{v_p(n) + 1}$. If we have $v_p(m) \leq v_p(n)$, then $v_p(n - m) \geq v_p(m)$

Thus we have $v_p(m) \leq v_p(n - m)$ for all $p \in A$, and we specifically have $v_a(m) < v_a(n - m)$.

This means $f(m) < f(n - m)$. Notice that if $|A| \geq 2$, for sufficiently large $n$, we will have $m < n$ since there will have to be a prime $p \in A$ s.t. $p^{v_p(n)} < \sqrt{n}$ thus $p^{v_p(n) + 1} < n$. Therefore for all sufficiently large $n$, we can find a number $m < n$ and $f(m) \neq f(n - m)$. Thus $|A|$ has to be 1 and we are done.
This post has been edited 3 times. Last edited by DeathIsAwe, May 15, 2025, 6:26 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
TwentyIQ
31 posts
#50
Y by
The only ones that work are $f(n) = c \cdot \nu_p(n)$ for any prime $p$ and any positive integer $c$. It's easy to verify these work, so we prove they are the only solutions.

Let $M$ be the least positive integer such that $f(M) = 0$; then by the second condition $M$ must necessarily be prime. Set $M = p$ and let $f(p) = c$. By induction, we can show that $f(p^k) = k \cdot c$ for any $k \in \mathbb Z^+$.

Claim. If $n$ satisfies the third condition and $d \mid n$, then so does $d$.
Proof. Set $n = d \ell$ for some positive integer $\ell$. If $k < d$, then:
\[ f(k \ell) = f(k) + f(\ell) = f(d \ell - k \ell) = f(\ell) + f(d - k)\]and the claim follows. $\square$

Claim. If $n$ satisfies the third condition, then $p \mid n$ or $n < p$.
Proof. If $n \ge p$, then using the division algorithm write $n = pq + r$, where $0 \le r < p$. Then note that $f(r) = f(pq) = f(p) + f(q) > 0$, which yields a contradiction if $r \neq 0$. $\square$

Claim. Any $n$ satisfying the third condition must be of the form $mp^a$, where $1 \le m < p$.
Proof. Set $b = \nu_p(n)$, and let $n = mp^b$ where $p \nmid m$. By the first claim, $m$ also satisfies the third condition, which by the second claim is a contradiction if $m \ge p$. $\square$

Since infinitely many positive integers satisfy the third condition, the third and first claims imply that every power of $p$ satisfies the third condition. We can now finish the problem. Suppose for the sake of contradiction that for some prime $p' > p$, $f(p') > 0$. Then note that $f(1) = 0 = f(p^{p' - 1} - 1)$, which is a contradiction since $p' \mid p^{p' - 1} + 1$. Therefore, the only functions that work are the ones claimed. $\square$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
monval
233 posts
#51
Y by
We claim the answer is all $f$ of the form $f(x)=s\nu_p(x)$, for some $s\in\mathbb Z^+$ and prime $p$. For all such $f$, we can take $n=ap^t$ for $a<p$. Then for all $k<n$ \[f(ap^t-k)=s\nu_p(ap^t-k)=s\nu_p(k)=f(k)\]as desired.

We now show that these are the only such $f$; consider a solution $f$. Let $p$ be the least prime with $f(p)>0$. We now claim that all $n$ must be of the form $ap^t$ for $a<p$. Suppose FTSOC there is $n$ not of this form, and write $n=ap^t$ for $p\nmid a$ with $a>p$. Let $b$ be the remainder when $a$ is divided by $p$. Then \[f(ap^t-bp^t)=f(a-b)+f(p^t)>f(p^t)=f(bp^t)\]yields a contradiction, and so all $n$ are of the claimed form. Now suppose FTSOC there is a prime $q\neq p$ with $f(q)>0$, and consider the smallest such $q$. Consider any $n=ap^t$ that works, and write $n=vq+r$ for some $0<r<q$. Then $\nu_p(v)=\nu_p(vq)=\nu_p(r)$, but \[f(vq)=f(v)+f(q)>f(v)\geq f(p)\nu_p(v)=f(p)\nu_p(r)=f(r)\]yields a contradiction. Then there is no such $q$, and \[f(x)=f(p)\nu_p(x)\]for all $x$.
Z K Y
N Quick Reply
G
H
=
a