- Thread starter
- #1

- Jan 26, 2012

- 644

For those of you more into logical thinking, here are a few related problems I made up. They are not difficult by any means and are mostly meant to improve deductive skills, logic and proofwriting. Please be comfortable with the basic properties of the totient function as we'll use it as a framework for this problem set.

Are you sure? You can't forget hints.

Problems, in rough order of difficulty - solutions will be posted on Tuesday 2PM UTC+12 (NZST):Consider the mapping $\mathbb{F}_n : \mathbb{N} \to 2^\mathbb{N}$ defined as:

$$a \in \mathbb{F}_n ~ \Leftrightarrow ~ \varphi{(a)} = n ~ ~ ~ ~ \left ( \text{for all} ~ a > 1 \right )$$

Where $\varphi(a)$ is the Euler totient of $a$, and $n \in \mathbb{N}$. In other words, $\mathbb{F}_n$ is the "inverse totient" of $n$. As an example:

$$\mathbb{F}_{10} = \{ 11, 22 \} ~ ~ \text{and} ~ ~ \mathbb{F}_{32} = \{ 51, 64, 68, 80, 96, 102, 120 \}$$

Consider the tree graph produced by iterating this mapping on its outputs recursively, starting at $n = 1$. See here (limited to 50, green squares are odd primes, yellow squares may or may not have children on the full tree).

Hints (click to show if you are out of ideas):1. Show that $\mathbb{F}_n$ is empty when $n > 1$ is an odd integer. Show that the converse is true.

2. Prove that $\mathbb{F}_n$ always has an even number of elements when $n + 1$ is prime.

3. Show that $a \in \mathbb{F}_{n_1}$ and $a \in \mathbb{F}_{n_2}$ implies $n_1 = n_2$ (the converse is trivially true).

4. Prove that if $n = 2^m$, then $\mathbb{F}_n = m + 2$, with the exception of $m = 0$ where $\mathbb{F}_n = 1$.

5. Show that the tree has the heap property (i.e integers always get larger as you go down the tree).

6. Prove that any integer in the tree appears only once.

7. Show that this tree is infinite, that is, it has infinitely many elements.

8. Decide whether or not this tree contains all positive integers, and prove so.

9. We place an upper bound $m$ on elements of $\mathbb{F}_n$ (like the example tree did with $m = 50$). Give the tightest bound you can obtain for the maximum number of levels the resulting tree will have.

10. On what level of the tree is the integer $a$, on average? The root is at level zero.

11. How many elements will the tree have at level $l$, on average?

* For the three last problems, make reasonable assumptions on the distribution of elements in the tree.

2. Try and divide $\mathbb{F}_{37 - 1}$ into pairs, and find a pattern.

3. Remember $\mathbb{F}_n$ is not a function, but $\varphi$ is. What does this entail?

4. If $\varphi{(a)} = 2^m$, what form can $a$ possibly have? Check $a = 2^r (2^p + 1)$ with $2^p + 1$ prime.

5. Go back to the definition of $\varphi$.

6. What do (3) and (5) tell you?

7. Traverse the tree backwards by iterating $\varphi$ instead.

8. Using the same iteration approach as in (7), show the sequence will converge to 1 for any integer.

9. Use the method hinted at for (7). Study the rate at which the iterated value decreases.

10. Use your results for (9) to consider the average case.

11. This is a trick question, you can't just assume the tree is finite. First, apply the same reasoning as in (9) by rigorously bounding the size of the tree, then take the limit at infinity.

Last edited: