Kongruente Zahlen

21

Definitionen:

  • Ein Dreieck wird als rechtwinkliges Dreieck betrachtet, wenn einer der Innenwinkel genau 90 Grad beträgt.
  • Eine Zahl wird als rational angesehen, wenn sie durch ein Verhältnis von ganzen Zahlen dargestellt werden kann, dh p/qwenn beide pund qganze Zahlen sind.
  • Eine Zahl nist eine kongruente Zahl, wenn es ein rechtwinkliges Flächendreieck gibt, nin dem alle drei Seiten rational sind.
  • Dies ist OEIS A003273 .

Herausforderung

Dies ist eine . Ausgeben xeines eindeutigen und konsistenten Werts, wenn xes sich um eine kongruente Zahl handelt, und eines separaten eindeutigen und konsistenten Werts, wenn xes sich nicht um eine kongruente Zahl handelt. Die Ausgabewerte müssen in Ihrer Sprache nicht unbedingt wahr oder falsch sein.

Sonderregel

Für die Zwecke dieser Herausforderung können Sie davon ausgehen, dass die Vermutung von Birch und Swinnerton-Dyer wahr ist. Wenn Sie alternativ die Vermutung von Birch und Swinnerton-Dyer beweisen können, fordern Sie Ihren 1.000.000-Dollar-Millennium-Preis an. ;-)

Beispiele

(Verwendung Truefür kongruente Zahlen und Falsesonstiges).

5 True
6 True
108 False

Regeln und Erläuterungen

  • Die Ein- und Ausgabe kann auf jede bequeme Weise erfolgen .
  • Sie können das Ergebnis an STDOUT drucken oder als Funktionsergebnis zurückgeben. Bitte geben Sie bei Ihrer Übermittlung an, welche Werte die Ausgabe annehmen kann.
  • Es ist entweder ein vollständiges Programm oder eine Funktion zulässig.
  • Standardlücken sind verboten.
  • Dies ist daher gelten alle üblichen Golfregeln, und der kürzeste Code (in Byte) gewinnt.
AdmBorkBork
quelle
3
Ist die Eingabe eine positive Ganzzahl?
Lynn
Mein anfänglicher Ansatz war es, die Eingabe mit einer willkürlichen quadratischen Zahl zu multiplizieren, bis sie die Hälfte des Produkts der Beine in einem Pythagoreischen Tripel ist, aber dann wurde mir klar, dass es ein bisschen schwierig sein könnte, sie tatsächlich für eine nicht kongruente Eingabe zu terminieren.
Nicht verwandte String
@ Xi'an Okay, aber Herausforderungen sollten in sich geschlossen sein.
Lynn
@Lynn Ja, die Eingabe ist eine positive Ganzzahl.
AdmBorkBork

Antworten:

8

R 179 173 142 141 137 135 134 Bytes

Wenn Sie dieselben Argumente verwenden, die auf dem Satz von Tunnell basieren , wird ein 0if zurückgegeben, ndas nicht kongruent ist, 1andernfalls. (Ich habe lange gebraucht, um die Einschränkung für die Bedingung zu erkennen, die nur für ganze Zahlen ohne Quadrate gilt .)

function(n){b=(-n:n)^2
for(i in b^!!b)n=n/i^(!n%%i)
P=1+n%%2
o=outer
!sum(!o(y<-o(8/P*b,2*b,"+")/P-n,z<-16/P*b,"+"),-2*!o(y,4*z,"+"))}

Probieren Sie es online aus

Verbesserungen von Arnaud und Giuseppe (der letzte Code ist hauptsächlich der von Guiseppe!), Mit -3 dank Robin

Syntaxanalyse:

for(i in b[b>0])n=n/i^(!n%%i) #eliminates all square divisors of n
P=2^(n%%2)                    #n odd (2) or even (1)
o=outer                       #saves 3 bytes 
o(8/P*b,2*b,"+")/P-n          #all sums of (8/P)x^2+(2/P)*y^2-n
o(...,16/P*b,"+")             #all sums of above and (16/P)*z^2
o(...,4*z,"+"))               #all sums of above and (64/P)*z^2
!o(...,4*z,"+"))              #all sums of above equal to zero
!sum(!...,2*!...)             #are zeroes twice one another (Tunnell)

mit dem Satz von Tunnell , dass n genau dann kongruent ist, wenn die Anzahl der ganzzahligen Lösungen zu 2x² + y² + 8z² = n doppelt so groß ist wie die Anzahl der ganzzahligen Lösungen zu 2x² + y² + 32z² = n, wenn n ungerade ist und die Anzahl von ganzzahligen Lösungen auf 8x² + y² + 16z² = n ist doppelt so viel wie die Anzahl von ganzzahligen Lösungen auf 8x² + y² + 64z² = n, wenn n gerade ist.

