Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
share|improve this question
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. –  Yong Hao Ng Oct 31 '12 at 0:32
    
@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. –  Mat Oct 31 '12 at 1:34

1 Answer 1

up vote 3 down vote accepted

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 $<p$.

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;

share|improve this answer
    
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? –  Mat Oct 31 '12 at 2:52
    
I added the working to describe how one might work out the solution set given the equation. –  Yong Hao Ng Oct 31 '12 at 4:01
    
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. You may check here to see an example I did earlier. –  Yong Hao Ng Oct 31 '12 at 4:33
    
I'm not entirely sure how I would use a karnaugh map when f(x) can return 2 as well as 1 or 0. –  Mat Oct 31 '12 at 5:39
    
@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 is a guide if you want to try it yourself. :) –  Yong Hao Ng Oct 31 '12 at 10:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.