For $k=1$, we may choose $n=2^{p-1}$ where $p\ge3$ is prime.

Take $n=2^{p-1}\times3\times5\times...\times q_{k}$ where $q_{k}$ is the $k^{\text{th}}$ prime number and $p$ is a sufficiently large prime. Then $\omega\left(n\right)=k$ and $d\left(n\right)=2^{k-1}p$. Now $d\left(n\right)\mid d\left(a^{2}+b^{2}\right)\Rightarrow p\mid d\left(a^{2}+b^{2}\right)\Rightarrow Q^{p-1}\mid a^{2}+b^{2}$ for some prime $Q$. Thus $Q^{p-1}\leq a^{2}+b^{2}\leq\left(a+b\right)^{2}=n^{2}=4^{p-1}\times3^{2}\times5^{2}\times...\times q_{k}^{2}$. Now if $Q>4$ then by taking $p$ sufficiently large then we get a contradiction. Thus $Q=2,3$. Now if $Q=3$ then $3^{p-1}\mid a^{2}+b^{2}\Rightarrow 3^{p-1}\mid a^{2},b^{2}$ as $-1$ is not a quadratic residue modulo $3$. But then $3^{\frac{p-1}{2}}\mid a,b\Rightarrow 3^{\frac{p-1}{2}}\mid a+b=n$ which is a contradiction as $p$ is sufficiently large. Thus $Q=2$ so $2^{p-1}\mid a^{2}+b^{2}\Rightarrow 2^{p-1}\mid a^{2},b^{2}$ as $-1$ is not a quadratic residue modulo $4$ (and $p$ is sufficiently large). Thus $2^{\frac{p-1}{2}}\mid a,b$. Hence we can write $a=2^{\frac{p-1}{2}}\alpha,b=2^{\frac{p-1}{2}}\beta$ where $\alpha+\beta=2^{\frac{p-1}{2}}\times3\times5\times...\times q_{k}$ - note $\alpha+\beta$ is even. Then $a^{2}+b^{2}=2^{p-1}\left(\alpha^{2}+\beta^{2}\right)$. Now as $\alpha+\beta$ is even, so is $\alpha^{2}+\beta^{2}$, and furthermore the largest power of $2$ dividing $\alpha^{2}+\beta^{2}$ is $2^{p-1}$. Thus $a^{2}+b^{2}=2^{p+x}s$ where $s$ is odd and $0\leq x\leq p-2$. Hence $d\left(a^{2}+b^{2}\right)=\left(p+x+1\right)d\left(s\right)$. So $d\left(n\right)\mid d\left(a^{2}+b^{2}\right)\Rightarrow 2^{k-1}p\mid\left(p+x+1\right)d\left(s\right)$. But as $0\leq x\leq p-2$ we have that $p,p+x+1$ are coprime. Thus $p\mid d\left(s\right)$ so $\exists$ some odd prime $R$ such that $R^{p-1}\mid s$. But $s=\frac{a^{2}+b^{2}}{2^{p+x}}\leq\frac{a^{2}+b^{2}}{2^{p}}\leq\frac{n^{2}}{2^{p}}=2^{p-2}\times3^{2}\times5^{2}\times...\times q_{k}^{2}$. By making $p$ sufficiently large we get a contradiction. As required.

Choose $n=2^{P-1}m$, with $P$ a very big prime, and $m$ an odd integer such that $w(m)=k-1$. Suppose there exists $a+b=n$ such that $d(n) | d(a^2+b^2)$. Then there exists a prime $q$ such that $P | v_q(a^2+b^2)+1$. Now, take $c \in \mathbb{R}$ such that $n=2^{c(P-1)}$, with $c$ greater than but close to $1$. Then $q^{P-1} | a^2+b^2$, so $2^{log_2(q)*(P-1)} = q^{P-1} \le a^2+b^2 \le n^2 = 2^{(2c)(P-1)}$ and so $log_2(q) \le 2c$. But we can choose $c$ to be as close to $1$ as we want, so therefore we can assure $q=3$ or $q=2$. But it is impossible to have $3 | a^2+b^2$. Therefore $q=2$ and $P | v_2(a^2+b^2)+1$. If $v_2(a)$ and $v_2(b)$ are distinct, say $v_2(b) < v_2(a)$, then $P | 2v_2(b)+1$. Since $2^{(3P-1)/2} > n > b$ (if we choose $c$ small enough), then $v_2(b)=(P-1)/2$. But $b=n-a$ and $v_2(n)=P-1$. So $v_2(a)=(P-1)/2$. Contradiction. Therefore $v_2(a)=v_2(b)$. Say $a=2^rc$, $b=2^rd$, with $c$ and $d$ odd. Clearly $r \le P-1$. Then $c+d=2^(P-r)m$ and $P | v_2(c^2+d^2)+2r+1$. But $v_2(c^2+d^2)=1$, so $P | 2r+2$. So $2P \le 2r+2$ and so $P \le r+1$. So $P=r+1$. But it is impossible to have $a+b=2^{P-1}m$ and also $v_2(a)=v_2(b)=P-1$. Therefore we have a contradiction. Clearly $w(n)=k$ so we are finished.

