On random divisor sums modulo $2^k$ Let $k,n,\ell$ be positive integers with $k,n\ge 2$ and $0\le \ell \le k-1$. For each integer $2\le j \le n$, choose a divisor $d_j$ of $j$, uniformly at random from the divisors of $j$. We denote by $P(n,k,\ell)$ the probability that $$d_2 + d_3 + \cdots + d_n \equiv \ell \pmod{k}.$$ This answer on MSE shows that $P(n, k, \ell) \to 1/k$ as $n\to\infty$, regardless of $\ell$.
The proof given in the MSE answer is "Fourier analytic." Alternatively, we could argue "algebraically", as follows:
Sketch when $k=p$ is an odd prime: using Dirichlet's theorem, take a sequence of primes $\{a_i\}$ such that each $a_i$ is a primitive root modulo $p$. Consider the sequence $q_i = a_{i}^{p-2}$. The divisors of each $q_i$ are equidistributed modulo $p$, so roughly, whenever $n$ is one of these $q_i$, the probability of the divisor sum hitting what we want will be about $1/p$. Doing a sort of interpolation between these points (the details aren't too tricky) gives the result.
But when $k = 2^j$, this argument won't work, since powers of $2$ don't have primitive roots. However, the following generating function/"Fourier analytic" argument will work:
Consider the polynomial $$p_n (x) = \prod_{k=2}^{n} \left(\sum_{d\vert n} x^d \right) = (x+x^2)(x+x^3)(x+x^2+x^4) \cdots$$ Taking $\omega$ a $2^j$-th root of unity, a roots of unity filter gives $$P(n, 2^j, 0) = \frac{1}{2^j p_n (1)}\sum_{i=0}^{2^j - 1} p_n (\omega^i)$$ Now, note that for each $i$, by Dirichlet's theorem, we can find a prime $p$ of the form $$2^{i+1} m + 2^i + 1 = 2^i (2m+1)+1$$ so that $x^{2^i} + 1$ divides $x^p + x$. It follows that there exists $n_0$ such that for all $n\ge n_0$, $$(x^{2^{k-1}} + 1)(x^{2^{k-2}}+1) \cdots (x^4 + 1)(x^2 + 1)(x+1)\, \big \vert\,  p_n (x)$$ and hence $p_n (\omega) = p_n (\omega^2) = \cdots p_n (\omega^{2^j - 1}) = 0$. Accordingly, $P(n, 2^j,0)$ is exactly $1/2^j$ for $n\ge n_0$.
My first question is what can be said about $n_0$? For instance, when $k=32$, then using Dirichlet's theorem to compute the smallest primes that satisfy the desired divisibility condition will show that $p_{41} (x)$ is divisible by $\prod_{i=0}^{4} (x^{2^i} + 1)$. But actually, in this case, $n_0 = 27 < 41$, because $x^8 + 1$ "anomalously" divides $x+x^3 + x^9 + x^{27}$.
So we are asking the question: for each $i$, what is the smallest $k$ for which $x^{2^i} + 1$ divides $q_k (x) = \sum_{d\vert k} x^d$? This also suggests the more general problem: how does the polynomial $q_k (x)$ factor? 

This is a consequence of the Catalan conjecture.
$'x^8+1'$ is a 'cube plus 1', hence 'misses a beat' when it factors $x+x^3+x^9+x^{27}$.
Because $27-3$ has $8$ as a factor, the factorization is:
$$x+x^3+x^9+x^{27}=(1+x^8)(x+x^3-x^{11}+x^{19})$$ as $11$ and $19$ are both $3\mod8$.
And this only works because $9=3^2=1+8=1+2^3$, so it is the only 'anomaly'.
