Соревнование

Пластический номер представляет собой число , связанное золотое сечение, со многими интересными математическими свойствами. Таким образом, существует много подходов, которые можно использовать для расчета числа.

Чтобы точно указать номер для этой задачи, мы будем использовать следующее определение (хотя существует множество эквивалентных определений, и вы можете использовать любое определение, которое вы пожелаете, если речь идет об одном и том же номере):

Пластическое число является действительным числом ρ таким, что ρ ³ = ρ +1.

Ваша задача состоит в том, чтобы написать программу или функцию, которая принимает целое число x в качестве входных данных (с x > 1) и производит приближение к ρ в качестве выходного значения, так что чем больше значение x , тем ближе выходной сигнал к ρ ( с не более чем конечным числом исключений; для этой цели остается то же значение, которое считается «ближе», и для любого положительного числа δ в вашей программе есть некоторый вход x, который выдает выходной сигнал, который находится в пределах δ от ρ .

Разъяснения

• Если вы выводите с помощью метода, который по своей природе выводит строки (например, стандартный поток вывода), вы можете отформатировать вывод либо в десятичном виде (например 1.3247179572), либо в виде отношения двух целых чисел с /символом между ними.
• Если вы выводите в качестве значения на вашем языке программирования (например, возвращая из функции), оно должно быть с фиксированной, плавающей или рациональной типами. (В частности, вы не можете использовать типы данных, которые хранят числа символически, если только они не используются для хранения отношения двух целых чисел. Поэтому, если вы используете Mathematica или подобный язык, вам нужно будет включить дополнительные код для генерации цифр на выходе.)
• Ваш ответ должен работать в гипотетическом варианте вашего языка, в котором целые числа могут быть произвольно большими, а память (включая стек) не ограничена. Вы не можете предполагать, что арифметика с плавающей запятой в вашем языке является произвольно точной, но вместо этого должна использовать ее фактическую точность (это означает, что вывод числа с плавающей запятой возможен только в языках, где точность чисел с плавающей запятой может быть контролируется во время выполнения).
• x может иметь любое значение, которое вы хотите (при увеличении оно дает более точные результаты). Я полагаю, что в большинстве представлений он контролирует количество выводимых цифр или количество итераций алгоритма, используемого вашей программой для схождения по пластиковому числу, но допустимы и другие значения.

Прецедент

Вот первые несколько цифр пластикового номера:

1.32471795724474602596090885

Больше цифр доступно на OEIS .

Состояние победы

Как обычно для code-golf , чем короче, тем лучше, измеряется в байтах. Однако не стесняйтесь публиковать ответы, даже если они не выигрывают, если они добавляют что-то (например, другой язык или другой алгоритм) к существующим ответам.

Python 2 , 49 байт

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

Попробуйте онлайн!

Идея состоит в том, чтобы выразить ρс ρ³=ρ+1как дробь n/x, знаменатель которой xявляется параметром точности ввода. Мы берем (n/x)³=n/x+1и очищаем знаменатели, чтобы получить n³=x²(x+n).

Поскольку LHS увеличивается nбыстрее, чем RHS, мы можем приблизить точку равенства nкак наименьшее с n³≥x²(x+n). Код считается до nтех пор, пока это не так, начиная с xкоторого меньше.

Небольшое байтовое сохранение позволяет разделить обе стороны x²на запись n³/x²≥x+n(отрицается в whileусловии). Это разделение по полу в коде, но потеря дробной части незначительна.

Альтернатива той же длины вместо xчислителя ставит :

Python 2 , 49 байт

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

Попробуйте онлайн!

Mathematica, 20 байтов

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

Встроенная Rootфункция Mathematica дает решения полиномиального уравнения f[x] == 0.

объяснение

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

Образец ввода / вывода

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 байт

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

-1 байт от Мартина
-2 байта от овса

вход

[27]

выход

{} +1,32471795724474602596090885

sed , 67 60 (59 + 1) байт

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

Попробуйте онлайн!

+1 за -Eфлаг (ERE вместо BRE). Вход и выход являются одинарными: вход 11111 для x = 5, например, Выход представляет собой дробную часть двух унарных чисел: вышеупомянутый вход 11111 дает выход 11111/1111 (5/4 в десятичном виде).

Аппроксимирует пластическое число как дробь между последовательными элементами последовательности Падована .

Mathematica, 27 байт

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

Используется усеченное приближение вложенной кубической формы радикала ³√ (1 + ³√ (1 + ³√ (1 + ...))) . В то время как выходной сигнал всегда будет иметь X-1 знаки после запятой, результат на самом деле меньше , чем точный, поскольку выражение сходится медленнее , чем на одну цифры итерации ( х также используются как число вложенных радикалов , которые вычисляются). Например, х = 100 дает

_________________________________________________________________________
1.324717957244746025960908854478097340734404056901733364534015050302827850993693624204577670741656151

где подчеркнутая часть верна.

Октава , 50 байт

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

Попробуйте онлайн!

Определяет анонимную функцию с nжелаемым количеством цифр вывода.

Этот ответ злоупотребляет тем, что digitsвозвращает текущую настройку для количества цифр в арифметике с переменной точностью. Это означает, что мы можем просто использовать его в анонимной функции без ошибок о «слишком много выходных аргументов».

Кроме этого, это действительно просто: vpasolveэто сокращение от Variable-Precision Arithmetic Solve, с точностью, установленной последним вызовом digits. Так vpaкак это символический тип данных в Octave, который запрещен согласно спецификации, мы просто оборачиваем всю функцию, char(...)чтобы получить вывод строки. Обратите внимание, что в solveи vpasolve, f==0подразумевается, поэтому r^3==r+1был заменен наr^3-r-1 (==0)

MATL ( 27 28 байт)

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

Мое первое решение (27 байт)

Попробуйте онлайн!

Это конечно не оптимально, я все еще привыкаю к ​​MATL.

Объяснение:

Я создаю последовательность Падована до ввода + 3, а затем нахожу соотношение двух последних чисел.

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 ρ

Правильный вывод дроби (35 байт) (28 байт, @Sanchises):

Тем не менее, первое решение не удовлетворяет потребности в произвольной точности, являющейся пределом с плавающей запятой настроек по умолчанию MATL. Таким образом, вместо добавления нескольких байтов для повышения этой точности проще выбрать правильный дробный маршрут и записать дробь из двух последних целых чисел в (N-1) ^-й и N- ^й элементы усеченной последовательности Падована.

например, "114/86"

7BG: "т @) у @ 1 +) + Н] + tg3) V '/' YcyG2 +) VYc

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

Предоставлено пользователем @Sanchises. :)

