Liczby kwadratowe to te, które przyjmują postać, n^2gdzie n jest liczbą całkowitą. Są one również nazywane idealnymi kwadratami, ponieważ gdy weźmiesz ich pierwiastek kwadratowy, otrzymasz liczbę całkowitą.

Pierwsze 10 liczb kwadratowych to: ( OEIS )

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

Liczby trójkątne to liczby, które mogą tworzyć trójkąt równoboczny. N-ty numer trójkąta jest równy sumie wszystkich liczb naturalnych od 1 do n.

Pierwsze 10 liczb trójkątnych to: ( OEIS )

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

Kwadratowe liczby trójkątne to liczby zarówno kwadratowe, jak i trójkątne.

Pierwsze 10 kwadratowych liczb trójkątnych to: ( OEIS )

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

Istnieje nieskończona liczba liczb kwadratowych, liczb trójkątnych i kwadratowych liczb trójkątnych.

Napisz program lub nazwaną funkcję, która podała liczbę wejściową (parametr lub standard) n, oblicza nkwadratową liczbę trójkątną i wysyła / zwraca ją, gdzie n jest dodatnią liczbą niezerową. (Dla n = 1 zwraca 0)

Aby program / funkcja była poprawnym przesłaniem, powinna mieć możliwość zwrócenia co najmniej wszystkich liczb kwadratowych trójkątów mniejszych niż 2 ^ 31-1.

Premia

-4 bajty za możliwość wypisania wszystkich kwadratowych liczb trójkątnych mniejszych niż 2 ^ 63-1

-4 bajty umożliwiające teoretyczne wyprowadzenie kwadratowych liczb trójkątnych o dowolnym rozmiarze.

+8 bajtów kary za rozwiązania wymagające czasu niepolarnego.

Stos bonusów.

To wyzwanie dla golfa, więc wygrywa odpowiedź z najmniejszą liczbą bajtów.

CJam, 12 8 bajtów

XUri{_34*@-Y+}*;

Wykorzystuje relację powtarzalności z artykułu z Wikipedii.

Kod ma długość 16 bajtów i kwalifikuje się do obu bonusów.

Wypróbuj online w interpretatorze CJam .

Jak to działa

Mój kod okazał się być identyczny jak xnor w każdym aspekcie, z wyjątkiem tego, że używam stosu CJam zamiast zmiennych.

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.

Python 2, 45-4-4 = 37

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

Iteruje przy użyciu reccurence

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

Teoretycznie obsługuje to liczby dowolnej wielkości, ale działa w czasie wykładniczym, więc nie powinno kwalifikować się do bonusów. Powinien działać dla liczb o dowolnym rozmiarze. Na przykład dla 100 daje

1185827220993342542557325920096705939276583904852110550753333094088280194260929920844987597980616456388639477930416411849864965254621398934978872054025

Rozwiązanie rekurencyjne wykorzystuje 41 znaków, ale nie powinno się kwalifikować, ponieważ zajmuje wykładniczy czas.

f=lambda k:k>2and 34*f(k-1)-f(k-2)+2or~-k

Pyth, 16 - 4 - 4 = 8 bajtów

Wykorzystuje rekurencyjną formułę z artykułu OEIS.

K1uhh-*34G~KGtQZ

Używa polecenia post-przypisania, które jest całkiem nowe i wydaje się naprawdę fajne. Używa skrócenia n-1czasu iteracji z powodu indeksowania 1.

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.

Wydaje się być wielomianem, ponieważ zapętla się n razy i wykonuje matematykę i przypisuje każdą iterację, ale nie jestem informatykiem. Kończy n = 10000 prawie natychmiast.

Wypróbuj tutaj online .

Oaza , 7 - 4 - 4 = -1 (nie konkuruje)

34*c-»T

Wypróbuj online!

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

Oasis obsługuje liczby całkowite o dowolnej precyzji, więc powinno być możliwe zwiększenie dowolnej liczby, o ile nie nastąpi przepełnienie stosu. Daj mi znać, jeśli nie liczy się to z powodu przepełnienia stosu. Możliwe jest również, że ten konkretny algorytm nie jest wielomianowy i daj mi znać, jeśli tak jest.

Niekonkurencyjny, ponieważ wyzwanie stanowi postdatowanie języka.

Wyjaśnienie:

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

Alternatywne rozwiązanie:

-35*d+T

Zamiast tego używa a(n) = 35*(a(n-1)-a(n-2)) + a(n-3)

JavaScript (ES6), 29-4 = 25 bajtów

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

Zaoszczędź 5 bajtów dzięki @IsmaelMiguel !

Musiałem zakodować 0, 1 i negatywy, aby uniknąć nieskończonej rekurencji.

Konsolę nazwałem funkcją f:

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

