Important: As before, when reading these, you don’t need to memorize the terms. We won’t give you an exam about them. Instead, we want you to really understand them. If you encounter a term again in a later chapter but forgot what it means, you can simply refer back to this page. No penalties for that!

Functions

You probably encountered functions in high school, and you probably had to learn to plot functions like $f(x) = x^2 + 2x + 1$ on graphing paper. But the thing is, these functions you encountered are probably just functions from real numbers to real numbers. Functions are much more than that, and not all functions can be plotted as a graph.

A function is really just a mapping from a set to another set. In other words, a function $f$ is just a mapping from a set $A$ to another set $B$. For example, say $A = \{1, 2, 3\}$ and $B = \{7, 8, 9\}$. Then we can define three functions $f_1$, $f_2$ and $f_3$:

• $f_1$ maps $1 \rightarrow 7$, $2 \rightarrow 9$ and $3 \rightarrow 8$.
• $f_2$ maps $1 \rightarrow 8$, $2 \rightarrow 8$ and $3 \rightarrow 7$.
• $f_3$ maps $1 \rightarrow 8$, $2 \rightarrow 8$ and $3 \rightarrow 8$.

Notice that in $f_2$, no element of $A$ is mapped to $9$. That’s okay. The only requirement for being a function is that each element of $A$ must be mapped to exactly one element of $B$. Also, note that there are other functions from $A$ to $B$. These are just examples.

Let $f$ be a function from $A$ to $B$, and $x$ be an element of $A$. We usually write $f(x)$ to be the element to which $x$ is mapped to. In the above examples, $f_1(1) = 7$ and $f_2(1) = 8$.

The set $A$ is called the domain of $f$, and $B$ is called the codomain. However, not all elements of $B$ may have an element of $A$ mapped to it. (For example, $f_2$ above.) Thus, we may also want to refer to the set of elements of $B$ which have an element of $A$ mapped to it. This is called the image of $f$. In set notation, the image of $f$ is $\{f(x) : x \in A\}$, and it’s a subset of $B$.

A function where every element of $A$ is mapped to the same element of $B$ is called a constant function. For example, $f_3$ above is a constant function.

The Collatz Conjecture

Here’s an interesting function on positive integers: $$f(n) = \begin{cases} 3n+1 & \text{if n is odd} \\\ n/2 & \text{if n is even} \end{cases}$$

This is interesting because there is a nice problem associated with it called the Collatz problem (also called the 3n+1 problem):

First start with any positive integer. Then apply $f$ to it to produce a new number. Then apply $f$ to the new number to produce another number. And so on. For example, if we start with $13$, then we’ll generate the following sequence:

$$13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 2 \rightarrow 1 \ldots$$

Notice that, at the end, the sequence $1 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 2 \ldots$ just repeats. In fact, this seems to occur no matter which integer you start with. So the problem is: Starting from any positive integer, do you always arrive at $1$? This is a huge open problem in mathematics. No one has proved or disproved it yet. All starting numbers up to $2^{60} \approx 10^{18}$ have been checked already, and so far everything ended up at $1$ (but this doesn’t count as a proof because we need to check all starting points, and there are an infinite number of them).

Function on things other than numbers

Notice that when we defined a function, we didn’t put any restrictions on the sets $A$ or $B$, i.e. we didn’t require $A$ and $B$ to be numbers or something. (Certainly not real numbers.) This is the reason why functions are much more powerful than you probably think. And this is the reason why probably some of them can’t be plotted.

Since $A$ and $B$ aren’t restricted, we can potentially define lots of kinds of functions. For example, if $A$ is the set of all lowercase strings of characters, then we can define a function whose domain is $A$ and whose codomain is $\mathbb{Z}$, called $\operatorname{length}$, that maps each string to its length. For example, $\operatorname{length}(\text{"banana"}) = 6$. We can also define a function from $A$ to $A$ called $\operatorname{reverse}$ which maps each string to its reverse. For example, $\operatorname{reverse}(\text{"banana"}) = \text{"ananab"}$. I’m sure you can think of many other functions that involve other objects.

Multi-argument functions

We can extend the concept of functions so that it allows multiple inputs. For example, we can view subtraction as a function that maps two numbers to their difference. In function notation, we write this as $f(x,y)$. Functions with more than two arguments can also be defined similarly.

Examples of multi-argument functions are:

• The subtraction function on integers, which maps a pair of integers to another integer: their difference. For example, if we name the function $\operatorname{sub}$, then $\operatorname{sub}(3, 11) = -8$. (You’re probably more familiar with the infix notation though: $3 - 11 = -8$.)
• The function $\operatorname{concat}$, which maps a pair of strings to another string: their concatenation. For example, $\operatorname{concat}(\text{"stan"}, \text{"ley"}) = \text{"stanley"}$. We can also define a three-argument version: $\operatorname{concat}(\text{"life"}, \text{"is"}, \text{"strange"}) = \text{"lifeisstrange"}$. In fact, $\operatorname{concat}$ can be defined for any number of arguments.
• The function $\operatorname{get}$, which maps a pair of a string $s$ and an integer $i$ and returns a character: the $i$th character of $s$. For example, $\operatorname{get}(\text{"maxpayne"}, 3) = \text{'x'}$. This example shows that the inputs and output don’t have to be of the same type.

Problems

• Project Euler #14
• 10696 - f91
• 100 - The 3n + 1 problem
Note 1: Data and time limit for this problem are not too strict, so a naïve algorithm can pass.
Note 2: There are some subtle special cases (and an important lesson to be learned) in this problem. If you’re stuck, feel free to ask us.