beautiful functional equation problem

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

B

No tags match your search

M

beautiful functional equation problem

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Netherlands TST for BxMO 2017 problem 2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

757 posts

Medjl

#1 h Feb 1, 2018, 3:10 PM • 4 Y

Y by Muradjl, Adventure10, Mango247, PikaPika999

Let define a function $f: \mathbb{N} \rightarrow \mathbb{Z}$ such that :
$i)$ $f(p)=1$ for all prime numbers $p$ .
$ii)$ $f(xy)=xf(y)+yf(x)$ for all positive integers $x,y$
find the smallest $n \geq 2016$ such that $f(n)=n$

This post has been edited 2 times. Last edited by Medjl, Feb 1, 2018, 3:16 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3749 posts

#2 h Feb 1, 2018, 3:13 PM • 2 Y

Y by Adventure10, PikaPika999

Why is this named beautiful problem. Titles are meant for description please.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4071 posts

#3 h Feb 1, 2018, 4:57 PM • 7 Y

Y by rkm0959, Muradjl, Math-Ninja, Com10atorics, Adventure10, Mango247, PikaPika999

Not hard to prove by induction on $s\in \mathbb{Z}^+$ that $f(n)=n\sum_{i=1}^{k}{\frac{\alpha_i }{p_i}}$ where $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ is the canonical form of $n$ with $\sum_{i=1}^{k}{\alpha_i} =s$ .
Hence, $f(n)=n\sum_{i=1}^{k}{\frac{\alpha_i }{p_i}}$ where $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ is the canonical form of $n$ is true for all positive integer $n$ .
We want to find $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ that $f(n)=n\iff \sum_{i=1}^{k}{\frac{\alpha_i }{p_i}} =1$ .

If $k\geq 2$ , we get that $\alpha_i \leq p_i$ for all $i\in \{ 1,2,...,k\}$ .
But we've $\sum_{i=1}^{k}{\alpha_i \times \frac{P}{p_i} }=P$ where $P=\prod_{i=1}^{k}{p_i}$ . Modulo $p_1$ gives us $p_1\mid \alpha_1 \times \frac{P}{p_1}$ , impossible since all $p_i$ s are distinct.

So, $k=1$ . This gives $n=p^p$ for some prime number $p$ .
Easy to see that the smallest such $n$ that not smaller than $2016$ is $3125=5^5$ .

This post has been edited 1 time. Last edited by ThE-dArK-lOrD, Feb 1, 2018, 4:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5348 posts

soryn

#4 h Feb 1, 2018, 9:43 PM • 2 Y

Y by Adventure10, PikaPika999

Very nice! I like this problem, I like this solution! Congratulations!

)))))

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

472 posts

#5 h Feb 4, 2018, 9:10 PM • 3 Y

Y by Adventure10, Mango247, PikaPika999

ThE-dArK-lOrD wrote:

Not hard to prove by induction on $s\in \mathbb{Z}^+$ that $f(n)=n\sum_{i=1}^{k}{\frac{\alpha_i }{p_i}}$ where $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ is the canonical form of $n$ with $\sum_{i=1}^{k}{\alpha_i} =s$ .
Hence, $f(n)=n\sum_{i=1}^{k}{\frac{\alpha_i }{p_i}}$ where $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ is the canonical form of $n$ is true for all positive integer $n$ .
We want to find $n=\prod_{i=1}^{k}{p_i^{\alpha_i}}$ that $f(n)=n\iff \sum_{i=1}^{k}{\frac{\alpha_i }{p_i}} =1$ .

If $k\geq 2$ , we get that $\alpha_i \leq p_i$ for all $i\in \{ 1,2,...,k\}$ .
But we've $\sum_{i=1}^{k}{\alpha_i \times \frac{P}{p_i} }=P$ where $P=\prod_{i=1}^{k}{p_i}$ . Modulo $p_1$ gives us $p_1\mid \alpha_1 \times \frac{P}{p_1}$ , impossible since all $p_i$ s are distinct.

So, $k=1$ . This gives $n=p^p$ for some prime number $p$ .
Easy to see that the smallest such $n$ that not smaller than $2016$ is $3125=5^5$ .

How did you find the function? What's the motivation behind that?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

370 posts

#6 h May 12, 2018, 12:08 PM • 3 Y

Y by Adventure10, Mango247, PikaPika999

It's 2015 Austria MO (maybe not posted yet)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

229 posts

#7 h Apr 6, 2025, 9:25 PM • 1 Y

Y by PikaPika999

Easy to see that $f(0)=0$ and $f(1)=0$ , and them being the only zeroes of this function. One can also say $f$ doesn't take any negative numbers.

Induct to get $f(p^x)=xp^{x-1}$

Let $n=p^x\cdot A$ , where $p\nmid A$ , and assume this number satisfies the given condition

$p^x\cdot A=n=f(n)=f(p^x\cdot A)=p^xf(A)+Af(p^x)=p^xf(A)+xAp^{x-1}$

$LHS\equiv 0~(mod~p^x)\Rightarrow RHS\equiv0~(mod~p^x).$ We get that $p\mid x$ . Rewriting $x=p\cdot k$ gives $(1-k)A=f(A)$ It should be obvious that $k=1$ and $f(A)=0$ . Since $A\neq0$ (Or else $n=0$ ), we have $n=p^p$ . All that is left to find the smallest prime that satisfies $p^p\geq 2016$ , which is $5$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a