# 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}$

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?

• The first thing for me that comes to mind is some modification of $\left \lceil{tan x}\right \rceil$, but I haven't had enough time to verify – Brenton May 17 '15 at 15:23
• @Brenton That's what I was thinking about a little while ago, but I think the issue is that $x\in\mathbb{N}$. If we had $\eta\colon\mathbb{R}\to\mathbb{N}$, then I think that might work, but I don't think it will work as is. – veritas May 17 '15 at 15:24

$\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$.

• Okay. I'm interested in really understanding this answer because this is actually what I originally had in mind, but I thought this would not work because we have $\eta\colon\mathbb{N}\to\mathbb{N}$ instead of $\eta\colon\mathbb{R}\to\mathbb{N}$. Doesn't that cause an issue? It doesn't seem like we could actually map to all values of $\mathbb{N}$ using only values of $\mathbb{N}$ as inputs into $\tan(x)$. Where am I going wrong here? – veritas May 17 '15 at 16:01
• @KevinChurch How might the function definition be fixed up then? – veritas May 17 '15 at 16:14
• I have tried to spell it out in a bit more detail. – Rob Arthan May 17 '15 at 16:17
• Hm. I guess I'm just getting confused with notation now. It seems like you're saying to define $\eta(x)=\lfloor|\tan(x)|\rfloor=n$ where this will have infinitely many solutions. Sorry I'm a bit dense--no pun intended. – veritas May 17 '15 at 16:30
• I'm not entirely sure what you mean by $\{m:\mathbb{N}\mid m>n\}$ either. Did you mean $m\in\mathbb{N}$? Otherwise, I'm not sure how that fits in precisely. – veritas May 17 '15 at 16:32

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

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

• This seems like it might be the easiest way to look at it. How would $\eta(x)$ be defined then? Depends on the prime number under consideration right? – veritas May 17 '15 at 15:45
• @veritas $\eta(x)=d(x)$. The standard formula is $\eta(x)=(a_1+1)...(a_k+1)$ where $x=p_1^{a_1}... p_k^{a_k}$. – N. S. May 17 '15 at 15:46

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.

• I'm not sure I understand this one. Are you talking about the number of prime factors of $x$? – Kitegi May 17 '15 at 15:38
• @Farnight Let $1<x\in\mathbb N$. Then we can find primes $p_1,\ldots,p_l$ such, that $x=p_1\cdot\ldots\cdot p_l$. We define $\eta(x)=l$. If $x=1$, then $\eta(x)=1$. – Alex W May 17 '15 at 15:40
• And $\eta_0(x)=\eta(x)-1$ if you have $0\in\mathbb{N}$, with $\eta_0(0)=42$. – egreg May 17 '15 at 15:52
• @AlexW What if $n=6$? You would have $\eta(x)=6$. Are you saying, then, $x=p_1\cdot p_2=2\cdot 3=6$? Could you give an example? I'm not entirely sure I understand your answer just yet. – veritas May 17 '15 at 15:56
• @veritas $6=2\cdot 3$. Here we have 2 prime factors, hence $\eta(6)=2$. Another example. Let $x=4!$. Then $x=2\cdot 3\cdot 2\cdot 2$ - $4$ prime factors. Hence $\eta(x)=4$. – Alex W May 17 '15 at 16:02

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.

• Is this any different than G. H. Faust's answer on the other thread (the linked to question)? I feel like there must be a somewhat simple mapping definition lurking out there. Just don't see it. At all. – veritas May 17 '15 at 15:34
• @veritas Sorry about that. I didn't check the other thread before posting. But the formula for $\eta$ is made explicit in here. (recursive definition) – Kitegi May 17 '15 at 15:34
• My answer's equivalent. Just not recursive – ogogmad May 17 '15 at 15:55

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$.

• Observe that the function $\eta$ must map the natural numbers into natural numbers...+1 – k1.M May 17 '15 at 22:37
• @k1.M I think you changed the content of this answer somewhat by having the $-1$. – veritas May 17 '15 at 22:46
• Yes that was needed, because the function maps natural numbers to itself, hence by new definition $\eta(2)-1=0$ which means that $\eta(2)=1$. – k1.M May 17 '15 at 22:49
• @k1.M Aren't you then claiming $\eta(1)=0$, a number that is not a natural number? – veritas May 17 '15 at 22:54
• Observe that we have $\eta(1)-1=1$, hence $\eta(1)=2$. – k1.M May 17 '15 at 22:55

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

• This is almost completely indecipherable. – veritas May 17 '15 at 23:35
• Ok...i made typing mistake. Now clear? – user195218 May 18 '15 at 0:02
• A good idea. I also thought about it ) – Alex W May 18 '15 at 0:23

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$$

$\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.