Wyzwanie

Liczba plastyczna jest liczbą związaną ze złotym współczynnikiem, o wielu interesujących właściwościach matematycznych. W związku z tym istnieje wiele metod obliczania liczby.

Aby precyzyjnie określić liczbę do celów tego wyzwania, użyjemy następującej definicji (chociaż istnieje wiele równoważnych definicji i możesz użyć dowolnej definicji, o ile dotyczy tej samej liczby):

Liczba plastyczna jest liczbą rzeczywistą ρ taką, że ρ ³ = ρ +1.

Wyzwanie polega na napisaniu programu lub funkcji, która przyjmuje na wejściu liczbę całkowitą x (przy x > 1) i daje przybliżenie do ρ jako wyjścia, tak że im większa jest wartość x , tym bardziej zbliża się do ρ ( z co najwyżej skończonymi wyjątkami; pozostawanie na tej samej wartości liczy się jako „bliżej” w tym celu), a dla dowolnej liczby dodatniej δ , twój program ma pewną wartość x , która daje wynik w granicach δ od ρ .

Wyjaśnienia

• Jeśli wyprowadzasz dane za pomocą metody, która z natury wysyła ciągi znaków (np. Standardowy strumień wyjściowy), możesz sformatować dane wyjściowe albo w systemie dziesiętnym (np. 1.3247179572), Albo jako stosunek dwóch liczb całkowitych ze /znakiem między nimi.
• Jeśli wypisujesz jako wartość w swoim języku programowania (np. Wracasz z funkcji), musi ona być typu stałego, zmiennoprzecinkowego lub wymiernego. (W szczególności nie można używać typów danych, które przechowują liczby symbolicznie, chyba że są one używane tylko do zachowania stosunku dwóch liczb całkowitych. Więc jeśli używasz Mathematica lub podobnego języka, musisz dołączyć dodatkowe kod, który faktycznie generuje cyfry wyniku).
• Twoja odpowiedź musi działać w hipotetycznym wariancie języka, w którym liczby całkowite mogą być dowolnie duże, a pamięć (w tym stos) jest nieograniczona. Być może nie przyjąć, że zmiennoprzecinkową arytmetyczne w języku polskim jest arbitralnie dokładna, ale musi zamiast używać jej rzeczywistej dokładności (czyli wyprowadzanie liczbę zmiennoprzecinkową tylko będzie to możliwe w językach gdzie dokładność liczb zmiennoprzecinkowych może być kontrolowane w czasie wykonywania).
• x może mieć dowolne znaczenie (o ile jego zwiększenie daje bardziej dokładne wyniki). Wyobrażam sobie, że większość zgłoszeń sprawi, że będzie kontrolować liczbę cyfr danych wyjściowych do wyprodukowania lub liczbę iteracji algorytmu używanego przez twój program do zbieżności na plastikowej liczbie, ale inne znaczenia są dopuszczalne.

Testcase

Oto kilka pierwszych cyfr plastikowego numeru:

1.32471795724474602596090885

Więcej cyfr jest dostępnych w OEIS .

Warunek zwycięstwa

Jak zwykle dla golfa kodowanego , krótszy jest lepszy, mierzony w bajtach. Możesz jednak zamieszczać odpowiedzi, nawet jeśli nie wygrywają, o ile dodadzą coś (np. Inny język lub inny algorytm) do istniejących odpowiedzi.

Python 2 , 49 bajtów

n=x=input()
while n**3/x/x<n+x:n+=1
print n,'/',x

Wypróbuj online!

Chodzi o to, aby wyrazić ρw ρ³=ρ+1postaci frakcji n/x, których mianownik xjest parametrem dokładności wejściowego. Przyjmujemy (n/x)³=n/x+1i usuwamy mianowniki, aby je zdobyć n³=x²(x+n).

Ponieważ LHS rośnie nszybciej niż RHS, możemy przybliżać punkt równości njako najmniejszy n³≥x²(x+n). Kod liczy się, ndopóki tak się nie stanie, zaczynając od tego, xktóry jest mniejszy.

Mały zapis bajtów polega na podzieleniu obu stron przez x²zapis n³/x²≥x+n(zanegowany w whilestanie). Jest to podział podłogi w kodzie, ale utracona część ułamkowa jest znikoma.

Zamiast tego zamiast xlicznika jest umieszczana alternatywa o tej samej długości :

Python 2 , 49 bajtów

n=x=input()
while x**3/n/n<n+x:n-=1
print x,'/',n

