Tantangan

Angka plastik adalah angka yang terkait dengan rasio emas, dengan banyak sifat matematika yang menarik. Karena itu, ada banyak pendekatan yang dapat digunakan untuk menghitung angka.

Untuk menentukan secara tepat angka untuk tujuan tantangan ini, kami akan menggunakan definisi berikut (meskipun ada banyak definisi yang setara, dan Anda dapat menggunakan definisi apa pun yang Anda inginkan asalkan sampai ke nomor yang sama):

Angka plastik adalah bilangan real ρ sehingga ρ ³ = ρ +1.

Tantangan Anda adalah menulis sebuah program atau fungsi yang mengambil integer x sebagai input (dengan x > 1), dan menghasilkan perkiraan untuk ρ sebagai output, sehingga semakin besar nilai x didapat, semakin dekat output ke ρ ( dengan paling banyak pengecualian, bertahan pada nilai yang sama dengan "lebih dekat" untuk tujuan ini), dan untuk setiap angka positif δ , ada beberapa input x untuk program Anda yang menghasilkan output yang berada dalam δ dari ρ .

Klarifikasi

• Jika Anda mengeluarkan melalui metode yang secara inheren mengeluarkan string (misalnya aliran output standar), Anda dapat memformat output dalam bentuk desimal (misalnya 1.3247179572), atau sebagai rasio dua bilangan bulat dengan /karakter di antara mereka.
• Jika Anda menghasilkan sebagai nilai dalam bahasa pemrograman Anda (misalnya kembali dari suatu fungsi), itu harus dari titik tetap, titik mengambang, atau jenis rasional. (Secara khusus, Anda tidak dapat menggunakan tipe data yang menyimpan angka secara simbolis, kecuali jika mereka hanya digunakan untuk menahan rasio dua bilangan bulat. Jadi, jika Anda menggunakan Mathematica atau bahasa yang serupa, Anda harus menyertakan tambahan kode untuk benar-benar menghasilkan digit dari output.)
• Jawaban Anda harus bekerja dalam varian hipotetis dari bahasa Anda di mana bilangan bulat dapat secara sewenang-wenang besar, dan memori (termasuk tumpukan) tidak terbatas. Anda tidak boleh berasumsi bahwa aritmatika titik-mengambang dalam bahasa Anda akurat secara sewenang-wenang, tetapi sebaliknya harus menggunakan keakuratannya yang sebenarnya (artinya mengeluarkan nomor titik-mengambang hanya akan mungkin dilakukan dalam bahasa-bahasa di mana akurasi angka-angka titik-mengambang dapat dikontrol saat runtime).
• x dapat memiliki makna apa pun yang Anda inginkan (selama meningkatkannya memberikan hasil yang lebih akurat). Saya membayangkan bahwa sebagian besar pengiriman akan mengontrol jumlah digit output yang akan dihasilkan, atau jumlah iterasi dari algoritma yang digunakan oleh program Anda untuk berkumpul pada nomor plastik, tetapi makna lain dapat diterima.

Kasus cobaan

Berikut adalah beberapa digit pertama nomor plastik:

1.32471795724474602596090885

Lebih banyak digit tersedia di OEIS .

Kondisi kemenangan

Seperti biasa untuk kode-golf , lebih pendek lebih baik, diukur dalam byte. Namun, jangan ragu untuk mengirim jawaban meskipun mereka tidak menang, asalkan mereka menambahkan sesuatu (misalnya bahasa yang berbeda, atau algoritma yang berbeda) ke jawaban yang ada.

Python 2 , 49 byte

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

Cobalah online!

Idenya adalah untuk mengekspresikan ρdengan ρ³=ρ+1sebagai pecahan n/xyang penyebutnya xadalah parameter akurasi input. Kami mengambil (n/x)³=n/x+1dan menghapus penyebut untuk mendapatkan n³=x²(x+n).

Karena LHS meningkat nlebih cepat daripada RHS, kita dapat memperkirakan titik persamaan nsebagai yang terkecil n³≥x²(x+n). Kode ini dihitung nhingga hal ini terjadi, mulai dari xyang lebih kecil.

Hemat byte kecil adalah untuk membagi kedua sisi dengan x²menulis n³/x²≥x+n(dinegasikan dalam whilekondisi). Ini adalah pembagian lantai dalam kode, tetapi bagian pecahan yang hilang dapat diabaikan.

Alternatif dengan panjang yang sama digunakan xsebagai pembilang:

Python 2 , 49 byte

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

Cobalah online!

Mathematica, 20 byte

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

RootFungsi builtin Mathematica memberikan solusi untuk persamaan polinomial f[x] == 0.

Penjelasan

#^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 *)

