24
$\begingroup$

I've seen a few similar questions:

But can we extend these arguments to find a function

$$ f : \mathbb{Z} \to \mathbb{Z}$$ That takes every value infinitely often?

$\endgroup$
  • 2
    $\begingroup$ Have you found a function that takes every value, say, 100 times? What is the progress you made in your attempt? Please share that. $\endgroup$ – P Vanchinathan Oct 30 '16 at 14:03
  • 3
    $\begingroup$ Hint: use the infinitude of the primes $\{p_n\}$. Start with a function that takes $p_n^a$ to $n$ for prime powers. Already that hits the natural numbers infinitely often. $\endgroup$ – lulu Oct 30 '16 at 14:10
  • 1
    $\begingroup$ Indeed, while the integers are countable, this question has uncountably many solutions... $\endgroup$ – Parcly Taxel Oct 30 '16 at 14:39
  • 5
    $\begingroup$ Do you know a bijection $\mathbb Z\rightarrow \mathbb Z\times \mathbb Z$? If so, just compose that with a projection! $\endgroup$ – Milo Brandt Oct 30 '16 at 16:55
  • 1
    $\begingroup$ It suffices to have $\mathbb Z=\cup_{n\in \mathbb Z}S_n$ where each $S_n$ is infinite and $S_m\cap S_n=\emptyset$ when $m\ne n,$ as we can let $ f(x)=n$ for $x\in S_n.$ The answers given are various ways to obtain such $ \{S_n: n\in \mathbb Z\}.$ $\endgroup$ – DanielWainfleet Oct 30 '16 at 20:03

15 Answers 15

39
$\begingroup$

A simple solution would be oscillating further and further away from origin, so f(0), f(1), f(2) ... will be:

0

-1 0 1

-2 -1 0 1 2

....

It's trivial and intuitive to see that each value is taken infinitely often.

$\endgroup$
  • $\begingroup$ For completeness, your function needs to be defined also on the negative integers (e.g. $f(n)=0$ for $n<0$). $\endgroup$ – John Bentin Oct 30 '16 at 17:49
  • 6
    $\begingroup$ That's not hard to deal with, just let it oscillate over positive numbers on the positive semiaxis and vice versa. I really like the elegance of this approach. $\endgroup$ – The Vee Oct 30 '16 at 18:39
  • 1
    $\begingroup$ This is the same as Alex Ravsky's answer (except for an inversion of order). $\endgroup$ – Scott Nov 1 '16 at 22:37
19
$\begingroup$

Hint: you may use the following auxiliary map $g:\Bbb N\to\Bbb Z^2$.

enter image description here

$\endgroup$
9
$\begingroup$

For an explicit example:

$$f(n) = \begin{cases} i, & \text{if $n=p_i^a$ is a prime power} \\ -i, & \text{if $n=6p_i^a$ is six times a prime power}\\ 0, & \text{otherwise} \end{cases}$$

Here $p_i$ denotes the $i^{th}$ prime. Thus $f(27)=2=f(81)$, $f(6)=0=f(15)$, $f(12)=-1$ and so on.

$\endgroup$
8
$\begingroup$

For any positive integer $n$, let $f(n) \ge 0$ be the largest number of factors of two dividing $n$. I.e., $$ f(n) = k \text{ where } 2^k \mid n \text{ and } 2^{k+1} \not\mid n. $$ Also let $f(0) = 0$. Then $f$ gives us what we want: it's a function $\mathbb{N} \to \mathbb{N}$ that takes on every value infinitely many times.


If we must have a function $\mathbb{Z} \to \mathbb{Z}$, we could first use a bijection between $\mathbb{N}$ and $\mathbb{Z}$ and then apply the above example. Alternatively, as celtschk suggests in a comment, we could set $f(-n) = -f(n)$ for all $n > 0$.

$\endgroup$
  • 1
    $\begingroup$ Alternatively, you could simply extend the function from $\mathbb N$ to $\mathbb Z$ by defining $f(-n) = -f(n)$. $\endgroup$ – celtschk Oct 31 '16 at 16:32
  • $\begingroup$ @celtschk Thanks, good suggestion. $\endgroup$ – 6005 Oct 31 '16 at 16:35
7
$\begingroup$

