23

Hoje seu objetivo é encontrar inteiros um e b dado inteiro não negativo n tal que:

(3 + sqrt (5)) ^ n = a + b * sqrt (5)

Você deve escrever um programa ou uma função que leva parâmetro n e gera um e b em um formato de sua escolha.

Aplicam-se brechas padrão. Além disso, você pretende implementar o problema acima usando aritmética básica. Portanto, você não pode usar a funcionalidade exata da álgebra, os racionais ou as funções que implementam construções matemáticas não triviais (por exemplo, a sequência de Lucas ).

O menor código em bytes vence.

Exemplo de entrada / saída:

0 → 1, 0
1 → 3, 1
2 → 14, 6
3 → 72, 32
4 → 376, 168
5 → 1968, 880
6 → 10304, 4608
7 → 53952, 24128
8 → 282496, 126336
9 → 1479168, 661504

code-golf arithmetic orlp
fonte

3

Dyalog APL, 18 bytes

((3∘×+5 1×⌽)⍣⎕)1 0

Este é um programa que recebe entrada ⎕.

 (         )         Monadic train:
  3∘×                3 times argument
     +               Plus
      5 1×⌽          (5 1) times the reverse
(           ⍣⎕)      Apply that function (input) times
               1 0   starting with (1 0)

Os recursos usados aqui foram implementados bem antes de abril de 2015, validando esta resposta.

Experimente aqui . Observe que o tryapl.org é um subconjunto limitado do Dyalog e não suporta ⎕.

lirtosiast
fonte

16

Oitava, 26 bytes

[3 5;1 3]**input('')*[1;0]

Como ( a + b * sqrt (5)) * (3 + sqrt (5)) = ( 3a + 5b ) + ( a + 3b ) * sqrt (5),

multiplicando o vetor de entrada

| 1 |    /* a = 1 */
| 0 |    /* b = 0 */

que significa 1 = (3 + sqrt (5)) ^ 0 pela matriz

| 3 5 |
| 1 3 |

parece natural. Em vez de ntempos de loop , aumentamos a matriz à potência de ne depois a multiplicamos pelo vetor de entrada.

pawel.boczarski
fonte

Você está vendendo-se curto, [3 5;1 3]**input('')*[1;0]é de 26 bytes, e não 41.

orlp

3

@(n)[3 5;1 3]^n*[1;0](identificador de função) economizaria cinco caracteres, mude a ideia!

flawr

14

Python 2, 50

a=1;b=0
exec"a,b=3*a+5*b,3*b+a;"*input()
print a,b

Multiplica-se 3+sqrt(5)repetidamente por sua ação no par que (a,b)representa a+b*sqrt(5). Equivale a começar com o vetor da coluna [1,0]e os ntempos de multiplicação à esquerda pela matriz [[3,5],[1,3]].

xnor
fonte

12

Julia, 22 20 bytes

n->[3 5;1 3]^n*[1;0]

Isso cria uma função lambda que recebe um único inteiro como entrada e retorna um vetor de 2 elementos com números inteiros correspondentes à solução [a, b]. Para chamá-lo, dê um nome, por exemplo f=n->....

Comece multiplicando

Expansão inicial

Podemos então traduzir o lado direito dessa equação em uma matriz de 2 colunas, onde a primeira corresponde ao coeficiente de a e a segunda ao coeficiente de b :

Matriz

Multiplique esta matriz por si mesma n vezes, depois multiplique à direita pelo vetor da coluna (1, 0) e POOF! Out aparece o vetor da solução.

Exemplos:

julia> println(f(0))
[1,0]

julia> println(f(5))
[1968,880]

Alex A.
fonte

8

J, 20 bytes

+/@:*(3 5,.1 3&)&1 0

Multiplique o vetor [1 0]pelos [[3 5] [1 3]] ntempos da matriz .

2 bytes salvos graças a @algorithmshark.

Uso e teste:

   (+/@:*(3 5,.1 3&)&1 0) 5
1968 880

   (+/@:*(3 5,.1 3&)&1 0) every i.6
   1   0
   3   1
  14   6
  72  32
 376 168
1968 880

randomra
fonte

Você pode obter até 20 explorando análise advérbio tácito: +/ .*(3 5,:1 3&)&1 0.

algorithmshark

@algorithmshark Obrigado, embora por que (+/@:*&(3 5,.1 3)&1 0)funciona e (+/@:*&1 0&(3 5,.1 3))não? O segundo não deveria se relacionar corretamente e o primeiro trocar?

Random #

Entendi, eles se ligam como eu esperava, mas o externo &faz a alimentação / looping, para que você modifique a entrada do lado esquerdo durante a alimentação (oposta à modificação normal do lado direito).

Random #

7

Pitão, 20 bytes

u,+*3sGyeG+sGyeGQ,1Z