Contoh I / O

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 byte

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

-1 byte dari Martin
-2 byte dari ovs

memasukkan

[27]

keluaran

{1.32471795724474602596090885}

sed , 67 60 (59 +1) byte

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

Cobalah online!

+1 untuk -Ebendera (ERE bukan BRE). Input dan output keduanya unary: input 11111 untuk x = 5 misalnya Output adalah sebagian kecil dari dua angka unary: input 11111 tersebut menghasilkan output 11111/1111 (5/4 dalam desimal).

Perkiraan angka plastik sebagai fraksi antara elemen berurutan dari urutan Padovan .

Mathematica, 27 byte

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

Menggunakan pendekatan terpotong dari bentuk radikal kubik bersarang ³√ (1 + ³√ (1 + ³√ (1 + ...)))) . Sementara output akan selalu memiliki tempat desimal x-1 , hasilnya sebenarnya kurang akurat dari itu, karena ekspresi menyatu lebih lambat dari satu digit per iterasi ( x juga digunakan sebagai jumlah radikal bersarang yang dihitung). Misalnya x = 100 memberi

_________________________________________________________________________
1.324717957244746025960908854478097340734404056901733364534015050302827850993693624204577670741656151

di mana bagian yang digarisbawahi benar.

Oktaf , 50 byte

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

Cobalah online!

Menentukan fungsi anonim, dengan njumlah digit output yang diinginkan.

Jawaban ini menyalahgunakan yang digitsmengembalikan pengaturan saat ini untuk jumlah digit dalam aritmatika presisi variabel. Ini berarti kita bisa menggunakannya dalam fungsi anonim tanpa kesalahan tentang 'Terlalu banyak argumen keluaran'.

Selain itu, ini sangat mudah: vpasolvekependekan dari Variable-Precision Arithmetic Solve, dengan ketepatan yang ditetapkan oleh panggilan terakhir digits. Karena vpamerupakan tipe data simbolik dalam Oktaf, yang dilarang per spec, kami hanya membungkus seluruh fungsi char(...)untuk mendapatkan output string. Perhatikan bahwa di solvedan vpasolve, f==0tersirat, jadi r^3==r+1telah diganti olehr^3-r-1 (==0)

MATL ( 27 28 byte)

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

Solusi pertama saya (27 byte)

Cobalah online!

Ini tentu tidak optimal, saya masih terbiasa dengan MATL.

Penjelasan:

Saya membuat urutan Padovan hingga memasukkan + 3 kemudian menemukan rasio dari dua angka terakhir.

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 ρ

Output fraksi yang tepat (35 byte) (28 byte, @Sanchises):

Namun, solusi pertama tidak memenuhi kebutuhan akan presisi yang berubah-ubah menjadi batas titik mengambang dari pengaturan MATL default. Jadi, daripada menambahkan beberapa byte untuk memperpanjang presisi ini, itu mudah untuk mengambil rute fraksi yang tepat dan menulis sebagian kecil dari akhir dua bilangan bulat dalam (N-1) ^th dan N ^th elemen dari urutan Padovan terpotong.

mis. "114/86"

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

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

Atas perkenan pengguna @Sanchises. :)

Cobalah online!

Evaluasi non-iteratif:

Khususnya, kode terpendek saya untuk versi 'tepat' adalah (23 byte):

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

Cobalah online!

... tetapi tidak memberikan presisi yang sewenang-wenang. Saya bertanya-tanya apakah ada yang bisa menyesuaikan ini untuk memenuhi aturan (gunakan input dll) dan masih menambahkan kurang dari 5 byte? : P

M , 15 14 byte

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

Cobalah online!

Algoritma

Ini menggunakan rasional dan metode Newton. Khususnya, untuk input x , iterasi x pertama dengan nilai awal x diterapkan.

Kami mencoba menemukan akar spesifik dari polinomial p (t) = t³ - t - 1 . Metode Newton mencapai ini dengan mengambil nilai awal t ₀ - cukup dekat dengan ρ - dan secara rekursif mendefinisikan urutan dengan
t _{n + 1} = t _n - p (t _n ) / p '(t _n ) .

Karena p '(t) = 3t² -1 , kita mendapatkan
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) .

Perhatikan bahwa perkiraan awal x semakin memburuk dengan meningkatnya x . Sementara output untuk x = 3 sedikit kurang tepat daripada output untuk x = 2 , karena metode Newton konvergen secara kuadrat ke ρ , ini seharusnya tidak menjadi masalah untuk nilai x yang besar .

Bagaimana itu bekerja

Ç¡    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 byte

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

Menggunakan rasional dan metode Newton.

Cobalah online!

05AB1E , 23 byte

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

