Dreieckige quadratische Zahlen

11

Quadratische Zahlen sind solche, bei n^2denen n eine ganze Zahl ist. Diese werden auch als perfekte Quadrate bezeichnet, da Sie eine ganze Zahl erhalten, wenn Sie ihre Quadratwurzel ziehen.

Die ersten 10 Quadratzahlen sind: ( OEIS )

0, 1, 4, 9, 16, 25, 36, 49, 64, 81


Dreieckszahlen sind Zahlen, die ein gleichseitiges Dreieck bilden können. Die n-te Dreieckszahl ist gleich der Summe aller natürlichen Zahlen von 1 bis n.

Die ersten 10 Dreieckszahlen sind: ( OEIS )

0, 1, 3, 6, 10, 15, 21, 28, 36, 45


Quadratische Dreieckszahlen sind Zahlen, die sowohl quadratisch als auch dreieckig sind.

Die ersten 10 quadratischen Dreieckszahlen sind: ( OEIS )

0, 1, 36, 1225, 41616, 1413721, 48024900, 1631432881, 55420693056, 1882672131025, 63955431761796


Es gibt unendlich viele quadratische Zahlen, Dreieckszahlen und quadratische Dreieckszahlen.

Schreiben Sie ein Programm oder eine benannte Funktion, die eine Eingabe- (Parameter- oder Standard-) Nummer angibt n, die ndreieckige Zahl im Quadrat berechnet und ausgibt / zurückgibt, wobei n eine positive Zahl ungleich Null ist. (Für n = 1 0 zurückgeben)

Damit das Programm / die Funktion eine gültige Übermittlung ist, sollte es in der Lage sein, mindestens alle quadratischen Dreieckszahlen zurückzugeben, die kleiner als 2 ^ 31-1 sind.

Bonus

-4 Bytes für die Ausgabe aller quadratischen Dreieckszahlen kleiner als 2 ^ 63-1

-4 Bytes, um theoretisch quadratische Dreieckszahlen beliebiger Größe ausgeben zu können.

+8 Byte Strafe für Lösungen, die nicht polynomielle Zeit benötigen.

Bonusstapel.

Dies ist eine Code-Golf-Herausforderung, daher gewinnt die Antwort mit den wenigsten Bytes.

Rodolphito
quelle
Ich habe eine 8-Byte-Strafe für Lösungen hinzugefügt, die> O (n) Zeit benötigen, um sie für diejenigen fairer zu gestalten, die schnelleren Code anstreben.
Rodolphito
@ Rodolvertice Ich glaube nicht, dass du lineare Zeit meinst. Die iterative Lösung, die ich habe, ist die quadratische Zeit, weil es nSchritte gibt, und in jedem Schritt nimmt die Arithmetik lineare Zeit in Anspruch, weil die Anzahl der Ziffern linear wächst n. Ich denke nicht, dass lineare Zeit möglich ist. Es sei denn, Sie sagen, arithmetische Operationen sind konstante Zeit?
xnor
1
@ Rodolvertice Ich meine, dass meine iterative Lösung nicht O (n) ist. Ich denke, das Sauberere ist, stattdessen "Polynomzeit" zu sagen. Wenn Sie eine lineare Zeitarithmetik annehmen, erhalten Sie seltsame Dinge wie eine Lösung, bei der die Potenzierung als konstante Zeit bezeichnet wird. Amortisation kommt hier nicht ins Spiel.
xnor
1
Ich
2
"Die ersten 10 quadratischen Dreieckszahlen ..." Sicherlich meinten Sie 11? : P
Alex A.

Antworten:

8

CJam, 12 8 Bytes

XUri{_34*@-Y+}*;

Verwendet die Wiederholungsrelation aus dem Wikipedia-Artikel.

Der Code ist 16 Byte lang und qualifiziert sich für beide Boni.

Probieren Sie es online im CJam-Interpreter aus .

Wie es funktioniert

Mein Code erwies sich in jeder Hinsicht als identisch mit dem von xnor, außer dass ich den Stapel von CJam anstelle von Variablen verwende.

XU               e# Push 1 and 0 on the stack.
                 e# Since 34 * 0 - 1 + 2 = 1, this compensates for 1-based indexing.
  ri{        }*  e# Do int(input()) times:
     _34*        e#   Copy the topmost integer and multiply it by 34.
         @-      e#   Subtract the bottommost integer from the result.
           Y+    e#   Add 2.
               ; e# Discard the last result.
Dennis
quelle
Es wird sofort für sehr große Eingaben ausgeführt, aber über 3000 gibt es einen Javascript-Bereichsfehler auf dem Online-Interpreter. Ich werde es auf der Java-Implementierung versuchen.
Rodolphito
@ Rodolvertice: Ich habe zu einem iterativen Ansatz gewechselt. Es ist tatsächlich kürzer und weniger speicherintensiv.
Dennis
8

