Is this equation for hamming code block size unsolvable?

Question

I'm only a freshman in Algebra II, so don't expect this question to be as high level as the other ones on this site, but I'm trying. Anyway, to help me learn about hamming codes, I decided to write a piece of software that automatically applied hamming codes to files. I wanted to implement a feature where the user can enter the percentage of bits they want to dedicate to redundancy. I was able to derive the following equation to calculate the percentage based on the block size: $$p=\frac{log_2(b)+1}{b}$$ (the $+1$ is there to account for the extra full-block parity bit). I know that all I have to do is take the inverse of this equation, or solve $b$ in terms of $p$, but neither I nor my Algebra II teacher can solve it. We think that it may be an unsolvable problem, but I don't know how to make a proof of the unsolvability of an equation, and all the papers I can find online are much above my level of understanding. I was wondering if y'all could point me in the direction of a lower-level explanation on constructing such proofs, or if you could help shed light on whether it even is indeed unsolvable.

Thank you so much for the help.

Answer 1

There's no elementary solution to this equation. However, as is often the case with simple looking problems that don't have elementary solutions, mathematicians have defined a new function to make there be a solution. In this case, where we have a mixture of linear and logarithmic factors, it's the Lambert W function. That might sound intimidating, but its definition is actually pretty simple: $y = W_k(x)$ is the $k$th complex solution to $y\exp(y) = x$. Since we're working with real numbers, we only need to worry about $k = 0$ and $k = -1$. We'll figure out which one later. So all we have to do is get the equation into that form and we can use the $W$ function to solve. This can be done by $$ p = \frac{\log_2(b) + 1}{b} \Longrightarrow bp = \log_2(b) + 1 \Longrightarrow 2^{bp} = 2b \Longrightarrow-\frac{\ln2}{2}p = (-bp\ln2) e^{-bp\ln2}. $$ Now we use the $W$ function to get $$ -bp\ln2 = W_k\left(-\frac{\ln 2}{2}p\right)\Longrightarrow b = -\frac{1}{p\ln2}W_k\left(-\frac{\ln 2}{2}p\right) $$ Now, do we want $k = 0$ or $k = -1$? $k = 0$ gives values in the range $(0, 1)$ while $k = -1$ gives values in the range $(2, \infty)$. The latter makes much more sense for $b$, so we have $$ b = -\frac{1}{p\ln2}W_{-1}\left(-\frac{\ln 2}{2}p\right) $$