Let p be a prime congruent to -1 modulo 4, $\kron{n}{p}$ the Legendre symbol and $S(k) = \sum_{n=1}^{p-1}n^k \kron{n}{p}$. The problem of finding a prime p such that $S(3) >0$ was one of the motivating forces behind the development of several of Shanks' ideas for computing in algebraic number fields, although neither he nor D. H. and Emma Lehmer were ever successful in finding such a p. In this paper we exhibit some techniques which were successful in producing, for each k such that $3\le k \le 2000$, a value for p such that $S(k) >0$.