The formula for calculating how many binary switching elements you need is
$$N = \log_2 \left \lceil \frac{\max - \min}{\text{step}} \right\rceil$$
where \$\lceil x \rceil\$ is rounding up to next whole integer, and \$\log_2\$ is base-2 logarithm; you can use \$\log_2 x = (\log x) / (\log 2)\$ (regardless of the base of the logarithms on the right side, as long as you use the same one for both).
Or, in another terms, \$\log_2\lceil x \rceil\$ means you find the smallest power of two that is at least \$x\$, i.e. the smallest \$k\$ for which \$x \le 2^k\$, and use the exponent \$k\$.
When you have \$N\$ switching elements in series, there are \$2^N\$ combinations. The base one, \$\text{step}\$, is then
$$\text{step} = \frac{\max - \min}{2^N - 1}$$
If you round it up, you'll push \$\max\$ higher; round it down, and you reduce \$\max\$:
$$\max = \min + (2^N - 1)\text{step}$$
(The term \$2^N-1\$ comes from the fact that the largest \$N\$-bit value is \$2^N-1\$. There are a total of \$2^N\$ values, yes, but the smallest one is zero.)
The step from 50 Ohm to 3k Ohm should be under 15 Ohm (mimic 0.5% scale)
\$\frac{3000 - 50}{15} \le 197\$, and the closest power of two not smaller than that is \$256 = 2^8\$, so you need 8 steps for that. You'll also need a non-switchable 50 Ohm resistor in series with the switchable ones.
and from 3k to 4k5 with max 30 Ohm step (mimic 1% resistor).
Because the steps are formed by the smaller resistors, you save nothing by combining two separate linear scales into one resistor pack. Here, you'd need \$33\$ steps, and even if we round it down to \$32 = 2^5\$, you'll still add five new resistors.
If you instead extend the range to 4k5, \$\frac{4500-50}{15} \le 297\$, the closest power of two not smaller than that is \$512 = 2^9\$. Only one added resistor, in other words.
So how many bits I need to accomplish that?
Only nine, and you get a full 50 to 4k5 range with constant-sized steps, assuming exact resistor values.
You even have options. For example, if your smallest resistor is 10 Ohms, and you start at 10 Ohms (i.e. have an unswitchable 10 Ohms always in series), the range will be from 10 Ohm to 5120 Ohm (0 to 5110 Ohm if you do not have a fixed 10 Ohm resistor), with a step of 10 Ohms, because
$$\max = \min + 10 \times (2^9 - 1) = \min + 10 \times 511 = \min + 5110$$
Edited: In practice, if each switchable resistor is precise to within \$v/N\$ (in Ohms, i.e. absolute precision, not relative precision like is usually used), your resistor pack will be precise to within \$v\$ Ohms. There are other ways to ensure precision, but I think this is the most useful (I could be wrong, though).
In any case, I personally would get – borrow, hire – a precise resistance meter when building the resistor packs.