Here is a much simpler prime-related example involving the number-of-divisors function: $$f(n)=\operatorname{sgn}(n)(\tau(|n|)-2)$$ where $\operatorname{sgn}$ is the sign function. $f(n)=0$ for all primes and negations of primes $n$; for non-zero $x$, an infinite sequence of arguments $n_i$ for which $f(n_i)=x$ is $n_i=\operatorname{sgn}(x)p_i^{|x|+1}$ where $p_i$ is the $i$th prime. For example, $f(n)=-1$ for $n=-4,-9,-25,-49,-121,\dots$

$\endgroup$
6
$\begingroup$

Fix an arbitrary bijection $g : \mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}$ and let $\pi : \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$ denote the projection on the first coordinate: $\pi(k, l) = k$. Then

$$f = \pi \circ g$$

is a function that takes every value infinitely many times, because

$$f(n) = k \iff g(n) = (k, l) \text{ for some } l \in \mathbb{Z}.$$

$\endgroup$
  • $\begingroup$ Note: substitute any infinite set for $\mathbb{Z}$ and it still works. $\endgroup$ – Adayah Oct 30 '16 at 17:17
  • 2
    $\begingroup$ This is quite correct. However, if the OP were able to construct an example of a bijection from $\Bbb Z$ to $\Bbb Z^2$, he would probably be well able to answer his own question. $\endgroup$ – John Bentin Oct 30 '16 at 17:41
  • $\begingroup$ For example, the standard pairing function for $\Bbb N$ (en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function) is a start. It's easy to come up with a bijection between $\Bbb N$ and $\Bbb Z$. $\endgroup$ – BrianO Oct 30 '16 at 19:13
5
$\begingroup$

A simple modification of the arithmetic function $d(n)$ should do.

For all odd numbers $n>1$ define $f(n)$ to be the count of distinct prime factors of $n$.

For positive even integers, set $f(n)=0$.

For negative integers $n$ define $f(n)$ to be $-f(-n)$.

For $n=0,1,-1$ define $f(n)=1729$ (or your favourite integer).


Now a prime-free version, with uniform definition for all integers:

Define $g(n)$= number of 7's minus number of 3's in the decimal representation of $n$.

$\endgroup$
  • $\begingroup$ The last line, on its own, would be a fine answer. $\endgroup$ – John Bentin Nov 1 '16 at 22:53
  • $\begingroup$ @John Bentin. Thanks. I have one more solution that I'll post soon. $\endgroup$ – P Vanchinathan Nov 1 '16 at 23:48
4
$\begingroup$

Every natural number $n\in\Bbb N$ can be written uniquely as the sum of a triangular number $\mathrm t_m:=\frac12m^2+\frac12m$ and a number $k_n$, where $m\in\Bbb N$ and $k_n$ runs from $0$ to $m$ corresponding to each $\mathrm t_m$. Thus, to each $n\in\Bbb N$, we can assign $k_n\in\Bbb N$ accordingly. Likewise, for each negative integer $-n$, we can assign the negative integer $-k_n$.

In this way, each integer $\pm k$ (with $k\geqslant0$) is assigned to infinitely many many integers: $-\mathrm t_k-k,-\mathrm t_{k+1}-k,$ and so on or $\mathrm t_k+k,\mathrm t_{k+1}+k,$ etc. The function representing this assignment thus has domain $\Bbb Z$ and maps infinitely many integers to each value $\pm k\in\Bbb Z$.

$\endgroup$
4
$\begingroup$

Let $\{p_0, p_1, p_2, \dots \} = \{2, 3, 5, \dots \}$ be the set of positive prime numbers. If $p_k$ is the smallest positive prime number dividing $n$, then define

$$f(n) = \begin{cases} k, & n>1 \\ -k, & n<-1 \\ 0, & n \in \{-1, 0, 1\} . \end{cases}$$

If $N \ge 0$, then notice that the set $\{p_N ^d \mid d \ge 1\} = \{p_N, p_N ^2, p_N ^3, \dots \}$ is infinite, and for each of its elements $f$ takes the value $N \ge 0$.

If $N \le 0$, then notice that the set $\{- p_{-N} ^d \mid d \ge 1\} = \{- p_{-N}, - p_{-N} ^2, - p_{-N} ^3, \dots \}$ is infinite, and for each of its elements $f$ takes the value $N \le 0$.

