Euler's numerus idoneus

Question

Euler's numerus idoneus, or idoneal numbers, are a finite set of numbers whose exact number is unknown, as it depends on whether or not the Generalized Riemann hypothesis holds or not. If it does, there are exactly 65 idoneal numbers. If not, there are either 66 or 67. For the purposes of this challenge, we'll revolutionise mathematics and say that the Generalised Riemann hypothesis is true (I'd prove it, but I'm trying to golf the challenge body).

Under this assumption, the 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, 1848

This is A000926, and many different ways to describe this sequence can be found there. However, we'll include two of the most standard ones here:

• A positive integer \$D\$ is idoneal if, for any integer expressible in the form \$x^2 \pm Dy^2\$ in exactly one way (where \$x^2\$ and \$Dy^2\$ are co-prime), that integer is either a prime power, or twice a prime power.

  For example, let \$D = 3\$. \$3\$ is idoneal, meaning that all integers that can be expressed as \$x^2 \pm 3y^2\$ for exactly one co-prime pair \$(x, y)\$ are either primes \$p\$, powers of primes \$p^n\$ or twice a prime power \$2p^n\$. As an example, \$(x, y) = (2, 3)\$ yields \$29\$ as \$x^2 + 3y^2\$. \$29\$ is a prime, and cannot be expressed in the form \$x^2 \pm 3y^2\$ for any other co-prime pair \$(x, y)\$.

• Alternatively (and rather more simply), a positive integer \$n\$ is idoneal iff it cannot be written in the form \$ab + ac + bc\$ for distinct positive integers \$a, b, c\$

  For example, \$11 = 1\times2 + 1\times3 + 2\times3\$, therefore, \$11\$ is not idoneal.

This is a standard sequence challenge, you may choose one of the following three options:

• Take an integer \$n\$ (either \$0 \le n < 65\$ or \$0 < n \le 65\$, your choice) as input, and output the \$n\$th (either 0 or 1 indexed, also your choice) idoneal number. You may choose how to order the idoneal numbers, so long as its consistent.
• Take a positive integer \$1 \le n \le 65\$ and output the first \$n\$ idoneal numbers. Again, you may choose how to order the idoneal numbers.
• Output all 65 idoneal numbers, in any order, with no duplicates.

This is code-golf, so the shortest code in bytes wins

Answer 1

Wolfram Language (Mathematica), 53 bytes

