Thank you, I'll need some time to go over the details, but it seems reasonable. Also thank you for the references, I imagined such things have been dealt with before but didn't know where to look.

It means a typo, thanks for pointing it out!

Since the algorithm terminates for the first 3 numbers, it suffices to show that for any N, iterating the algorithm eventually produces a number smaller than N. Then analysing congruences mod 10 shows that only numbers ending in 9 have not became smaller after 4 iterations. But for higher iterations the numbers obtained are now always even, so they don't end in 9, and so eventually any number becomes smaller (I think this can be proved analysing mod 10.000 but have not checked).

I would (perhaps naively) expect $d_k$ to tend to zero as $n$ tends to infinity for any given $k$, it is just that the scales at which it happens will vary with $k$ since the sum of all the $d_k$ is always $1$. I imagine for smaller $n$ you will see $d_2$ increasing before it starts decreasing, and for large enough $n$, $d_3$ will eventually decrease to $0$.

I'm not sure this graph is helpful: I think a random number of a given size will display a similar behavior (i.e. listing the parity of the times each prime divides it, one would get a row similar to the ones in this graph for the corresponding size). In particular it will have several "ones" on the right.

Well, you can look at all vectors with weight one (there are only $n$ of them up to scaling) to see if they belong to $U$, if not move to weight two, and so on... but presumably you want a faster algorithm.