frill wrote: Take $n=2^{p-1}\times3\times5\times...\times q_{k}$ where $q_{k}$ is the $k^{\text{th}}$ prime number and $p$ is a sufficiently large prime. Then $\omega\left(n\right)=k$ and $d\left(n\right)=2^{k-1}p$. Now $d\left(n\right)\mid d\left(a^{2}+b^{2}\right)\Rightarrow p\mid d\left(a^{2}+b^{2}\right)\Rightarrow Q^{p-1}\mid a^{2}+b^{2}$ for some prime $Q$. Thus $Q^{p-1}\leq a^{2}+b^{2}\leq\left(a+b\right)^{2}=n^{2}=4^{p-1}\times3^{2}\times5^{2}\times...\times q_{k}^{2}$. Now if $Q>4$ then by taking $p$ sufficiently large then we get a contradiction. Thus $Q=2,3$. Now if $Q=3$ then $3^{p-1}\mid a^{2}+b^{2}\Rightarrow 3^{p-1}\mid a^{2},b^{2}$ as $-1$ is not a quadratic residue modulo $3$. But then $3^{\frac{p-1}{2}}\mid a,b\Rightarrow 3^{\frac{p-1}{2}}\mid a+b=n$ which is a contradiction as $p$ is sufficiently large. Thus $Q=2$ so $2^{p-1}\mid a^{2}+b^{2}\Rightarrow 2^{p-1}\mid a^{2},b^{2}$ as $-1$ is not a quadratic residue modulo $4$ (and $p$ is sufficiently large). Thus $2^{\frac{p-1}{2}}\mid a,b$. Hence we can write $a=2^{\frac{p-1}{2}}\alpha,b=2^{\frac{p-1}{2}}\beta$ where $\alpha+\beta=2^{\frac{p-1}{2}}\times3\times5\times...\times q_{k}$ - note $\alpha+\beta$ is even. Then $a^{2}+b^{2}=2^{p-1}\left(\alpha^{2}+\beta^{2}\right)$. Now as $\alpha+\beta$ is even, so is $\alpha^{2}+\beta^{2}$, and furthermore the largest power of $2$ dividing $\alpha^{2}+\beta^{2}$ is $2^{p-1}$. Thus $a^{2}+b^{2}=2^{p+x}s$ where $s$ is odd and $0\leq x\leq p-2$. Hence $d\left(a^{2}+b^{2}\right)=\left(p+x+1\right)d\left(s\right)$. So $d\left(n\right)\mid d\left(a^{2}+b^{2}\right)\Rightarrow 2^{k-1}p\mid\left(p+x+1\right)d\left(s\right)$. But as $0\leq x\leq p-2$ we have that $p,p+x+1$ are coprime. Thus $p\mid d\left(s\right)$ so $\exists$ some odd prime $R$ such that $R^{p-1}\mid s$. But $s=\frac{a^{2}+b^{2}}{2^{p+x}}\leq\frac{a^{2}+b^{2}}{2^{p}}\leq\frac{n^{2}}{2^{p}}=2^{p-2}\times3^{2}\times5^{2}\times...\times q_{k}^{2}$. By making $p$ sufficiently large we get a contradiction. As required.

frill wrote: Now $d\left(n\right)\mid d\left(a^{2}+b^{2}\right)\Rightarrow p\mid d\left(a^{2}+b^{2}\right)\Rightarrow Q^{p-1}\mid a^{2}+b^{2}$ for some prime $Q$. Thus $Q^{p-1}\leq a^{2}+b^{2}\leq\left(a+b\right)^{2}=n^{2}=4^{p-1}\times3^{2}\times5^{2}\times...\times q_{k}^{2}$. If $Q^{pl-1}\mid a^2+b^2$ ? for some positive integers $l$