Range[7!]/.<|Array[+##(3#+#2)-#3#->Set@$&,49+0{,,}]|>

Try it online!

Outputs all(?) 65 idoneal numbers. Filters out numbers of the form \$a(a+b)+(a+b)(a+b+c)+(a+b+c)a\$ with \$a,b,c\$ positive integers.

Answer 2

Jelly, 13 bytes

2ȷœc3ṙ€1ḋƊḟ@R

Try it online!

First Jelly answer! Prints all ideonal numbers.

Gosh this was painful. This should work given several terabytes of RAM and a couple of hours. To see, replace 2ȷ(2000) with 20 or something.

-10 thanks to Dude coinheringaahing.

2ȷœc3          # Combinations of 1..2000 of length 3 
     ṙ€1ḋ      # Calculate ab+ac+bc for each
         Ɗḟ@   # Remove these from 
2ȷ          R  # 1...2000

Answer 3

Charcoal, 30 bytes

Ｆ⁹⁹ＦιＦκ⊞υ⁺×⊕ι⁺⊕κ⊕λ×⊕κ⊕λＩ⁻…¹⊗φυ

Try it online! Link is to verbose version of code. Explanation:

Ｆ⁹⁹ＦιＦκ

Loop over distinct 100 > a > b > c > 0. (Replacing ⁹⁹ with φ would save a byte but make the code too slow for TIO.)

⊞υ⁺×⊕ι⁺⊕κ⊕λ×⊕κ⊕λ

Calculate ab + ac + bc.

Ｉ⁻…¹⊗φυ

Take the range from 1 to 1999 and remove all values that resulted from the above calculation.

Answer 4

R, 72 65 62 bytes

r=i=1:2e3
for(a in r)for(b in a+r)i[(b+r)*(a+b)+a*b]=F;r[i[r]]

Try it online!

Outputs all idoneal numbers in ascending order.

The TIO link will time-out, since r is needlessly set to 1...2000 to save bytes; here is a link to a version with r initialized to 1...99 instead, which doesn't time-out (and still gives the right output).

Answer 5

Vyxal, 17 bytes

∞'£ɾ3ḋ'Ǔ*∑¥=;ḃ;?i

Try it Online!

Warning: This will not work for n ≥ 7. It's just too slow.

∞'            ;?i # Get the nth number where...
             ḃ    # None of
   ɾ3ḋ'     ;     # The ways you can choose 3 numbers less than n
       Ǔ*∑        # Have ab+ac+bc...
  £       ¥=      # Equal n

Answer 6

JavaScript (V8),  87  85 bytes

Saved 2 bytes thanks to @tsh

A full program printing the sequence in reverse order.

for(i=2e3;--i;)for(a=99;--a?b=~a&&a:print(i);)while(c=--b)while(--c)a*=a*b+a*c+b*c!=i

Try it online!

Commented

for(                 // 1st loop
  i = 2e3;           // going from i = 1999 to i = 1
  --i;               //
)                    //
  for(               //   2nd loop
    a = 99;          //   starting with a = 99
    --a ?            //   decrement a; if it's not zero:
      b = ~a && a    //     stop if a = -1, otherwise set b to a
    :                //   else:
      print(i);      //     we've reached a = 0: print i
  )                  //
    while(c = --b)   //     3rd loop going from b = a - 1 to b = 1
      while(--c)     //       4th loop going from c = b - 1 to c = 1
        a *=         //         clear a if ab + ac + bc is equal to i,
          a * b +    //         which will turn it into -1 on the next
          a * c +    //         iteration of the 2nd loop
          b * c != i //         (otherwise, leave it unchanged)

Answer 7

APL(Dyalog Unicode), 23 bytes ^SBCS

(⍳!7)~(1⊥2×/4⍴+\)¨⍳3⍴50

Try it on APLgolf!

A full program that prints all 65 terms. Essentially the same strategy as att's Mathematica answer. All attempts to factor out ⍳!7 failed, so here goes an efficient solution.

How it works

(⍳!7)~(1⊥2×/4⍴+\)¨⍳3⍴50    Full program; no input
                  ⍳3⍴50    50x50x50 cube containing coordinates of each cell
      (         )¨         For each item...
              +\             Cumulative sum
       1⊥2×/4⍴               From a, b, c compute ab+bc+ca
(⍳!7)~                     Remove all numbers appearing in ^ from 1..5040

Answer 8

Ruby, 75 bytes

p [*1..2e3]-(r=*1..56).product(r,r).map{|i|a,b,c=i;a<b&&b<c ?a*b+b*c+c*a:0}

Try it online!

A full program printing an array.

An array of the numbers 1..2000 is created and all non-ideonal numbers deleted from it. The smallest value of range r that works is 1..56. Reducing the number below 56 fails to delete 1012 corresponding to a,b,c = 5,12,56.

Answer 9

Python 3, ⁹³ 82 bytes

R=range(1,2000)
print({*R}-{a*b+c*(a+b)for a in R for b in R for c in R if a<b<c})

Try it online!

Outputs all the idoneal numbers (works but times out on TIO).

This version works on TIO:

Python 3, ¹⁰³ 92 bytes

R=range(1,99)
print({*range(1,2000)}-{a*b+c*(a+b)for a in R for b in R for c in R if a<b<c})

Try it online!

Saved 11 bytes thanks to FryAmTheEggman!!!

Answer 10

jq, 76 bytes

[range(2e3)+1]-[[range(56)+1]|.[]as$a|[.[]+$a][]as$b|$a*$b+($a+$b)*(.[]+$b)]

Try it online!

I don't really know why [.[]+$a][] and .[]+$a have different behavior.

Answer 11

Wolfram Language (Mathematica), 58 bytes

Select[Range[7!],!Reduce[a(b+c)+b*c-#==0<a<b<c,Integers]&]

Try it online! (here are values <100 because TIO times out)

-1 byte from Dude coinheringaahing
-8 bytes from @att

Answer 12

Jelly, 13 bytes

⁹œc3P-Ƥ€§ṬCTḣ

Try it online!

Monadic link that returns the first n terms. The leading ⁹ (constant 256) is necessary to get the correct output for n = 1 and 2 (otherwise the output is empty for those two inputs). The linked code has ⁹ replaced by 20 for demonstration purposes.

How it works

⁹œc3P-Ƥ€§ṬCTḣ    Monadic link. Left arg = n, the number of terms
⁹œc3             3-combinations of 1..256
    P-Ƥ€§        ab+bc+ca for each row
         ṬCT     List of numbers in 1..max(above) that do not appear
                 in the above list
            ḣ    Take first n

In order to filter out all ab+bc+ca numbers before 1848, the input numbers should be at least:

• 56 if you use "3-combinations of 1..(some fixed number)"
• 44 if you use "cumulative sums of 3rd cartesian power of 1..(some fixed number)"

In both cases, the hardest one to filter out is (5, 12, 56) → 1012. The next hardest is (8, 17, 51) → 1411.

---

Jelly, 14 bytes

³œc3P-Ƥ€§2ȷR¤ḟ

Try it online!

Full program that prints all 65 terms. This one finishes within a few seconds without modification.

How it works

³œc3P-Ƥ€§2ȷR¤ḟ    Niladic chain.
³œc3              3-combinations of 1..100
    P-Ƥ€§         Compute ab+bc+ca for each row
         2ȷR¤ḟ    Filter out the above from 1..2000

Answer 13

05AB1E, 14 bytes

₄·LD3.ÆεĆü*O}K

Outputs all 65 values.

Try it online (with ≤2000 replaced with ≤50).

Explanation:

₄            # Push 1000
 ·           # Double it to 2000
  L          # Pop and push a list in the range [1,2000]
   D         # Duplicate this list
    3.Æ      # Get all triplets with unique integers
       ε     # Map each triplet to:
        Ć    #  Enclose; append its own head: [a,b,c] to [a,b,c,a]
         ü   #  For each overlapping pair:
          *  #   Multiply them together: [a*b,b*c,c*a]
           O #  Sum this list: ab+bc+ca
       }K    # After the map: remove all those non-idoneal numbers from the [1,2000] list
             # (after which the result is output implicitly)

Answer 14

Husk, 17 bytes

Ṡ-omoΣSz*ṙ1Ṗ3ḣ□43

Try it online!

Returns all idoneal numbers in ascending order, but too inefficiently to run in <1min on TIO.
Instead, try idoneal numbers less than 100 without timing-out

             ḣ□43   # 1..1849 (square of 43)
Ṡ-                  # return those that aren't
  omoΣ              # sums of
      Sz*           # zipping together by multiplying       
           Ṗ3       # all combinations of picking 3 numbers
         ṙ1         # with that combination rotated by 1

Answer 15

Pari/GP, 52 bytes

f()=[n|n<-[1..7!],![c-2|c<-quadclassunit(-4*n).cyc]]

Try it online!