Python 2, 45 - 4 - 4 = 37

a=1;b=0
exec"a,b=b,34*b-a+2;"*input()
print a

Iteriert mit der Wiederholung

f(0) = 1
f(1) = 0
f(k) = 34*f(k-1)-f(k-2)+2

Theoretisch unterstützt dies Zahlen jeder Größe, läuft jedoch in exponentieller Zeit, sodass es sich nicht für die Boni qualifizieren sollte. Sollte für Zahlen jeder Größe funktionieren. Zum Beispiel für 100 gibt

1185827220993342542557325920096705939276583904852110550753333094088280194260929920844987597980616456388639477930416411849864965254621398934978872054025

Eine rekursive Lösung verwendet 41 Zeichen, sollte sich jedoch nicht qualifizieren, da dies exponentiell dauert.

f=lambda k:k>2and 34*f(k-1)-f(k-2)+2or~-k
xnor
quelle
Das ist ziemlich betrügerisch, eine "Schleife" durch String-Multiplikation, haha.
Rodolphito
@ Rodolvertice: Eigentlich gar nicht schummeln. Ziemlich klug und in der Tat ziemlich häufig auf der Website.
Alex A.
Ich glaube, Ihre rekursive Lösung qualifiziert sich für den ersten Bonus, der mit der execLösung verbunden wäre. Wenn Sie das Rekursionslimit ändern dürfen, kann es auch eine quadratische Dreieckszahl beliebiger Größe berechnen und für # 2 qualifizieren. Ich bin mir jedoch nicht sicher, ob dies qualifiziert ist (@Rodolvertice).
Kade
7

Pyth, 16 - 4 - 4 = 8 Bytes

Verwendet die rekursive Formel aus dem OEIS-Artikel.

K1uhh-*34G~KGtQZ

Es verwendet den Post-Assign-Befehl, der ziemlich neu ist und wirklich cool erscheint. Die Verwendung wird n-1aufgrund der 1-basierten Indizierung auf Iterationszeiten reduziert .

K1            Set K=1
u       tQ    Reduce input()-1 times
         Z    With zero as base case
 hh            +2
  -           Subtract
   *34G       34 times iterating variable
   ~K         Assign to K and use old value
    G         Assign the iterating variable.

Scheint polynomisch zu sein, weil es n-mal wiederholt wird und jede Iteration mathematisch und zuweisend ausführt, aber ich bin kein Informatiker. Beendet n = 10000 fast sofort.

Probieren Sie es hier online aus .

Maltysen
quelle
Ich denke, Sie können vermeiden, 1 von der Eingabe zu subtrahieren, wenn Sie eine Iteration bei 0,1 anstatt bei 1,0 beginnen - siehe meine Python-Antwort.
xnor
@xnor: Ich denke er macht das schon. Das von der Schleife zurückgegebene Ergebnis ist jedoch Ihr b.
Dennis
5

Oasis , 7 - 4 - 4 = -1 (nicht konkurrierend)

34*c-»T

Probieren Sie es online aus!

Verwendet a(0) = 0, a(1) = 1; for n >= 2, a(n) = 34 * a(n-1) - a(n-2) + 2

Oasis unterstützt Ganzzahlen mit beliebiger Genauigkeit, daher sollte es in der Lage sein, eine beliebige Anzahl zu erreichen, solange kein Stapelüberlauf auftritt. Lassen Sie mich wissen, wenn dies aufgrund eines Stapelüberlaufs nicht für den Bonus zählt. Es ist auch möglich, dass dieser spezielle Algorithmus nicht polynomisch ist, und lassen Sie mich wissen, ob dies der Fall ist.

Nicht konkurrierend, weil die Postdates der Sprache eine Herausforderung darstellen.

Erläuterung:

34*c-»T -> 34*c-»10

a(0) = 0
a(1) = 1
a(n) = 34*c-»

34*c-»
34*    # 34*a(n-1)
   c-  # 34*a(n-1)-a(n-2)
     » # 34*a(n-1)-a(n-2)+2

Alternative Lösung:

-35*d+T

Verwendet stattdessen a(n) = 35*(a(n-1)-a(n-2)) + a(n-3)

Zwei
quelle
Die Frage lautet For n=1 return 0, aber dies gibt 1 zurück. Dies kann durch Hinzufügen der Option -O behoben werden .
Grimmy
4

JavaScript (ES6), 29-4 = 25 Bytes

n=>n>1?34*f(n-1)-f(n-2)+2:n|0

5 Bytes dank @IsmaelMiguel gespart !

