Integer function which takes every value infinitely often I've seen a few similar questions:


*

*Function which takes every value uncountably often

*Construct a function $f:[0,1] \to [0,1]$ that takes every value in $[0,1]$ an infinite number of times.
But can we extend these arguments to find a function
$$ f : \mathbb{Z} \to \mathbb{Z}$$
That takes every value infinitely often?
 A: 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$
A: 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}.$$
A: 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$.
A: 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.
A: 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$.
A: 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$.
A: Hint: you may use the following auxiliary  map $g:\Bbb N\to\Bbb Z^2$.  

A: 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.
A: 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$.
A: 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.
A: 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.)
A: 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).
A: 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$.
A: 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$. 
A: 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. 
