(I am a very, very new to mathematics, so I apologise in advance for posing a question so basic, but am out of ideas).


In [*Idoneal Numbers and some Generalizations*](http://www.mast.queensu.ca/~kani/papers/idoneal.pdf), pp. 15, Ernst Kani quotes Euler's criterion for idoneal numbers: 



>  
> An integer n ≥ 1 is idoneal if and only if for every k = 1,..., [√(n∕3)] with (k, n) = 1 we have that n + k2 = p, p2 , 2p or 2s, for some odd prime p and some integer s ≥ 1.
> 


However, my interpretation of this criterion leads to false positives: non-idoneal integers being recognised as idoneal. Kani discusses that others were dissatisfied with this formulation, but it is my understanding that these criticisms are mainly theoretical. That is, the formulation above is supposed to correctly identify all known idoneal numbers.


I take k to be every value between 1 and √(n∕3) inclusive that is coprime to n. I assume k should only take integer values, but am unsure of how to round the square root, i.e. nearest, floor, or ceiling.


For every value of k I compute sum = n + k2. If sum is odd and prime, I take this to be the n + k2 = p result. If sum is a perfect square whose square root is prime, I take it to be the n + k2 = p2 result. If sum is even and sum∕2 is prime, I assume n + k2 = 2p. Lastly, if sum is a power of 2 whose exponent is ≥ 1, I assume 
n + k2 = 2s.


I require one of the above results for each value of k to regard n as idoneal.


Let n = 36. √(n∕3) = 3.4641016151377544. Therefore, k = 1, 2, or 3. Only 1 is coprime to n, so this is k's sole value. n + k2 = p = 36 + 1 = 37. 37 is both odd and prime. This seems to satisfy the criterion as I understand it, but 36 is not an idoneal number. n = 100 is but one of other false positives.


Any clues on either how to interpret this criterion correctly or a better algorithm (short of brute force) to recognise idoneal numbers?



Interpreting Euler's Criterion for Idoneal Numbers
In the remark below the statement of Euler's criterion in the paper you linked to, notice that Grube, who tried to correct Euler's original "proof" of this criterion, actually only provided a correct version in one direction - 



> 
> Frei [17], p. 57, points out that Grube only proved one direction of this criterion and
>  says, “whether [this criterion] is also sufficient is still an open problem”
> 
> 
> 


which explains why you might get false positives.


