Hardy-Ramanujan-Zahlenverallgemeinerung

12

1729, bekannt als die Hardy-Ramanujan-Zahl , ist die kleinste positive Ganzzahl, die auf zwei Arten als Summe von zwei Würfeln positiver Ganzzahlen ausgedrückt werden kann ( 12^3+1^3=10^3+9^3=1729). Wenn Sie eine Ganzzahl angeben n(als Eingabe in einer beliebigen Form, die für Ihre Sprache Ihrer Wahl natürlich ist), finden Sie die kleinste positive Ganzzahl, die als Summe von zwei positiven Ganzzahlen ausgedrückt werden kann, die nauf zwei einzigartige Arten nach der Potenz angehoben werden. Keine Verwendung externer Quellen. Die wenigsten Charaktere gewinnen.

Beachten Sie, dass dies tatsächlich ein ungelöstes Problem für ist n>4. Lassen Sie für diese Zahlen Ihr Programm für immer auf der Suche laufen, oder versuchen Sie es nicht mehr! Stellen Sie sicher, dass das Programm das Problem löst, wenn Sie unendlich viel Zeit und Ressourcen zur Verfügung haben.

Ben Reich
quelle
2
Möglicherweise möchten Sie (?) "Die Summe von zwei positiven Ganzzahlen angeben, die nach der nth-Potenz angehoben werden". Ansonsten ist 91(nicht 1729) die Lösung für n=3, da 6^3+(−5)^3=4^3+3^3=91. Ich habe dies über Ihren Wikipedia-Link erfahren. Vielleicht macht Ihre HM-Referenz dies aus konventionellen Gründen unnötig. Prost!
Darren Stone
Eigentlich 1ist die erste Lösung:1 = cbrt(0.5)^3 + cbrt(0.5)^3 = ...
John Dvorak
Danke für die Anregungen und Bearbeitung - ich meinte 2 positive ganze Zahlen!
Ben Reich
1
@ JanDvorak, ha, ja. Keeping it R eal!
Darren Stone
Sie sagen , „ finden die kleinste positive ganze Zahl , dass“ ..., als ob es ist ein - aber für alle n > 4, die Existenz solcher Zahlen ist ein ungelöstes Problem . Vielleicht sollten Sie sagen "finde die kleinste positive ganze Zahl ( falls es eine gibt ), die" ... Es ist möglich, dass die "Antworten" keine Endlosschleifen sind, die nichts finden.
Res

Antworten:

3

APL  45  41

{⍺←1⋄2≤+/,⍺=(v∘.≤v)×∘.+⍨⍵*⍨v←⍳⌊⍺*.5:⍺⋄⍵∇⍨⍺+1}

Kürzere aber langsamere Version von 41 Zeichen:

{⍺←1⋄2≤+/,⍺=(v∘.≤v)×∘.+⍨⍵*⍨v←⍳⍺:⍺⋄⍵∇⍨⍺+1}

Sie können es online ausprobieren , indem Sie die Funktion einfügen und mit einer Zahl aufrufen:

      {⍺←1⋄2≤+/,⍺=(v∘.≤v)×∘.+⍨⍵*⍨v←⍳⌊⍺*.5:⍺⋄⍵∇⍨⍺+1} 2
50
      {⍺←1⋄2≤+/,⍺=(v∘.≤v)×∘.+⍨⍵*⍨v←⍳⌊⍺*.5:⍺⋄⍵∇⍨⍺+1} 3
1729

(Der Algorithmus ist jedoch ziemlich dumm. Erwarten Sie nicht, dass der Online-Interpreter n = 4 berechnet.)

Die Antwort für n = 2 ist 50 = 5² + 5² = 7² + 1², weil es sich um eine Zahl handelt, die "als die Summe zweier Quadrate positiver Ganzzahlen ausgedrückt werden kann - nicht anders ausgedrückt - auf zwei Arten."

Wenn Sie die unterschiedliche Klausel, nur Änderung hinzufügen möchten (v∘.≤v)in (v∘.<v), gleiche Anzahl von Zeichen, und n = 2 wird 65:

      {⍺←1⋄2≤+/,⍺=(v∘.<v)×∘.+⍨⍵*⍨v←⍳⌊⍺*.5:⍺⋄⍵∇⍨⍺+1} 2
