Integer function which takes every value infinitely often

Solution 1:

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.

Solution 2:

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

Solution 3:

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.

Solution 4:

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

Solution 5:

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$