EDYCJA : okazuje się, że JavaScript zaokrągli liczby do 16 (15) cyfr (Spec), ponieważ te liczby są zbyt duże, co powoduje przepełnienie. Umieść 714341252076979033 W konsoli JavaScript i przekonaj się sam. To bardziej ograniczenie JavaScript

Excel VBA - 90 bajtów

Używając relacji rekurencji ze strony Wikipedii:

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

Po wykonaniu pojawi się monit o n, następnie sekwencja do n włącznie włącznie jest wyprowadzana do kolumny A:

Można go uruchomić do wartości n = 202 włącznie, zanim wystąpi błąd przepełnienia.

[Nie konkuruje] Pyth (14 - 4 - 4 = 6 bajtów)

K1u/^tG2~KGQ36

Użyłem pierwszego wznowienia z OEIS , że po 0,1,36 można znaleźć A _n = (A _n-1 -1) ² / A _n-2 . A Nie konkuruje, ponieważ to rozwiązanie zaczyna się od 36, jeśli zejdziesz niżej, dzielisz przez zero (więc wejście 0 daje 36). Musiałem także zakodować na stałe 36.

Wypróbuj tutaj

Java, 53–4 = 49 bajtów

To kolejna prosta rekurencja, ale często nie publikuję Java z wynikiem <50, więc ...

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

Teraz coś dla -recursive, robi się trochę dłużej. Ten jest zarówno dłuższy (112-4 = 108) - i wolniejszy, więc nie jestem pewien, dlaczego go publikuję, z wyjątkiem tego, że mam coś iteracyjnego:

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;}

Julia, 51 bajtów - 4 - 4 = 43

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

Wykorzystuje pierwszą relację powtarzalności wymienioną na stronie Wikipedii dla kwadratowych liczb trójkątnych. Oblicza n = 1000 w 0,006 sekundy, a n = 100000 w 6,93 sekundy. Jest o kilka bajtów dłuższy niż rozwiązanie rekurencyjne, ale jest o wiele szybszy.

Niegolfowane + wyjaśnienie:

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

Przykłady:

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)

PHP, 65 59 56-4 = 52 bajty

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

powtarzaj, aż pierwiastek kwadratowy z $s∈ℤ: dodaj $fdo sumy $s, zwiększaj $f;
powtarzać $argv[1]czasy.
suma wyjściowa.

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

n(100,R)Wyjścia bieżące :

X = 40283218019606612026870715051828504163181534465162581625898684828251284020309760525686544840519804069618265491900426463694050293008018241080068813316496

Uruchomienie zajmuje około 1 sekundy n(10000,X) na moim komputerze .

Edycja : Wersja 66 jest rekurencyjna. Poprzednia nie rekurencyjna wersja jest następująca:

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.

Mają tę samą długość w bajtach, ale nie rekurencyjny generuje przepełnienie stosu powyżej pewnego punktu (na moim komputerze około 20500).

JavaScript ES6, 77 75 71 znaków

// 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)}}

• Rozwiązanie jest liniowe.
• Rozwiązanie może wypisać wszystkie liczby mniejsze niż 2 ^ 53 ze względu na typ liczb.
• Sam algorytm może być wykorzystywany do nieograniczonej liczby liczb.

Test:

f(11)

0
1
36
1225
41616
1413721
48024900
1631432881
55420693056
1882672131025
63955431761796

C, 68 bajtów

To było zabawne wyzwanie z C.

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

Zobacz, jak działa tutaj: https://ideone.com/0ulGmM

Galareta , 13 - 8 = 5 bajtów

To kwalifikuje się do obu bonusów.

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

Wypróbuj online!

Sporządzono obok Cairna coinheringaahing na czacie .

Wyjaśnienie

× 8 ', µÆ²Ạ ~ Link pomocnika.

× 8 ~ 8 razy liczba.
  „~ Przyrost.
   , ~ W połączeniu z bieżącym numerem.
    µ ~ Uruchamia nowe łącze monadyczne (1-arg).
     Ʋ ~ Vectorized „Is Square?”.
       All ~ Wszystko. Zwróć 1 tylko wtedy, gdy oba są zgodne z prawdą.



0Ç # Ṫ ~ Główny link.

0 # ~ Począwszy od 0, zbierz pierwsze N ​​liczb całkowitych z prawdziwymi wynikami, po zastosowaniu:
 Ç ~ Ostatni link jako monada.
   Ṫ ~ Ostatni element. Wynik niejawnie.

Perl 6 , 25–8 = 17 bajtów

{(0,1,2-*+34* *…*)[$_]}

Wypróbuj online!

05AB1E , 10–8 = 2 bajty

1ÎGDŠ34*Ìα

Wypróbuj online!

APL (NARS), 67 znaków, 134 bajty

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

test:

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

f szukałby w kolejności kwadratowej również elementów, które są liczbą trójkątną, więc muszą przestrzegać wzoru trójkątnej kontroli w APL: 0 = 1∣√1 + 8 × m z liczbą m do sprawdzenia.