Idoneal numbers: Difference between revisions

From Rosetta Code
Content added Content deleted
(Added Swift solution)
(J draft)
Line 57: Line 57:
312 330 345 357 385 408 462 520 760 840 1320 1365 1848
312 330 345 357 385 408 462 520 760 840 1320 1365 1848
Calculations took 28.5862 ms</pre>
Calculations took 28.5862 ms</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|PARI/GP}}==
=={{header|PARI/GP}}==
Line 68: Line 79:
120 130 133 165 168 177 190 210 232 240 253 273 280
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>
312 330 345 357 385 408 462 520 760 840 1320 1365 1848</pre>

=={{header|Pascal}}==
=={{header|Pascal}}==
==={{header|Free Pascal}}===
==={{header|Free Pascal}}===

Revision as of 14:41, 24 September 2022

Idoneal numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Idoneal numbers (also called suitable numbers or convenient numbers) are the positive integers D such that any integer expressible in only one way as x2 ± Dy2 (where x2 is relatively prime to Dy2) 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


C#

Translation of: Python
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);
  }
}
Output:
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

J

   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

Here, comb 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.)

PARI/GP

Adapted from the OEIS:A000926 page.

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", "")))
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

Pascal

Free Pascal

copy of Raku/Python etc only reducing multiplies in sum.

program idoneals;
{$IFDEF FPC} {$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$ENDIF}
{$IFDEF WINDOWS}{$APPTYPE CONSOLE}{$ENDIF}
function isIdoneal(n: Uint32):Boolean;
var
  a,b,c,sum : Uint32;
begin
  For a := 1 to n do
    For b := a+1 to n do
    Begin
      if (a*b + a + b > n) then
        BREAK;
      sum := a*b + b*b + a*b;        
      For c := b+1 to n do
      begin
       {sum3 = a * b + b * c + a * c}
        sum += a+b;
        if (sum = n) then
          EXIT(false);
       if (sum > n) then
         BREAK;
      end;  
    end;
   exit(true);
end;   

var 
  n ,l: Uint32;
//  idoneals : array of Uint32;

begin 
  l := 0;
  For n := 1 to 1850 do
    if isIdoneal(n) then
    Begin
     inc(l);
//   setlength(idoneals,l);  idoneals[l-1] := n;
     write(n:5);
     if l mod 13 = 0 then
       Writeln; 
    end;  
end.
@TIO.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

Real time: 0.102 s User time: 0.081 s Sys. time: 0.020 s

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

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" : " ")
    }
}
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