@ISHO95: I do not quite understand what you are asking. If $Q^{pl-1}\mid a^{2}+b^{2}$ for some $l\in\mathbb{Z}^{+}$ then in particular $Q^{p-1}\mid a^{2}+b^{2}$ since $Q^{p-1}\mid Q^{pl-1}$ $\left(\text{as }p-1\leq pl-1\right)$.

Weird problem. The condition is very artificial, although the construction is kind of fun. I'm guessing the low scores during the actual contest were actually due to an unusually tricky P2. Let $n = 2^{p-1}t$, where $t \equiv 5 \pmod 6$, $\omega(t) = k-1$, and $p \gg t$ is a sufficiently large prime. Let $a+b=n$ and $a^2+b^2=c$. We claim that $p \nmid d(c)$ which solves the problem. First, note that $3 \nmid a^2+b^2$, since $3 \nmid n$. Next, note that $c < 2n^2 < 5^{p-1}$ (since $p \gg t$) so no exponent of an odd prime in $c$ exceeds $p-2$. Moreover, $c < 2^{3p-1}$. So, it remains to check that $\nu_2(c) \notin \{p-1, 2p-1\}$. On the one hand, if $\nu_2(a) < \nu_2(b)$, then $\nu_2(a) = p-1$ and $\nu_2(c) = 2\nu_2(a) = 2p-2$. On the other hand, if $\nu_2(a) = \nu_2(b)$ then $\nu_2(a) \le p-2$, and $\nu_2(c) = 2\nu_2(a)+1$ is odd and less than $2p-1$.

My solution is a bit long and bashy, but I think it gets the job done. It also addresses what ISHO95 asked frill. For this proof, let $v_p (m)$ denote the largest exponent of a prime p that divides m. We wish to show that n = $2^{p-1}*q_1*q_2*...*q_{k-1}$ is a solution, where $q_i$ are arbitrary odd primes and p is a sufficiently large prime number. To begin, note that $a^2 + b^2 < n^2 < 2^{2p-2} *2^p = 4^{p-1} *2^p < 2^{3p-1}$ for sufficiently large p. Hence, for d(n) $\mid d(a^2+b^2)$, $v_2(a^2+b^2) = 2p-1, v_2(a^2+b^2) = p-1 $or$ v_3(a^2+b^2) = p-1$. Case one: $v_2(a^2+b^2) = 2p-1$ Let gcd(a,b)=d. Hence, a = a'$\cdot$d, b = b'$\cdot$d where gcd(a',b') = 1. Since a+b = n and 2|n, a' $\equiv$ b' $\equiv$ 1 mod 2. Also note that the quadratic residues in mod 4 are 0 and 1. So $v_2(a'^2 + b'^2) = 1$ Hence, $v_2 (a^2+b^2) = v_2 (gcd(a^2, b^2)) + 1 < v_2 (n^2) +1 = 2p-1 $. So $v_2 (a^2 +b^2)$ cannot equal 2p-1. Case two: $v_3(a^2+b^2)$ = p-1 Suppose on the contrary that this statement was true. Since the quadratic residues in modulo 3 are 0 and 1, $v_3 (a'^2 + b'^2) = 0$. So $v_3 (a^2+b^2) = v_3 (d^2)$. Since d $\mid$ n, $\frac{p-1}{2} = v_3 (d) \leq v_3 (n) = 0 $ or 1, a contradiction for sufficiently large p. Case three: $v_2(a^2+b^2)$ = p-1 Suppose on the contrary that this statement was true. Note that $v_2 (a'^2+b'^2) = 1$. Hence, $v_2 (a^2+b^2) = v_2 (d^2) +1 = p-1 \iff v_2 (d) = \frac{p-2}{2}$. For odd n, this is a contradiction since $\frac{p-2}{2}$ is not an integer. Hence all our cases do not contradict our desired statement and we can generate an infinite set of solutions from our n.

