View source for Idoneal numbers

{{draft task}}

'''[[wp:Idoneal_number|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<sup>2</sup> ± Dy<sup>2</sup>''' (where '''x<sup>2</sup>''' is relatively prime to '''Dy<sup>2</sup>''') 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
;* [[wp:Idoneal_number|Wikipedia: Idoneal numbers]]
;* [[oeis:A000926|OEIS:A000926 - Euler's "numerus idoneus" (or "numeri idonei", or idoneal, or suitable, or convenient numbers)]]


=={{header|BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="BASIC256">r = 0
print "The 65 known Idoneal numbers:"
for n = 1 to 1850
	if isIdoneal(n) then
		print rjust(string(n),5);
		r += 1
		if r mod 13 = 0 then print
	end if
next n
end

function isIdoneal(n)
	for a = 1 to n
		for b = a+1 to n
			if (a*b + a + b > n) then exit for
			for c = b+1 to n
				sum = a*b + b*c + a*c
				if sum = n then return false
				if sum > n then exit for
			next c
		next b
	next a
	return true
end function</syntaxhighlight>
{{out}}
<pre>Same as the original entry FreeBASIC.</pre>


==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Idoneal_numbers
// by Jjuanhdez, 09/2022

r = 0
print "The 65 known Idoneal numbers:"
for n = 1 to 1850
    if isIdoneal(n) then 
        print n using "#####";
        r = r + 1
        if mod(r,13) = 0  print
    end if
next n
end

sub isIdoneal(n)
    local a, b, c, sum
    for a = 1 to n
        for b = a+1 to n
            if (a*b + a + b > n)  break
            for c = b+1 to n
                sum = a*b + b*c + a*c
                if sum = n  return false
                if sum > n  break
            next c
        next b
    next a
    return true
end sub</syntaxhighlight>
{{out}}
<pre>Same as the original entry FreeBASIC.</pre>

=={{header|C#|CSharp}}==
{{trans|Python}}
<syntaxhighlight lang="csharp">using System;

class Program {

  static void Main(string[] args) {
    var sw = System.Diagnostics.Stopwatch.StartNew();
    int a, b, c, i, n, s3, ab; var res = new int[65];
    for (n = 1, i = 0; n < 1850; n++) {
      bool found = true;
      for (a = 1; a < n; a++)
         for (b = a + 1, ab = a * b + a + b; b < n; b++, ab += a + 1) {
            if (ab > n) break;
            for (c = b + 1, s3 = ab + (b + a) * b; c < n; c++, s3 += b + a) {
                if (s3 == n) found = false;
                if (s3 >= n) break;
            }
         }
      if (found) res[i++] = n;
    }
    sw.Stop();
    Console.WriteLine("The 65 known Idoneal numbers:");
    for (i = 0; i < res.Length; i++)
      Console.Write("{0,5}{1}", res[i], i % 13 == 12 ? "\n" : "");
    Console.Write("Calculations took {0} ms", sw.Elapsed.TotalMilliseconds);
  }
}</syntaxhighlight>
{{out}}
<pre>The 65 known Idoneal numbers:
    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
Calculations took 28.5862 ms</pre>

=={{header|FreeBASIC}}==
{{trans|Wren}} - original version
{{trans|Pascal}} - version with minimized multiplications
<syntaxhighlight lang="freebasic">Function isIdonealOrg(n As Uinteger) As Boolean
    Dim As Uinteger a, b, c, sum
    For a = 1 To n
        For b = a+1 To n
            If (a*b + a + b > n) Then Exit For
            For c = b+1 To n
                sum = a*b + b*c + a*c
                If sum = n Then Return false
                If sum > n Then Exit For
            Next c
        Next b
    Next a
    Return true
End Function

Function isIdoneal(n As Uinteger) As Boolean
    Dim As Uinteger a, b, c, axb, ab, sum
    
    For a = 1 To n
        ab = a+a
        axb = a*a
        For b = a+1 To n
            axb += a
            ab +=1
            sum = axb + b*ab
            If (sum > n) Then Exit For
            For c = b+1 To n
                sum += ab
                If (sum = n) Then Return false
                If (sum > n) Then Exit For
            Next c
        Next b
    Next a
    Return true
End Function

Dim As Double t0 = Timer
Dim r As Byte = 0
Print "The 65 known Idoneal numbers:"
For n As Uinteger = 1 To 1850
    If isIdonealOrg(n) Then 
        Print Using "#####"; n;
        r += 1
        If r Mod 13 = 0 Then Print
    End If
Next n
Print !"\nTime:"; (Timer - t0); Chr(10)

Dim As Double t1 = Timer
For n As Uinteger = 1 To 1850
    If isIdoneal(n) Then 
        Print Using "#####"; n;
        r += 1
        If r Mod 13 = 0 Then Print
    End If
Next n
Print !"\n\nTime:"; (Timer - t1)
Sleep</syntaxhighlight>
{{out}}
<pre>'Tested in jdoodle.com

The 65 known Idoneal numbers:
    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
 0.5490732192993164 ms per run

    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
 0.3645658493041992 ms per run</pre>

=={{header|J}}==
<syntaxhighlight lang=J style="width: max-content">   requre'stats'
   _10]\(1+i.255)-.+/1*/\.|:1+3 comb 255
  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
</syntaxhighlight>
Here, <code>comb</code> gives us all combinations of 3 numbers in ascending order in the given range (originally in the range 0..254 here, adding 1 shifts them to 1..255). Then we multiply all pairs from these combinations, sum the resulting products and remove those products from a sequence 1..255. (And we form the result into rows of 10 numbers each, to avoid an excessively long row of numbers.)

=={{header|jq}}==
This entry uses jq's `break` because the equivalent program using `until` is much slower.

Using either the C or Go implementations of jq,
the program shown below takes about 5 seconds to produce the 65
idoneal numbers.
For gojq, the definition of the `_nwise` helper function must be
uncommented.
<syntaxhighlight lang=jq>
# For gojq:
# def _nwise($n):
#   def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
#   n;

def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;

def isIdoneal: 
  first(
    label $out
    | . as $n
    | range(1; $n) as $a
    | label $startB
    | range($a+1; $n) as $b
    | ($a+$b) as $sum
    | ($a*$b) as $prod
    | if $prod + $sum > $n then break $startB
      else label $startC
      | range($b+1; $n) as $c
      | ($prod + $sum*$c) as $x
      | if $x == $n then 0, break $out
        elif $x > $n then break $startC
        else empty
        end
      end )
  // true | if . == 0 then false else . end;

# Search blindly
def idoneals: range(1; infinite) | select(isIdoneal);

# The task:
[limit(65; idoneals)]
 | _nwise(13) | map(lpad(5)) | join(" ")
</syntaxhighlight>
Invocation: jq -nr -f idoneal.jq
{{output}}
<pre>
    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
</pre>

=={{header|PARI/GP}}==
Adapted from the [[oeis:A000926|OEIS:A000926]] page.
<syntaxhighlight lang="parigp">ok(n) = !#select(k -> k <> 2, quadclassunit(-n << 2).cyc) \\ Andrew Howroyd, Jun 08 2018
c = 0; for (n = 1, 1850, ok(n) & printf("%5d%s", n, if (c++ % 13 == 0, "\n", "")))</syntaxhighlight>
{{out}}
<pre>    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</pre>

=={{header|Pascal}}==
==={{header|Free Pascal}}===
copy of Raku/Python etc only reducing multiplies in sum.</br>
version with minimized multiplications.
<syntaxhighlight lang="pascal">
program idoneals;
{$IFDEF FPC}
  {$MODE DELPHI}
  {$OPTIMIZATION ON,ALL}
  {$CODEALIGN loop=1}
{$ENDIF}
{$IFDEF WINDOWS}
  {$APPTYPE CONSOLE}
{$ENDIF}

uses
  sysutils;
const
 runs = 1000;
type
  Check_isIdoneal = function(n: Uint32): boolean;

var
  idoneals : array of Uint32;

function isIdonealOrg(n: Uint32):Boolean;
var
  a,b,c,sum : NativeUint;
begin
  For a := 1 to n do
    For b := a+1 to n do
    Begin
      if (a*b + a + b > n) then
        BREAK;
      For c := b+1 to n do
      begin
        sum := a * b + b * c + a * c;
        if (sum = n) then
          EXIT(false);
        if (sum > n) then
         BREAK;
      end;
    end;
  exit(true);
end;

function isIdoneal(n: Uint32):Boolean;
var
  a,b,c,axb,ab,sum : Uint32;
begin
  For a := 1 to n do
  Begin
    ab := a+a;
    axb := a*a;
    For b := a+1 to n do
    Begin
      axb += a;
      ab +=1;
      sum := axb + b*ab;
      if (sum > n) then
        BREAK;
      For c := b+1 to n do
      begin
        sum += ab;
        if (sum = n) then
          EXIT(false);
        if (sum > n) then
          BREAK;
      end;
    end;
  end;
  EXIT(true);
end;

function Check(f:Check_isIdoneal):Uint32;
var
  n : Uint32;
begin
  result := 0;
  For n := 1 to 1848 do
    if f(n) then
    Begin
      inc(result);
      setlength(idoneals,result);   idoneals[result-1] := n;
    end;
end;

procedure OneRun(f:Check_isIdoneal);
var
  T0 : Int64;
  i,l : Uint32;
begin
  T0 := GetTickCount64;
  For i := runs-1 downto 0 do
    l:= check(f);
  T0 := GetTickCount64-T0;

  dec(l);
  For i := 0 to l do
  begin
    write(idoneals[i]:5);
    if (i+1) mod 13 = 0 then
      writeln;
  end;

  Writeln(T0/runs:7:3,' ms per run');
end;

BEGIN
  OneRun(@isIdonealOrg);
  OneRun(@isIdoneal);
END.</syntaxhighlight>
{{out|@TIO.RUN}}
<pre>
    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
  6.018 ms per run
    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
  2.036 ms per run</pre>

=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
 <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
 <span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
 <span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1850</span> <span style="color: #008080;">do</span>
     <span style="color: #004080;">bool</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">;</span>
     <span style="color: #008080;">for</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
         <span style="color: #008080;">for</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">=</span><span style="color: #000000;">a</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
             <span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">found</span> <span style="color: #008080;">or</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">*</span><span style="color: #000000;">b</span><span style="color: #0000FF;">+</span><span style="color: #000000;">a</span><span style="color: #0000FF;">+</span><span style="color: #000000;">b</span><span style="color: #0000FF;">></span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
             <span style="color: #004080;">integer</span> <span style="color: #000000;">ab</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">a</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">b</span>
             <span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">b</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
                 <span style="color: #000000;">ab</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">+</span><span style="color: #000000;">b</span>
                 <span style="color: #008080;">if</span> <span style="color: #000000;">ab</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">n</span> <span style="color: #008080;">then</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
                 <span style="color: #008080;">if</span> <span style="color: #000000;">ab</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">n</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
             <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
          <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> 
     <span style="color: #008080;">if</span> <span style="color: #000000;">found</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">n</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
 <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The %d known Idoneal numbers:\n%s\n"</span><span style="color: #0000FF;">,</span>
          <span style="color: #0000FF;">{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%4d"</span><span style="color: #0000FF;">)})</span>
<!--</syntaxhighlight>-->
<pre>
The 65 known Idoneal numbers:
   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
</pre>

=={{header|Python}}==
{{trans|Raku}}
<syntaxhighlight lang="python">''' 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 '')
</syntaxhighlight>{{out}}
<pre>
    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
</pre>

=={{header|Raku}}==
First 60 in less than 1/2 second. The remaining 5 take another ~5 seconds.
<syntaxhighlight lang="raku" line>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)</syntaxhighlight>
{{out}}
<pre>   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</pre>

=={{header|Swift}}==
<syntaxhighlight lang="swift">import Foundation

func isIdoneal(_ n: Int) -> Bool {
    for a in 1..<n {
        for b in a + 1..<n {
            if a * b + a + b > n {
                break
            }
            for c in b + 1..<n {
                let sum = a * b + b * c + a * c
                if sum == n {
                    return false
                }
                if sum > n {
                    break
                }
            }
        }
    }
    return true
}

var count = 0
for n in 1..<1850 {
    if isIdoneal(n) {
        count += 1
        print(String(format: "%4d", n), terminator: count % 13 == 0 ? "\n" : " ")
    }
}</syntaxhighlight>

{{out}}
<pre>
   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
</pre>

=={{header|Wren}}==
{{trans|Raku}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascript">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)</syntaxhighlight>

{{out}}
<pre>
   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 
</pre>

=={{header|XPL0}}==
Some optimizations borrowed from others.
Times on Pi4: real 170ms, user 34ms, sys 24ms
<syntaxhighlight lang "XPL0">func IsIdoneal(N);      \Return 'true' if N is an Idoneal number
int  N, A, B, C, AB, S, T;
[for A:= 1 to N do
    for B:= A+1 to N do
        [AB:= A*B;
        S:= A+B;
        if AB+S > N then B:= N
        else for C:= B+1 to N do
                [T:= AB + C*S;
                if T = N then return false;
                if T > N then C:= N;
                ];
        ];
return true;
];

int N, C;
[N:= 1;  C:= 0;
Format(5, 0);
loop    [if IsIdoneal(N) then
            [RlOut(0, float(N));
            C:= C+1;
            if rem(C/13) = 0 then CrLf(0);
            if C >= 65 then quit;
            ];
        N:= N+1;
        ];
]</syntaxhighlight>
{{out}}
<pre>
    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
</pre>