Ich musste die 0, 1 und die Negative fest codieren, um eine unendliche Rekursion zu vermeiden.

Konsole, ich habe die Funktion benannt , f:

f(1);  // 0
f(13); // 73804512832419600
f(30); // 7.885505171090779e+42 or 7885505171090779000000000000000000000000000

BEARBEITEN : Es stellt sich heraus, dass JavaScript die Zahlen auf 16 (15) Stellen (Spezifikation) rundet, da diese Zahlen zu groß sind und einen Überlauf verursachen. Fügen Sie 714341252076979033 in Ihre JavaScript-Konsole ein und überzeugen Sie sich selbst. Es ist eher eine Einschränkung von JavaScript

Downgoat
quelle
Ich denke nicht, dass dies für den Bonus qualifiziert ist. f(15)sollte zurückkehren 85170343853180456676, nicht 85170343853180450000.
Dennis
@ Tennis JavaScript muss es abschneiden. .-. Ja, JavaScript rundet auf 16 Stellen, wenn
Downgoat
Versuchen Sie dieses: n=>n?n<2?0:34*f(n-1)-f(n-2)+2:1(31 Bytes). Ich habe bis zur 5. Nummer getestet.
Ismael Miguel
1
Hier haben Sie jetzt eine 29 Bytes lange Lösung : n=>n>1?34*f(n-1)-f(n-2)+2:!!n. Es kehrt falseweiter 0, trueweiter 1und 36weiter 2. Wenn Sie es wollen , eine Reihe zurückkehren, können Sie ersetzen !!nmit +!!n.
Ismael Miguel
1
Das Problem wurde behoben. Verwenden Sie dies: n=>n>1?34*f(n-1)-f(n-2)+2:n|0(gleiche Byteanzahl, gibt jetzt immer Zahlen zurück)
Ismael Miguel
3

Excel VBA - 90 Bytes

Verwenden der Wiederholungsrelation von der Wikipedia-Seite:

n = InputBox("n")
x = 0
y = 1
For i = 1 To n
Cells(i, 1) = x
r = 34 * y - x + 2
x = y
y = r
Next i

Wenn Sie ausgeführt werden, werden Sie zur Eingabe von n aufgefordert, und die Sequenz bis einschließlich n wird in Spalte A ausgegeben:

Ausgabe

Es kann bis einschließlich n = 202 ausgeführt werden, bevor ein Überlauffehler auftritt.

Wightboy
quelle
2

[Nicht konkurrierend] Pyth (14 - 4 - 4 = 6 Bytes)

K1u/^tG2~KGQ36

Verwendet die erste Wiederholung von OEIS , dass nach 0,1,36 A n = (A n-1 -1) 2 / A n-2 gefunden werden kann . A Nicht konkurrierend, da diese Lösung bei 36 beginnt. Wenn Sie nach unten gehen, dividieren Sie durch Null (die Eingabe von 0 ergibt also 36). Musste auch 36 fest codieren.

Probieren Sie es hier aus

cmxu
quelle
2

Java, 53 - 4 = 49 Bytes

Es ist eine weitere einfache Rekursion, aber ich kann Java nicht oft mit einer Punktzahl von <50 posten, also ...

long g(int n){return n<2?n<1?1:0:34*g(n-1)-g(n-2)+2;}

Für etwas Nicht- Rekursives wird es jetzt ziemlich viel länger. Dieser ist sowohl länger (112-4 = 108) als auch langsamer, daher bin ich mir nicht sicher, warum ich ihn poste, außer um etwas Iteratives zu haben:

long f(int n){long a=0,b,c,d=0;for(;a<1l<<32&n>0;)if((c=(int)Math.sqrt(b=(a*a+a++)/2))*c==b){d=b;n--;}return d;}
Geobits
quelle
2

Julia, 51 Bytes - 4 - 4 = 43

f(n)=(a=b=big(1);b-=1;for i=1:n a,b=b,34b-a+2end;a)

Hierbei wird die erste auf der Wikipedia-Seite aufgeführte Wiederholungsrelation für quadratische Dreieckszahlen verwendet. Es berechnet n = 1000 in 0,006 Sekunden und n = 100000 in 6,93 Sekunden. Es ist ein paar Bytes länger als eine rekursive Lösung, aber es ist viel schneller.

Ungolfed + Erklärung:

function f(n)
    # Set a and b to be big integers
    a = big(1)
    b = big(0)

    # Iterate n times
    for i = 1:n
        # Use the recurrence relation, Luke
        a, b = b, 34*b - a + 2
    end

    # Return a
    a
end

Beispiele:

julia> for i = 1:4 println(f(i)) end
0
1
36
1225

