1
$\begingroup$

(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, 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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Also: don't you mean to say, "36 is not an idoneal number"? $\endgroup$
    – Zev Chonoles
    Commented Jan 10, 2010 at 8:43
  • $\begingroup$ Yes, I do. Sorry. $\endgroup$
    – user3114
    Commented Jan 10, 2010 at 8:53
  • $\begingroup$ You can edit your post to fix it :) $\endgroup$
    – Zev Chonoles
    Commented Jan 10, 2010 at 9:00

2 Answers 2

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Yes, I saw that. I assumed that was on the subject of proof; it seemed unlikely that the criterion would fail for such trivial cases, which is why I assumed the mistake was mine. Proposition 17, which follows the quoted passage, is based on the same principles, and ostensibly correct, but I have similar problems with that. If this approach is wrong, then, what would be a better alternative (optimising for simplicity rather than mathematical elegance)? $\endgroup$
    – user3114
    Commented Jan 10, 2010 at 8:42
  • $\begingroup$ Well, I don't really know anything about this subject other than the Wikipedia page and the couple of paragraphs I read in the paper you linked to, but since Euler and Gauss got a list which is at worst missing one idoneal number, I do think brute force (while inelegant) is a reasonable option here - it certainly takes less time than doing a lot of number crunching. However, if you're searching for that possible one extra idoneal number, I suppose the criterion "$n$ is idoneal iff it cannot be written as $ab+ac+bc$ for integers $0<a<b<c$" is suitable for a computer search. $\endgroup$
    – Zev Chonoles
    Commented Jan 10, 2010 at 8:54
  • $\begingroup$ (because once you check past, say, $a=\frac{\sqrt{n}}{3}$, you'll know whether $n$ is idoneal or not) $\endgroup$
    – Zev Chonoles
    Commented Jan 10, 2010 at 9:20
  • $\begingroup$ Thank you for your help, Zev. My intent is to learn about concepts by writing programs whose accuracy I can verify by testing them against a given sequence in the OEIS. I can hard-code the sequence in my program or utilise a brute force algorithm, but it would be more edifying if my implementation was based on some measure of theory. (I fear I have wasted respondents' time by neglecting to state my purpose upfront :-(). Perhaps the approach regarding class numbers will be more fruitful. :-) $\endgroup$
    – user3114
    Commented Jan 11, 2010 at 0:07
  • $\begingroup$ No problem - I'm glad you're interested in learning more about math! I would say, though, that your approach is not quite as much a test of understanding the math, as it is of knowing how to program (which is an important skill!). In my opinion, trying some problems in a textbook covering this topic would help your understanding of it more than writing programs which implement the theory. $\endgroup$
    – Zev Chonoles
    Commented Jan 14, 2010 at 18:25
1
$\begingroup$

I think that we have had a previous thread related idoneal numbers here. The known idoneal numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16, 18, 21, 22, 24, 25, 28, 30, 33, 37, 40, 42, 45, 48, 57, 58, 60, 70, 72, 78, 85, 88, 93, 102, 105, 112, 120, 130, 133, 165, 168, 177, 190, 210, 232, 240, 253, 273, 280, 312, 330, 345, 357, 385, 408, 462, 520, 760, 840, 1320, 1365, and 1848 there is possibly one more. If there is an additional idoneal number it must be greater than 8436. If the generalized Riemann hypothesis holds the above sequence is complete. I got this number from the wikipedia article there is also a online integer sequence for these numbers at A000926.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .