APM_2F005 - Algorithms For Discrete Mathematics Bachelor 2
Lecturer: Lucas Gerin

Experimental Maths 2: Multiplicative persistence, Benford distribution, coin-changing problem, Kruskal-Katona decomposition, ...

Table of contents

Exercise 1. Playing with digits

Write a function ProductOfDigits(n) which returns the product of digits of $n$. For example, ProductOfDigits(2281)=32, since $2\times 2\times 8\times 1 =32$.
(Hint: Recall that in python 3 the euclidean division is obtained with //.)

For an integer $n$, we consider the following procedure. Multiply all the digits of $n$ by each other, repeating with the product until a single digit is obtained. Let us denote by $\mathrm{M}(n)$ the number of steps required to get one single digit number, starting from $n$. (If $n<10$ we set $\mathrm{M}(n)=0$.)

For example, for $n=2281$: $$ 2281 \stackrel{\text{1st step}}{\longrightarrow} 2\times 2\times 8\times 1= 32 \stackrel{\text{2d step}}{\longrightarrow} 3\times 2 =6. $$
Therefore $\mathrm{M}(2281)=2$.

Write a program which computes $\mathrm{M}(n)$.
Find the smallest integer $K$ such that $\mathrm{M}(K)\geq 7$.
  1. Let $\Pi(n)$ denote the product of digits of $n$. Prove that $\Pi(n) < n $ for every $n\geq 10$.
  2. Deduce that $\mathrm{M}(n)<+\infty$ for every $n$.
  3. (Bonus) Find a constant $c>0$ such that for every $n\geq 1$ one has $\mathrm{M}(n)\leq c\log(n)$.
  1. Let $n\geq 1$ be an integer with $c+1$ digits and denote by $a_c,a_{c-1},a_{c-2},\dots a_1,a_0$ its digits (in basis $10$). Then $$ n=a_c10^c +a_{c-1}10^{c-1}+\dots +a_1\times 10+a_0 \geq a_c 10^c. $$ Besides $$ \Pi(n)=a_c\times a_{c-1}\times \dots \times a_0 \leq a_c\times9 \times 9 \times \dots \times 9 \leq a_c 9^{c} $$ (since each digit is less than $9$). If we combine our two inequalities for $c\geq 1$ we obtain $$ \Pi(n) < n. $$
  2. This means that at each iteration of $\Pi$, the quantity is (strictly) decreasing. After at most $n-10$ steps, $n$ is mapped onto a integer $<10$.
  3. The idea is that
    • If $n$ is large then we prove that $\Pi(n)$ is way smaller than $n$
    • If $n$ is small we use python.
    Let us prove it rigously. Let $n\geq 1$. From above we have (with $c=\lfloor \log_{10}(n)\rfloor$): $$ \Pi(n)\leq a_c 9^{c} \leq \frac{n}{10^c}9^c = n(9/10)^{\lfloor \log_{10}(n)\rfloor} $$ i.e. $$ \frac{\Pi(n)}{n} \leq (9/10)^{\lfloor \log_{10}(n)\rfloor}. $$ Now, if $n>10^7$ (see script A below) then the right-hand side is $<0.5$ and therefore we have $\Pi(n) < n/2$. This means that:
    • As long as $ n > 10^7 $, $ \Pi(n) $ decreases at least by a factor $2$ at each iteration. So after $s$ steps we are below $n \times (1/2)^s$. This is less than $10^7$ if $s\geq \log_2(n)$.
      • If $n\leq 10^7$ then $\mathrm{Mp}(n)\leq 8$ (see script B below)
    Finally, it takes less than $\log_2(n)$ steps to reach $10^7$ and then at most $8$ steps to reach $0$. We have proved $$ \mathrm{Mp}(n)\leq \log_2(n)+8. $$

Exercise 2. $L$-decompositions (the coin-changing problem)

This problem is defined as follows. Let $L=[a_1,a_2,\dots,a_k]$ be a list of distinct positive integers.

For a fixed integer $n\geq 1$ we want to find the number of solutions $(x_1,\dots,x_k)$ to the equation

$$ a_1 x_1 +a_2 x_2 + \dots a_k x_k=n, \qquad\qquad (\star) $$
where $x_i$'s are non-negative integers. We denote by $H_n(L)$ be the number of such solutions. For example if $L=[1,2,5]$ then $H_6([1,2,5])=5$, since

\begin{align*} 6&=5+1 \\ &=2+2+2\\ &=2+ 2+1+1\\ &=2+1+1+1+1\\ &=1+1+1+1+1+1 \end{align*}

In other words, the solutions to $(\star)$ are: $$ (x_1,x_2,x_3)=(1,0,1),\quad (0,3,0),\quad (2,2,0),\quad (4,1,0),\quad (6,0,0) $$

The typical questions we will ask are:

Throughout the exercise we focus on the case $L=[1,2,5]$.

  1. Justify that for every $n\geq 3$:

    $$ H_n([1,2])=1+ H_{n-2}([1,2]). $$
  2. Prove a similar recurrence formula for $H_n([1,2,5])$: write $H_n([1,2,5])$ as a function of $H_1([1,2]),\dots,H_n([1,2])$ and $H_1([1,2,5]),\dots,H_{n-1}([1,2,5])$ (justify your formula).
  3. Deduce from these recurrence formulas:
    • A function `H_125(n)` which computes $H_n([1,2,5])$.(To check your result: $H_{30}([1,2,5])=58$.)
      • A plot of $n\mapsto H_n([1,2,5])$.
  4. Show a numerical experiment which shows that $H_n([1,2,5])\sim cn^2$ for some positive constant $c$ (and find an approximation of $c$).
  1. A solution in $H_n([1,2])$ ends either with a $1$ (in that case the solution is $1,1,\dots,1$) or a $2$. Hence: $$ H_n([1,2])=1+ H_{n-2}([1,2]). $$
  2. A solution in $H_n([1,2,5])$ ends either with a $1$ , a $2$ or a $5$. Hence: $$ H_n([1,2,5])=1+ H_{n-2}([1,2])+H_{n-5}([1,2,5]) $$

Exercise 3. First digit and powers of two

Write a function FirstDigit(n) which returns the leftmost digit of $n$:

FirstDigit(238)
2
Hint: Think recursive!

The Benford distribution is the probability distribution $(p_k)_{1\leq k\leq 9}$ on $\{1,2,\dots, 9\}$ defined by $$ p_k=\log_{10}(k+1)-\log_{10}(k), $$ where $\log_{10}$ stands for the logarithm in basis $10$. Benford's law of anomalous numbers states that for many data sets the leftmost digit is not uniformly distributed but follows rather the Benford distribution. We want to illustrate the fact that the data set $2,2^2,2^3,2^4,2^5,\dots,2^n$ satisfies Benford's law (when $n$ is large).

  1. (Theory) Justify briefly that $(p_k)_{1\leq k\leq 9}$ is indeed a probability distribution.
  2. Fix $n=1000$. Plot on the same figure:
    • The histogram of the frequencies of $\{1,2,\dots,9\}$ among the leftmost digit of $2,2^2,2^3,2^4,2^5,\dots,2^n$.
    • The distribution $k\mapsto (p_k)_{1\leq k\leq 9}$


To plot a normalized histogram of a list of data in $\{1,2,\dots,9\}$, use:
plt.hist(MyData, bins= [k+0.5 for k in range(10)], density=True, ec='k')
1. As $x\mapsto \log_{10}(x)$ is increasing the $p_k$'s are positive. Moreover \begin{align*} p_1+\dots +p_{9}&=\log_{10}(2)-\log_{10}(1)+\log_{10}(3)-\log_{10}(2)+\dots +\log_{10}(10)-\log_{10}(9)\\ &=\log_{10}(10)-\log_{10}(1)=1-0=1. \end{align*}

It can be proved with ergodic theory that the limiting frequencies (when $n\to +\infty$) are governed by the Benford distribution $B$: $$ \text{Frequency of }i \stackrel{n\to +\infty}{\to} B(i) :=\log_{10}((i+1)/i). $$ (See this link for a nice account on this problem.)

Exercise 4. Kruskal–Katona decomposition

The Kruskal–Katona decomposition states that for every integers $n,\ell\geq 1$ there exists an integer $t$ and $a_\ell>a_{\ell-1}>a_{\ell-2}>\dots >a_1$ with $$ n=\binom{a_\ell}{\ell} + \binom{a_{\ell-1}}{\ell-1} + \dots + \binom{a_t}{t}. $$ The decomposition is explicit and given by the following greedy recursive algorithm:

For example for $n=62$, $\ell=5$ one gets \begin{align*} 62&=\binom{8}{5}+\binom{5}{4}+\binom{3}{3}\\ &= 56+5+1 \end{align*}

1. Write a function `a_max(n,l)` which returns the largest integer such that $n\geq \binom{a_\ell}{\ell}$. You can use
import scipy.special
scipy.special.binom(n,l)
 2.Write a function Katona(n,l) which returns the Kruskal-Katona decomposition of the pair $(n,\ell)$. The output must be a list of list of sizes $2$: