What is the maximum difference between these two functions?

1k Views Asked by At

Supposed the function $f(n)$ is defined as follows:

For values of $n$ less than or equal to $121$

$$f(n)= \begin{cases} 0 ,& \text{if } n < 121\\ 1 ,& \text{if } n = 121\\ \end{cases}$$

For values of $n$ greater than $121$

$$f(n+1)= \begin{cases} f(n) ,& \text{if $n+1$ is not evenly divisible by 11}\\ f(n) ,& \text{if $n+1$ is evenly divisible by 2,3,5,7}\\ f(n)+ 1 ,& \text{if $n+1$ is evenly divisible by 11 but not 2,3,5 or 7}\\ \end{cases}$$ Basically, $f(n)$ increments when a value of $n$ is encountered that is evenly divsible by 11 and no lower prime number.

Also, let's suppose the function $g(n)$ is defined as follows:

$$g(n) = (n/2)(2/3)(4/5)(6/7)(1/11)$$

What is the maximum difference between $f(n)$ and $g(n)$ for any natural number $n$?

How do you calculate this difference?

1

There are 1 best solutions below

3
On

First note that for $n<11$ the maximum difference between $f(n)$ and $g(n)$ is at $n=10$, where $$|f(10)-g(10)|=\frac{16}{77}.$$ For $n\geq11$ the function $f$ satisfies $$f(n+1)=\begin{cases} f(n)+1 & \text{ if }\gcd(2310,n+1)=11\\ f(n) & \text{ otherwise} \end{cases}.$$ For every $n\in\Bbb{N}$ the number of integers $m$ with $n\leq m<n+2310$ and $\gcd(2310,m)=11$ is precisely $$\varphi(\tfrac{2310}{11})=\varphi(2\cdot3\cdot5\cdot7)=\varphi(2)\varphi(3)\varphi(5)\varphi(7)=1\cdot2\cdot4\cdot6=48,$$ which shows that $f(n+2310)=f(n)+48$ for all $n\geq11$. On the other hand $$g(n)=\frac n2\frac23\frac45\frac67\frac{1}{11}=\frac{48}{2310}n,$$ which shows that also $g(n+2310)=g(n)+48$ for all $n\geq11$. This shows that the maximum difference between $f(n)$ and $g(n)$ is achieved with $11\leq n<2321$.

So to find the maximum difference between $f(n)$ and $g(n)$ for $n\in\Bbb{N}$, it suffices to find the maximum difference between $f(n)$ and $g(n)$ for $11\leq n<2321$, and to check that this does not exceed the maximum difference between $f(n)$ and $g(n)$ for $n<11$. A quick check shows that the maximum is $$\frac{828}{385}=g(1066)-f(1066).$$ Edit: As noted in the comments, this is not the maximum. A second check, this time with a computer, shows that the maximum is at $n=120$, where $$|f(120)-g(120)|=|0-120\cdot\tfrac{48}{2310}|=\frac{192}{77}\approx2.4935.$$