65

Ich besiege GolfScript? Kann nicht sein !!

Tobia
quelle
nett! Und ich habe verschiedene ganze Zahlen gemeint, aber ich habe nicht spezifiziert, also mehr Kraft für dich! Zurück zum Zeichenbrett für das GolfScript ...
Ben Reich
2

Rubin, 132

n=$*[r=0].to_i;while r+=1
r.times{|a|r.times{|b|next if
a**n+b**n!=r;r.times{|c|r.times{|d|puts(r)if
c**n+d**n==r&&a!=c&&a!=d}}}}end

Übergeben nals Befehlszeilenargument. Erste Zeile stdoutist die Lösung.

Optimiert für Code-Golf, nicht für Performance. (Läuft korrekt. Aber langsam. Arbeitet mehr als nötig.)


Hier ist ein längeres, etwas schnelleres C-Programm. Gleicher korrekter aber schrecklicher Algorithmus. (Ich muss wirklich mehr Theorie studieren!)

Getestet auf n= 2, n= 3.

C 234

#include<stdio.h>#include<math.h>
r,a,b,c,d;main(n){scanf("%d",&n);while(++r){for(a=0;a<r;++a){for(b=a;b<r;++b){if(pow(a,n)+pow(b,n)!=r)continue;for(c=a+1;c<r;++c){for(d=0;d<r;++d){if(pow(c,n)+pow(d,n)==r&&a!=d)printf("%d\n",r);}}}}}}

Die C - Version nimmt nauf stdin. Wie oben ist die erste Zeile stdoutdie Lösung.

Darren Stone
quelle
1

GolfScript 53

1\.{;\).,{}@.@\{?}+%.`{\{+}+%~}+%$.`{\{=}+,,4=}+,.!}do)

Die Eingabe ist die Anfangsnummer auf dem Stapel. Die Zahl oben auf dem Stapel am Ende ist die Antwort. Ich werde das genauer erklären, wenn ich die Gelegenheit dazu bekomme.

Z.B

{1\.{;\).,@.@\{?}+%.`{\{+}+%~}+%$.`{\{=}+,,4=}+,.!}do)}:f
2 f -> 25 
3 f -> 1729

Das ist momentan ziemlich langsam. Es zählt auch 0(damit 25 die Antwort ist n=2, da 25=5^2+0^2=3^2+4^2. Um nicht 0 zu zählen, fügen Sie die 2 Zeichen (;nach dem ersten hinzu,

1\.{;\).,(;{}@.@\{?}+%.`{\{+}+%~}+%$.`{\{=}+,,4=}+,.!}do)

Um das zu finden 2 f=65, seit65=8^2+1^2=5^2+6^2

Ben Reich
quelle
1

GolfScript (30 Zeichen)

:N{).,{)N?}%:P{1$\-P?)},,3<}do

Hinweis: Dies ist recht langsam, da es eher eine Brute-Force-Suche als etwas Elegantes wie eine Prioritätswarteschlange ausführt. Das eleganteste daran ist die Wiederverwendung Nals Untergrenze für die Suche: Dies gilt 1^N + 2^N > Nfür alle N.

Nimmt Nder Stapel auf, bleibt die entsprechende Taxinummer auf dem Stapel. Zu nehmen Nvon stdin, voranstellen ~.

Die obige Version erlaubt x^N + x^N(also dafür N=2gibt es 50). Wenn Sie eindeutige Zahlen hinzufügen möchten ( 65stattdessen geben), ändern Sie den Wert 3auf 4. Um zu erlauben 0^N + x^N(zu geben 25), entfernen Sie die )unmittelbar zuvor N?.

Peter Taylor
quelle
0

Mathematica, 58 Zeichen

Eine sehr sehr langsame Lösung unter Verwendung der Erzeugungsfunktion:

0//.i_/;(D[Sum[x^(n^#),{n,1,i}]^2,{x,i}]/.x->0)/i!<4:>i+1&
Alephalpha
quelle