Xi'an
quelle
1
Willkommen bei PPCG! Ziel ist es, den Code so kurz wie möglich zu halten. Vielleicht sehen Sie sich diese Tipps zum Golfen oder diese R-spezifischen Tipps an .
Giuseppe
1
Es gibt eine Menge Leerzeichen, und ich würde auch empfehlen, einen Link zu Try It Online hinzuzufügen! um deinen Code zu verifizieren :-)
Giuseppe
1
Wenn Sie möchten, können Sie auch den R-Golf-Chat nutzen . Sie können benachrichtigen, indem Sie @[username]... Ich nehme an, Sie wurden von Robin Ryder in den Code-Golf gezogen?
Giuseppe
1
142 Bytes - anonyme Funktionen sind vollkommen in Ordnung, und ich habe ein paar andere Golfspiele gemacht, die ich gerne erläutere
Giuseppe
1
Nett! Gibt es einen Grund, den du verwendest -n:n? Ich habe das Theorem von Tunnel nicht gelesen, aber es scheint mir, dass n:0es für -1 Byte genauso gut funktionieren würde ... Außerdem, Profi-Tipp, wenn Sie die "Link" -Taste oben auf TIO drücken, werden Sie nett Formate zum Kopieren und Einfügen in PPCG :-) EDIT: Ich sehe, es gibt einige Fälle, in denen n:0nicht funktioniert.
Giuseppe
3

Rust - 282 Bytes

fn is(mut n:i64)->bool{let(mut v,p)=(vec![0;4],n as usize%2);while let Some(l)=(2..n).filter(|i|n%(i*i)==0).nth(0){n/=l*l;}for x in -n..=n{for y in -n..=n{for z in -n..=n{for i in 0..2{if n-6*x*x*(n+1)%2==2*x*x+(2-n%2)*(y*y+(24*i as i64+8)*z*z){v[2*p+i]+=1};}}}}v[2*p]==2*v[2*p+1]}
  • Verwenden Sie den Satz von Jerrold B. Tunnell , den ich eigentlich nicht verstehe, der aber trotzdem zu funktionieren scheint.
  • Dividieren Sie n durch alle seine quadratischen Faktoren, um es "quadratfrei" zu machen, da in den folgenden Abhandlungen der Satz von Tunnell nur für quadratische Freiheiten beschrieben wird.
    • Ich glaube, das könnte funktionieren, weil jede kongruente Zahl, wenn sie mit einem Quadrat multipliziert wird, eine größere kongruente Zahl ergibt und umgekehrt. Wenn wir also die kleinere Zahl testen, können wir die größere validieren, die in unserem Fall n ist. (Alle entfernten Quadrate können zu einem großen Quadrat multipliziert werden.)
  • if n is odd, test if n = 2x2+y2+32z2 and/or 2x2+y2+8z2
    if n is even, test if n = 8x2+2y2+64z2 and/or 8x2+2y2+16z2
    • Im Code selbst wurden die vier Gleichungen in einer Schleife zu einer verschmolzen, wobei Modulo für gerade / ungerade verwendet wurde
  • Zählen Sie, welche Gleichungen mit n übereinstimmen
  • Teste nach dem Looping die Verhältnisse der Tallies (per Tunnell)

Siehe auch:

korrigiert gerade / ungerade, danke @Level River St

Don Bright
quelle
1
Na ja, als ich das zum Laufen brachte, sah ich nur die Antwort von C ++, die falsch war ...
don bright
danke Level River St
don bright
3

C ++ (gcc) , 251 234 Bytes

Vielen Dank an @arnauld für den Hinweis auf einen dummen Tippfehler von meiner Seite.

-17 Bytes dank @ceilingcat.

#import<cmath>
int a(int n){int s=sqrt(n),c,x=-s,y,z,i=1,X;for(;++i<n;)for(;n%(i*i)<1;n/=i*i);for(;x++<s;)for(y=-s;y++<s;)for(z=-s;z++<s;c+=n&1?2*(n==X+24*z*z)-(n==X):2*(n==4*x*x+2*X+48*z*z)-(n/2==2*x*x+X))X=2*x*x+y*y+8*z*z;return!c;}

Probieren Sie es online!

Gibt 1 zurück, wenn nkongruent ist, andernfalls 0.

qs2q ist auch kongruent (der Algorithmus scheint bei einigen quadratischen Zahlen zu brechen).

Neil A.
quelle
1
@Arnauld: ah, das war ein Tippfehler von meiner Seite. Fest.
Neil A.
1

JavaScript (ES7), 165 Byte

Ähnlich wie die Antwort von @ NeilA. Basiert diese auf dem Satz von Tunnell und geht daher davon aus, dass die Vermutung von Birch und Swinnerton-Dyer wahr ist.

Gibt einen Booleschen Wert zurück.

n=>(r=(g=i=>i<n?g(i+!(n%i**2?0:n/=i*i)):n**.5|0)(s=2),g=(C,k=r)=>k+r&&g(C,k-1,C(k*k)))(x=>g(y=>g(z=>s+=2*(n==(X=(n&1?2:8)*x+(o=2-n%2)*y)+o*32*z)-(n==X+o*8*z))))|s==2

Probieren Sie es online!

Wie?

nnr=ns2

