Artificial Intelligence Blog

In the previous 5 parts, I described several theorems which are useful for finding the maximum value of a function $f$ over integers.  In parts 1, 2, and 3, $f$ was concave.  In part 4, $f$ was continuous.  And in part 5, there were no restrictions on $f$.  In this post, the focus is on finding the maximum value of an investment game function over integers.

What is the maximum of $$f(x)=\exp(\alpha x) (T-x)$$ over all integers?  This function appears in several investment board games including Terraforming Mars, Master of Orion, and Roll for the Galaxy.

EXAMPLE $f(x)=\exp(\alpha x) (T-x)$

Let’s find the maximum of $f:\mathbb{R}\rightarrow\mathbb R$ where $$f(x)=\exp(\alpha x) (T-x),$$ $\alpha>0$, and $T>0$. The $\exp(\alpha x)$ is always postive, so $$f(x)>0\quad\mathrm{\ if\ and\ only\ if\ } x<T.$$

Let $g(x) = f(x+1) – f(x)$ as in “Maximizing a Function over Integers (Part 5)“. Let $\beta=\exp(\alpha)$. We can use some algebra to better understand the behavior of $g$.

$$\begin{aligned}g(x) &= f(x+1) – f(x)\\&= \exp(\alpha (x+1)) (T-(x+1)) – \exp(\alpha x) (T-x)\\&= \beta\beta^x (T-x -1) – \beta^x (T-x)\\&= \beta^x [ \beta(T-x -1) - T+x]\\&=\beta^x [ (1-\beta) x + (\beta-1) T -\beta]\\&=\beta^x [ (\beta-1)(T-x) -\beta].\end{aligned}
$$

So $g(x)>0$ if and only if

$$\begin{aligned}(\beta-1)(T-x) -\beta &>0\\(\beta-1)(T-x) &>\beta\\T-x &>\frac{\beta}{\beta-1} \\T- \frac{\beta}{\beta-1} &> x\\\gamma &> x\end{aligned}
$$
where $$\gamma=T- \frac{\beta}{\beta-1}.$$ Consequently,

$g(x)<0$ if and only if $\gamma < x$,

and by reversing the inequalities in the argument above,

$g(x)>0$ if and only if $\gamma > x$.

(This statement implies that if we restrict $f$ to integer inputs, then $f$ is increasing for inputs less than $\gamma-1$ and decreasing for inputs greater than $\gamma$.)

We can apply the lemmas from Part 5 to conclude that

– if $\gamma$ is an integer, then the maximum value of $f$ amoung all integers is $f(\gamma)$ which is also equal to $f(\gamma+1)$, and
– if $\gamma$ is not an integer, then the maximum value of $f$ amoung all integers is $f(\mathrm{ceil}(\gamma))$ and that maximum value is only attained by the input $\mathrm{ceil}(\gamma)$.

(Technical note: The lemmas in Part 5 can be applied with $b=T+1$ and and real number $a<\gamma-1$.)

$f(x) = 1.1^x (100-x)$

For example, if $$f(x) = 1.1^x (100-x)=\exp(\alpha x)(T-x)$$ with $\alpha=\log(1.1)$ and $T=100$, then

$$\begin{aligned}\beta=\exp(\alpha)&=\exp(\log(1.1)) = 1.1,\quad\mathrm{and}\\ \gamma= T- \frac{\beta}{\beta-1}&= 100- \frac{1.1}{1.1-1}= 100 -11 = 89.\end{aligned}$$

We conclude that the maximum value of $f$ over all integers is $$f(\gamma) =f(\gamma+1) = f(89)=f(90)\approx53130.2$$ Note that $f(88) \approx 52691.1$ and $f(91)\approx 52598.9$.

$f(x)=(1+1/k)^x(T-x).$ for any positive integer $k$

More generally, let $k$ be any positive integer and let $$f(x)=(1+1/k)^x(T-x).$$
Then $$f(x)=\exp(\alpha x)(T-x)$$ with $\alpha=\log(1+1/k),$

$$\begin{aligned}\beta=\exp(\alpha)&=\exp(\log(1+1/k)) =1+1/k,\quad\mathrm{and}\\\gamma= T- \frac{\beta}{\beta-1}&= T – \frac{1+1/k}{1+1/k-1}= T- (k+1) .\end{aligned}$$

We conclude that the maximum value of $f$ over all integers is $$f(\gamma) =f(\gamma+1) = f(T-k-1)=f(T-k).$$

