38
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Very good question. In general, a lot of things we can find by trial and error, and after we find it we may discover some simpler way to obtain it, such as dxiv's answer. But I can bet that dxiv first found it by trial and error also, if he/she didn't already see it before... To further hone your trial and error skills, try to find a simple formula for $1,2,3,2,1,2,3,2,...$ and $1,1,2,1,2,3,1,2,3,4,...$. =) $\endgroup$ – user21820 Mar 6 '18 at 8:17
  • 2
    $\begingroup$ Oh and I should say that if you're interested in a program, the easiest way to repeat any sequence in general is to use a list. In my first exercise, def f(n): return [2,1,2,3][n%4] would finish the job quickly and cleanly. $\endgroup$ – user21820 Mar 6 '18 at 8:24
  • 4
    $\begingroup$ @WilliamElliot: The notation $f : S \to T$ does not imply that $f$ must be a surjection from $S$ onto $T$. The question is wrong only in calling the desired output sequence a set. $\endgroup$ – user21820 Mar 6 '18 at 8:26
  • 30
    $\begingroup$ I just want to note here - since somehow no one has yet - that 'the function which repeats the pattern 1, 2, 3, 1, 2, 3, ...' is a perfectly good definition of the function in its own right. Be careful not to confuse a function with a formula for the function. $\endgroup$ – Steven Stadnicki Mar 6 '18 at 18:42
  • 2
    $\begingroup$ There's nothing wrong with "trial and error". That's the exact method by which a huge amount of mathematics is discovered. $\endgroup$ – Lee Mosher Mar 7 '18 at 18:30

13 Answers 13

43
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ To generalize the observations in this answer: if you want to repeat the first $p$ members of an arithmetic sequence $a_k=m(k-1)+d$, then the function you need is $m((k-1)\bmod p)+d$ $\endgroup$ – J. M. is a poor mathematician Mar 6 '18 at 5:54
  • $\begingroup$ @J.M.isnotamathematician Indeed, worth pointing out. $\endgroup$ – dxiv Mar 6 '18 at 6:05
39
$\begingroup$

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

$\endgroup$
  • 14
    $\begingroup$ As it turns out, explicitly evaluating the matrix power and simplifying yields a remarkably simple expression: $$1-\frac1{\sqrt{3}}\sin\frac{2\pi k}{3}+2\sin^2\frac{\pi k}{3}$$ $\endgroup$ – J. M. is a poor mathematician Mar 7 '18 at 13:21
  • 12
    $\begingroup$ I would argue it is not a simpler expression. Trancendental functions and irrational numbers are lots less simple computationally speaking than binary shuffles / pointer arithmetics which you can implement permutation matrices with. $\endgroup$ – mathreadler Mar 7 '18 at 13:58
  • 1
    $\begingroup$ @J.M.isnotamathematician. FWIW this is the same as $ 2-\frac{2}{\sqrt{3}}\sin(2k+1)\frac{\pi}{3}$ $\endgroup$ – David Quinn Mar 7 '18 at 14:09
  • 2
    $\begingroup$ This is not an answer to the question. $\endgroup$ – JiK Mar 8 '18 at 10:44
  • 3
    $\begingroup$ I suspect @JiK means that this does not give what the questioner asked for, namely a systematic approach to arriving at the formula they themself found, i.e. $ ( ( x - 1 ) \bmod n ) + 1 $. $\endgroup$ – PJTraill Mar 8 '18 at 21:59
19
$\begingroup$

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

$\endgroup$
  • 7
    $\begingroup$ Ingenious (+1) though not too practical computationally. $\endgroup$ – dxiv Mar 6 '18 at 6:02
  • 2
    $\begingroup$ This is not an answer to the question. $\endgroup$ – JiK Mar 8 '18 at 10:44
  • 2
    $\begingroup$ I presume @JiK means that this does not give what the questioner asked for, namely a systematic approach to arriving at the formula they themself found, i.e. $ ( ( x - 1 ) \bmod n ) + 1 $. $\endgroup$ – PJTraill Mar 8 '18 at 22:00
