MHB Expressing First 1000 Positive Integers as Floor Functions

anemone
Gold Member
MHB
POTW Director
Messages
3,851
Reaction score
115
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?
 
Mathematics news on Phys.org
Brute force! :LOL: :p

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

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$.
 
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.
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Thread 'Imaginary Pythagoras'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
Back
Top