AcknowledgmentS

Thanks to stackedit.io for helping me write the TeX.  GPT3 also recommended a change to one of the sentences in the introductory paragraph.

In parts 1,2, and 3, I described some theorems about finding the integer $i$ which maximizes $f(i)$, the value of a concave function $f:[a,b]\rightarrow \mathbb R$.  In part 4, I described a theorem for finding integers $i$ which maximize $f(i)$ where $f:[a,b]\rightarrow \mathbb R$ is a continuous function.  In part 5, I will describe some rather obvious, but useful facts and lemmas for finding integers $i$ which maximize $f(i)$ for any function $f:[a,b]\rightarrow \mathbb R$.

NOTATION

•  $[a,b]$ is the set of real numbers $x$ where $a\leq x \leq b$, and $a$ and $b$ are real numbers.
• $f:[a,b]\rightarrow \mathbb R$ means that the function $f$ takes as input real numbers from $[a,b]$ and gives as outputs real numbers.  More generally, the notation  $f:A\rightarrow B$ denotes a function $f$ where the input elements are from set $A$ and the outputs are in set $B$.  For example, we could define $f:[1, 10]\rightarrow \mathbb R$ by $f(x) =\log(x)$ for real numbers $x$ between 1 and 10 where the outputs are real numbers.
• We will use  floor$(x)$  to denote the largest integer less than or equal to $x$. You can think of floor($x$) as rounding $x$ down.
• We will use  ceil$(x)$  to denote the smallest integer greater than or equal to $x$.  You can think of ceil($x$) as rounding $x$ up.

MAIN ASSUMPTION

For the rest of this post assume that $a$ and $b$ are real numbers, $a+1\leq b$, and $f$ is a real valued function with domain [a,b].  $f:[a,b] \rightarrow\mathbb{R}$, .

DEFINITIONS

• We say that a function $f$ is increasing on the set of numbers $D$ if for all $x_1$ and $x_2$ in $D$ $$a\leq x_1 < x_2 \leq b\quad\mathrm{implies}\quad f(x_1) \leq f(x_2).$$ As the value of $x$ increases, the function increases.  If the function is differentiable, this is equivalent to the derivative being non-negative.
• We say that a function $f$ is strictly increasing on the set of numbers $D$ if for all $x_1$ and $x_2$ in $D$ $$a\leq x_1 < x_2 \leq b\quad\mathrm{implies}\quad f(x_1) <f(x_2).$$If the function is differentiable, this is almost the same as the derivative being positive.
• We say that a function $f$ is decreasing on the set of numbers $D$ if for all $x_1$ and $x_2$ in $D$ $$a\leq x_1 < x_2 \leq b\quad\mathrm{implies}\quad f(x_1) \geq f(x_2).$$ As the value of $x$ increases, the function decreases.  If the function is differentiable, this is equivalent to the derivative being non-positive.
• We say that a function $f$ is strictly decreasing on the set of numbers $D$ if for all $x_1$ and $x_2$ in $D$ $$a\leq x_1 < x_2 \leq b\quad\mathrm{implies}\quad f(x_1)>f(x_2).$$ If the function is differentiable, this is almost the same as the derivative being negative.

SOME OBVIOUS YET USEFUL FACTS

1. If $f$ is a strictly increasing function, then the integer $i$ that maximizes $f(i)$ is $\mathrm{floor}(b)$.
2. If $f$ is an increasing function, then the set of integers that maximize $f$ is non-empty and has the form $\{j,j+1, j+2, \ldots, \mathrm{floor}(b)\}$ where $j$ is an integer and $a\leq j\leq b$.
3. If $f$ is a strictly decreasing function, then the integer $i$ that maximizes $f(i)$ is $\mathrm{ceil}(a)$.
4. If $f$ is a decreasing function, then the set of integers that maximize $f$ is non-empty and has the form $\{\mathrm{ceil}(a),\mathrm{ceil}(a)+1,\ldots, j\}$ where $j$ is an integer and $a\leq j\leq b$.
5. Suppose that the integer $i$ maximizes $f(i)$. Then either

5a) $i=\mathrm{ceil}(a)$ or $i=\mathrm{floor}(b)$ (i.e. $i$ is on the “border” of $[a,b]$), or

