17
\$\begingroup\$

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 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 , so the shortest code in bytes wins

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Brownie points for beating/matching my 13 byte Jelly answer which outputs the first \$n\$ idoneal numbers, or my 14 byte Jelly answer which outputs all 65 \$\endgroup\$ Sep 1 at 20:08
  • 3
    \$\begingroup\$ Shouldn't it be numeri idonei (plural)? \$\endgroup\$
    – Luis Mendo
    Sep 1 at 20:51
  • \$\begingroup\$ @LuisMendo I have no idea - I don't know Latin. I'm just going by the first name from OEIS (because "Idoneal numbers" was too short a title). I think the OEIS page also has that listed as one of the names though \$\endgroup\$ Sep 1 at 20:54
  • \$\begingroup\$ This Jelly 12-byter works for "first n terms", except for 1 and 2 :/ \$\endgroup\$
    – Bubbler
    Sep 2 at 1:57
  • 8
    \$\begingroup\$ ...the margin of this stack exchange question is not large enough to contain my proof of the Riemann... \$\endgroup\$
    – neph
    Sep 2 at 20:07

15 Answers 15

5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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 (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
\$\endgroup\$
1
4
\$\begingroup\$

Charcoal, 30 bytes

F⁹⁹FιFκ⊞υ⁺×⊕ι⁺⊕κ⊕λ×⊕κ⊕λI⁻…¹⊗φυ

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

F⁹⁹FιFκ

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.

I⁻…¹⊗φυ

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

\$\endgroup\$
4
\$\begingroup\$

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).

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ for(a=99;--a?b=~a&&a:print(i);) \$\endgroup\$
    – tsh
    Sep 2 at 2:42
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 68 bytes \$\endgroup\$ Sep 2 at 1:08
  • \$\begingroup\$ 53 bytes - times out on TIO \$\endgroup\$
    – G B
    Sep 2 at 12:52
3
\$\begingroup\$

Python 3, 93 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, 103 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!!!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ I'm pretty sure that in this case a<b<c is equivalent to (a-b)*(b-c)*(c-a). Could make it a bit faster, too? \$\endgroup\$ Sep 2 at 0:13
  • \$\begingroup\$ @FryAmTheEggman Great golf - thanks! Yeah, that's a few times faster! :D \$\endgroup\$
    – Noodle9
    Sep 2 at 9:37
3
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ You can use 2e3 instead of 1848 for -1 byte \$\endgroup\$ Sep 5 at 19:46
  • \$\begingroup\$ -n flag indicates no input, may help with later answers \$\endgroup\$
    – Razetime
    Sep 6 at 3:44
  • \$\begingroup\$ From what I've heard at the jq IRC, I think the [.[]+$a][] and .[]+$a distinction is due to some weird variable shenanigans. \$\endgroup\$
    – Razetime
    Sep 6 at 3:47
2
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ Can you use 2E3 (or something similar) instead of 1848 to save a byte? \$\endgroup\$ Sep 1 at 20:28
  • \$\begingroup\$ @Dudecoinheringaahing I guess 7! could save a byte... \$\endgroup\$
    – ZaMoC
    Sep 1 at 20:31
  • \$\begingroup\$ 59 bytes \$\endgroup\$
    – att
    Sep 1 at 20:39
  • \$\begingroup\$ 58 \$\endgroup\$
    – att
    Sep 1 at 20:42
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Could you filter the infinite list of natural numbers instead, to save 3 bytes? \$\endgroup\$ Sep 3 at 14:18
  • \$\begingroup\$ @Dudecoinheringaahing - Hmm... I think that that would never terminate, even if the request to return all combinations of picking 3 from it worked (which I doubt). Or am I missing something? \$\endgroup\$ Sep 3 at 14:25
  • \$\begingroup\$ I'm not sure exactly how Husk's infinite lists work, I was thinking that it'd be able to handle that (for some reason) \$\endgroup\$ Sep 3 at 14:26
1
\$\begingroup\$

Pari/GP, 55 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.