Function which creates the sequence 1, 2, 3, 1, 2, 3, ...

Question

I was wondering how to map the set $\mathbb{Z}^+$ to the sequence $1, 2, 3, 1, 2, 3, \ldots$. I thought it would be easy, but I was only able to obtain an answer through trial and error.

For a function $f \colon \mathbb{Z}^+ \rightarrow \mathbb{Z}$, we have that

$f(x) = x \bmod 3$ gives the numbers $1, 2, 0, 1, 2, 0, \ldots$

$f(x) = (x \bmod 3) + 1$ gives the numbers $2, 3, 1, 2, 3, 1, \ldots$

After a bit of experimenting, I finally found that

$f(x) = ((x + 2) \bmod 3) + 1$ gives the numbers $1, 2, 3, 1, 2, 3, \ldots$

More generally, if I want to map the set $\mathbb{Z}^+$ to the sequence $\{1, 2, \ldots, n, 1, 2, \ldots, n, \ldots\}$, I need to use the function

$$f(x) = ((x + n - 1) \bmod n) + 1$$

I was only able to come to this result by trial and error. I was not able to find a solution to this relatively simple question online (although perhaps my search terms were off).

How would one come to this result in a more systematic way?

Answer 1

You figured out already that $\,x \bmod n\,$ gives the periodic sequence $\,(1, 2, \ldots, n-1, \color{red}{0}, 1, \ldots)\,$ then the rest is just "shifting" it to fit the desired start/end values. To match $\,(1, 2, \ldots, \color{red}{n}, 1, \ldots)\,$ for example, you need to shift $\,x \bmod n\,$ up by $\color{blue}{1}$, and $\,x\,$ down by $\color{green}{1}$ to compensate for it. So in the end you'd be getting $\,\color{blue}{1} + (x-\color{green}{1}) \bmod n\,$, and of course $\,(x-1) \bmod n = (x+n-1) \bmod n\,$.

Answer 2

The $k$:th number will be: $$[1,0,0]{\bf C}^k[1,2,3]^T$$

where ${\bf C}= \left[\begin{array}{ccc}0&1&0\\0&0&1\\1&0&0\end{array}\right]$

Now you can exchange the vector to the right for any ordered set of numbers you want to $\bf C$ycle through.

---

(It is actually a representation matrix for a generator of the cyclic group $C_3$ if you want to dig into some theory).

---

Now to make this a function of $k$, (which is actually what is asked), maybe you prefer the notation

$$k\overset{f(k)}{\longrightarrow} [1,0,0]{\bf C}^k[1,2,3]^T$$ or maybe

$$f(k)= [1,0,0]{\bf C}^k[1,2,3]^T$$

Answer 3

As an alternative, here is a purely trigonometric function which generates the required sequence:

$$f(x)=\frac{\sqrt{3}\sin(\frac 23\pi(x-2))}{\cos(\frac 23\pi(x-2))+2}+2$$

Here we have $f(1)=1$, $f(2)=2$, $f(3)=3$, $f(4)=1$, and so on.

Answer 4

$f(x)=\left\lfloor 10^x\cdot {123\over999}\right\rfloor\mod 10$.

More generally, with $b>n>1$, $$f(x)=\left\lfloor b^x\cdot {(123\ldots n)_b\over b^n-1}\right\rfloor\mod b. $$

Answer 5

Let's assume we want to find a formula for the sequence \begin{align*} \color{blue}{3,1,\frac{1}{3},\frac{1}{3},1,3,3,1,\frac{1}{3},\frac{1}{3},1,3,3,1,\frac{1}{3},\frac{1}{3},1,3,\ldots} \end{align*} repeating in cycles of $6$ elements.

