MHB Expressing First 1000 Positive Integers as Floor Functions

[anemone]

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]

Spoiler

Brute force! :LOL: :p

# -*- 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.

 

[Opalg]

Spoiler

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]

Thanks Opalg for your great insight and excellent solution!

Spoiler: Solution of other

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.