5b) $a+1\leq i \leq b-1$, $g(i-1) \geq 0$, and $g(i)\leq 0$ where $$g:[a, b-1]\rightarrow\mathbb R \quad\mathrm{and}\quad g(x) = f(x+1) – f(x).$$ This is equivalent to $f(i-1) \leq f(i)$ and $f(i) \geq f(i+1)$.

 TWO LEMMAS

Fact 5 is related to the following two lemmas. Assume that

• the function $g:[a, b-1]\rightarrow\mathbb{R}$ is defined by $g(x) = f(x+1) – f(x)$,
• $\gamma$ is a real number where $a+1\leq \gamma \leq b-1$,
• $g(x)>0$ if and only if $\gamma > x$, and
• $g(x)<0$ if and only if $x>\gamma$.

Lemma 1: If $\gamma$ is an integer, then the set of integers that maximize $f$ is $\{\gamma, \gamma+1\}$.
Lemma 2: If $\gamma$ is not an integer, then the unique integer that maximizes $f$ is $\mathrm{ceil}(\gamma).$

Proof: Let $i$ be an integer in $[a,b]$ that maximizes $f(i)$. (i.e. $f(i)\geq f(j)$ for all integers $j$ in $[a,b]$.)

If $\gamma > i$ then $g(i)>0$ which implies that $f(i+1)> f(i)$ in which case $f(i)$ is not the maximum of $f$ over all integers in $[a,b]$ contradicting the definition of $i$. Hence $\gamma\leq i$.

If $i-1>\gamma$ then $g(i-1)<0$ which implies that $f(i)< f(i-1)$ and again $f(i)$ is not the maximum of $f$ over all integers in $[a,b]$ contradicting the definition of $i$. Hence $i \leq \gamma+1$.

We conclude that $\gamma\leq i \leq \gamma +1$.

If $\gamma$ is not an integer, then $i=\mathrm{ceil}(\gamma)$ proving Lemma 2.

Notice that $g(\gamma)=0$, so $f(\gamma) = f(\gamma+1)$.  If $\gamma$ is an integer, then $i$ can be either $\gamma$ or $\gamma+1$ proving Lemma 1.

About two years ago, I wrote 3 posts about finding the maximum of a real valued concave functions over a set of consecutive integers.

http://artent.net/2020/12/25/maximizing-a-function-over-integers-part-1/

There is a related theorem for continuous functions.

Theorem:  Suppose that $f:[a,b] \rightarrow\mathbb R$ is continuous with $a+1\leq b$. Let
$$m=\max_{i\in \mathbb Z\cap[a,b]} f(i)\quad\mathrm{and}\quad S=\{ i\in \mathbb Z\cap[a,b]\, | f(i)= m\}.$$
Then $S$ is non-empty, and for all $i\in S\cap[a+1, b-1]$, there exists an $x(i)$ such that $$f(x(i)) = f(x(i)+1)$$ and $x(i)\leq i \leq x(i)+1.$

This is very nice if it is easy to find all the solutions to $f(x) = f(x+1)$ where $a\leq x \leq b$.  If you find those solutions, then the maximizer of $f$ over the set of integers in $[a,b]$ is either the smallest integer in $[a, b]$, the largest integer in $[a, b]$, or it is in the set $[x,x+1]$ where $x$ is one of the solutions to $f(x)=f(x+1)$.

More formally, if $i$ is an integer in $[a,b]$ and $f(i)\geq f(j)$ for all integers $j\in[a,b]$, then either

1. $i$ is on the “border” of $[a, b]$, i.e. $i\in [a, a+1)\cup (b-1, b]$, or
2. there exists a real number $x\in[a, b-1]$ such that $x\leq i \leq x+1$ and $f(x) = f(x+1).$

Proof of the Theorem:

$S$ is non-empty because $[a,b]\cap\mathbb Z$ is compact. Now for any $i\in S\cap[a+1, b-1]$, one of the three following cases must hold,

Case 1: $f(i-1) = f(i)$. In this case, let $x(i) = i-1$ and the theorem holds.

Case 2: $f(i) = f(i+1)$ In this case, let $x(i) = i$ and the theorem holds.

