8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Brenton May 17 '15 at 15:23
  • $\begingroup$ @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. $\endgroup$ – veritas May 17 '15 at 15:24
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – veritas May 17 '15 at 16:01
  • $\begingroup$ @KevinChurch How might the function definition be fixed up then? $\endgroup$ – veritas May 17 '15 at 16:14
  • $\begingroup$ I have tried to spell it out in a bit more detail. $\endgroup$ – Rob Arthan May 17 '15 at 16:17
  • $\begingroup$ 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. $\endgroup$ – veritas May 17 '15 at 16:30
  • $\begingroup$ 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. $\endgroup$ – veritas May 17 '15 at 16:32
8
$\begingroup$

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

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – veritas May 17 '15 at 15:45
  • 1
    $\begingroup$ @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}$. $\endgroup$ – N. S. May 17 '15 at 15:46
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm not sure I understand this one. Are you talking about the number of prime factors of $x$? $\endgroup$ – Kitegi May 17 '15 at 15:38
  • $\begingroup$ @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$. $\endgroup$ – Alex W May 17 '15 at 15:40
  • $\begingroup$ And $\eta_0(x)=\eta(x)-1$ if you have $0\in\mathbb{N}$, with $\eta_0(0)=42$. $\endgroup$ – egreg May 17 '15 at 15:52
  • $\begingroup$ @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. $\endgroup$ – veritas May 17 '15 at 15:56
  • $\begingroup$ @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$. $\endgroup$ – Alex W May 17 '15 at 16:02
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – veritas May 17 '15 at 15:34
  • $\begingroup$ @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) $\endgroup$ – Kitegi May 17 '15 at 15:34
  • $\begingroup$ My answer's equivalent. Just not recursive $\endgroup$ – jkabrg May 17 '15 at 15:55
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Observe that the function $\eta$ must map the natural numbers into natural numbers...+1 $\endgroup$ – k1.M May 17 '15 at 22:37
  • $\begingroup$ @k1.M I think you changed the content of this answer somewhat by having the $-1$. $\endgroup$ – veritas May 17 '15 at 22:46
  • $\begingroup$ 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$. $\endgroup$ – k1.M May 17 '15 at 22:49
  • $\begingroup$ @k1.M Aren't you then claiming $\eta(1)=0$, a number that is not a natural number? $\endgroup$ – veritas May 17 '15 at 22:54
  • $\begingroup$ Observe that we have $\eta(1)-1=1$, hence $\eta(1)=2$. $\endgroup$ – k1.M May 17 '15 at 22:55
3
$\begingroup$

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

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.