$\endgroup$
  • $\begingroup$ What is $p_{-1}$ ? $\endgroup$ – John Bentin Oct 30 '16 at 16:10
  • $\begingroup$ In the third line of your definition of $f$, you write " $k\in\{-1,0,1\}$ ". Now $k$ is defined to be the index (counting from $0$) of the smallest prime, namely $p_k$, dividing $n$. What then is meant by $p_k$ when $k$ is the negative element of the set $\{-1,0,1\}$ ? $\endgroup$ – John Bentin Oct 30 '16 at 17:27
  • $\begingroup$ @JohnBentin: Ah, thank you, that was supposed to be $n$. $\endgroup$ – Alex M. Oct 30 '16 at 17:48
  • $\begingroup$ OK. But you still have a possibly negative subscript for $p$ in the final sentence. $\endgroup$ – John Bentin Oct 30 '16 at 18:02
  • $\begingroup$ @JohnBentin: Thank you, it is reassuring to know that one can rely on one's readers. Now everything should be fine. $\endgroup$ – Alex M. Oct 30 '16 at 18:13
0
$\begingroup$

Some of these are pretty complicated. I like $f(n) = \sigma(n) \left( n \pmod{\lfloor \sqrt{|n|} \rfloor} \right)$, where $\sigma(n) = \begin{cases} -1 ,& n < 0 \\ 0,& n = 0 \\ 1 ,& 0 < n \end{cases}$ is the "sign" function and we use the convention that $0 \pmod{0} = 0$. Not hard to show that the graph of the function is a sequence of pairs of equal height spikes separated by $0$, where each pair is one unit taller than the previous pair. (Use induction and the fact that the sum of sequential odd numbers is square.)

$\endgroup$
0
$\begingroup$

A very simple one:

$$ f(n) = n-2^{\lfloor log_2 |n|\rfloor}\text{sgn}(n) $$ In simple terms, it removes the most significant bit of the integer, leaving the sign intact. I would take $f(0)=0$ (it's not clearly defined by the formula).

$\endgroup$
0
$\begingroup$

I assume that you know that both $\mathbb Z$ and $\mathbb Z\times\mathbb N$ are countably infinite. So take a bijection $\mathbb Z\to\mathbb Z\times\mathbb N$ and compose it with the projection $\mathbb Z\times\mathbb N\to\mathbb Z$.

$\endgroup$
0
$\begingroup$

Here's another simple one: $$f(n) = \begin{cases} n - \lfloor\sqrt{n}\rfloor^2 & n\ge 0\\ -f(-n) & n<0 \end{cases}$$ The values for $n=0,1,2,3,\ldots$ are $0,0,1,2,0,1,2,3,4,0,1,2,3,4,5,6,0,1,2,3,4,5,6,7,8,0,1,\ldots$ In particular, it is $0$ for every perfect square (of which there are infinitely many), and then counts up until the next perfect square is hit. Since the difference between consecutive squares grows monotonously without bound, every positive integer will appear infinitely many time. All negative values are covered by the second case, which just ensures $f(-n)=-f(n)$, therefore making sure that also the negative numbers are encountered infinitely often.

$\endgroup$
0
$\begingroup$

This is another answer. In my other post I'd already given two solutions.

Define the function $h(n)$ by:

$h(n)= 0$ for even integers $n$.

$h(n)={}$ sum of the digits (in base 10) for $n>1$ odd.

$h(n)= -h(-n)$ for $n<0$. This function is infinite-to-one when restricted to (decimal) numbers where each digit is $1$ or $0$.

$\endgroup$
0
$\begingroup$

Here is my fourth solution to this problem.( I have an obsession over this problem!) It is totally different from all the other solutions; uses no number theory or arithmetic function. In fact it uses no mathematics beyond grade 3.

I solve a version that constructs a function from non-negative integers to itself with inverse image infinite for all.

I need to define an infinite word using the alphabet of just two letters B and W. I have inserted spaces inside the word just for readability, but those spaces should be ignored.

BW BBWW BBBWWW BBBBWWWW

That is, k B's followed by an equal number of W's for $k=1,2,3,\ldots$

The function is $f(n) = (\mbox{number of B's}) - (\mbox{number of W's})$ in the initial segment of length $n$.

Proof: Think of this as a tally of goals scored in an infinite football match by teams B and W. We see that B has an upper hand any time, always leading. Our function is the lead. W catches up and with a sequence of goals until they equalize. Before equalization B's lead will be all numbers from $k$ to 1.

Alternative Proof: Think of an infinite series where every term is either $+1$ or $-1$. The above string of B and W can be converted to $+1$ and $-1$. The $n$th partial sum regarded as a function of $n$ is what we are describing.

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