An integer $\ k\ $ is given.
Can we decide whether $\ \sigma(n)-2n=k\ $ has a solution and if yes, can we find one solution efficiently ?
The following even numbers were not "covered" by the range $\ [1,10^9]\ $ (That means that for those even $\ k\ $ with $\ |k|\le 1\ 000\ $ upto $\ n=10^9\ $ there is no solution.
[-482, 358, 442, 526, 550, 598, 694, 718, 778, 898, 902]
Of course, for odd $\ k\ $, the situation is much worse because for $\ n\ge 2\ $ , $\ \sigma(n)-2n\ $ is odd if and only if $\ n=m^2\ $ or $\ n=2m^2\ $ for some positive integer $\ m\ $.
Update : I found a sufficient condition for the existence of a solution :
Suppose , $\ s\ge 1\ $ is an integer such that $$m:=2^s-k-1$$ is an odd prime. With $\ n:=2^{s-1}\cdot m\ $ we have $$\sigma(n)=(2^s-1)(m+1)=2^s\cdot m+2^s-m-1=2n+k$$