The $r$-th roots of unity $\omega_j=\exp\left(\frac{2\pi ij}{r}\right), 0\leq j<r$ have the nice property to filter elements. For $r>0$ we obtain \begin{align*} \frac{1}{r}\sum_{j=0}^{r-1}\exp\left(\frac{2\pi ij n}{r}\right)= \begin{cases} 1&\qquad r\mid n\\ 0& \qquad otherwise \end{cases} \end{align*} Therefore the sequence \begin{align*} \left(\frac{1}{6}\sum_{j=0}^5\exp\left(\frac{2\pi ijn}{6}\right)\right)_{n=0}^{\infty} =(\color{blue}{1},0,0,0,0,0,\color{blue}{1},0,0,0,0,0,\color{blue}{1},\ldots)\tag{1} \end{align*} generates a $1$ at each $6$-th position and $0$ otherwise and multiplication with $3$ gives a sequence with $3$ at each $6$-th position and $0$ otherwise.

Appropriately shifting of (1) can be used to generate a $1$ on each $6$-th position shifted by $k$ positions with $0\leq k < 6$. Multiplication with $3,1$ and $\frac{1}{3}$ and adding all these terms provides the wanted sequence.

Hint: Some instructive examples can be found in H.S. Wilf's book generatingfunctionology, (2.4.5) to (2.4.9).

Answer 6

I'm surprised no one has mentioned composition. You've identified that you need to shift the range

$$f_1(x) = x - 1$$

then take the value modulo $n$

$$f_2(x) = x \mod n$$

and finally shift the result again

$$f_3(x) = x + 1$$

The function you want is just the composition $f = f_3 \circ f_2\circ f_1$.

Answer 7

Let be $\omega\in\Bbb C$, $\omega^3 = 1$, $\omega\ne 1$. $\omega^n$ gives: $$\omega^0 = 1,$$ $$\omega^1 = \omega,$$ $$\omega^2 = \omega^{-1},$$ $$\omega^3 = 1,$$ $$\cdots$$ "But I want $1,2,3,\dots$!" Solution: compose with a polynomial $P$ s.t. $$P(1) = 1,\qquad P(\omega) = 2,\qquad P(\omega^{-1}) = 3.$$ Now, $$P(\omega^0) = 1,$$ $$P(\omega^1) = 2,$$ $$P(\omega^2) = 3,$$ $$P(\omega^3) = 1,$$ $$\cdots$$ This trick will work for any periodic sequence.

Answer 8

The function

