O desafio
O número do plástico é um número relacionado à proporção áurea, com muitas propriedades matemáticas interessantes. Como tal, existem muitas abordagens que podem ser usadas para calcular o número.
Para especificar com precisão o número para os objetivos deste desafio, usaremos a seguinte definição (embora existam muitas definições equivalentes e você possa usar qualquer definição que desejar, desde que chegue ao mesmo número):
O número do plástico é um número real ρ tal que ρ ³ = ρ +1.
Seu desafio é escrever um programa ou função que use um número inteiro x como entrada (com x > 1) e produza uma aproximação de ρ como saída, de modo que, quanto maior o valor de x , maior a proximidade de ρ ( com no máximo muitas exceções finitas; permanecer no mesmo valor conta como "mais próximo" para essa finalidade) e para qualquer número positivo δ , há alguma entrada x no seu programa que produz uma saída dentro de δ de ρ .
Esclarecimentos
- Se você estiver produzindo através de um método que gera inerentemente seqüências de caracteres (por exemplo, o fluxo de saída padrão), você pode formatar a saída em decimal (por exemplo
1.3247179572
) ou como uma proporção de dois números inteiros com um/
caractere entre eles. - Se você estiver produzindo como um valor na sua linguagem de programação (por exemplo, retornando de uma função), ela deve ser do tipo ponto fixo, ponto flutuante ou racional. (Em particular, você não pode usar tipos de dados que armazenam números simbolicamente, a menos que sejam usados apenas para manter a proporção de dois números inteiros. Portanto, se você estiver usando o Mathematica ou um idioma semelhante, precisará incluir o extra código para realmente gerar os dígitos da saída.)
- Sua resposta deve funcionar em uma variante hipotética do seu idioma, na qual os números inteiros podem ser arbitrariamente grandes e a memória (incluindo a pilha) é ilimitada. Você não pode presumir que a aritmética de ponto flutuante no seu idioma seja arbitrariamente precisa, mas deve usar sua precisão real (o que significa que a saída de um número de ponto flutuante só será possível em idiomas onde a precisão dos números de ponto flutuante pode ser controlado em tempo de execução).
- x pode ter o significado que você quiser (desde que aumentado, produza resultados mais precisos). Eu imagino que a maioria das submissões controlará o número de dígitos da saída a ser produzida ou o número de iterações do algoritmo usado pelo seu programa para convergir para o número plástico, mas outros significados são aceitáveis.
Caso de teste
Aqui estão os primeiros dígitos do número do plástico:
1.32471795724474602596090885
Mais dígitos estão disponíveis no OEIS .
Condição de vitória
Como de costume no código-golfe , quanto menor, melhor, medido em bytes. No entanto, sinta-se à vontade para postar respostas, mesmo que não ganhem, desde que adicionem algo (por exemplo, um idioma diferente ou um algoritmo diferente) às respostas existentes.
Respostas:
Python 2 , 49 bytes
Experimente online!
A idéia é expressar o
ρ
comρ³=ρ+1
como uma fraçãon/x
cujo denominadorx
é o parâmetro de precisão da entrada. Tomamos(n/x)³=n/x+1
e limpamos denominadores para obtern³=x²(x+n)
.Como o LHS aumenta
n
mais rapidamente que o RHS, podemos aproximar o ponto de igualdaden
como o menor comn³≥x²(x+n)
. O código contan
até que este seja o caso, começando pelox
qual é menor.Uma pequena economia de bytes é dividir os dois lados por
x²
escrevern³/x²≥x+n
(negado nawhile
condição). Esta é a divisão de piso no código, mas a parte fracionária perdida é insignificante.Uma alternativa de mesmo comprimento coloca
x
como numerador:Python 2 , 49 bytes
Experimente online!
fonte
2**input()
e não apenasinput()
; então, cada aproximação será tão precisa quanto a anterior.Mathematica, 20 bytes
A
Root
função embutida do Mathematica fornece as soluções para uma equação polinomialf[x] == 0
.Explicação
E / S de amostra
fonte
Root[x^3-x-1,1]~N~#&
funciona bem (apesar de não dizer quex
é uma variável) para a mesma contagem de bytes.Mathematica, 27 bytes
-1 byte de Martin
-2 bytes de ovs
entrada
saída
fonte
Solve[x^3==x+1>2,x]~N~#&
para 24 bytes{{x -> 1.32...}}
entanto. Convém verificar com ais se esse é um formato de saída válido.{1.32...}
, na verdade, mas esse formato é provavelmente menos controverso.sed ,
6760 (59 + 1) bytesExperimente online!
+1 para a
-E
bandeira (ERE em vez de BRE). Entrada e saída são unárias: entrada 11111 para x = 5, por exemplo, Saída é uma fração de dois números unários: a entrada 11111 mencionada acima produz a saída 11111/1111 (5/4 em decimal).Aproxima o número do plástico como uma fração entre os elementos consecutivos da sequência Padovan .
fonte
b
comando, mas pode reduzi -lo ainda mais usando o rótulo vazio (:
eb
sem argumento). tio.run/#%23K05N@f@/…t
vez deb
, para que seja um salvamento bastante agradável. Obrigado :)Mathematica, 27 bytes
Usa uma aproximação truncada da forma de radical cúbico aninhado ³√ (1 + ³√ (1 + ³√ (1 + ...))) . Embora a saída sempre tenha casas decimais x-1 , o resultado é menos preciso do que isso, porque a expressão converge mais lentamente que um dígito por iteração ( x também é usado como o número de radicais aninhados que são calculados). Por exemplo, x = 100 fornece
onde a parte sobreposta está correta.
fonte
dc
, mas fiquei frustrado, porque acontece que ele não possui uma operação de raiz de cubo e aumentar um número para o poder ⅓ também não funciona :-( Pelo menos você sempre pode contar com Mathematica para ter builtins apropriados…CubeRoot
mas ninguém tem bytes para isso.Oitava , 50 bytes
Experimente online!
Define uma função anônima, com
n
o número desejado de dígitos da saída.Esta resposta abusa que
digits
retorna a configuração atual para o número de dígitos na aritmética de precisão variável. Isso significa que podemos apenas usá-lo em uma função anônima sem erros sobre 'Muitos argumentos de saída'.Fora isso, é realmente simples:
vpasolve
é a abreviação de Aritmética de precisão variável, com a precisão definida pela última chamada dedigits
. Comovpa
é um tipo de dados simbólico no Octave, que é banido de acordo com as especificações, envolvemos toda a funçãochar(...)
para obter a saída da string. Observe que emsolve
evpasolve
, of==0
está implícito, portantor^3==r+1
, foi substituído porr^3-r-1 (==0)
fonte
MATL (
2728 bytes)Minha primeira solução (27 bytes)
Experimente online!
Certamente não é o ideal, ainda estou me acostumando com o MATL.
Explicação:
Eu crio uma sequência Padovan até a entrada + 3 e depois encontro a proporção dos dois últimos números.
Saída de fração adequada
(35 bytes)(28 bytes, @Sanchises):No entanto, a primeira solução não atende à necessidade de precisão arbitrária, sendo o limite de ponto flutuante das configurações padrão do MATL. Então, ao invés de adicionar vários bytes para estender esta precisão, é mais simples para tomar a rota fração própria e escrever uma fração dos dois últimos números inteiros na (N-1) th e N º elementos da sequência Padovan truncado.
por exemplo "114/86"
7BG: "t @) y @ 1 +) + h] tG3 +) V '/' YcyG2 +) VYcCortesia do usuário @Sanchises. :)
Experimente online!
Avaliação não iterativa:
Notavelmente, meu código mais curto para a versão 'exata' é (23 bytes):
Experimente online!
... mas não fornece precisão arbitrária. Gostaria de saber se alguém pode ajustar isso para cumprir as regras (use a entrada etc) e ainda adicionar menos de 5 bytes? : P
fonte
1+
pode ser reduzido paraQ
. Com isso em mente, você pode substituir@)y@1+)+
por apenas@tQh)s
. Além disso, você pode usarJ
para indicar o final de uma matriz; e, finalmente, o MATL não faz distinção entre matrizes normais e matrizes de caracteres, para que você possa substituí-loYc
porh
(você não precisa da funcionalidade extra deYc
). Isso fornece apenas 28 bytes:7BG:"t@tQh)sh]tJ)V47hyJq)Vh&
(observe&
para evitar saída supérflua e substitua'/'
por 47).7B
embora, muito melhor do que ingenuamente empurrandolllv
J
de transferência, por padrão1j
, contém , mas a área de transferênciaL
também contém muitas funções de indexação úteis (observe que1j
é igual aend
MATL).M ,
1514 bytesExperimente online!
Algoritmo
Isso usa racionalidades e método de Newton. Especificamente, para a entrada x , as primeiras x iterações com o valor inicial x são aplicadas.
Estamos tentando encontrar uma raiz específica do polinômio p (t) = t³ - t - 1 . O método de Newton consegue isso pegando um valor inicial t 0 - suficientemente próximo de ρ - e definindo recursivamente uma sequência por
t n + 1 = t n - p (t n ) / p '(t n ) .
Como p '(t) = 3t² -1 , obtemos
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) .
Observe que a aproximação inicial x piora progressivamente à medida que x aumenta. Embora a saída para x = 3 seja um pouco menos precisa que a saída para x = 2 , como o método de Newton converge quadraticamente para ρ , isso não deve ser um problema para grandes valores de x .
Como funciona
fonte
µ¡
...Julia 0,5 ,
4440 bytesUsa racional e método de Newton.
Experimente online!
fonte
05AB1E , 23 bytes
Experimente online!
Porta direta de /codegolf//a/126822/59376 pela xnor.
fonte
Carvão , 28 bytes
Experimente online! Link para o modo detalhado. Também aparentemente eu errei
Divide
eIntDivide
: |Usa o mesmo método que as respostas Python e JavaScript.
fonte
NewStack , 14 bytes
Demolir:
Como funciona:
A fórmula (2x 3 +1) / (3x 2 -1) deriva da simplificação do método de Newton para a equação x 3 = x + 1. Você pode encontrá-lo aqui . Repetindo esse processo, uma quantidade infinita de vezes converge para o número plástico. Sua taxa de convergência é bastante rápida, em torno de 2,6 decimais por iteração.
Alternativa de sequência Padovan,
272517 bytesDemolir:
-2 bytes, escolhendo uma melhor estratégia de impressão
-8 bytes, escolhendo a melhor maneira de indexar a pilha
Como funciona:
À medida que a sequência Padovan continua, a proporção dos dois últimos elementos converge para o número do plástico.
fonte
Clojure, 46 bytes
Usa a fórmula de raiz de cubo iterada. Isso é um pouco mais interessante, mas mais longo:
fonte
Javascript, 36 bytes
Funciona da mesma forma que a resposta python superior. Não
console.log
foi incluído porque se você executarf(x)
no console, ele será registrado automaticamente.fonte
> <> , 38 + 3 = 41 bytes
Espera que a entrada esteja presente na pilha no início do programa, portanto, +3 bytes para o
-v
sinalizador.Experimente online!
Efetivamente realiza uma pesquisa binária para restringir o valor de saída. Aumentar
x
aumenta o número de iterações a serem executadas.Editar: cálculo refatorado ligeiramente para economizar 1 byte, versão anterior:
fonte
k, 27 bytes
Experimente online! Isso pressupõe números inteiros infinitos (o que, infelizmente, não é verdadeiro). Ele usa a sequência Padovan .
fonte
TI-BASIC, 21 bytes
Usa essa fórmula recursiva .
Curiosamente, codificar o número e arredondá-lo fornece o mesmo número de bytes:
TI-BASIC, 21 bytes
Usa essa fórmula trigonométrica .
fonte
Your answer must work in a hypothetical variant of your language in which integers can be arbitrarily large, and memory (including stack) is unlimited. You may not assume that floating-point arithmetic in your language is arbitrarily accurate, but must instead use its actual accuracy (meaning that outputting a floating-point number is only going to be possible in languages where the accuracy of floating-point numbers can be controlled at runtime).
C # , 317 bytes
Retorna o resultado como uma fração.
Explicação
Ele usa o método de Newton com x iterações para encontrar a raiz do polinômio p ^ 3-p-1 = 0. A fórmula é x_n = 1- (f (x_ (n-1))) / (f '(x_ (n-1))) e x_0 é o ponto de partida.
A derivada polinomial é 3p ^ 2-1, e digamos x_ (n-1) = b / c. Então, usando a fórmula acima, obtemos que x_n = (2 b ^ 3 + c ^ 3) / (3 b ^ 2 cc ^ 3). Digamos também que, partindo de 1, isso acontecerá quando x = 2, porque x> 1 e é um número inteiro. Código identificado e comentado:
fonte
PHP, 86 bytes
Sandbox do PHP Online
Cria a espiral Padovan e imprime a proporção dos dois últimos números.
fonte
Axioma, 96 bytes
resultados
como você pode ver h (2) deve ser 1,32 e não 1,33, por isso há algum erro nos últimos dígitos
Então haveria este de 110 bytes
Use a fórmula para resolver a equação da classe III do tipo x ^ 3-3 * p * x-2 * q = 0 no caso q ^ 2-p ^ 3> = 0 que é m = sqrt (q ^ 2- Dê sua nota! Dê sua nota! 2Comentários (2)
No nosso caso, r ^ 3-r-1 = 0, isso pode ser escrito como r ^ 3-3 * (1/3) r-2 * (1/2) = 0, então p = 1/3 q = 1/2 Qual é a raiz quadrada de 2? Matemática5 pontos
este que usa a iteração de Newton com o ponto inicial r = 1
ele muda na função, digita o valor para obter um objetivo de n + 1 dígitos após o ponto flutuante. No final, o valor de dígitos () é atribuído novamente ao valor anterior.
fonte
Ruby , 35 bytes
Experimente online!
fonte