shivangjindal wrote: We denote the number of positive divisors of a positive integer $m$ by $d(m)$ and the number of distinct prime divisors of $m$ by $\omega(m)$. Let $k$ be a positive integer. Prove that there exist infinitely many positive integers $n$ such that $\omega(n) = k$ and $d(n)$ does not divide $d(a^2+b^2)$ for any positive integers $a, b$ satisfying $a + b = n$. Let $n=2^mj$ where $\gcd(j, 6)=1$ with $\omega(j)=k-1$ and $m+1$ is a prime with $m>10^9j$. Notice that $3 \nmid a^2+(n-a)^2$ else $3 \mid n$. Suppose $r \ge 5$ is a prime with $r^{\ell} \mid a^2+(n-a)^2$ and $\ell$ is the largest possible. Since $\left(\tfrac{r}{4}\right)^m>(1.25)^m>j^2$ we see $r^m>n^2>a^2+(n-a)^2$. Consequently, $\ell+1\le m$ so $(m+1) \nmid (v_r(a^2+(n-a)^2)+1)$ for any prime $r>2$. Finally, we see $v_2(a^2+(n-a)^2)=2v_2(a)+1$ for $v_2(a)<m$ and $2v_2(a)$ otherwise. So $(m+1) \nmid (v_2(a^2+(n-a)^2)+1)$ and we're good to go. Note: For $k=1$ let $j=1$ be the empty product; even then our proof works well. $\blacksquare$

Let $p_1 < p_2 < ... < p_m < ...$ be the sequence of all primes larger than $3$. Let $c = p_1...p_{k-1}$ (if $k=1$, $c=1$). Let $p$ be any odd prime such that $(5/4)^{p-1} > c^2$. Then we claim that $n = 2^{p-1}*c$ works, which would solve the problem. Suppose there exist positive integers $a, b$ with $a+b = n$, with $t = a^2 + b^2$, and $d(n) | d(t)$. We get a contradiction in the following way: Note that if $3 | a^2 + b^2$, then $3 | a+b = n$, a contradiction. So $3$ doesn't divide $t$. Note that $t < n^2$. Suppose $p$ doesn't divide $v_2(t) + 1$. Then $n^2 > t \geq 5^{p-1} > 4^{p-1}*c^2 = n^2$, a contradiction. So $p | v_2(t) + 1$. Now suppose $v_2(a) < v_2(b)$. Then $v_2(a) = v_2(n) = p-1$, and $v_2(t) = 2v_2(a) = 2(p-1)$, but $p | v_2(t) + 1$, a contradiction. So, $v_2(a) = v_2(b) = v$. Then $p-1 = v_2(n) \geq v+1$. $v_2(t) = 2v+1$ (as the sum of two odd squares has $v_2 = 1$). So $v_2(t) \leq 2p-3$, so $v_2(t) = p - 1$, so $2v + 1 = p-1$, which is a contradiction as $p-1$ is even but $2v + 1$ is odd. Note: Some of the conditions are useless remnants from my initial attempts at finding a construction. For example, it seems that actually any $c$ coprime to $6$ with $w(c) = k-1$ should work.

$(p_i)_{i=1} ^{\infty} $ is the sequence of prime numbers. Let $n = 2^{\mathcal{P}-1}\cdot p_3 \cdot p_4 \cdots p_{k+1}$ where $\mathcal{P}$ is a very large prime number. Let $\mathcal{C} = p_3 \cdot p_4 \cdots p_{k+1}$. Let $q$ be a prime divisor of $a^2+b^2$. Now $a^2+b^2 < n^2 = 2^{2\mathcal{P}-2} \mathcal{C}^2$. Choose $\mathcal{P}$ so that $5^{\mathcal{P}-1} > 2^{2\mathcal{P}-2} \mathcal{C}^2 \longleftrightarrow \bigg( \frac{5}{4} \bigg)^{\mathcal{P}-1}>\mathcal{C}^2$. So such $\mathcal{P}$ exists. Now for $q \geq 5, \ v_q(a^2+b^2)<\mathcal{P}-1$. If not, then $$a^2 +b^2 \geq q^{\mathcal{P}-1} \geq 5^{\mathcal{P}-1}>n^2 >a^2 +b^2$$Moreover if $q=3$ then $3 \mid a$ so $3 \mid b$. Then $3 \mid n$, contradiction. So now consider $q=2$. $v_2(a^2+b^2) = v_2( 2a^2 +n^2 -2an) \leq v_2(n^2)= 2\mathcal{P}-2< 2\mathcal{P}-1$. Now if $ v_2( 2a^2 +n^2 -2an) = \mathcal{P}-1$ then $v_2(2a^2) = \mathcal{P}-1$. But $\mathcal{P}-1$ is even while $v_2(2a^2)$ is odd. Not possible. So for all primes $q \mid a^2+b^2, \ \ \mathcal{P} \nmid v_q(a^2+b^2)+1$. So $\mathcal{P} \mid d(n)$ but $\mathcal{P} \nmid d(a^2+b^2)$. So we are done.