$$f(x)=\left\{ \begin{array}{ll} x, & \text{if } x \leq n\\ f(x-n), & \text{otherwise} \end{array}\right.$$

maps the set $\mathbb{Z}^+$ to the sequence $\{1, 2, \ldots, n, 1, 2, \ldots, n, \ldots\}$. Is this way "more systematic" to you?

Answer 9

Well, there are many answers to this actually, for instance $$ f(n) = n + 1 - 3\lfloor n/3\rfloor $$ (assuming $\mathbb Z^+$ starts with $0$).

How to come to this? The basic idea is that $s(x)=x-\lfloor x\rfloor$ is the sawtooth function with range $[0,1)$. Then $ns(x/n)$ is the same function scaled $n$ times in both directions, i.e., it's the sawtooth function with range $[0,n)$. However, you need range $[1,n+1)$, so that's the “$+1$” part.

Answer 10

f(x) = ((x−1) mod n) + 1

Step 1: You want a function with a period of n, i.e. it repeats every n numbers. Then necessarily you are modding something by n. g(x) = h(x) mod n Step 2: You want the function to reset after every nth number. But the nature of modular division is that it resets on every nth number, not after every nth number. So you necessarily have to subtract 1 before performing modular division. h(x) = x - 1. g(h(x)) = (x - 1) mod n. This is a horizontal shift, akin to an x-intercept. Step 3: You want the function to vary from 1 to n, but the nature of modular division is to vary from 0 to n-1. So you have to add 1 to each term after the modular division. i(x) = g(h(x)) + 1 = ((x - 1) mod n) + 1. This is a vertical shift, akin to a y-intercept. Unnecessary step 4: If you wanted each term to be a multiple of 1 through n, i.e. (3, 6, 9, ... 3n), you would perform multiplication last. I.e. j(x) = 3 * i(g(h(x)) = 3 * (((x - 1) mod n) + 1). This is an amplitude shift, akin to a slope.

Answer 11

In group theory, the modulus function is often taken to be a function from Z to Z/nZ. That is, the output is not an integer, but the equivalence class of integers that have the same remainder when divided by n. E.g. 1->{...-5,-2,1,4,7...}. In computer science, on the other hand, modulus functions generally give a particular representative of the equivalence class, more specifically whatever representative lies in [0,n-1]. You're trying to instead get the representative that lies in [1,n]. Note that this differs only in how 0+nZ is treated; the standard function sends it to 0, but you want it sent to n. So if you were writing a program, one option would be to simply do output = (k mod n) then if output==0: output=n. However, that's somewhat of an inelegant solution.

A solution that is in some sense more elegant is to realize that you want your output range shifted up one. If you do output = (k mod n)+1, then instead of your output ranging from 0 to n-1, your output will be 1 to n. However, this shifts not only the output range, but also what each input goes to; 1 goes to 2 instead of 1, 2 goes to 3, etc. If you subtract 1 before taking the modulus, then this will cancel out with the adding 1 afterwards. The exception to this will be multiples of n; by subtracting 1, you get to n-1, then when you add 1 afterwards, you get to n, instead of 0.

Your formula adds n-1 instead of subtracting 1, but since (n-1) mod n = -1, this amounts to the same thing.

One way of visualizing this is imagining n tick marks in a circle. There's a tick mark labeled 1, a tick mark labeled 2, etc., up to n-1. But when you get to n, the tick mark is labeled 0, and then at n+1 you're back at the tick mark labeled 1. What if you want your output for n to be n, instead of 0? Well, you can think of there being a "drop" between the tick mark labeled n-1 and the one labeled 0; between those two tick marks, the output drops from n-1 to 0. You want to move n over to before this drop, and make the drop to instead be between n and n+1. So to move n to before the drop, you subtract 1; this shifts n over to before the drop. But now you need to add 1 back. The addition and subtraction cancel out in the sense that you end up in the same equivalence class (remember, the equivalence class for both 0 and n is {-2n,-n,0,n,2n...}), but by doing the subtraction before doing the modulus, and the addition after, you end up with a different representative.

More generally, if you want to shift j numbers from the beginning to the end, you can do (k-j) mod n + j. For instance, k mod 12 would take k to between 0 and 11, but (k-3) mod 12 + 3 will take k to between 3 and 14. To go the other way, you reverse the addition and subtraction; (k+3) mod 12 - 3 will take k to between -3 and 8.

Answer 12

Maybe those with allergies to both complex numbers and trigonometry are more tolerant to homogeneous coordinate transforms?

$$ f(k) = [1 \ 0\ 2] \begin{bmatrix} -\frac12 & -\frac{\sqrt3}2 & 0 \\ \frac{\sqrt3}2 &-\frac12 & 0 \\ 0 & 0 & 1 \end{bmatrix}^k \begin{bmatrix} 1 \\ \frac{\sqrt3}3 \\ 1 \end{bmatrix} $$

Answer 13

Your only problem is that you're counting up from one. If you started counting from zero, then $$f(x) = x \bmod 3$$ would do the job, generating the output sequence $0,1,2,0,1,2,0,1,2,\dots$ when applied to the input sequence $0,1,2,3,4,5,6,7,8,\dots$.

But if you insist on one-based counting, then you simply need to shift the input down by one, and the output correspondingly up by one, as in $$f(x) = ((x-1) \bmod 3) + 1.$$ This will generate the output sequence $1,2,3,1,2,3,1,2,3,\dots$ when applied to the input sequence $1,2,3,4,5,6,7,8,9,\dots$.