23

Hoy su objetivo es encontrar los números enteros a y b entero no negativo dado n tal que:

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

Usted debe escribir un programa o una función que toma el parámetro n y da salida a una y B en un formato de su elección.

Se aplican lagunas estándar. Además, se pretende que implemente el problema anterior utilizando la aritmética básica usted mismo. Por lo tanto, no puede utilizar la funcionalidad de álgebra exacta incorporada, los racionales o las funciones que implementan construcciones matemáticas no triviales (por ejemplo, la secuencia de Lucas ).

El código más corto en bytes gana.

Ejemplo de entrada / salida:

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
fuente

3

Dyalog APL, 18 bytes

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

Este es un programa que recibe información ⎕.

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

Las características utilizadas aquí se implementaron mucho antes de abril de 2015, lo que hace que esta respuesta sea válida.

Probarlo aquí . Tenga en cuenta que tryapl.org es un subconjunto limitado de Dyalog y no es compatible ⎕.

lirtosiast
fuente

16

Octava, 26 bytes

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

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

vector de entrada multiplicador

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

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

| 3 5 |
| 1 3 |

parece natural En lugar de ntiempos de bucle , preferimos elevar la matriz a la potencia de ny luego multiplicarla por el vector de entrada.

pawel.boczarski
fuente

Te estás vendiendo corto, [3 5;1 3]**input('')*[1;0]es 26 bytes, no 41.

orlp

3

@(n)[3 5;1 3]^n*[1;0](manejador de funciones) le ahorraría cinco caracteres, ¡buena idea!

flawr

14

Pitón 2, 50

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

Multiplica por 3+sqrt(5)repetidamente por su acción sobre el par que (a,b)representa a+b*sqrt(5). Equivalente a comenzar con el vector de columna [1,0]y multiplicar a la izquierda npor la matriz [[3,5],[1,3]].

xnor
fuente

12

Julia, 22 20 bytes

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

Esto crea una función lambda que toma un entero entero como entrada y devuelve un vector de enteros de 2 elementos correspondiente a la solución [a, b]. Para llamarlo, dale un nombre, por ejemplo f=n->....

Comienza multiplicando

Expansión inicial

Luego podemos traducir el lado derecho de esta ecuación en una matriz de 2 columnas, donde la primera corresponde al coeficiente de a y la segunda al coeficiente de b :

Matriz

Multiplique esta matriz por sí misma n veces, luego multiplique a la derecha por el vector de columna (1, 0) y ¡POOF! Fuera aparece el vector solución.

Ejemplos:

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

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

Alex A.
fuente

8

J, 20 bytes

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

Multiplica el vector [1 0]con los [[3 5] [1 3]] ntiempos de la matriz .

2 bytes guardados gracias a @algorithmshark.

