1

Not sure what to make the title. Let $f(x)$ represent the function that takes a hexadecimal number and returns its value in base 10. Let $x$ be a number in base 10. Can we solve $f(x) - x = y$?

For example, choose $y$ to be, say, 400,000. Then can we determine $x$? Here is what I came up with:

Express $x:= \sum_{0}^{n} a_i \cdot (10)^i$ where $a_i \in \{0, \dots, 9\}$

Then $f(x) := \sum_{0}^{n} a_i \cdot (16)^i$

Then $f(x) - x = \sum_{i=1}^n a_i \cdot ({16}^i - {10}^i)$.

At this point I think it must be brute forced? But there should always exist a unique solution, so we know if we start brute forcing, we should find an answer in finite time?

No clue what to tag or title this.

Prince M
  • 3,893
  • Numbers are numbers regardless of base. If $x$ is a number then $x = x $whether written in base 10 or 16 so $ f(x) -x = 0$. ALways. If you mean the symbols that we write on paper so that $f("2a") = 2*16+10 = "42"$. That's okay but the $f(x) - x$ doesn't make sense. $f(x) = "42"$ and $x = "2a"$ so what is $"42"-"2a"$? It is not at all clear what you mean. "$2a_{16}$" and "$42_{10}$" are both the same thing so $f(x)-x =42_{10} - 2a_{16} = 0$ is the only way I see to interpret this. – fleablood Mar 30 '19 at 03:48
  • For the record, $f(x)-x=2$ has no solutions, so it is unclear to me on what basis you expect $f(x)-x=400000$ to have exactly one. –  Mar 30 '19 at 03:49
  • 1
    You say $f(x)$ takes a hesidecimal number and returns it in base 10. when you say $x = \sum a_i 10^i$ and $f(x) = \sum a_i 16^i$ that is taking a *base 10$ number and returning the number that would be expressed if it were intepreted as hexidecimal instead. The exact opposite. – fleablood Mar 30 '19 at 03:58
  • @fleablood no, I am simply starting with a number in base 10, but then choosing to interpret it in hexadecimal. Then I’m converting it back to decimal – Prince M Mar 30 '19 at 04:06
  • @SaucyO'Path you’re right, I forgot to mention In the post that I was choosing numbers for $y$ that we’re already known to be solutions to equations of this form. – Prince M Mar 30 '19 at 04:08
  • @PrinceM For instance, the $f(x)-x$ you indicated is always a multiple of $6$, since $x^n-y^n=(x-y)\sum\limits_{j=0}^{n-1} x^jy^{n-1-j}$ for all $n\in\Bbb N$. –  Mar 30 '19 at 04:12

1 Answers1

2

$16^0 - 10^0 =1-1 = 0$

$16-10 = 6$

And $16^2 - 10^2 = 156$

And $16^3 - 10^3 = 3096$

And $16^5 - 10^4 = 55,536$

And $16^4 - 10^5 = 948,576$

So you want to solve $55,536a + 3,096b + 156c + 6d + 0e = 400,000$ where $0 \le a,b,c,d,e \le 9$. There may not be a solution but if there is it is unique (except for $e$) as each coefficient is more than ten times the previous.

$400,000 = 7*55,536 + 11,248$

$11,248 = 3*3,096 + 1960$.

$1960 > 10*156$.

so there is no solution.

It's worth noting that $(16 -10)=6$ will always divide $16^k -10^k$ so there can only be a solution if $6|y$. As $6\not \mid 400,000$ there is no solution for $y = 400, 000$.

But having $y$ divisible by $6$ is not enough to guarentee there will be a solution.

fleablood
  • 124,253
  • The context is this: a coworker and I were joking that we should go to our bases and say when they made a salary offer to us we thought it was in hexadec, but paychecks would be in base 10. I did a quick estimate and said “ha, they would owe me about 400k more per year” and my friend and I both immediately wondered, can she reverse engineer my salary in base 10 from this information – Prince M Mar 30 '19 at 04:17
  • Also, are those just typos on the exponents in the last two inlines ? – Prince M Mar 30 '19 at 04:20
  • I gladly accept your answer since technically you precisely answered exactly what I asked. Can you point me towards where I can learn about how you justified uniqueness? – Prince M Mar 30 '19 at 04:21
  • 1
    Each $16^k - 10^k$ is more than $10$ times the previous $16^{k-1} - 10^k$ term. So $x_k(16^k-10^k) + x_{k-1}(16^{k-1}-10^{k-1})+ ....+x_16 < 16{k-1}-10^{k-1}$ So if $y_m(16^m-10^k)+ ..... + y_{k+1)(16^{k+1}-10^{k-1}) + [y_k(16^k-10^k) + y_{k-1}(16^{k-1}-10^{k-1})+ ....+y_16] = x_m(16^m-10^k)+ ..... + x_{k+1)(16^{k+1}-10^{k-1}) + [x_k(16^k-10^k) + x_{k-1}(16^{k-1}-10^{k-1})+ ....+x_1*6] $ means that $[y_k(16^k-10^k) + y_{k-1}(16^{k-1}-10^{k-1})+ ....+y_1*6] = [x_k(16^k-10^k) + x_{k-1}(16^{k-1}-10^{k-1})+ ....+x_1*6]$ and by induction the expression is unique. – fleablood Mar 30 '19 at 16:15