Idoneal numbers
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#
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
FreeBASIC
- original version
- version with minimized multiplications
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- Output:
'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
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.
version with minimized multiplications.
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.
- @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
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
Phix
with javascript_semantics sequence res = {} for n=1 to 1850 do bool found = true; for a=1 to n do for b=a+1 to n do if not found or a*b+a+b>n then exit end if integer ab = (2*a + b)*b for c=b+1 to n do ab += a+b if ab == n then found = false end if if ab >= n then exit end if end for end for end for if found then res &= n end if end for printf(1,"The %d known Idoneal numbers:\n%s\n", {length(res),join_by(res,1,13," ",fmt:="%4d")})
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
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 '')
- 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
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