uque é reduzir em geral, é usado aqui como um loop aplicar repetidamente. A função de atualização é G-> ,+*3sGyeG+sGyeG, onde Gé uma tupla de 2. Essa função se traduz em 3*sum(G) + 2*G[1], sum(G) + 2*G[1]. sé sum, yé *2.

isaacg
fonte

Eu escolhi a resposta da @ randomra sobre a sua porque a dela foi publicada 16 minutos antes, desculpe.

orlp

5

APL (22)

{⍵+.×⍨2 2⍴3 5 1}⍣⎕⍨2↑1

Explicação:

{... }⍣⎕⍨2↑1: leia um número e execute a seguinte função várias vezes, usando [1,0]como entrada inicial.
- 2 2⍴3 5 1: o Matrix [[3,5],[1,3]]
- ⍵+.×⍨: multiplique o primeiro número em ⍵ por 3, o segundo por 5 e some-os, esse é o novo primeiro número; então multiplique o primeiro número em ⍵ por 1, o segundo por 3 e some esses, que é o novo segundo número.

marinus
fonte

1

Awww yiss, APL.

Nit

5

Gelatina , 13 bytes

5W×U++Ḥ
2BÇ³¡

Experimente online!

Como funciona

5W×U++Ḥ    Helper link. Argument: [a, b]

5W         Yield [5].
  ×U       Multiply it by the reverse of [a, b]. This yields [5b, a].
    +      Hook; add the argument to the result. This yields [a + 5b, a + b].
     +Ḥ    Fork; add the doubled argument ([2a, 2b]) to the result.
           This yields [3a + 5b, a + 3b].

2BÇ³¡      Main link. Argument: n

2B         Convert 2 to binary, yielding [1, 0].
    ¡      Repeat:
  Ç            Apply the helper link...
   ³           n times.

Dennis
fonte

Não, eu tenho certeza que Jelly estava por muito tempo antes da criação da internet: P

Conor O'Brien

1

@ Doᴡɴɢᴏᴀᴛ Para respostas não concorrentes, prefiro manter a contagem de bytes na segunda linha. Isso evita que a resposta suba ao topo nas tabelas de classificação e nos scripts dos usuários, o que parece injusto.

Dennis

3

Mathematica, 31