Case 3: $f(i-1) < f(i)$ and $f(i+1) < f(i)$. For this case, define $g:[a, b-1]\rightarrow \mathbb R$ by $$g(x) = f(x+1) – f(x).$$ The continuity of $f$ implies that $g$ is continuous. Also, $g(i-1) >0$, and $g(i)<0$, so by the intermediate value theorem, there exists an $x^*\in(i-1, i)$ such that
$$\begin{aligned}
g(x^*) &=0\quad\mathrm{thus}\\
f(x^* +1) – f(x^*) &=0.
\end{aligned}$$
Setting $x(i)=x^*$ satisfies the theorem for case 3.

We have shown that in all three cases, there exists an $x(i)$ such that $x(i)\leq i \leq x(i)+1$ and $f(x(i)) = f(x(i)+1)$ proving the theorem.

Yesterday, I wrote about how the fractions

$$\begin{aligned}
\frac{1000}{998999} &= 0.00100100200300500801302103405509… \\
\frac{10000}{99989999} &= 0.000100010002000300050008001300210… \\
\frac{100000}{9999899999} &= 0.0000100001000020000300005000080001… \\
\frac{1000000}{999998999999} &= 1.000001000002000003000005000008000013…\cdot 10^{-6} \\
\frac{10000000}{99999989999999} &= 1.000000100000020000003000000500000080000013\cdot 10^{-7} \\
\end{aligned}$$

display the first several values of the Fibonacci sequence.  The general formula for these fractions is $$f_k = \frac{10^k}{10^{2 k} – 10^k – 1}.$$

Today, I will provide a fairly simple derivation for this formula without summing an infinite series.

Let $a_1=1, a_2=1, a_3=2, a_4=3, a_5=5, a_6=8,\ldots$ be the Fibonacci sequence.  Let $a_i=0$ when $i\leq 0$.  Now, we know that by definition

$$a_n = a_{n-1} + a_{n-2}$$

for all $n>1$.  The formula above also holds for $n<1$, but fails for $n=1$.  We can fix that by adding in the Kronecker delta function $\delta_{i,j}$ which is 0 if $i\neq j$ and 1 when $i=j$.  The amended formula valid for all $n$ is

$$a_n = a_{n-1} + a_{n-2} +\delta_{n,1}.$$

In the prior article, we defined the Fibonacci fractions to be

$$f_k = \sum_{i=1}^\infty \frac{a_i}{10^{\ ki}}.$$

So,

$$\begin{aligned} f_k &= \sum_{i=1}^\infty \frac{a_i}{10^{\ ki}}  \\ &= \sum_{i=1}^\infty \frac{a_{i-1} + a_{i-2} + \delta_{i,1}}{10^{\ ki}}\\&= \sum_{i=1}^\infty \frac{a_{i-1}}{10^{\ ki}}  +\frac{a_{i-2}}{10^{\ ki}} + \frac{\delta_{i,1}}{10^{\ ki}}\\&= \frac{1}{10^{\ k}}  + \sum_{i=1}^\infty \frac{a_{i-1}}{10^k10^{\ k(i-1)}}  +\frac{a_{i-2}}{10^{2k}10^{\ k(i-2)}} \\&= \frac{1}{10^{\ k}}  + \frac{f_k}{10^k}  +\frac{f_k}{10^{2k}}. \end{aligned}$$

Thus,

$$f_k= \frac{1}{10^{\ k}}  + \frac{f_k}{10^k}  +\frac{f_k}{10^{2k}}$$

$$f_k   – \frac{f_k}{10^k}  -\frac{f_k}{10^{2k}} =  \frac{1}{10^{\ k}}$$

$$f_k  \left(1 – \frac{1}{10^k}  -\frac{1}{10^{2k}}\right) =  \frac{1}{10^{\ k}}$$

$$f_k  = \frac{\frac{1}{10^{\ k}}}{ 1 – \frac{1}{10^k}  -\frac{1}{10^{2k}} }$$

$$f_k  = \frac{10^{\ k}}{ 10^{2k} – 10^k  -1 }$$

which completes the derivation.

This technique is often used for Z-transforms and generating functions.

I think that it is really cool that some fractions have interesting patterns in their decimal expansion.  For example,

$$1/499 = 0.0020040080160320641282565130260….$$

You can see the first 8 values of the doubling sequence (a.k.a the powers of 2)  2, 4, 8, 16, 32, 64, 128, and 256 in the decimal expansion.  If you want more values, you can just add more 9’s to the denominator.

$$\begin{aligned} 1/49999 = &0.0000200004000080001600032000640012800256005120\\&1024020480409608192163\
8432768655373107462….\end{aligned}$$

