1
$\begingroup$

Given that $x$ is an integer in the interval $[0,8]$ and $f(x)$ is also an integer in the interval $[0,2]$, I have the following equality:

$$4\lfloor\frac{x}{3}\rfloor - f(x) - 3\lfloor\frac{x-3f(x)}{9}\rfloor=x$$

Is it possible to solve for $f(x)$ in this case?

Given the intervals of $x$ and $f(x)$, $\frac{x-3f(x)}{9}$ must be in the interval $[-1,1)$, so its floor must be either -1 or 0. I would write it as this:

$$4\lfloor\frac{x}{3}\rfloor-f(x)+3\big(x<3f(x)\big)=x$$

But I suspect that makes simplifying further impossible. (should probably mention I come from a programming background, the above is probably wrong mathematically)

Edit: The formula is from the following table:

x    f(x) 0     0 1     2 2     1 3     1 4     0 5     2 6     2 7     1 8     0 
  • 1
    I suppose $[0-2]$ is intended to be $[0,2]$ (Looks like it might be $[0,-2]$)? If so, I suspect it may be easier to just bruteforce all the possible combinations $f(x)\rightarrow x$, which requires evaluation of $9^3$ cases. But perhaps you are looking for a way to do it Mathematically.2012-10-31
  • 0
    @YongHaoNg, you are correct, it was meant to be $[0,2]$. I have a table of results from which I derived the above formula. I'll post it above.2012-10-31

1 Answers 1

3

Solution 1: Lagrange Interpolation:

Given any $n$ data set, there exists a polynomial of degree $n-1$ that fits them.
I did this on Mathematica:
Expand[InterpolatingPolynomial[{{0,0},{1,2},{2,1},{3,1},{4,0},{5,2},{6,2},{7,1},{8,0}},$x$]]

Where the braces represent $(x,f(x))$ values. Or you may think of them as $(x,y)$ coordinates.
This gives me the following function:

$f(x)=\dfrac{3662 x}{105}-\dfrac{10707 x^2}{140}+\dfrac{3247 x^3}{48}-\dfrac{4941 x^4}{160}+\dfrac{947 x^5}{120}-\dfrac{91 x^6}{80}+\dfrac{29 x^7}{336}-\dfrac{3 x^8}{1120}$ $=\dfrac{-x (-117184+256968 x-227290 x^2+103761 x^3-26516 x^4+3822 x^5-290 x^6+9 x^7)}{3360}$

The problem with this is clearly the fact that the starting polynomial is ugly.
We can make this simpler given your range though.

Find out what is the factorization of the denominator: $3360=2^5\cdot 3\cdot 5\cdot 7$.
Choose the smallest prime not in this factorization and bigger than the max $f(x)$. i.e. $p=11$.
We can form a new polynomial under modulo $p$:
$f(x)=9 x+5 x^2+6 x^3+7 x^4+10 x^5+10 x^6+3 x^7+7 x^8$ where each coefficient is $.

The draw back is you need to do a mod $p$ after computing $f(x)$.
The conversion is simple, just perform modulo $p$ on all coefficients (division is modulo inverse).
$p$ is chosen to not divide denominator so that inverse exists.

Solution 2: Solving equation by cases:

Since the greatest denominator in the floor function is 9, it can be solved in 9 cases.
We start by considering $x=9m,9m+1,\dots,9m+8$.
This works because it allows you to remove the floor function.

First, a property of the floor function: $\lfloor x+n\rfloor = \lfloor x\rfloor + n$, where $x$ is real and $n$ an integer.
This means that whenever we have an integer within the floor function, we may take it out.

Let $x=9m+a$, where $0\leq a<9$.
$4\lfloor \frac{9m+a}{3}\rfloor-f(x)-3\lfloor \frac{9m+a-3f(x)}{9}\rfloor=9m+a$
$4\lfloor 3m+\frac{a}{3}\rfloor-f(x)-3\lfloor m+\frac{a}{9}-\frac{f(x)}{3}\rfloor=9m+a$
$12m+4\lfloor\frac{a}{3}\rfloor-f(x)-3m-3\lfloor \frac{a}{9}-\frac{f(x)}{3}\rfloor=9m+a$
$4\lfloor\frac{a}{3}\rfloor-f(x)-3\lfloor \frac{a}{9}-\frac{f(x)}{3}\rfloor=a$

There are 2 approaches here, by restricting $a$ or $f(x)$.
It is faster to consider $f(x)=3n+b$, where $0\leq b<3$.

$4\lfloor\frac{a}{3}\rfloor-(3n+b)-3\lfloor \frac{a}{9}-\frac{3n+b}{3}\rfloor=a$
$4\lfloor\frac{a}{3}\rfloor-3n-b-3\lfloor \frac{a}{9}-n-\frac{b}{3}\rfloor=a$
$4\lfloor\frac{a}{3}\rfloor-3n-b+3n-3\lfloor \frac{a}{9}-\frac{b}{3}\rfloor=a$
$4\lfloor\frac{a}{3}\rfloor-b-3\lfloor \frac{a-3b}{9}\rfloor=a$

Up till this point, this shows that indeed we only need to consider $x\in [0,8]$ and $f(x)\in [0,2]$.
For any solution set $(x,f(x))$, we may add $9m$ to $x$ and $3n$ to $f(x)$.

$\underline{\text{Case } b=0}$:
$4\lfloor\frac{a}{3}\rfloor-3\lfloor \frac{a}{9}\rfloor=a$
$4\lfloor\frac{a}{3}\rfloor=a$
$a=\lbrace 0,4,8\rbrace$
Hence we have $(9m+0,3n+0),(9m+4,3n+0),(9m+8,3n+0)$

