# [SOLVED]Floor function

#### anemone

##### MHB POTW Director
Staff member
How many of the first 1000 positive integers can be expressed in the form $\lfloor 2x \rfloor+\lfloor 4x \rfloor+\lfloor 6x \rfloor+\lfloor 8x \rfloor$, where $x$ is a real number?

#### Theia

##### Well-known member
Brute force!

Python:
# -*- coding: utf-8 -*-

def f(x):
r = int(2*x)
r += int(4*x)
r += int(6*x)
r += int(8*x)
return r

def solve(n):
x0 = 0
f0 = -n
x1 = n
f1 = f(x1) - n
v = 0
while v < 201:
x = 0.5*(x0 + x1)
ff = f(x) - n
v += 1
if ff == 0:
return x
if ff < 0:
#root between x and x1
x0 = x
f0 = ff
if ff > 0:
#root between x0 and x
x1 = x
f1 = ff
return -1

sol = 0
nsol = 0
for i in range(1,1001):
t = solve(i)
if(t == -1):
nsol += 1
print(i, 'no solution')
else:
sol += 1
print(i, t)

print('')
print(sol, 'numbers possible')
print(nsol, 'numbers not possible')
Output as an attachment.

#### Attachments

• 16.9 KB Views: 4

#### Opalg

##### MHB Oldtimer
Staff member
Let $f(x) = \lfloor 2x \rfloor+\lfloor 4x \rfloor+\lfloor 6x \rfloor+\lfloor 8x \rfloor$. It is an increasing function, taking only integer values. It has jumps at some multiples of $\frac1{24}$ and is constant everywhere else.

In the interval $0<x\leqslant\frac12$, $f(x)$ takes the value $0$ for $0<x<\frac3{24} = \frac18$. It then jumps to $1$ when $x=\frac3{24}$ (because $\lfloor 8x \rfloor$ becomes $1$ at that point). After that, it jumps to $2$ when $x = \frac4{24} = \frac16$. The next jump occurs at $x=\frac6{24}=\frac14$, when both $\lfloor 4x \rfloor$ and $\lfloor 8x \rfloor$ increase by $1$. So at that point $f(x)$ skips the value $3$ and goes straight from $2$ to $4$. There are then further jumps of $1$ at $x = \frac8{24}$ and $\frac9{24}$. After that, the next jump is at $x = \frac{12}{24} = \frac12$, when all four terms in $f(x)$ increase by $1$, and $f(x)$ jumps from $6$ to $10$, skipping over the values $7$, $8$ and $9$.

So in that interval from $0$ to $\frac12$, $f(x)$ increases by $10$, taking six integer values and skipping the other four. The same pattern then repeats in every interval of length $\frac12$: $f(x)$ will increase by $10$, taking six integer values and skipping the other four. So in the interval from $0$ to $50$, $f(x)$ will go from $0$ to $1000$, taking $600$ values and skipping $400$.

#### anemone

##### MHB POTW Director
Staff member
Thanks Opalg for your great insight and excellent solution!

Let $f(x)=\lfloor 2x \rfloor+\lfloor 4x \rfloor+\lfloor 6x \rfloor+\lfloor 8x \rfloor$--(1).

Observe that if $n$ is a positive integer, then from (1),

$f(x+n)=f(x)+20n$--(2) follows.

In particular, this means that if an integer $k$ can be expressed in the form $f(x_0)$ for some real $x_0$, then for $n=1,\,2,\,3,\cdots$ one can express $k+20n$ similarly, i.e. $k+20n=f(x_0)+20n=f(x_0+n)$.

In view of this, one may restrict attention to determining which of the first 20 positive integers are generated by $f(x)$ as $x$ ranges through the half-open interval $(0,\,1]$.

Next, observe that as $x$ increases, the value of $f(x)$ changes only when either $2,\,4x,\,6x$ or $8x$ attains an integral value, and that the change in $f(x)$ is always to a new, higher value. In the interval $(0,\,1]$, such changes occur precisely when $x$ is of the form $\dfrac{m}{n}$, where $1\le m \le n$ and $n=2,\,4,\,6,\,8$. There are 12 such fractions, in increasing order they are:

$\dfrac{1}{8},\,\dfrac{1}{6},\,\dfrac{1}{4},\,\dfrac{1}{3},\,\dfrac{3}{8},\,\dfrac{1}{2},\,\dfrac{5}{8},\,\dfrac{2}{3},\,\dfrac{3}{4},\,\dfrac{5}{6},\,\dfrac{7}{8}$ and $1$.

Therefore, only 12 of the first 20 positive integers can be represented in the desired form. Since $1000=50(20)$, in view of (2), this implies that in each of the 50 sequences,

$1,\,2,\,3,\,\cdots,20;21,\,22,\,23,\cdots,40;\cdots ;981,\,982,\,983,\,\cdots, 1000$

of 20 consecutive integers only 12 can be so expressed, leading to a total of $50(12)$ or 600 positive integers of the desired form.