An example of a mapping $\eta\colon\mathbb{N}\to\mathbb{N}$ such that $\eta(x)=n$ has infinitely many solutions for each $n\in\mathbb{N}$

Question

Suppose I have the mapping $\eta\colon\mathbb{N}\to\mathbb{N}$ such that for each $n\in\mathbb{N}$ the equation $\eta(x)=n$ has infinitely many solutions. I saw this question which is basically the same thing, but some of the examples/solutions are a bit over my head.

I was wondering if someone might know of a closed-form definition for $\eta(x)$ that is relatively simple that accomplishes the goal at hand. There doesn't seem to be anything all that simple even though it is easy to understand the problem. I was thinking of trying to use a trigonometric function, the floor or ceiling function, something modular, etc., but nothing is working out very nicely. Any examples of some mapping definitions that might work out nicely?

Answer 1

$\eta(x) = \lfloor |\tan(x)| \rfloor$ will do, because (1) $\tan$ is periodic with period $\pi$ and maps the set $D = [0, \pi/2) \cup (\pi/2, \pi)$ continuously onto $\mathbb{R}$ and (2) for any $n\in\mathbb{N}$, reduction modulo $\pi$ maps $\{m \in \mathbb{N} \mathrel{|} m > n\}$ onto a dense subset of $D$. Statements (1) and (2) imply that for any real number $y$ and any given $\epsilon > 0$, $|\tan(m) - y| < \epsilon$ for infinitely many $m \in \mathbb{N}$. So given $n \in \mathbb{N}$, take $y = n + 1/4$ and $\epsilon = 1/8$, to get infinitely many $m\in\mathbb{N}$ for which the floor of $\tan(m)$ is $n$.

Answer 2

You could choose $$\eta(0,1,2,3,4,5,6\dots)= (\color{red}0,\color{blue}{0,1},\color{orange}{0,1,2},\color{green}{0,1,2,3}\dots)$$

i.e: $\eta(0)=\eta(1)=0$ and

$$ \eta(n+1) = \begin{cases} \eta(n)+1 & \text{if } \eta(n)\leq \max\{\eta(0),\dots,\eta(n-1)\} \\ 0 & \text{otherwise} \end{cases} $$

It's easy to see that $\eta(x)=n$ has infinitely many solutions.

Answer 3

Let for any $x\in \mathbb N$, $x>1$ $\eta(x)$ be the number of factors in factorization of $x$ in the product of prime numbers. We define $\eta(1)=1$. Then $\eta$ satisfies your conditions. Here $\mathbb N=\mathbb{Z}_{>0}$.

Another variant: Infinite Hotel.

Third variant. For $x\in\mathbb N$ let $\eta(x)=1+\max\{k\in\mathbb{Z}_{\geq 0}:2^k\mid x\}$, in other words, $\eta(x)=1+$ the length of "zero tail" of $x$ in binary expansion of x. Instead of two, you can take any other natural number greater than $1$ (inspired by HowDoIMath).

After all, I found Hilbert's Hotel.

Answer 4

$\eta\left(x + \frac{n(n+1)}{2}\right) = x$ where $x \leq n$.

Equivalently, $\eta(x) = x - \frac{n(n+1)}{2}$ where $n$ is such that $\frac{n(n+1)}{2} \leq x < \frac{(n+1)(n+2)}{2}$, $\therefore n = \lfloor\frac{1}{2}(\sqrt{8x+1} - 1)\rfloor$

This is a nonrecursive formulation of Farnight's answer.

Answer 5

$d(n)=$ the number of divisors of $n$.

Note that $d(p^{n-1})=n$ for all primes $p$.

Answer 6

Let $x\in\mathbb{N}$, and let $\eta(x)$ be the number of times the digit 1 appears in the binary expansion of $x$.

For any $n$, the equation $\eta(x)=n$ has infinitely many solutions. For instance, if $n=4$, then the numbers with the binary expansions $1111$, $11110$, $\ldots$, $111100\ldots 00$ are all mapped to $4$.

Notice that in this example, we have $\mathbb{N}=\{1,2,3,\ldots\}$, i.e. $0\not\in\mathbb{N}$.

As suggested in the comments, one can also let $\eta(x)-1$ be the number of times the digit $1$ appears in the decimal expansion of $x$.

Answer 7

Let $A_{1}$ be the set of all positive integer whose lowest prime factor is 2 , $A_{2}$ be the set of all positive integer whose lowest prime factor is 3 , $A_ {3} $ be the set of all positive integer whose lowest prime factor is 5 and so on....clearly $A_{i}$ are infinite and mutually disjoint. Now define $\eta \colon \mathbb{N} \rightarrow\mathbb{N}$ by $ \eta (x) = 1 $ if $ x \in A_{1}\cup\{1\}$

= 2 if $ x\in A_{2}$
= 3 if $ x \in A_{3}$
= 4 if $ x \in A_{4}$
and so on.. Note that this is well defined map. How? .....this works and simple

Answer 8

Here is another simple example:

Write $n$ in binary (or any other basis) and define $\eta$ to be the erasing of the first digit.

This has the desired property because for all integers $x$, as long as $2^m >x$ we have $$\eta(2^m+x) =x$$