Nest[{{3,5},{1,3}}.#&,{1,0},#]&

alefalpha
fonte

3

CJam, 21 bytes

0X{_2$3*+@5*@3*+}li*p

Experimente online.

Como funciona

0X       " Stack: [ 0 1 ]                                ";
li{      " Do int(input()) times:                        ";
  _2$    " Stack: [ a b ] -> [ a b b a ]                 ";
  3*+    " Stack: [ a b b a ] -> [ a b (b+3a) ]          ";
  @5*@3* " Stack: [ a b (b+3a) ] -> [ (b+3a) 5a 3b ]     ";
  +      " Stack: [ (b+3a) 5a 3b ] -> [ (b+3a) (5a+3b) ] ";
}*       "                                               ";
p        " Print topmost stack item plus linefeed.       ";
         " Print remaining stack item (implicit).        ";

Dennis
fonte

3

Javascript, 63 61 bytes

Estou usando uma avaliação recursiva do binômio: (x + y) ^ n = (x + y) (x + y) ^ {n-1}

Novo (graças a @ edc65)

F=n=>{for(i=y=0,x=1;i++<n;)[x,y]=[3*x+5*y,x+3*y];return[x,y]}

Velho

F=n=>{for(i=y=0,x=1;i<n;i++)[x,y]=[3*x+5*y,x+3*y];return [x,y]}

flawr
fonte

1

Pode querer considerar editar sua fórmula. Não temos mais o MathJax.

Alex A.

Eu pensei que foi introduzido há alguns dias atrás?

flawr

Sim, mas isso atrapalhou os trechos da pilha, e teve que ser desativado.

Alex A.

Conto 63 como é, e pode ser encurtado para 61F=n=>{for(i=y=0,x=1;i++<n;)[x,y]=[3*x+5*y,x+3*y];return[x,y]}

edc65

n=>[...Array(n)].map(_=>[x,y]=[3*x+5*y,x+3*y],y=0,x=1)[n-1]mesmo comprimento

l4m2

2

C, 114 bytes

g(n){int i,a[2]={1,0},b[2];for(i=0;i<n;i++)*b=*a*3+5*a[1],b[1]=*a+3*b[1],*a=*b,a[1]=b[1];printf("%d,%d",*a,a[1]);}

Isso implementa a multiplicação de matrizes da maneira chata. Para uma solução de 238 bytes mais divertida (citação: "incrivelmente horrível"), não precisa procurar mais!

f(n){int p[2][n+3],i,j,k=0,a[2]={0};for(j=0;j<n+3;j++)p[0][j]=0;*p[1]=0;(*p)[1]=1;for(j=0;j<n;j++,k=!k)for(i=1;i<n+3;i++)p[!k][i]=p[k][i-1]+p[k][i];for(i=1;i<n+2;i++)a[!(i%2)]+=p[k][i]*pow(3,n+1-i)*pow(5,(i-1)/2);printf("%d,%d",*a,a[1]);}

Desvendado:

g(n){
    int i,a[2]={1,0},b[2];
    for(i=0;i<n;i++)
        *b=3**a+5*a[1],b[1]=*a+3*b[1],*a=*b,a[1]=b[1];
    printf("%d,%d",*a,a[1]);
}

Provavelmente isso poderia ser reduzido. Experimente um programa de teste online !

BrainSteel
fonte

1

Isto é usa um algoritmo bastante complicado: P

orlp

@ orlp Eu não conseguia pensar em um algoritmo mais curto para essa linguagem. Eu pensei que este iria dar certo, mas meio que ficou fora de controle, haha. Implementar a multiplicação da matriz manualmente pode muito bem ser mais curto.

BrainSteel

1

Voto positivo porque isso é incrivelmente horrível.

precisa saber é o seguinte

2

k2 - 22 car

Função tendo um argumento.

_mul[(3 5;1 3)]/[;1 0]

_mul é a multiplicação de matrizes, então a curry com a matriz (3 5;1 3) e, em seguida, a atingimos com o advérbio de poder funcional: f/[n;x]aplica f- se a x, ntimes. Mais uma vez, o curry, desta vez com o vetor inicial 1 0.

  _mul[2 2#3 5 1]/[;1 0] 5
1968 880
  f:_mul[2 2#3 5 1]/[;1 0]
  f'!8  /each result from 0 to 7 inclusive
(1 0
 3 1
 14 6
 72 32
 376 168
 1968 880
 10304 4608
 53952 24128)

Isso não vai funcionar em Kona, porque por algum motivo f/[n;x] não foi implementado corretamente. Somente a n f/xsintaxe funciona, portanto, a correção mais curta é de {x _mul[(3 5;1 3)]/1 0}23 caracteres.

algoritmshark
fonte

Uau. Esse uso de curry é tão inteligente que sinto que minha resposta em K é estúpida. Enfim, eu levantei o problema que você encontrou em Kona no rastreador de erros deles .

Kirbyfan64sos

Para sua informação, isso foi corrigido recentemente em Kona .

Kirbyfan64sos

2

25 bytes (20 caracteres)

({:{2,4}·x±Σx:}$1)∘1

Eu esperava melhor, mas existem muitas chaves necessárias para torná-la competente, a precedência do operador não é ideal para o golfe.

Ele espera que a entrada esteja no slot de memória de $ 1, portanto, isso funciona:

ised '@1{9};' '({:{2,4}·x±Σx:}$1)∘1'

Para n = 0, o zero é ignorado (gera 1, em vez de 1 0). Se isso for um problema, substitua a final 1por ~[2].

orion
fonte

2

Sério, 32 bytes, não concorrente

,╗43/12`╜";)@4*≈(6*-"£n.X4ì±0`n

Hex Dump:

2cbb34332f313260bd223b2940342af728362a2d229c6e2e58348df130606e7f

Experimente-o Onlline

Obviamente, não é um candidato pelo menor tempo, mas pelo menos o método é original. (Observando que esse problema indica necessariamente uma sequência de Lucas, conforme mencionado na descrição, este programa gera termos sucessivos das sequências usando a relação de recorrência

a_n = 6 * a_ {n-1} - 4 * a_ {n-2}.)

quintopia
fonte

1

Haskell, 41 bytes

(iterate(\(a,b)->(3*a+5*b,a+3*b))(1,0)!!)

Exemplo de uso: (iterate(\(a,b)->(3*a+5*b,a+3*b))(1,0)!!) 8-> (282496,126336).

nimi
fonte

1

C / C ++ 89 bytes

void g(int n,long&a,long&b){if(n){long j,k;g(n-1,j,k);a=3*j+5*k;b=j+3*k;}else{a=1;b=0;}}

Formatado:

    void g(int n, long&a, long&b) {
if (n) {
    long j, k;
    g(n - 1, j, k);
    a = 3 * j + 5 * k;
    b = j + 3 * k;
} else {
    a = 1;
    b = 0;
}}

Mesmo conceito:

void get(int n, long &a, long& b) {
    if (n == 0) {
        a = 1;
        b = 0;
        return;
    }
    long j, k;
    get(n - 1, j, k);
    a = 3 * j + 5 * k;
    b = j + 3 * k;
}

O banco de ensaio:

#include <iostream>
using namespace std;    
int main() {
    long a, b;
    for (int i = 0; i < 55; i++) {
        g(i, a, b);
        cout << i << "-> " << a << ' ' << b << endl;
    }
    return 0;
}

A saída:

0-> 1 0
1-> 3 1
2-> 14 6
3-> 72 32
4-> 376 168
5-> 1968 880
6-> 10304 4608
7-> 53952 24128
8-> 282496 126336
9-> 1479168 661504
10-> 7745024 3463680
11-> 40553472 18136064
12-> 212340736 94961664
13-> 1111830528 497225728
14-> 5821620224 2603507712
15-> 30482399232 13632143360
16-> 159607914496 71378829312
17-> 835717890048 373744402432
18-> 4375875682304 1956951097344
19-> 22912382533632 10246728974336
20-> 119970792472576 53652569456640
21-> 628175224700928 280928500842496
22-> 3289168178315264 1470960727228416
23-> 17222308171087872 7702050360000512
24-> 90177176313266176 40328459251089408
25-> 472173825195245568 211162554066534400
26-> 2472334245918408704 1105661487394848768

philn
fonte

Bem-vindo ao site, e boa primeira resposta!

DJMcMayhem

0

K, 37 bytes

f:{:[x;*(1;0)*_mul/x#,2 2#3 1 5;1 0]}

ou

f:{:[x;*(1;0)*_mul/x#,(3 1;5 3);1 0]}

Ambos são a mesma coisa.

kirbyfan64sos
fonte

0

Python 3, 49 bytes

w=5**0.5;a=(3+w)**int(input())//2+1;print(a,a//w)

embora na minha máquina, isso só dê a resposta correta para entradas na faixa 0 <= n <= 18.

Isso implementa a fórmula de formulário fechado

w = 5 ** 0.5
u = 3 + w
v = 3 - w
a = (u ** n + v ** n) / 2
b = (u ** n - v ** n) / (2 * w)

e aproveita o fato de que a v ** npeça é pequena e pode ser calculada por arredondamento, em vez de cálculo direto.

fonte

1

Esta não é uma solução válida (você deve oferecer suporte a qualquer n ), mas como você não está nem perto de ser o mais curto, não vejo motivo para desistir. É uma solução legal.

orlp

0

Esquema, 97 bytes

(define(r n)(let s([n n][a 1][b 0])(if(= 0 n)(cons a b)(s(- n 1)(+(* a 3)(* b 5))(+ a(* b 3))))))

Penguino
fonte

0

C 71 bytes (60 com variáveis pré-inicializadas)

Escopo para o golfe ainda, mas apenas para provar que C não precisa ser "terrivelmente horrível".

f(int n,int*a){for(*a=1,a[1]=0;n--;a[1]=*a+3*a[1],*a=(5*a[1]+4**a)/3);}

Se os valores em a forem inicializados em {1,0}, faremos melhor.

f(int n,int*a){for(;n--;a[1]=*a+3*a[1],*a=(5*a[1]+4**a)/3);}

Isso é iterativamente usando os mapeamentos a-> 3a + 5b, b-> a + 3b, mas evitando uma variável temporária calculando a a partir do novo valor de b.

Alquimista
fonte

Sua solução transborda números inteiros para entradas grandes :)

orlp

@ orlp - Isso é C para você. A solução concedida falha mais cedo do que outras por causa do cálculo intermediário entre parênteses, mas ela só gerenciaria algumas etapas extras de qualquer maneira, a menos que eu alterasse o tipo de dados. Vale a pena mudar explicitamente a pergunta para fornecer o intervalo que você espera apoiar? Provavelmente tarde demais agora.

Alchymist

Não há um intervalo para suporte; uma solução adequada deve funcionar para qualquer entrada. Em C, isso significa que você terá que implementar números inteiros de largura arbitrária, desculpe = /

orlp

Sugerir em a[*a=1]=0vez de*a=1,a[1]=0

ceilingcat 23/02

0

(não concorrente) Gelatina, 10 bytes

31,53Dæ*³Ḣ

Experimente online!

Usa matriz. Calcula ([[3,1], [5,3]] ** entrada ()) [0].

Freira Furada
fonte

Cálculo (3 + sqrt (5)) ^ n exatamente

Respostas:

Dyalog APL, 18 bytes

Oitava, 26 bytes

Python 2, 50

Julia, 22 20 bytes

J, 20 bytes

Pitão, 20 bytes

APL (22)

Gelatina , 13 bytes

Como funciona

Mathematica, 31

CJam, 21 bytes

Como funciona

Javascript, 63 61 bytes

C, 114 bytes

k2 - 22 car

25 bytes (20 caracteres)

Sério, 32 bytes, não concorrente

Haskell, 41 bytes

K, 37 bytes

Python 3, 49 bytes

Esquema, 97 bytes

(não concorrente) Gelatina, 10 bytes