Uso y prueba:

   (+/@:*(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
fuente

Se puede llegar hasta el 20 por explotar análisis adverbio tácita: +/ .*(3 5,:1 3&)&1 0.

algormshark

@algorithmshark Gracias, aunque ¿por qué (+/@:*&(3 5,.1 3)&1 0)funciona y (+/@:*&1 0&(3 5,.1 3))no? ¿No debería el segundo enlace correctamente y el primero intercambiado?

randomra

Lo tengo, se unen como esperaba, pero el exterior &hace la alimentación / bucle para que modifique la entrada del lado izquierdo durante el encendido (opuesto a la modificación normal del lado derecho).

randomra

7

Pyth, 20 bytes

u,+*3sGyeG+sGyeGQ,1Z

uque se reduce en general, se usa aquí como un ciclo de aplicación repetida. La función de actualización es G-> ,+*3sGyeG+sGyeG, donde Ghay una tupla 2. Esa función se traduce en 3*sum(G) + 2*G[1], sum(G) + 2*G[1]. ses sum, yes *2.

isaacg
fuente

Elegí la respuesta de @ randomra sobre la tuya porque la suya fue publicada 16 minutos antes, lo siento.

orlp

5

APL (22)

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

Explicación:

{... }⍣⎕⍨2↑1: lea un número y ejecute la siguiente función muchas veces, utilizando [1,0]como entrada inicial.
- 2 2⍴3 5 1: la matriz [[3,5],[1,3]]
- ⍵+.×⍨: multiplique el primer número en ⍵ por 3, el segundo por 5, y sume, este es el nuevo primer número; luego multiplique el primer número en ⍵ por 1, el segundo por 3, y sume esos, ese es el nuevo segundo número.

marinus
fuente

1

Awww sí, APL.

Nit

5

Jalea , 13 bytes

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

Pruébalo en línea!

Cómo 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
fuente

No, estoy bastante seguro de que Jelly estuvo mucho tiempo antes de la creación de Internet: P

Conor O'Brien

1

@ Doᴡɴɢᴏᴀᴛ Para respuestas que no compiten, prefiero mantener el conteo de bytes en la segunda línea. Esto evita que la respuesta llegue a la cima en las tablas de clasificación y los guiones de usuario, lo que parece injusto.

Dennis

3

Mathematica, 31

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

alephalpha
fuente

3

CJam, 21 bytes

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

Pruébalo en línea.

Cómo 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
fuente

3

Javascript, 63 61 bytes

Estoy usando una evaluación recursiva del binomio: (x + y) ^ n = (x + y) (x + y) ^ {n-1}

Nuevo (gracias a @ edc65)

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

Antiguo

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

falla
fuente

1

Quizás quieras considerar editar tu fórmula. Ya no tenemos MathJax.

Alex A.

Pensé que se acaba de presentar hace unos días.

flawr

Sí, pero estropeó los fragmentos de la pila, por lo que tuvo que ser desactivado.

Alex A.

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

Cuento

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

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

Esto implementa la multiplicación de matrices de forma aburrida. Para una solución más divertida (cita: "increíblemente horrible") de 238 bytes, ¡no busques más!

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

Desenredado:

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

Esto probablemente podría acortarse un poco. ¡Pruebe un programa de prueba en línea !

BrainSteel
fuente

1

Esto utiliza un algoritmo bastante complicado: P

orlp

@orlp No podría pensar en un algoritmo más corto para este lenguaje. Pensé que esto funcionaría, pero se salió de control, jaja. La implementación manual de la multiplicación de matrices podría ser más corta.

BrainSteel

1

Vota porque esto es increíblemente horrible.

kirbyfan64sos

2

k2 - 22 char

Función tomando un argumento.

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

_mules la multiplicación de matrices, así que de curry con la matriz (3 5;1 3)y luego golpearlo con el adverbio potencia funcional: f/[n;x]se aplica fa x, nveces. Nuevamente lo curry, esta vez con el vector de inicio 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)

Esto no funcionará en Kona, porque por alguna razón f/[n;x]no se implementa correctamente. Solo funciona la n f/xsintaxis, por lo que la solución más corta es {x _mul[(3 5;1 3)]/1 0}en 23 caracteres.

Algoritmo de tiburón
fuente

Guau. Este uso del curry es tan inteligente que siento que mi respuesta K es estúpida. De todos modos, planteé el problema que encontraste en Kona en su rastreador de errores .

kirbyfan64sos

Para su información, esto se solucionó recientemente en Kona .

kirbyfan64sos

2

ised, 25 bytes (20 caracteres)

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

Esperaba mejorar, pero se necesitan demasiados aparatos en ised para que sea competente, la prioridad del operador no es óptima para jugar al golf.

Espera que la entrada esté en la ranura de memoria de $ 1, por lo que esto funciona:

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

Para n = 0, se omite el cero (salidas 1, en lugar de 1 0). Si eso es un problema, reemplace el final 1con ~[2].

Orión
fuente

2

En serio, 32 bytes, no competitivos

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

Hex Dump:

2cbb34332f313260bd223b2940342af728362a2d229c6e2e58348df130606e7f

Pruébalo en línea

Obviamente no es un contendiente por el más corto, pero al menos el método es original. (Notando que tal problema necesariamente indica una secuencia de Lucas, como se menciona en la descripción, este programa genera términos sucesivos de las secuencias usando la relación de recurrencia

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

quintapia
fuente

1

Haskell, 41 bytes

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

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

nimi
fuente

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

Formateado:

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

Mismo concepto:

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

El banco de pruebas:

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

La salida:

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
fuente

Bienvenido al sitio, y buena primera respuesta!

DJMcMayhem

0

K, 37 bytes

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

o

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

Ambos son lo mismo.

kirbyfan64sos
fuente

0

Python 3, 49 bytes

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

aunque en mi máquina, esto solo da la respuesta correcta para las entradas en el rango 0 <= n <= 18.

Esto implementa la fórmula de forma cerrada

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

y aprovecha el hecho de que la v ** npieza es pequeña y puede calcularse mediante redondeo en lugar de cálculo directo.

fuente

1

Esta no es una solución válida (debes admitir cualquier n ), pero como no estás cerca de ser el más corto, no veo una razón para rechazarlo. Es una solución genial.

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
fuente

0

C 71 bytes (60 con variables preinicializadas)

Alcance para jugar al golf todavía, pero solo para demostrar que C no tiene que ser "horriblemente horrible".

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

Si los valores en a se inicializan a {1,0}, lo hacemos mejor.

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

Esto está utilizando iterativamente las asignaciones a-> 3a + 5b, b-> a + 3b pero evitando una variable temporal calculando a a partir del nuevo valor de b.

Alquimista
fuente

Su solución desborda enteros para entradas grandes :)

orlp

@orlp - Eso es C para ti. De acuerdo, esta solución falla antes que otras debido al cálculo intermedio entre paréntesis, pero de todos modos solo lograría un par de pasos adicionales a menos que cambie el tipo de datos. ¿Vale la pena cambiar explícitamente la pregunta para dar el rango que espera admitir? Probablemente demasiado tarde ahora sin embargo.

Alchymist

No hay un rango de soporte, una solución adecuada debería funcionar para cualquier entrada. En C eso significa que tendrá que implementar enteros de ancho arbitrario, lo siento = /

orlp

Sugerir en a[*a=1]=0lugar de*a=1,a[1]=0

ceilingcat

0

(no competitiva) Jelly, 10 bytes

31,53Dæ*³Ḣ

Pruébalo en línea!

Utiliza matriz. Calcula ([[3,1], [5,3]] ** input ()) [0].

Monja permeable
fuente

Calculando (3 + sqrt (5)) ^ n exactamente

Respuestas:

Dyalog APL, 18 bytes

Octava, 26 bytes

Pitón 2, 50

Julia, 22 20 bytes

J, 20 bytes

Pyth, 20 bytes

APL (22)

Jalea , 13 bytes

Cómo funciona

Mathematica, 31

CJam, 21 bytes

Cómo funciona

Javascript, 63 61 bytes

C, 114 bytes

k2 - 22 char

ised, 25 bytes (20 caracteres)

En serio, 32 bytes, no competitivos

Haskell, 41 bytes

K, 37 bytes

Python 3, 49 bytes

Esquema, 97 bytes

(no competitiva) Jelly, 10 bytes