julia> @time for i = 1:1000 println(f(i)) end
0
... (further printing omitted here)
elapsed time: 1.137734341 seconds (403573226 bytes allocated, 38.75% gc time)
Alex A.
quelle
2

PHP, 65 59 56-4 = 52 Bytes

while($argv[1]--)while((0|$r=sqrt($s+=$f++))-$r);echo$s;

Wiederholen, bis die Quadratwurzel von $s∈ℤ ist: Addiere $fzur Summe $s, inkrementiere $f;
Wiederholungszeiten $argv[1].
Ausgangssumme.

Titus
quelle
1

Prolog, 70 74 - 4 - 4 = 66

n(X,R):-n(X,0,1,R).
n(X,A,B,R):-X=0,R=A;Z is X-1,E is 34*B-A+2,n(Z,B,E,R).

Laufende n(100,R)Ausgaben:

X = 40283218019606612026870715051828504163181534465162581625898684828251284020309760525686544840519804069618265491900426463694050293008018241080068813316496

Die Ausführung n(10000,X)auf meinem Computer dauert ca. 1 Sekunde .

Bearbeiten : Die 66-Version ist schwanzrekursiv. Die vorherige nicht rekursive Version ist die folgende:

n(X,[Z|R]):-X>1,Y is X-1,n(Y,R),R=[A,B|_],Z is 34*A-B+2;X=1,Z=1,R=[0];Z=0.

Sie haben die gleiche Länge in Bytes, aber das nicht-rekursive Regenerieren erzeugt Stapelüberläufe ab einem bestimmten Punkt (auf meinem Computer um 20500).

Fatalisieren
quelle
1

Javascript ES6, 77 75 71 Zeichen

// 71 chars
f=n=>{for(q=t=w=0;n;++q)for(s=q*q;t<=s;t+=++w)s==t&&--n&console.log(s)}

// No multiplication, 75 chars
f=n=>{for(s=t=w=0,q=-1;n;s+=q+=2)for(;t<=s;t+=++w)s==t&&--n&console.log(s)}

// Old, 77 chars
f=n=>{for(s=t=w=0,q=-1;n;s+=q+=2){for(;t<s;t+=++w);s==t&&--n&console.log(s)}}
  • Die Lösung ist linear.
  • Die Lösung kann aufgrund des Zahlentyps alle Zahlen kleiner als 2 ^ 53 ausgeben.
  • Der Algorithmus selbst kann für unbegrenzte Zahlen verwendet werden.

Prüfung:

f(11)

0
1
36
1225
41616
1413721
48024900
1631432881
55420693056
1882672131025
63955431761796
Qwertiy
quelle
1

C 68 Bytes

Dies war eine lustige Herausforderung mit C.

main(o,k){o==1?k=0:0;k<9e9&&k>=0&&main(34*o-k+2,o,printf("%d,",k));}

Sehen Sie, wie es hier läuft: https://ideone.com/0ulGmM

Albert Renshaw
quelle
1

Gelee , 13 - 8 = 5 Bytes

Dies gilt für beide Boni.

×8‘,µÆ²Ạ
0Ç#Ṫ

Probieren Sie es online aus!

Geschehen neben Caird Coinheringaahing im Chat .

Erläuterung

× 8 ', µÆ²Ạ ~ Hilfsverbindung.

× 8 ~ 8 mal die Zahl.
  '~ Inkrement.
   , ~ Gepaart mit der aktuellen Nummer.
    µ ~ Startet eine neue monadische (1-arg) Verbindung.
     Ʋ ~ Vektorisiert "Ist Quadrat?".
       All ~ Alle. Geben Sie 1 nur zurück, wenn beide wahr sind.



0Ç # Ṫ ~ Hauptlink.

0 # ~ Sammeln Sie ab 0 die ersten N ganzen Zahlen mit wahrheitsgemäßen Ergebnissen, wenn sie angewendet werden:
 Ç ~ Das letzte Glied als Monade.
   Ṫ ~ Letztes Element. Ausgabe implizit.
Mr. Xcoder
quelle
0

APL (NARS), 67 Zeichen, 134 Bytes

r←f w;c;i;m
c←0⋄i←¯1⋄r←⍬
→2×⍳0≠1∣√1+8×m←i×i+←1⋄r←r,m⋄→2×⍳w>c+←1

Prüfung:

  f 10
0 1 36 1225 41616 1413721 48024900 1631432881 55420693056 1882672131025 

f würde in quadratischer Reihenfolge die Elemente suchen, die auch eine dreieckige Zahl sind, daher müssen sie der dreieckigen Prüfformel in APLs folgen: 0 = 1∣√1 + 8 × m mit der zu prüfenden Zahl m.

RosLuP
quelle