MathDB
Problems
Contests
International Contests
Balkan MO Shortlist
2014 Balkan MO Shortlist
N6
N6
Part of
2014 Balkan MO Shortlist
Problems
(1)
function
Source:
5/18/2015
Let
f
:
N
→
N
f: \mathbb{N} \rightarrow \mathbb{N}
f
:
N
→
N
be a function from the positive integers to the positive integers for which
f
(
1
)
=
1
,
f
(
2
n
)
=
f
(
n
)
f(1)=1,f(2n)=f(n)
f
(
1
)
=
1
,
f
(
2
n
)
=
f
(
n
)
and
f
(
2
n
+
1
)
=
f
(
n
)
+
f
(
n
+
1
)
f(2n+1)=f(n)+f(n+1)
f
(
2
n
+
1
)
=
f
(
n
)
+
f
(
n
+
1
)
for all
n
∈
N
n\in \mathbb{N}
n
∈
N
. Prove that for any natural number
n
n
n
, the number of odd natural numbers
m
m
m
such that
f
(
m
)
=
n
f(m)=n
f
(
m
)
=
n
is equal to the number of positive integers not greater than
n
n
n
having no common prime factors with
n
n
n
.
number theory
function