Wypróbuj online!

Mathematica, 20 bajtów

#^3-#-1&~Root~1~N~#&

Wbudowana Rootfunkcja Mathematica daje rozwiązania równania wielomianowego f[x] == 0.

Wyjaśnienie

#^3-#-1&~Root~1~N~#&
                   &  (* Function *)
#^3-#-1&              (* A pure-function polynomial, x^3-x-1 *)
        ~Root~1       (* Find the first root *)
               ~N~#   (* approximate to (input) digits *)

Próbki we / wy

In[1]:= f=#^3-#-1&~Root~1~N~#&;
        f[1]

Out[1]= 1.

In[2]:= f[9]

Out[2]= 1.32471796

In[3]:= f[100]

Out[3]= 1.324717957244746025960908854478097340734404056901733364534015050302827851245547594054699347981787280

Mathematica, 27 bajtów

x/.Solve[x^3==x+1>2,x]~N~#&

-1 bajt z Martin
-2 bajty z ovs

wkład

[27]

wydajność

{1.32471795724474602596090885}

sed , 67 60 (59 + 1) bajtów

s,^,1/1/1 ,
:;s,(1*/(1*)/(1*).*)1$,\2\3/\1,
t
s,(/1*).*,\1,

Wypróbuj online!

+1 za -Eflagę (ERE zamiast BRE). Zarówno wejście, jak i wyjście są jednoargumentowe: wejście 11111 dla x = 5, np. Wyjście jest ułamkiem dwóch liczb jednoargumentowych: wyżej wspomniane wejście 11111 daje wyjście 11111/1111 (5/4 dziesiętnie).

Przybliża liczbę plastyczną jako ułamek między kolejnymi elementami sekwencji Padovana .

Mathematica, 27 bajtów

Nest[(1+#)^(1/3)&,1,#]~N~#&

Wykorzystuje skrócone przybliżenie zagnieżdżonej formy sześciennej rodnika √√ (1 + √√ (1 + √√ (1 + ...))) . Chociaż dane wyjściowe zawsze będą miały x-1 miejsc dziesiętnych, wynik jest w rzeczywistości mniej dokładny niż to, ponieważ wyrażenie zbiega się wolniej niż jedna cyfra na iterację ( x jest również używany jako liczba obliczonych rodników zagnieżdżonych). Na przykład x = 100 daje

_________________________________________________________________________
1.324717957244746025960908854478097340734404056901733364534015050302827850993693624204577670741656151

gdzie podkreślona część jest poprawna.

Oktawa , 50 bajtów

@(n)char(digits(n)*0+vpasolve(sym('r^3-r-1'))(1));

Wypróbuj online!

Definiuje anonimową funkcję z nżądaną liczbą cyfr wyjścia.

Ta odpowiedź nadużywa, która digitszwraca bieżące ustawienie liczby cyfr w arytmetyki o zmiennej precyzji. Oznacza to, że możemy go używać w funkcji anonimowej bez błędów dotyczących „Zbyt wielu argumentów wyjściowych”.

Poza tym jest to naprawdę proste: vpasolvejest skrótem od Variable-Precision Arithmetic Solve, z precyzją ustawioną przez ostatnie wywołanie digits. Ponieważ vpajest to symboliczny typ danych w Octave, który jest zbanowany zgodnie ze specyfikacją, po prostu zawijamy całą funkcję, char(...)aby uzyskać ciąg znaków. Zauważ, że w solvei vpasolve, f==0implikowane, więc r^3==r+1zostało zastąpione przezr^3-r-1 (==0)

MATL ( 27 28 bajtów)

7BG:"t@)y@Q)+h]tG3+)yG2+)/

Moje pierwsze rozwiązanie (27 bajtów)

Wypróbuj online!

To z pewnością nie jest optymalne, wciąż przyzwyczajam się do MATL.

Wyjaśnienie:

Tworzę sekwencję Padovana do wejścia + 3, a następnie znajduję stosunek dwóch ostatnich liczb.

7B     % Turn 7 into binary to give 1 1 1 
G:"    % For k=1:input do...
t@)    % Existing sequence member k
y@1+)  % Existing sequence member k+1
+h     % Add them together and concatenate to the sequence array
]      % End loop
tG3+)  % Final sequence member
yG2+)  % Second last sequence member
/      % Divide to approximate ρ

Prawidłowe wyjście ułamkowe (35 bajtów) (28 bajtów, @ Kanały):