$\underline{\text{Case } b=1}$:
$4\lfloor\frac{a}{3}\rfloor-1-3\lfloor \frac{a-3}{9}\rfloor=a$
If $0\leq a<3$:
$4\lfloor\frac{a}{3}\rfloor-1-3(-1)=a$
$4\lfloor\frac{a}{3}\rfloor+2=a$
$a=2\implies$ solution $(9m+2,3n+1)$
If $(3\leq a<9)$:
$4\lfloor\frac{a}{3}\rfloor-1=a$
$a=\lbrace 3,7\rbrace$
Solution: $(9m+3,3n+1),(9m+7,3n+1)$

$\underline{\text{Case } b=2}$:
$4\lfloor\frac{a}{3}\rfloor-2-3\lfloor \frac{a-6}{9}\rfloor=a$
If $0\leq a<6$:
$4\lfloor\frac{a}{3}\rfloor-2-3(-1)=a$
$4\lfloor\frac{a}{3}\rfloor+1=a$
$a=\lbrace 1,5\rbrace$
Solution: $(9m+1,3n+2),(9m+5,3n+2)$
If $6\leq a<9$:
$4\lfloor\frac{a}{3}\rfloor-2=a\implies a=6$
Solution: $(9m+6,3n+2)$

This describes the solution set of the equation entirely.

Solution 3: Karnaugh Map:
We view the input $x$ as $x_3x_2x_1x_0$, where $x_3$ is the most significant bit.
We view the output $f(x)$ as $f(x)_1f(x)_0$, where $f(x)_1$ is the most significant bit.
$$\begin{array}{|c|c|c|c|c|c|}\hline & & x_1x_0 & x_1x_0 & x_1x_0 & x_1x_0 \\\hline & f(x)_0 & 00 & 01 & 11 & 10 \\\hline x_3x_2 & 00 & 0 & 0 & 1 & 1 \\\hline x_3x_2 & 01 & 0 & 0 & 1 & 0 \\\hline x_3x_2 & 11 & X & X & X & X \\\hline x_3x_2 & 10 & 0 & X & X & X \\\hline \end{array} $$

$f(x)_0 = \bar{x_3}x_2x_1x_0+\bar{x_3}\bar{x_2}x_1=\bar{x_3}x_1(x_2x_0+\bar{x_2})$
C code: y0 = (~x3) & x1 & ((x2 & x0) | (~x2));

$$\begin{array}{|c|c|c|c|c|c|}\hline & & x_1x_0 & x_1x_0 & x_1x_0 & x_1x_0 \\\hline & f(x)_1 & 00 & 01 & 11 & 10 \\\hline x_3x_2 & 00 & 0 & 1 & 0 & 0 \\\hline x_3x_2 & 01 & 0 & 1 & 0 & 1 \\\hline x_3x_2 & 11 & X & X & X & X \\\hline x_3x_2 & 10 & 0 & X & X & X \\\hline \end{array} $$

$f(x)_1=\bar{x_3}x_2x_1\bar{x_0}+\bar{x_3}\bar{x_1}x_0=\bar{x_3}(x_2x_1\bar{x_0}+\bar{x_1}x_0)$
C code: y1 = (~x3) & ((x2 & x1 & (~x0)) | ((~x1) & x0));
y = (y1<<1) | y0;

  • 0
    I had looked at interpolation, could you please expand on how it can be simplified using my intervals? Could you also explain how working out the individual cases for m and n could lead to the general function?2012-10-31
  • 0
    I added the working to describe how one might work out the solution set given the equation.2012-10-31
  • 0
    I have also added a description on how to create polynomial with smaller coefficients. The draw back is you need to perform an additional mod $p$ at the end. I think there are no easy ways to find better polynomials (less degree). If you are aiming for the shortest code, the solution is usually always found via [karnaugh map](http://http://en.wikipedia.org/wiki/Karnaugh_map). You may check [here](http://math.stackexchange.com/questions/215487/what-function-f-1-2-3-4-rightarrow-0-1-1-0/217821#217821) to see an example I did earlier.2012-10-31
  • 0
    I'm not entirely sure how I would use a karnaugh map when f(x) can return 2 as well as 1 or 0.2012-10-31
  • 0
    @Mat Sorry I was sleeping. You are right, I totally forgot about that. The solution for this is to view the output as a 3 bit variable $y_0y_1y_2$ and create 3 Karnaugh Maps to get each $y_i$. Leave me a comment if you need a demonstration. [Here](http://www.electronicdesignworks.com/digital_electronics/karnaugh_map/karnaugh_map.htm) is a guide if you want to try it yourself. :)2012-10-31
  • 0
    Actually only need two, but good thinking! If you add an answer that says karnaugh maps then I'll mark it as correct, as the following works: `(!C && D || B && C && !D) << 1 | (C && D || !B && C)`2012-11-01
  • 0
    Demo of karnaugh map output: http://ideone.com/H5Brg92012-11-01
  • 0
    @Mat Added the Karnaugh Map solution! [ideone code here](http://ideone.com/djTCbr). I shall not try to minimize the boolean operations though, since that would be a little off the original topic. =)2012-11-01
  • 0
    Thanks for all your help. If I could give you 3 up votes I probably would.2012-11-01
  • 0
    You're welcome. You accepted the answer when it helped you and that is good enough for me. Also, good job working out the solution yourself! =)2012-11-01