Попробуйте онлайн!

Не итерационная оценка:

Примечательно, что мой самый короткий код для «точной» версии (23 байта):

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

Попробуйте онлайн!

... но не дает произвольной точности. Интересно, может ли кто-нибудь изменить это, чтобы соответствовать правилам (использовать входные данные и т. Д.), И при этом добавить менее 5 байт? :П

М , 15 14 байт

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

Попробуйте онлайн!

Алгоритм

Это использует рациональные и метод Ньютона. В частности, для ввода x применяются первые x итераций с начальным значением x .

Мы пытаемся найти конкретный корень многочлена p (t) = t³ - t - 1 . Метод Ньютона достигает этого, принимая начальное значение t ₀ - достаточно близкое к ρ - и рекурсивно определяя последовательность по
t _{n + 1} = t _n - p (t _n ) / p '(t _n ) .

Поскольку p '(t) = 3t² -1 , мы получаем
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) .

Обратите внимание, что начальное приближение x становится все хуже с увеличением x . Хотя выходные данные для x = 3 немного менее точны, чем выходные данные для x = 2 , поскольку метод Ньютона сходится квадратично к ρ , это не должно быть проблемой для больших значений x .

Как это работает

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

Юлия 0,5 ,  44  40 байт

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

Использует рациональные и метод Ньютона.

Попробуйте онлайн!

05AB1E , 23 байта

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

Попробуйте онлайн!

Прямой порт /codegolf//a/126822/59376 от xnor.