Let $n=2^ep_1\cdots p_{k-1}=2^eg$ where $p_1,\ldots,p_{k-1}$ are some $k-1$ fixed prime numbers that are all at least $5$, and where $e+1$ varies over all sufficiently large prime numbers. We claim that this satisfies the conditions of the problem. Clearly $\omega(n)=k$. We see that $d(n)=(e+1)2^{k-1}$, so suppose for sake of contradiction that there was some $1\le a\le\frac{n}{2}$ such that $2^{k-1}(e+1)\mid d(a^2+(n-a)^2)$. In fact, we'll derive a contradiction from just the fact that $e+1\mid d(a^2+(n-a)^2)$. Since $e+1$ is prime, the only way for $e+1\mid d(x)$ to be true is if there is some prime $q$ such that $e+1\mid\nu_q(x)+1$, or $\nu_q(x)\in\{e,2e+1,3e+2,4e+3,\ldots\}=:S_e$. Thus, there is a prime $q$ such that \[\nu_q(a^2+(n-a)^2)\in S_e.\]Note that $a^2+(n-a)^2\le n^2=4^eg$, so for $e$ sufficiently large, we must have $q\le 3$. Since $\gcd(n,3)=1$, it's not hard to check that $3\nmid a^2+(n-a)^2$, so the only possibility is that \[\nu_2(a^2+(2^eg-a)^2)\in S_e.\]Write $a=2^kr$ where $r$ is odd. There are three cases. First, suppose that $k\le e-1$. Here, we see that \[(2^kr)^2+(2^eg-2^kr)^2=2^{2k}(r^2+(2^{e-k}g-r)^2).\]We see that $(2^{e-k}g-r)^2\equiv r^2\pmod{4}$, so \[r^2+(2^{e-k}g-r)^2\equiv 2r^2\equiv 1\pmod{4}.\]Thus, $\nu_2(a^2+(n-a)^2)=2k+1$. Since $e$ is even, this can't be $e$, and since it is at most $2e-1$, it can't be anything else in $S_e$. So in this case, $q=2$ doesn't work, so $e+1\nmid d(a^2+b^2)$. Now, suppose that $k=e$. In this case, we see that \[a^2+(n-a)^2=2^{2e}(r^2+(g-r)^2).\]Since $g$ is odd, we see that $r^2+(g-r)^2$ is odd, so $\nu_2(a^2+(n-a)^2)=2e$, which isn't an element of $S_e$, so $e+1\nmid d(a^2+b^2)$ in this case as well. Finally, suppose that $k\ge e+1$. Then, \[a^2+(n-a)^2=2^{2k}r^2+2^{2e}(g-2^{k-e}r)^2,\]which has $\nu_2$ equal to $2k$, so $\nu_2(a^2+(n-a))^2=2k$. This could potentially be equal to $3e+2,5e+4,\ldots$, so then $k>\frac{3}{2}e$. By making $e$ sufficiently large however, we can ensure that \[2^{3e/2}>2^eg=n,\]so this doesn't work either. Therefore, in all cases, we get $e+1\nmid d(a^2+b^2)$, which is a contradiction. Therefore, the claimed $n$ works.

I have kinda suspicious solution, not using powers of $2$ First set $n = p_1p_2... p_k$ these being any primes. We will prove in this case $d(a^2+(n-a)^2)$ is odd Look at exponent of any prime $p$ in $d(a^2+(n-a)^2)$. We consider two cases $(1)$ $v_p(a^2) \neq v_p((n-a)^2)$ This implies $v_p(a^2+(n-a)^2) = min \{ v_p(a^2), v_p((n-a)^2) \} = min \{ 2v_p(a), 2v_p(n-1) \} $ and this is even $(2)$ $v_p(a^2) = v_p((n-a)^2) > 0$ This is equivalent to $v_p(a) = v_p(n-a)$ implying that $p$ divides $n$. We now rewrite this as $v_p(a^2+(n-a)^2) = v_p(p^2(\frac{a}{p})^2+p^2(\frac{n}{p}-\frac{a}{p})^2) = 2 + v_p((\frac{a}{p})^2+(\frac{n}{p}-\frac{a}{p})^2)$ Now $p$ no longer divides $n$ so by $(1)$ and first part of $(2)$ we have $v_p((\frac{a}{p})^2+(\frac{n}{p}-\frac{a}{p})^2)$ is even so the whole thing is even Putting this together we have $v_p(a^2+(n-a)^2) + 1$ is always odd so $d(n) = 2^k \nmid d(a^2+b^2)$ $\blacksquare$