Cobalah online!

Port langsung /codegolf//a/126822/59376 oleh xnor.

Arang , 28 byte

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

Cobalah online! Tautan ke mode verbose. Saya juga tampaknya kacau Dividedan IntDivide: |
Menggunakan metode yang sama dengan jawaban Python dan JavaScript.

NewStack , 14 byte

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

Kerusakan:

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

Bagaimana itu bekerja:

Rumus (2x ³ 1) / (3x ² -1) berasal dari penyederhanaan metode Newton untuk equasion x ³ = x + 1. Anda dapat menemukannya di sini . Mengulangi proses ini dengan jumlah kali tak terbatas yang menyatu dengan nomor plastik. Tingkat konvergensi agak cepat di sekitar 2,6 desimal per iterasi.

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

Alternatif urutan Padovan, 27 25 17 byte

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

Kerusakan:

¹                  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 byte dengan memilih strategi cetak yang lebih baik

-8 byte dengan memilih cara yang lebih baik untuk mengindeks tumpukan

Bagaimana itu bekerja:

Sebagai urutan Padovan berlanjut, rasio dari dua elemen terakhir bertemu dengan nomor plastik.

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

Clojure, 46 byte

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

Menggunakan formula cube-root iterated. Ini sedikit lebih menarik tetapi lebih lama:

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

((f 10)1)
1.3247179361449652

Javascript, 36 byte

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

Bekerja sama dengan jawaban python atas. Tidak console.logdimasukkan karena jika Anda menjalankan f(x)di konsol itu akan dicatat secara otomatis.

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

> <> , 38 + 3 = 41 byte

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

Mengharapkan input untuk hadir pada stack pada saat program mulai, jadi +3 byte untuk -vflag.

Cobalah online!

Secara efektif melakukan pencarian biner untuk mempersempit nilai output. Semakin banyak xmeningkatkan jumlah iterasi untuk melakukan.

Sunting: kalkulasi refactored sedikit untuk menghemat 1 byte, versi sebelumnya:

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

k, 27 byte

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

Cobalah online! Ini mengasumsikan bilangan bulat tak terbatas (yang, sayangnya, tidak benar). Ia menggunakan urutan Padovan .

TI-BASIC, 21 byte

: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

Gunakan formula rekursif ini .

Menariknya, mengkode angka dan membulatkannya memberikan byte-count yang sama:

TI-BASIC, 21 byte

: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

Menggunakan rumus trigonometri ini .

C # , 317 byte

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

Ini mengembalikan hasilnya sebagai sebagian kecil.

Penjelasan

Ia menggunakan metode Newton dengan x iterasi untuk menemukan akar polinomial p ^ 3-p-1 = 0. Rumusnya adalah x_n = 1- (f (x_ (n-1))) / (f '(x_ (n-1)))), dan x_0 adalah titik awal.

Turunan polinomialnya adalah 3p ^ 2-1, dan katakanlah x_ (n-1) = b / c. Kemudian, dengan menggunakan rumus di atas kita dapatkan, bahwa x_n = (2 b ^ 3 + c ^ 3) / (3 b ^ 2 cc ^ 3). Katakan juga, bahwa kita mulai dari 1, ini akan terjadi, ketika x = 2, karena x> 1, dan merupakan bilangan bulat. Kode idented, dan komentar:

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 byte

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

Menciptakan Padovan Spiral dan mencetak rasio dari dua angka terakhir.

Aksioma, 96 byte

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

hasil

(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

bagaimana Anda bisa melihat h (2) harus 1,32 dan bukan 1,33 sehingga ada beberapa kesalahan dalam digit terakhir

Maka akan ada yang satu ini dari 110 byte

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)

Ini menggunakan rumus untuk menyelesaikan persamaan kelas III tipe x ^ 3-3 * p * x-2 * q = 0 dalam kasus q ^ 2-p ^ 3> = 0 yaitu m = sqrt (q ^ 2- p ^ 3) dan x = (q + m) ^ (1/3) + (qm) ^ (1/3)

Dalam kasus kami r ^ 3-r-1 = 0 ini dapat ditulis sebagai r ^ 3-3 * (1/3) r-2 * (1/2) = 0 jadi p = 1/3 q = 1/2 m = 1 / 4-1 / 27 = 23/108 x = (0,5 + m) ^ (1/3) + (0,5-m) ^ (1/3)

ini yang menggunakan iterasi Newton dengan titik awal 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)

itu berubah dalam fungsi, nilai digit untuk mendapatkan satu objek n + 1 digit di atas titik float. Pada akhirnya nilai digit () ditugaskan kembali ke nilai sebelumnya.

Ruby , 35 byte

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

Cobalah online!