Древесный уголь , 28 байт

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

Попробуйте онлайн! Ссылка на подробный режим. Также я видимо напутал Divideи IntDivide: |
Использует тот же метод, что и ответы Python и JavaScript.

NewStack , 14 байтов

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

Сломать:

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

Как это работает:

Формула (2x ³ +1) / (3x ² -1) происходит от упрощения метода Ньютона для уравнения x ³ = x + 1. Вы можете найти это здесь . Повторяя этот процесс, бесконечное количество раз сходится к пластическому числу. Это скорость сходимости довольно быстро, около 2,6 десятичных знаков за итерацию.

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

Альтернатива последовательности Падована, 27 25 17 байт

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

Сломать:

¹                  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 байта, выбирая лучшую стратегию печати

-8 байт, выбирая лучший способ индексировать стек

Как это работает:

Поскольку последовательность Падована продолжается, отношение двух последних элементов сходится к пластиковому числу.

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

Clojure, 46 байт

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

Использует повторную формулу кубического корня. Это немного интереснее, но дольше:

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

((f 10)1)
1.3247179361449652

Javascript, 36 байт

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

Работает так же, как верхний ответ Python. Нет console.logбыл включен, потому что если вы запустите f(x)в консоли, он будет зарегистрирован автоматически.

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

> <> , 38 + 3 = 41 байт

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

Предполагается, что входные данные будут присутствовать в стеке при запуске программы, поэтому +3 байта для -vфлага.

Попробуйте онлайн!

Эффективно выполняет двоичный поиск, чтобы сузить выходное значение. Увеличение xувеличивает количество итераций для выполнения.

Редактировать: слегка изменен расчет для сохранения 1 байта, предыдущая версия:

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

к, 27 байт

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

Попробуйте онлайн! Это предполагает бесконечные целые числа (что, увы, не соответствует действительности). Он использует последовательность Падована .

TI-BASIC, 21 байт

: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

Использует эту рекурсивную формулу .

Интересно, что жесткое кодирование числа и его округление дает одинаковое количество байтов:

TI-BASIC, 21 байт

: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

Использует эту тригонометрическую формулу .

C # , 317 байт

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

Возвращает результат в виде дроби.

объяснение

Он использует метод Ньютона с x итерациями для нахождения корня многочлена p ^ 3-p-1 = 0. Формула имеет вид x_n = 1- (f (x_ (n-1))) / (f '(x_ (n-1))), а x_0 является отправной точкой.

Производная полиномов равна 3p ^ 2-1, и скажем, x_ (n-1) = b / c. Затем, используя приведенную выше формулу, получаем, что x_n = (2 b ^ 3 + c ^ 3) / (3 b ^ 2 cc ^ 3). Скажем также, что мы начинаем с 1, это произойдет, когда x = 2, потому что x> 1, и является целым числом. Идентифицированный и прокомментированный код:

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 байт

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

Создает спираль Падована и печатает соотношение двух последних чисел.

Аксиома, 96 байт

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

полученные результаты

(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

как вы можете видеть, h (2) должно быть 1,32, а не 1,33, поэтому есть некоторые ошибки в последних цифрах

Тогда будет этот один из 110 байтов

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)

Используется формула для уравнения разрешения III степени типа x ^ 3-3 * p * x-2 * q = 0 в случае q ^ 2-p ^ 3> = 0, то есть m = sqrt (q ^ 2- p ^ 3) и x = (q + m) ^ (1/3) + (qm) ^ (1/3)

В нашем случае r ^ 3-r-1 = 0 это можно записать как r ^ 3-3 * (1/3) r-2 * (1/2) = 0, так что p = 1/3 q = 1/2 m = 1 / 4-1 / 27 = 23/108 x = (0,5 + m) ^ (1/3) + (0,5-m) ^ (1/3)

этот, который использует итерацию Ньютона с начальной точкой 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)

это изменение в функции, значение цифры для получения одного объекта из n + 1 цифр после точки с плавающей запятой. В конце значение digits () возвращается к значению предварительной точности.

Рубин , 35 байт

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

Попробуйте онлайн!