<s>[INST] Base conversion problems Let $b$ be an integer greater than 2, and let $N_b = 1_b + 2_b + \cdots + 100_b$ (the sum contains all valid base $b$ numbers up to $100_b$). Compute the number of values of $b$ for which the sum of the squares of the base $b$ digits of $N_b$ is at most 512.
Since we are adding up to $100$ in base $b$, I set up the equation
$$N=\frac{b^2(b^2+1)}{2},$$
and then tried to find the values that satisfy this.
For even values, of $b$, i got 16 values, but I don't know about odd values.
Now I am stuck.
 [/INST] Note that from your formula, we can deduce that $N_b = \frac{10100_b}{ 2}$. Let us carry out the division in base $b$, distinguishing two cases:

*

*If $b$ is even, then we can note that since
$$N_b = \frac{10100_b}{ 2} = \frac{10000_b}{2} + \frac{100_b}{2} = \frac{b^4}{2} + \frac{b^2}{2} = \frac{b}{2}(b^3) + \frac{b}{2} (b)$$
the resulting quotient is $\left(\frac b2 0\frac {b}{2} 0\right)_b$. (Here the digits are the digits of $b/2$, followed by a zero, then followed by the digits of $b / 2$, then followed by a final zero. So for example, if $b = 6$, then the result is $3030_6$.) So the sum of squares of the digits is less than $512$ if and only if
$$\left( \frac{b}{2}\right)^2 + \left( \frac{b}{2}\right)^2 = \frac{b^2}{2} \leq 512 \iff b \leq 32$$
Indeed, there are $15$ such even values of $b$ that satisfy this inequality (remember we have counted $b = 2$ in a separate case).


*If $b$ is odd, then we can note that since
$$N_b = \frac{10100_b}{ 2_b} = \frac{b^4}{2} + \frac{b^2}{2} = \frac{b - 1}{2}(b^3) + \frac{b + 1}{2} (b^2)$$
the resulting quotient is $\left(\frac{b-1}{2} \frac{b + 1}{2} 0 0\right)_b$. Note that both $(b - 1) / 2$ and $(b + 1) / 2$ are integers as $b$ is odd. The sum of the squares of digits is less than $512$ if and only if
$$\frac14 \left[(b - 1)^2 + (b + 1)^2\right] \leq 512 \iff b^2 + 1 \leq 1024 \iff b \leq 31$$
And so you can count $15$ possible values of $b$ here.
In total, there are $\boxed{31}$ possible values of $b$, corresponding to $2 \leq b \leq 32$. $\square$
Follow-Up: What if we want the sum of squares of digits to be less than $512_b$?
Answer: As pointed out by mwt, for this question to make sense, we require $b \geq 6$. To answer this is not difficult; instead of having $512$ on the right-hand side of the above inequalities, we note that since
$$512_b = 5b^2 + b + 2$$
we instead want
$$\begin{cases}
\frac{b^2}{2} \leq 5b^2 + b + 2 \iff 9b^2 + 2b + 4 \geq 0 & b \text{ is even} \\
\frac{b^2 + 1}{2} \leq 5b^2 + b + 2 \iff 9b^2 + 2b + 3 \geq 0 & b \text{ is odd}
\end{cases}$$
You can solve these cases to determine the allowed values of $b$. Curiously, now every value of $b$ is satisfying!
</s>