Other fractions can encode other sequences.  The first several square numbers 1, 4, 9, 16, … are encoded by the fractions

$$\small\frac{10100}{970299},\frac{1001000}{997002999},\frac{100010000}{999700029999},\frac{10000100000}{999970000299999},\frac{1000001000000}{999997000002999999},….$$

For example,

$$\frac{1001000}{997002999} = 0.001004009016025036049064081100121144169196225….$$

It turns out that it is not too hard to find sequences of fractions which encode any sequence of positive integers that is a sum of

• polynomials  (e.g.  cubes         1, 8, 27, 64, 125, …),
• exponentials (e.g. powers of 3  1, 3, 9, 27, 81, 243, …), or
• products of polynomials and exponentials.  (e.g.  cubes times power of 3     1, 24, 243, 1728, 10125, 52488, 250047,…).

The Fibonacci sequence

The Fibonacci sequence is

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, ….

Each value after the initial ones is the sum of the previous two values (e.g. 2 +3 =5, 3+5 =8, …).  It turns out that the Fibonacci sequence is the sum of exponentials, so it also can be encoded in a sequence of fractions.

$$\begin{aligned}
\frac{1000}{998999} &= 0.00100100200300500801302103405509… \\
\frac{10000}{99989999} &= 0.000100010002000300050008001300210… \\
\frac{100000}{9999899999} &= 0.0000100001000020000300005000080001… \\
\frac{1000000}{999998999999} &= 1.000001000002000003000005000008000013…\cdot 10^{-6} \\
\frac{10000000}{99999989999999} &= 1.000000100000020000003000000500000080000013\cdot 10^{-7} \\
\end{aligned}$$.

All of these fractions $f_k$ can be computed with the formula

$$f_k=\sum_{i=1}^\infty \frac{a_i}{10^{\ k i}}$$

where the $a_i$ are the values of the sequence and $k$ is a positive integer specifying the spacing between the values of $a$ in the decimal expansion.   This sum is fairly easy to compute when $a$ is a polynomial, an exponential, or a combination of polynomials and exponentials.

For example, to get the doubling numbers $a_i = 2^i$, the fractions would be

$$\begin{aligned}\sum_{i=1}^\infty \frac{a_i}{10^{\ k i}}&= \sum_{i=1}^\infty \frac{2^i}{10^{\ k i}}\\&= \sum_{i=1}^\infty \left(\frac{2}{10^k}\right)^i\\&=\frac{\frac{2}{10^k}}{1-\frac{2}{10^k}}\quad{\text{using} \sum_{i=1}^\infty x^i= \frac{x}{1-x}}\\&= \frac{2}{10^k – 2}.\end{aligned}$$

For the Fibonacci sequence $$a_i = \frac{\varphi^i-\psi^i}{\varphi-\psi}= \frac{\varphi^n-\psi^n}{\sqrt 5}$$ where $$\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803$$ and $$\psi = \frac{1 – \sqrt{5}}{2} = 1 – \varphi = – {1 \over \varphi} \approx -0.61803.$$ (Copied verbatim with glee from the Wikipedia).

The math required to compute the Fibonacci fractions is almost the same as the powers of two math using the same $$\sum_{i=1}^\infty x^i= \frac{x}{1-x}$$ trick.  

After you go through the computations, the Fibonacci fractions can be found with the formula

$$f_k = \frac{10^k}{10^{2 k} – 10^k – 1}.$$

Most people look at the first four digits of 1/7 ~= .1428 and think that the fact that 7*2=14 and 7*4=28 is a mere coincidence. It’s not. Let’s compute the decimal expansion of 1/7 without doing long division, but using instead $$x/(1-x) = x + x^2 + x^3 + \ldots.$$
1/7
= 7/49
= 7*1/(50-1)
= 7*1/50/(1-1/50)
= 7*.02/(1-.02)
= 7*(.02 + .02^2 + .02^3 + …)
= 7*(.02 + .0004 + .000008 + .00000016 + .0000000032 + …)
= 7*(.020408163264…)
= 7*(.020408) + 7*(..000000163264)
= .142856 + 7*(.00000016) + 7*(.00000000326…)
= .142856 + .00000112 + 7*(.00000000326…)
Notice that the first n digits must be .142857. The decimal expansion of 1/j either terminates or repeats with at most (j-1) repeating digits and we have 6 digits, so those six digits must repeat, thus
1/7 = .142857142857142857142857142857142857….