18
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is not an answer to the question. $\endgroup$ – JiK Mar 8 '18 at 10:44
  • $\begingroup$ @JiK no perhaps not, but I thought I'd post it anyway. $\endgroup$ – David Quinn Mar 8 '18 at 18:58
  • $\begingroup$ @JiK is right: this does not give what the questioner asked for, namely a systematic approach to arriving at the formula they themself found, i.e. $ ( ( x - 1 ) \bmod n ) + 1 $. $\endgroup$ – PJTraill Mar 8 '18 at 22:00
  • 3
    $\begingroup$ @PJTraill So what? The OP is not the only one who reads these Q/As, and this and other answers giving alternate expressions (and systematic methods for finding them) are by no means off topic. If you dispute this, you should take it up on meta instead of spamming everyone's answers. $\endgroup$ – Mario Carneiro Mar 9 '18 at 3:24
10
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ For that portion of the audience allergic to complex numbers .... these can be done with trigonometric functions instead of complex exponentials. $\endgroup$ – GEdgar Mar 6 '18 at 12:10
  • $\begingroup$ @GEdgar I guess it comes down to whether people are more allergic to complex numbers or otherwise hard-to-remember compound angle formulae. $\endgroup$ – J.G. Mar 6 '18 at 15:50
  • 1
    $\begingroup$ This is not an answer to the question. $\endgroup$ – JiK Mar 8 '18 at 10:45
  • $\begingroup$ @JiK: This answer introduces a systematic way to build sequences $(a_1,a_2,a_3,...,a_n,a_1,a_2,...)$ consisting of repeated sub-sequences. All the more it provides a systematic way to build sequences $(1,2,3,...,n,1,2,...) which was OPs question. $\endgroup$ – Markus Scheuer Mar 8 '18 at 11:04
  • 1
    $\begingroup$ @MarkusScheuer The question is "How would one come to this result in a more systematic way?" (emphasis mine) $\endgroup$ – JiK Mar 8 '18 at 11:18
9
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ And it looks like a conjugation if you write it $f = f_1^{-1} \circ f_2 \circ f_1$. $\endgroup$ – Jeppe Stig Nielsen Mar 6 '18 at 23:19
  • 2
    $\begingroup$ I like this answer best because it actually gives a systematic way to convert the function $x \bmod 3$ into the function that was desired. $\endgroup$ – David K Mar 7 '18 at 2:01
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This does not give what the questioner asked for, namely a systematic approach to arriving at the formula they themself found, i.e. $ ( ( x - 1 ) \bmod n ) + 1 $. $\endgroup$ – PJTraill Mar 8 '18 at 22:02
5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I created a answer very much like yours but yours is both more general and correct. $\endgroup$ – Q the Platypus Mar 7 '18 at 3:55
  • 1
    $\begingroup$ This does not give what the questioner asked for, namely a systematic approach to arriving at the formula they themself found, i.e. $ ( ( x - 1 ) \bmod n ) + 1 $. $\endgroup$ – PJTraill Mar 8 '18 at 22:03
  • $\begingroup$ @PJTraill You're absolutely right. I apparently didn't read the question carefully enough. $\endgroup$ – HelloGoodbye Mar 9 '18 at 10:57
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is basically the definition of mod function. $a \mod b = a-b\lfloor{a\over b}\rfloor$ :) except it's shifted by one horizontally and then verticall $\endgroup$ – KKZiomek Mar 8 '18 at 4:29
  • $\begingroup$ @KKZiomek I don't say it is not :-) And I believe that this view is self-explanatory, that's why I consider it good for educational purposes. $\endgroup$ – yo' Mar 8 '18 at 8:49
  • $\begingroup$ This does not give (or only indirectly gives) what the questioner asked for, namely a systematic approach to arriving at the formula they themself found, i.e. $ ( ( x - 1 ) \bmod n ) + 1 $. $\endgroup$ – PJTraill Mar 8 '18 at 22:02
  • $\begingroup$ @PJTraill Well, that's true, but I still think that the way I show is a related point that could be useful in grasping the whole topic. $\endgroup$ – yo' Mar 8 '18 at 22:16
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ ▲ A useful description of the effects of the various steps involved in reaching the answer. $\endgroup$ – PJTraill Mar 8 '18 at 21:55
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This does not give what the questioner asked for, namely a systematic approach to arriving at the formula they themself found, i.e. $ ( ( x - 1 ) \bmod n ) + 1 $. $\endgroup$ – PJTraill Mar 8 '18 at 22:03
2
$\begingroup$

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

$\endgroup$

protected by J. M. is a poor mathematician Mar 7 '18 at 15:29

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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