r = (                // we will eventually save isqrt(n) into r
  g = i =>           // g = recursive function taking an integer i
    i < n ?          //   if i is less than n:
      g(i + !(       //     do a recursive call with either i or i + 1
        n % i**2 ?   //     if n is not divisible by i²:
          0          //       yield 0 and therefore increment i
        :            //     else:
          n /= i * i //       divide n by i² and leave i unchanged
      ))             //     end of recursive call
    :                //   else:
      n ** .5 | 0    //     stop recursion and return isqrt(n)
  )(s = 2)           // initial call to g with i = s = 2

gCk2r<kr

  g = (C, k = r) =>  // C = callback function, k = counter initialized to r
    k + r &&         //   if k is not equal to -r:
    g(               //     do a recursive call:
      C,             //       pass the callback function unchanged
      k - 1,         //       decrement k
      C(k * k)       //       invoke the callback function with k²
    )                //     end of recursive call

g(x,y,z)[r+1,r]3s2An=Bnn2Cn=Dnn

An=#{(x,y,z)[r+1,r]3n=2x2+y2+32z2}Bn=#{(x,y,z)[r+1,r]3n=2x2+y2+8z2}Cn=#{(x,y,z)[r+1,r]3n=8x2+2y2+64z2}Dn=#{(x,y,z)[r+1,r]3n=8x2+2y2+16z2}

g(x =>                            // for each x:      \    NB:
  g(y =>                          //   for each y:     >-- all these values are
    g(z =>                        //     for each z:  /    already squared by g
      s +=                        //       add to s:
        2 * (                     //         +2 if:
          n == (                  //           n is equal to either
            X =                   //           An if n is odd (o = 1)
            (n & 1 ? 2 : 8) * x + //           or Cn if n is even (o = 2)
            (o = 2 - n % 2) * y   //
          ) + o * 32 * z          //
        ) - (                     //         -1 if:
          n == X + o * 8 * z      //           n is equal to either
        )                         //           Bn if n is odd
    )                             //           or Dn if n is even
  )                               //
)                                 // if s in unchanged, then n is (assumed to be) congruent
Arnauld
quelle
1

Ruby , 126 Bytes

->n{[8,32].product(*[(-n..-t=1).map{|i|i*=i;n%i<1&&n/=i;i}*2+[0]]*3).map{|j|d=2-n%2
k,x,y,z=j
2*d*x+y+k*z==n/d&&t+=k-16}
t==1}

Probieren Sie es online!

fanden einen Ort zum Initialisieren t=1und Erweitern der Liste der Quadrate in ein Triplett, anstatt qzusätzliche Kopien zu erstellen.

Ruby , 129 Bytes

->n{t=0
[8,32].product(q=(-n..-1).map{|i|i*=i;n%i<1&&n/=i;i}*2+[0],q,q).map{|j|d=2-n%2
k,x,y,z=j
2*d*x+y+k*z==n/d&&t+=k-16}
t==0}

Probieren Sie es online!

Verwendet den Satz von Tunnell wie die anderen Antworten. Ich verwende eine einzelne Gleichung wie folgt.

2*d*x^2 + y^2 + k*z^2 == n/d  where d=2 for even n and d=1 for odd n

Wir prüfen die Fälle k=8und k=32, ob es doppelt so viele Lösungen gibt k=8wie k=32. Dies geschieht durch Hinzufügen k-16zu tjedem Zeitpunkt, an dem wir eine Lösung finden. Dies ist entweder +16 im Fall k=32oder -8 im Fall k=8. Insgesamt ist die Zahl kongruent, wenn sie tmit dem Anfangswert am Ende der Funktion übereinstimmt.

Es ist notwendig, alle Lösungen für die Testgleichung zu finden. Ich sehe viele Antworten zwischen +/- sqrt n. Es ist vollkommen in Ordnung, auch außerhalb dieser Grenzen zu testen, ob der Code dadurch kürzer wird, aber es werden keine Lösungen gefunden, da die linke Seite der Gleichung überschritten wird n. Das, was ich am Anfang vermisst habe, ist, dass Negatives und Positives x,y,zgetrennt betrachtet werden. Somit -3,0,3ergeben sich drei Quadrate 9,0,9und alle Lösungen müssen separat gezählt werden (0 muss einmal gezählt werden und 9muss zweimal gezählt werden.)

Ungolfed Code

->n{t=0                              #counter for solutions

  q=(-n..-1).map{|i|i*=i;n%i<1&&n/=i #make n square free by dividing by -n^2 to -1^2 as necessary 
  i}*2+[0]                           #return an array of squares, duplicate for 1^2 to n^2, and add the case 0 

  [8,32].product(q,q,q).map{|j|      #make a cartesian product of all possible values for k,x,y,z and iterate
    d=2-n%2                          #d=1 for odd n, 2 for even n
    k,x,y,z=j                        #unpack j. k=8,32. x,y,z are the squared values from q.
    2*d*x+y+k*z==n/d&&t+=k-16}       #test if the current values of k,x,y,z are a valid solution. If so, adjust t by k-16 as explained above.
t==0}                                #return true if t is the same as its initial value. otherwise false.
Level River St
quelle
Über positive und negative Lösungen, genau wie hier, habe ich eine ganze Weile damit verbracht, diesen Punkt zu verpassen!
Xi'an