Jednak pierwsze rozwiązanie nie spełnia wymogu dowolnej precyzji, która jest zmiennoprzecinkową granicą domyślnych ustawień MATL. Więc zamiast dodając kilka bajtów do rozszerzenia tej precyzji, to prostsze do podjęcia właściwej trasy frakcji i zapisać ułamek ostatnich dwóch liczb całkowitych w (n-1) ^th i N ^th elementów ściętego Padovan sekwencji.

np. „114/86”

7BG: „t @) y @ 1 +) + h] tG3 +) V '/' YcyG2 +) VYc

7BG:"t@tQh)sh]tJ)V47hyJq)Vh&

Dzięki uprzejmości użytkownika @Sanchises. :)

Wypróbuj online!

Ocena bez iteracji:

W szczególności mój najkrótszy kod dla „dokładnej” wersji to (23 bajty):

1-1h69X^12**108+1I/^6/s

Wypróbuj online!

... ale nie daje arbitralnej precyzji. Zastanawiam się, czy ktoś może to dostosować, aby spełnić reguły (użyj danych wejściowych itp.) I nadal dodać mniej niż 5 bajtów? : P

M , 15 14 bajtów

²×3’
*3Ḥ‘÷Ç
Ç¡

Wypróbuj online!

Algorytm

Używa to racjonalności i metody Newtona. W szczególności dla wejścia x stosowane są pierwsze x iteracje o wartości początkowej x .

Próbujemy znaleźć określony pierwiastek wielomianu p (t) = t³ - t - 1 . Metoda Newtona osiąga to poprzez przyjęcie wartości początkowej t ₀ - wystarczająco zbliżonej do ρ - i rekurencyjne zdefiniowanie sekwencji przez
t _{n + 1} = t _n - p (t _n ) / p '(t _n ) .

Ponieważ p '(t) = 3t² -1 , otrzymujemy
t _{n + 1} = t _n - (t _n ³ - t _n - 1) / (3t _n ² - 1) = (3t _n ³ - t _n - t _n ³ + t _n + 1) / (3t _n ² - 1) = (2t _n ³ + 1) / (3t _n ² - 1) .

Zauważ, że początkowe przybliżenie x pogarsza się wraz ze wzrostem x . Chociaż wynik dla x = 3 jest nieco mniej dokładny niż wynik dla x = 2 , ponieważ metoda Newtona zbiega się kwadratowo w ρ , nie powinno to stanowić problemu w przypadku dużych wartości x .

Jak to działa

Ç¡    Main link. Argument: x

Ç¡    Call the second helper link x times, which initial argument x.


*3Ḥ‘÷Ç  Second helper link. Argument: t

*3      Compute t³.
  Ḥ     Unhalve; yield 2t³.
   ‘    Increment; yield 2t³+1.
     Ç  Call the first helper link with argument t.
    ÷   Divide the left result by the right one.


²×3’    First helper link. Argument: t

²       Compute t².
 ×3     Compute 3t².
   ’    Decrement; yield 3t²-1.

Julia 0,5 ,  44  40 bajtów

|(x,r=1)=x<1?r:~-x|big(2r^3+1)//(3r^2-1)

Korzysta z racjonalności i metody Newtona.

Wypróbuj online!

05AB1E , 23 bajty