Cute Number Theory. For $k = 1$, take $n = 2^{P - 1}$ for a large prime $P$. Now, notice that $d(n) = P $. Then we have \[ P | d(a^2 + b^2) \]Since $a^2 + b^2 < 4^{P - 1}$. Then we have either $2^{P - 1} | a^2 + b^2$ or $3^{P - 1} | a^2 + b^2$. The latter case ruled out. Therefore, we have $2^{P - 1} | a^2 + b^2$. In particular, $\nu_2(a^2 + b^2) = kP - 1$ for an integer $k \ge 1$. Notice that if $\nu_2(a^2 + b^2) \ge 2P - 1$. This gives us $a = 2^{P - 1} | a$ and $2^{P - 1} | b$ which then result to $ a + b > 2^P$ , a contradiction. Therefore, we must have $\nu_2(a^2 + b^2) = P - 1$. This gives us $\min(\nu_2(a), \nu_2 (b)) = \frac{P - 1}{2}$. Notice that $\nu_2(a) = \nu_2(b)$. Otherwise $\nu_2(a + b) = \min ( \nu_2(a), \nu_2 (b) )$. Therefore, \[ \nu_2(a) = \nu_2(b) = \frac{P - 1}{2} \]This gives us $\nu_2(a^2 + b^2) > P - 1$, a contradiction. Take $n = 2^{P - 1} \cdot \prod_{k = 1}^{n} p_k$ where $p_1, p_2, \dots, p_n$ denote consecutive odd primes respectively, that is $p_1 = 3, p_2 = 5, \dots$ and $P$ is a large prime. Now, notice that \[ a^2 + b^2 < n^2 = \left( 2^{P - 1} \cdot \prod_{k = 1}^{n} p_k \right)^2 < 5^{P - 1}\]Note: Take $P$ such that \[ \left( \prod_{k = 1}^n p_k \right)^2 < \left( \frac{5}{4} \right)^{P - 1} \]Therefore, since we have $2^k P | d(a^2 + b^2)$. Then either $2^{P - 1} | a^2 + b^2 $ or $3^{P-1} | a^2 + b^2$. The latter one implies $3^{\frac{P - 1}{2}} | a, b$, which contradicts the fact that $a+b = n$. Lemma. $\nu_2(a^2 + b^2) = P - 1$ Suppose otherwise, that $\nu_2(a^2 + b^2) \ge 2P - 1$. Now, notice that $2^{2P - 1} | a^2 + b^2$ and $\nu_2(a + b) = P - 1$. The former equation gives us $2^{P - 1} | a$ and $2^{P - 1} | b$. Moreover, $\frac{a}{2^{P - 1}}$ and $\frac{b}{2^{P - 1}}$ must be in the same parity, or otherwise we have $\nu_2(a^2 + b^2) = 2P - 2$. But this final statement gives us $2^P | a + b$, a contradiction. Therefore, we must have $\nu_2(a^2 + b^2) = P - 1$ and $\nu_2(a + b) = P - 1$ as well. Therefore, since $\nu_2(a^2 + b^2)$ is even, we have that $\nu_2(a) \not= \nu_2(b)$. Otherwise, \[ \nu_2(a^2 + b^2) = 2 \nu_2(a) + 1 \]Therefore, \[ \nu_2(a+b) = \min(\nu_2(a), \nu_2(b)) = P - 1 \]WLOG, suppose $\nu_2(a) < \nu_2(b)$. But this gives us \[ \nu_2(a^2 + b^2) = \min ( 2 \nu_2(a), 2 \nu_2(b)) = 2\nu_2(a) = 2P - 2 \]a contradiction.

