While taking a brute-force look at this question I discovered that it seems that almost every prime (I'll conjecture every prime larger than 20627) can be written as $p=w^2+wc+d$ for $w,c,d\in \mathbb{Z}^+$ and with $cd$ a perfect cube.
This can be rearranged to say that for almost any $p$ there is a positive integer $a
This looks like a variation of seeking integer points on a Mordell curve, but allowing solutions on a finer grid. It might be a more difficult way of looking at the problem, but does it seem like some theory of elliptic curves could help classify when there's a solution (in general, or say given $a=1$ or $a=2$)? Or, given that there is a solution for $a=1$, does this suggest an algorithm for finding it?