is there a function $f:\mathbb{N}\rightarrow \mathbb{N}$ such that $i) \exists n\in \mathbb{N}:f(n)\neq n$ $ii)$ the number of divisors of $m$ is $f(n)$ if and only if the number of divisors of $f(m)$ is $n$
Problem
Source: iran tst 2014 third exam
Tags: function, number theory, prime numbers, number theory proposed
22.05.2014 17:27
Am i terribly dumb or we just take $f$ multiplicative and $f(p_1)=p_2,f(p_2)=p_3,...$ where $p_i$ is the primes sequence?
22.05.2014 17:49
@MariusBocanu : I think you're wrong, Because if f(p∨1)=(p∨2) then (p∨1) should have (p∨2) divisors so (p∨i=2) which is contradiction. Am I wrong??
22.05.2014 17:52
Oh, i totally misunderstood the problem. I read $m$ has the same number of divisors as $f(n)$ if and only if $f(m)$ has the same number of divisors as $n$. Sorry about that.
25.05.2014 20:58
I Think the answer is Yes. Let $d(m)$ be the number of divisors of $m$. Let $T(n)$ be the set of numbers $x$ such that $d(x)=n$. We have that $d(m)=f(n) \Leftrightarrow d(f(m))=n$. So, first let $f(1)=1$, $f(2)=2$. Let $n\ge 2$ be an integer. Clearly if we apply function $d$ to $n$ many times, we will reach $2$. Let $h(n)$ be the number of iterations needed to reach $2$. Let $h(2)=0$. For all $k \ge 0$, for all $i_1,...,i_k$ positive integers, I will define the set $X_{ki_1...i_k}$ recursivlely as follows. $X_{ki_1...i_k}$ will be the set of numbers that are the $i_k$-th smallest element of $T(x)$, where $x$ runs across $X_{(k-1)i_1...i_{k-1}}$. It is easy to see that $n\ge 3$ belongs to exactly one of these sets. Let $k=h(n)-1$. Define $i_k$ so that $n$ is the $i_k$-th smallest element of $T(d(n))$. Let $i_{k-1}$ be so that $d(n)$ is the $i_{k-1}$ smallest element of $T(d(d(n))$. And so on, until we reach a number that belongs to $X_0$ (a prime number). By definition, $k$ was defined correctly. It is also clear that each $X$-set is infinite. Now, for each $n \ge 3$ we will have that $f(n)$ will belong to the same $X$-set that $n$ does. Define $f$ in $X_0$ randomly, as long as its a bijection. In other words, order the odd prime numbers like this: $,...,p_{-1},p_0,p_1,...$ and let $f(p_i)=p_{i+1}$. Now, for set $X_{ki_1...i_k}$, let $n$ be any element of that set. We define $n$ as follows. Consider $f$ in $X_{(k-1)i_1...i_{k-1}}$. If $f(m)=d(n)$ then we will have exactly one number $m'$ in $X_{ki_1...i_k}$ such that $d(m')=m$. So we will define $f(n)=m'$. So we have defined $f$ such that it's a bijection, it's well defined and clearly $f(3)\neq 3$. Also, if $d(m)=f(n)$ then by definition, $f(m)=n'$ where $n'$ is such that $d(n')=n$. Also, if $d(f(m))=n$ then by definition $d(m)=f(n)$, by the recursive definition of the $X$-sets. So such a function does exist.