Let the first $k$ primes that are congruent to $1$ mod $4$ be $p_{1}, p_{2}, \ldots p_{k-1}, p_{k}$, and consider some large enough $M$ such that for all numbers $r > M$, we have \[4^{r}\cdot (p_{1}p_{2}\ldots p_{k-1})^{2} < 2\cdot 5^{r}\](This $M$ exists since $5 > 4$) Choose some prime $q > M$, and consider the number \[n = 2^{q-1}\cdot (p_{1}p_{2}\ldots p_{k-1})\]I claim this satisfies the conditions (which also proves infinite such $n$ exists, since there are infinite many choices of $q$). Since $q | d(n)$, if some $a, b$ existed where $a + b = n$ and $d(n) | d(a^{2} + b^{2})$. Thus, $q | d(a^{2} + b^{2})$, which means there exists some prime $p | a^{2} + b^{2}$, where $v_{p}(a^{2} + b^{2}) \equiv -1\mod q$. First, $p\not \equiv 3\mod 4$. This is because if $a^{2} + b^{2}\equiv 0\mod p$, then if $a, b\neq 0\mod p$, the order of $\frac{a}{b}$ mod $p$ is $4$ which contradicts $4 | p-1$. This means $p | a, b$, so $p | a+b = n$, but all the prime divisors of $n$ are $1\mod 4$ or $2$. Next, we also can not have $p = 2$. Let $v_{2}(a) = r, v_{2}(b) = s, a = 2^{r}\cdot c, b = 2^{s} \cdot b$. WLOG $s \geq r$. If $s > q-1$, then $v_{2}(n-b) = min(v_{2}(n), v_{2}(b)) = q-1$, which implies $v_{2}(a^{2} + b^{2}) = v_{2}(a^{2}) = 2q-2$, but then $v_{2}(a^{2} + b^{2})\not\equiv -1\mod q$. Thus, assume $r, s \leq q-1$. If $s\neq r$, then \[q-1 = v_{2}(n) = v_{2}(a + b) = v_{2}(2^{r}\cdot c + 2^{s}\cdot d) = r + v_{2}c + 2^{s-r}\cdot d) = r\]so $r = q-1$, and $s > q-1$, which we've already disproved. Thus, assume $r = s < q-1$. Since $c, d$ are both odd, this means $c^{2} + d^{2}\equiv 2\mod 4$, so \[v_{2}(a^{2} + b^{2}) = v_{2}(2^{2r}(c^{2} + d^{2})) = 2r + 1\]This can not be congruent to $-1\mod q$, since we have $r < q-1$, which concludes that $p\neq 2$ Therefore, we must have $p\equiv 1\mod 4$, which also means $p\geq 5$. This means since $v_{p}(a^{2} + b^{2}) \equiv -1\mod q$, the smallest possible value of $a^{2} + b^{2}$ is $5^{q-1}$, so $a^{2} + b^{2} \geq 5^{q-1}$. However, we have \[\frac{n^{2}}{2} \geq a^{2} + b^{2} \geq 5^{q-1} > \frac{4^{r}(p_{1}p_{2}\ldots p_{k-1})^{2}}{2} > \frac{n^{2}}{2}\]This is a contradiction. Thus, we will never have any $a, b$ such that $d(n) | d(a^{2} + b^{2})$, which implies this value of $n$ works. There are infinite such $n$, which proves the problem.

Let $P = p_1p_2\cdots p_{k-1}$ for some odd primes $p_i > 3$. We will choose the number $n = 2^{r-1}P$ for a sufficiently large prime $r$. This will need $r | d(a^2 + b^2)$, so there must be a prime $q$ such that $v_q(a^2 + b^2) = sr - 1 \ge r-1$. Note that $a^2 + b^2 \le n^2$ so picking $r$ to be very large, this prime $q$ can only be $2$ or $3$ since otherwise $q > 4$ so $q^{r-1}$ is too big. If $q = 3$, then since its $3$ mod $4$, we will need big powers of $3$ dividing both $a,b$ and so $n$, which is not possible since $n$ was not divisible by $3$. So $q = 2$. Also, we must have $s = 1,2$ otherwise again its too big. Write $S = a^2 + b^2 = a^2 + (n-a)^2 = n^2 - 2a(n-a)$. Suppose $v_2(a) = z$. If $z < r-1$, then $v_2(S) = 2z+1< 2r-1$, which is odd and so can't be $r-1$, and it cant be $2r-1$ because its smaller than it. If $z \ge r-1$, then the $v_2(S) = 2r-2$, which is again bad. So we cannot have $d(n) | d(a^2 + b^2)$, as desired. $\blacksquare$

oops forgot that $\nu_2(a)=\nu_2(b)$ implies they're both at most $p-2$. Let $p_1<p_2<\cdots$ be the $1 \pmod{4}$ primes in increasing order. Pick $k-1$ distinct massive primes of approximately the same size and let them be $q_1>\cdots>q_{k-1}$. Then pick some prime $q \gg q_1,\ldots,q_{k-1}$. Consider $n=2^{q-1}\cdot p_1^{q_1-1}\cdot p_2^{q_2-1} \cdots p_{k-1}^{q_{k-1}-1}$ and suppose that there exist $a+b=n$ with $d(n) \mid d(a^2+b^2)$. This implies that there is some prime $p$ with $\nu_p(a^2+b^2)=cq-1$ for some positive integer $c$. However, note that $p \neq 3$, since $3 \mid a^2+b^2 \implies 3 \mid a,b \implies 3 \mid n$ which is false, and if $p \geq 5$ then $p^{cq-1} \geq 5^{q-1}>n^2>a^2+b^2$ since we made $q$ massive. Hence $p=2$. However, $\nu_2(a^2+b^2)=q-1$ is impossible, since if $\nu_2(a)=\nu_2(b)$ then $\nu_2(a^2+b^2)$ is odd and otherwise we need $\min\{\nu_2(a),\nu_2(b)\}=q-1 \implies \nu_2(a^2+b^2)=2q-2$. Thus we have $c \geq 2$, and if we pick $q$ sufficiently large this in fact forces $c=2$, i.e. $\nu_2(a^2+b^2)=2q-1$. Now for all $1 \leq i \leq k-1$, there must exists some prime $p \neq 2$ with $\nu_p(a^2+b^2) \equiv -1 \pmod{q_i}$. On the other hand, if the $q_i$ are taken to be sufficiently large, we also have $5^{q_{k-2}q_{k-1}-1}>(n/2^{q-1})^2 \geq (a^2+b^2)/2^{2q-1}$, which implies that these $p$ are all pairwise distinct across our choices of $i$ (if $k \leq 2$ then we ignore this; obviously the $p$ are pairwise across our $0$ or $1$ choices of $i$!). On the other hand, these $p$ also cannot be $3 \pmod{4}$ primes, since in this case $p \mid a^2+b^2 \implies 3 \mid a,b \implies 3 \mid n$. Hence by considering this divisibility for all $i$ we have $$\frac{a^2+b^2}{2^{2q-1}} \geq p_1^{q_1-1}\cdots p_{k-1}^{q_{k-1}-1} \implies a^2+b^2\geq 2n^2,$$which is absurd. Hence all these $n$ work. $\blacksquare$

Let $m$ be an integer such that $\gcd(m, 6) = 1$ and $\omega(m) = k-1$ and let $p$ be a large prime. Then we'll prove that taking $n = 2^{p-1}m$ works. We only need to prove that $d(n)$ doesn't divide $d(a^2 + b^2)$. Note that $p \mid d(n)$, so it's enough to prove that $p$ doesn't divide $d(a^2 + b^2)$. Since $a^2 + b^2 < (a + b)^2 = n^2 = 4^{p-1}m^2 < 5^{p-1}$ and $3$ doesn't divide $a^2 + b^2$, so $\nu_q(a^2 + b^2) < p-1$ for all primes $q \ge 5$. So it remains to check that $p$ doesn't divide $\nu_2(a^2 + b^2) + 1$. We split three cases: If $\nu_2(a) < p-1$, then $\nu_2(a^2 + b^2) = 2\nu_2(a) + 1 < 2(p-1) + 1$ and $2\nu_2(p) + 1 \neq p-1$. If $\nu_2(a) = p-1$, then $\nu_2(a^2 + b^2) = 2(p-1)$, which is not equal to $p-1$ and $2p - 1$. If $\nu_2(a) > p-1$, then $\nu_2(a^2 + b^2) = 2(p-1)$, which is not equal to $p-1$ and $2p - 1$. Thus we're done. $\blacksquare$

Can we somehow force a²+b² to be a perfect square so d(a²+b²) is odd?