U[X3m¹/¹/¹X+›#X>U]X'/¹J

Wypróbuj online!

Bezpośredni port /codegolf//a/126822/59376 przez xnor.

Węgiel drzewny , 28 bajtów

ＡＩθθＡθνＷ‹∕∕Ｘν³θθ⁺νθＡ⁺ν¹νＩ∕νθ

Wypróbuj online! Link do trybu pełnego. Też najwyraźniej popsułem Dividei IntDivide: |
Używa tej samej metody co odpowiedzi w języku Python i JavaScript.

NewStack , 14 bajtów

¹Fᵢ{E2x³⁺÷3x²⁻

Awaria:

¹                Add arbitrary number 1 to the stack.
 Fᵢ{             Define for loop with a user's input amount of itterations.
    E            Define new edit for element 0 (element 0 being the 1 added. earlier).
     2x³⁺÷3x²⁻   update x to equal (2x^3+1)/(3x^2-1). (x = element 0).

Jak to działa:

Wzór (2x ³ +1) / (3x ² -1) pochodzi z uproszczenia metody Newtona dla równania x ³ = x + 1. Możesz go znaleźć tutaj . Powtarzanie tego procesu nieskończoną liczbę razy zbiega się z liczbą plastyczną. Jego tempo konwergencji jest dość szybkie i wynosi około 2,6 miejsca po przecinku na iterację.

INPUT ITERATION >> VALUE
0 >> 1
1 >> 1.5
2 >> 1.3478260869565217
3 >> 1.325200398950907
4 >> 1.3247181739990537
5 >> 1.3247179572447898
6 >> 1.324717957244746    <- 16 decimal precision in 6 iterations!
...
100 >> 1.324717957244746

Alternatywa sekwencji Padovan, 27 25 17 bajtów

¹Fᵢ{[ƨ2+ƨ3]ℲƤƨ/ƨ2

Awaria:

¹                  Append first element of Padovan sequence.
 Fᵢ{       Ⅎ       Define for loop of user's input amount of iterations.
    [ƨ2+ƨ3]        Append sum second and third to last elements.
            Ƥƨ/ƨ2  Print ratio of last two elements.

-2 bajty, wybierając lepszą strategię drukowania

-8 bajtów, wybierając lepszy sposób indeksowania stosu

Jak to działa:

W miarę kontynuowania sekwencji Padovana stosunek dwóch ostatnich elementów zbiega się z liczbą plastyczną.

INPUT ITERATION >> VALUE
0 >> 1
1 >> 2
...
10 >> 1.3157894736842106
...
89 >> 1.324717957244746    <- 16 decimal precision in 89 iterations
...
100> > 1.324717957244746

Clojure, 46 bajtów

#(nth(iterate(fn[i](Math/pow(inc i)(/ 3)))1)%)

Używa iterowanej formuły root-cube. Jest to nieco bardziej interesujące, ale dłuższe:

(def f #(apply comp(repeat %(fn[i](Math/pow(inc i)(/ 3))))))

((f 10)1)
1.3247179361449652

JavaScript, 36 bajtów

f=(x,n=x)=>n**3/x/x<n+x?f(x,++n):n/x

Działa tak samo jak odpowiedź na górny python. Nie console.logzostało uwzględnione, ponieważ jeśli uruchomisz f(x)konsolę, zostanie automatycznie zalogowane.

f=(x,n=x)=>n**3/x/x<n+x?f(x,++n):n/x
console.log(f(300))

> <> , 38 + 3 = 41 bajtów

11\n;
?!\}2,:01{::::}**-+0(?$-{+{1-:}

Oczekuje, że dane wejściowe będą obecne na stosie podczas uruchamiania programu, więc +3 bajty dla -vflagi.

Wypróbuj online!

Skutecznie wykonuje wyszukiwanie binarne w celu zawężenia wartości wyjściowej. Zwiększenie xzwiększa liczbę iteracji do wykonania.

Edycja: lekko zmieniono obliczenia, aby zaoszczędzić 1 bajt, poprzednia wersja:

11\n;
?!\}2,:0{::::}**$-1-0)?$-{+{1-:}

k, 27 bajtów

{"/"/$1_|x({y,z,x+y}.)/3#1}

Wypróbuj online! Zakłada to nieskończone liczby całkowite (co niestety nie jest prawdziwe). Wykorzystuje sekwencję Padovana .

TI-BASIC, 21 bajtów

:Prompt X //Prompt for input, 3 bytes
:While X  //While X, 3 bytes
:³√(1+Y→Y //Calculate cube root of 1+Y and store to Y, 7 bytes
:DS<(X,0  //Decrement X and skip next command (which doesn't do anything), 5 bytes
:End      //End While loop, 2 bytes
:Y        //Display Y, 1 byte

Wykorzystuje tę rekurencyjną formułę .

Co ciekawe, zakodowanie na stałe liczby i zaokrąglenie daje tę samą liczbę bajtów:

TI-BASIC, 21 bajtów

:Prompt X    //Prompt for input, 3 bytes
:.5√(3       //Store √(3)/2 to Ans, 5 bytes
:Ansֿ¹cosh(3ֿ¹coshֿ¹(3Ans //Store the plastic number to Ans, 9 bytes
:round(Ans,X //Round the plastic number X decimal digits, 4 bytes

Wykorzystuje ten wzór trygonometryczny .

C # , 317 bajtów

using m=System.Math;a=x=>{if(a==0)return "1/1";var d=a(x-1).Split('/');var b=int.Parse(d[0]);var c=int.Parse(d[1]);return string.Format("{0}/{1}",(2*m.Pow(b,3)+m.Pow(c,3)).ToString(new string('#',int.MaxValue.ToString().Length)),(3*m.Pow(b,2)*c-m.Pow(c,3)).ToString(new string('#',int.MaxValue.ToString().Length)));};

Zwraca wynik jako ułamek.

Wyjaśnienie

Wykorzystuje metodę Newtona z iteracjami x do znalezienia pierwiastka wielomianu p ^ 3-p-1 = 0. Formuła to x_n = 1- (f (x_ (n-1))) / (f '(x_ (n-1))), a x_0 jest punktem początkowym.

Pochodna wielomianów wynosi 3p ^ 2-1 i powiedzmy x_ (n-1) = b / c. Następnie, stosując powyższy wzór, otrzymujemy, że x_n = (2 b ^ 3 + c ^ 3) / (3 b ^ 2 cc ^ 3). Powiedzmy też, że zaczynamy od 1, tak się stanie, gdy x = 2, ponieważ x> 1, i jest liczbą całkowitą. Zidentyfikowany i skomentowany kod:

using System;
string PlasticNumber(int x)
{
    if (x == 2) 
        return "1/1";                 

//If x=2, we return our starting value, but we need to return it as a fraction

    var d = PlasticNumber(x - 1).Split('/');
    var b = System.Convert.ToInt32(d[0]);
    var c = int.Parse(d[1]);

//We parse the previous value of the fraction, and put it into two variables

    return string.Format("{0}/{1}", 
        (2 * Math.Pow(b, 3) + Math.Pow(c, 3))
        .ToString(new string('#', int.MaxValue.ToString().Length)),
        (3 * Math.Pow(b, 2) * c - Math.Pow(c, 3))
        .ToString(new string('#', int.MaxValue.ToString().Length)));

//We return the result as a fraction, but it's important not to return it in
  scientific notation, because that will cause issues in the parsing process 

}

PHP, 86 bajtów

for($p=[1,1,1];$i++<$argn;)$p[]=bcadd($p[$i],$p[$i-1]);echo bcdiv($p[$i+1],$p[$i],$i);

PHP Sandbox Online

Tworzy spiralę Padovan i wypisuje stosunek dwóch ostatnich liczb.

Aksjomat, 96 bajtów

h(n:NNI):Float==(n>1.E5=>-1;n:=n+1;j:=digits(n::PI);r:=solve(x^3-x=1,10.^-n);digits(j);rhs(r.1))

wyniki

(31) -> [h(i) for i in 0..10]
   (31)
   [1.0, 1.3, 1.33, 1.325, 1.3247, 1.32472, 1.324718, 1.324718, 1.32471796,
    1.324717957, 1.3247179572]
                                                         Type: List Float

jak widać h (2) powinien wynosić 1,32, a nie 1,33, więc w ostatnich cyfrach jest błąd

Byłby to jeden ze 110 bajtów

g(n:NNI):Float==(n>1.E5=>-1;n:=n+1;j:=digits(n::PI);x:=sqrt(23./108);r:=(.5+x)^(1/3)+(.5-x)^(1/3);digits(j);r)

Wykorzystuje wzór na równanie rozwiązywania klasy III typu x ^ 3-3 * p * x-2 * q = 0 w przypadku q ^ 2-p ^ 3> = 0, czyli m = sqrt (q ^ 2- p ^ 3) i x = (q + m) ^ (1/3) + (qm) ^ (1/3)

W naszym przypadku r ^ 3-r-1 = 0 można to zapisać jako r ^ 3-3 * (1/3) r-2 * (1/2) = 0, więc p = 1/3 q = 1/2 m = 1 / 4-1 / 27 = 23/108 x = (0,5 + m) ^ (1/3) + (0,5-m) ^ (1/3)

ten, który używa iteracji Newtona z punktem początkowym r = 1

f(n:NNI):Float==(n>1.E5=>-1;n:=n+1;j:=digits(n::PI);e:=10^-n;r:=1.;repeat(v:=(r^3-r-1)/(3*r^2-1);abs(v)<e=>break;r:=r-v);digits(j);r)

zmienia się w funkcji, wartość cyfr dla uzyskania jednego obj n + 1 cyfr po punkcie zmiennoprzecinkowym. Na koniec wartość cyfry () jest ponownie przypisywana do wartości dokładności.

Rubinowy , 35 bajtów

->x{n=1;n+=0.1**x while n**3-n<1;n}

Wypróbuj online!