Idoneal numbers

Idoneal numbers (also called suitable numbers or convenient numbers) are the positive integers D such that any integer expressible in only one way as x² ± Dy² (where x² is relatively prime to Dy²) is a prime power or twice a prime power.

A positive integer n is idoneal if and only if it cannot be written as ab + bc + ac for distinct positive integers a, b, and c with 0 < a < b < c.

There are only 65 known iodoneal numbers and is likely that no others exist. If there are others, it has been proven that there are at most, two more, and that no others exist below 1,000,000.

Task

Find and display at least the first 50 idoneal numbers (between 1 and 255).

Stretch

Find and display all 65 known idoneal numbers.

See also

Wikipedia: Idoneal numbers OEIS:A000926 - Euler's "numerus idoneus" (or "numeri idonei", or idoneal, or suitable, or convenient numbers)

Python

Translation of: Raku

''' Rosetta code task: rosettacode.org/wiki/Idoneal_numbers '''


def is_idoneal(num):
    ''' Return true if num is an idoneal number '''
    for a in range(1, num):
        for b in range(a + 1, num):
            if a * b + a + b > num:
                break
            for c in range(b + 1, num):
                sum3 = a * b + b * c + a * c
                if sum3 == num:
                    return False
                if sum3 > num:
                    break
    return True


row = 0
for n in range(1, 2000):
    if is_idoneal(n):
        row += 1
        print(f'{n:5}', end='\n' if row % 13 == 0 else '')

Output:

    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 1848

Raku

First 60 in less than 1/2 second. The remaining 5 take another ~5 seconds.

sub is-idoneal ($n) {
    my $idoneal = True;
    I: for 1 .. $n -> $a {
        for $a ^.. $n -> $b {
            last if $a × $b + $a + $b > $n; # short circuit
            for $b ^.. $n -> $c {
                $idoneal = False and last I if (my $sum = $a × $b + $b × $c + $c × $a) == $n;
                last if $sum > $n; # short circuit
            }
        }
    }
    $idoneal
}

$_».fmt("%4d").put for (1..1850).hyper(:32batch).grep( &is-idoneal ).batch(10)

Output:

   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 1848

Wren

Translation of: Raku

Library: Wren-fmt

import "./fmt" for Fmt

var isIdoneal = Fn.new { |n|
    for (a in 1...n) {
        for (b in a+1...n) {
            if (a*b + a + b > n) break
            for (c in b+1...n) {
                var sum = a*b + b*c + a*c
                if (sum == n) return false
                if (sum > n) break
            }
        }
    }
    return true
}

var idoneals = []
for (n in 1..1850) if (isIdoneal.call(n)) idoneals.add(n)
Fmt.tprint("$4d", idoneals, 13)

Output:

   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 1848