23

Aujourd'hui, votre objectif est de trouver des entiers a et b étant donné un entier non négatif n tel que:

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

Vous devez écrire un programme ou une fonction qui prend le paramètre n et génère a et b dans un format de votre choix.

Des échappatoires standard s'appliquent. De plus, il est prévu que vous implémentiez vous-même le problème ci-dessus en utilisant l'arithmétique de base. Vous ne pouvez donc pas utiliser la fonctionnalité d'algèbre exacte intégrée, les rationnels ou les fonctions mettant en œuvre des constructions mathématiques non triviales (par exemple la séquence de Lucas ).

Le code le plus court en octets gagne.

Exemple d'entrée / sortie:

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
la source

3

Dyalog APL, 18 octets

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

Il s'agit d'un programme qui prend en compte ⎕.

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

Les fonctionnalités utilisées ici ont été mises en œuvre bien avant avril 2015, ce qui rend cette réponse valide.

Essayez-le ici . Notez que tryapl.org est un sous-ensemble limité de Dyalog et ne prend pas en charge ⎕.

lirtosiast
la source

16

Octave, 26 octets

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

Parce que ( a + b * sqrt (5)) * (3 + sqrt (5)) = ( 3a + 5b ) + ( a + 3b ) * sqrt (5),

multipliant le vecteur d'entrée

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

ce qui signifie 1 = (3 + sqrt (5)) ^ 0 par matrice

| 3 5 |
| 1 3 |

semble naturel. Au lieu de ntemps de boucle , nous élevons plutôt la matrice à la puissance de npuis la multiplions par le vecteur d'entrée.

pawel.boczarski
la source

Vous vous vendez à découvert, [3 5;1 3]**input('')*[1;0]c'est 26 octets, pas 41.

orlp

3

@(n)[3 5;1 3]^n*[1;0](poignée de fonction) vous ferait économiser cinq caractères, bonne idée!

flawr

14

Python 2, 50

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

Multiplie par à 3+sqrt(5)plusieurs reprises par son action sur la paire (a,b)représentant a+b*sqrt(5). Équivaut à commencer par le vecteur colonne [1,0]et à multiplier les ntemps par la matrice [[3,5],[1,3]].

xnor
la source

12

Julia, 22 20 octets

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

Cela crée une fonction lambda qui prend un seul entier en entrée et retourne un vecteur à 2 éléments d'entiers correspondant à la solution [a, b]. Pour l'appeler, donnez-lui un nom, par exemple f=n->....

Commencez par multiplier

Expansion initiale

On peut alors traduire le côté droit de cette équation en une matrice à 2 colonnes, où la première correspond au coefficient de a et la seconde au coefficient de b :

Matrice

Multipliez cette matrice par elle-même n fois, puis multipliez à droite par le vecteur colonne (1, 0), et POOF! Sort le vecteur de solution.

Exemples:

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

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

Alex A.
la source

8

J, 20 octets

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

Multipliez le vecteur [1 0]par les [[3 5] [1 3]] ntemps matriciels .

2 octets enregistrés grâce à @algorithmshark.

Utilisation et test:

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

Vous pouvez descendre à 20 en exploitant l' analyse syntaxique adverbe tacite: +/ .*(3 5,:1 3&)&1 0.

algorithmshark

@algorithmshark Merci, mais pourquoi ça (+/@:*&(3 5,.1 3)&1 0)marche et (+/@:*&1 0&(3 5,.1 3))pas? Le deuxième ne devrait-il pas se lier correctement et le premier devrait-il être échangé?

randomra

J'ai compris, ils se lient comme je m'y attendais, mais l'extérieur &fait la mise sous tension / boucle donc vous modifiez l'entrée du côté gauche pendant la mise sous tension (contrairement à la modification normale du côté droit).

randomra

7

Pyth, 20 octets

u,+*3sGyeG+sGyeGQ,1Z

uqui est réduit en général, est utilisé ici comme boucle d'application répétée. La fonction de mise à jour est G-> ,+*3sGyeG+sGyeG, où Gest un tuple 2. Cette fonction se traduit par 3*sum(G) + 2*G[1], sum(G) + 2*G[1]. sest sum, yest *2.

isaacg
la source

J'ai choisi la réponse de @ randomra plutôt que la vôtre car la sienne a été publiée 16 minutes plus tôt, désolée.

orlp

5

APL (22)

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

Explication:

{... }⍣⎕⍨2↑1: lire un nombre et exécuter la fonction suivante autant de fois, en utilisant [1,0]comme entrée initiale.
- 2 2⍴3 5 1: la matrice [[3,5],[1,3]]
- ⍵+.×⍨: multipliez le premier nombre dans ⍵ par 3, le second par 5, et additionnez-les, c'est le nouveau premier nombre; multipliez ensuite le premier nombre dans ⍵ par 1, le second par 3 et additionnez-les, c'est-à-dire le nouveau deuxième nombre.

marinus
la source

1

Awww ouais, APL.

Nit

5

Gelée , 13 octets

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

Essayez-le en ligne!

Comment ça marche

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
la source

Non, je suis à peu près sûr que Jelly existait longtemps avant la création d'Internet: P

Conor O'Brien

1

@ Doᴡɴɢᴏᴀᴛ Pour les réponses non concurrentes, je préfère garder le nombre d'octets sur la deuxième ligne. Cela empêche la réponse de se hisser au sommet des classements et des scripts utilisateur, ce qui semble injuste.

Dennis

3

Mathematica, 31

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

alephalpha
la source

3

CJam, 21 octets

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

Essayez-le en ligne.

Comment ça marche

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
la source

3

Javascript, 63 61 octets

J'utilise une évaluation récursive du binôme: (x + y) ^ n = (x + y) (x + y) ^ {n-1}

Nouveau (merci à @ edc65)

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

Vieux

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

flawr
la source

1

Pourrait envisager de modifier votre formule. Nous n'avons plus MathJax.

Alex A.

Je pensais qu'il venait juste d'être introduit il y a quelques jours?

flawr

Oui, mais cela a gâché les extraits de pile, il a donc dû être désactivé.

Alex A.

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

quels

n=>[...Array(n)].map(_=>[x,y]=[3*x+5*y,x+3*y],y=0,x=1)[n-1]même longueur

l4m2

2

C, 114 octets

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

Cela implémente la multiplication matricielle de la manière ennuyeuse. Pour une solution plus amusante (citation: "horriblement horrible") de 238 octets, ne cherchez plus!

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

Démêlé:

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

Cela pourrait probablement être un peu raccourci. Essayez un programme de test en ligne !

BrainSteel
la source

1

Il utilise un algorithme plutôt compliqué: P

orlp

@orlp Je ne pouvais pas penser à un algorithme plus court pour cette langue. Je pensais que celui-ci fonctionnerait, mais il est devenu incontrôlable, haha. La mise en œuvre manuelle de la multiplication matricielle pourrait très bien être plus courte.

BrainSteel

1

Votez parce que c'est terriblement horrible.

kirbyfan64sos

2

k2 - 22 car

Fonction prenant un argument.

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

_mulest la multiplication matricielle, donc nous la recoupons avec la matrice (3 5;1 3), puis la frappons avec l'adverbe de puissance fonctionnelle: f/[n;x]s'applique fà x, nfois. Encore une fois, nous le curry, cette fois avec le vecteur de départ 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)

Cela ne fonctionnera pas dans Kona, car pour une raison quelconque, il f/[n;x]n'est pas correctement implémenté. Seule la n f/xsyntaxe fonctionne, donc le correctif le plus court est {x _mul[(3 5;1 3)]/1 0}à 23 caractères.

algorithmshark
la source

Sensationnel. Cette utilisation du curry est si intelligente que j'ai l'impression que ma réponse K est stupide. Quoi qu'il en soit, j'ai soulevé le problème que vous avez trouvé dans Kona sur leur traqueur de bogues .

kirbyfan64sos

Pour info, cela a été récemment corrigé à Kona .

kirbyfan64sos

2

isé, 25 octets (20 caractères)

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

J'espérais mieux, mais il y a juste trop de croisillons nécessaires pour le rendre compétent, la priorité de l'opérateur n'est pas optimale pour le golf.

Il s'attend à ce que l'entrée soit dans un emplacement de mémoire de 1 $, donc cela fonctionne:

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

Pour n = 0, le zéro est ignoré (sorties 1, au lieu de 1 0). Si c'est un problème, remplacez la finale 1par ~[2].

orion
la source

2

Sérieusement, 32 octets, sans compétition

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

Vidage hexadécimal:

2cbb34332f313260bd223b2940342af728362a2d229c6e2e58348df130606e7f

Essayez-le en ligne

Évidemment pas un concurrent pour le plus court, mais au moins la méthode est originale. (Notant qu'un tel problème indique nécessairement une séquence de Lucas, comme mentionné dans la description, ce programme génère des termes successifs des séquences en utilisant la relation de récurrence

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

quintopie
la source

1

Haskell, 41 octets

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

Exemple d'utilisation: (iterate(\(a,b)->(3*a+5*b,a+3*b))(1,0)!!) 8-> (282496,126336).

nimi
la source

1

C / C ++ 89 octets

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

Formaté:

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

Même concept:

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

Le banc d'essai:

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

Le résultat:

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
la source

Bienvenue sur le site et bonne première réponse!

DJMcMayhem

0

K, 37 octets

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

Ils sont tous les deux la même chose.

kirbyfan64sos
la source

0

Python 3, 49 octets

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

bien que sur ma machine, cela ne donne que la bonne réponse pour les entrées de la gamme 0 <= n <= 18.

Ceci implémente la formule du formulaire fermé

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

et profite du fait que la v ** npièce est petite et peut être calculée par arrondi plutôt que par calcul direct.

la source

1

Ce n'est pas une solution valide (vous devez prendre en charge n'importe quel n ), mais comme vous êtes loin d'être le plus court, je ne vois aucune raison de voter contre. C'est une bonne solution.

orlp

0

Schéma, 97 octets

(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
la source

0

C 71 octets (60 avec variables pré-initialisées)

Des possibilités pour le golf, mais juste pour prouver que C n'a pas à être "terriblement 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 les valeurs de a sont initialisées à {1,0}, nous faisons mieux.

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

Ceci utilise itérativement les mappages a-> 3a + 5b, b-> a + 3b mais en évitant une variable temporaire en calculant a à partir de la nouvelle valeur de b.

Alchymiste
la source

Votre solution déborde d'entiers pour de grandes entrées :)

orlp

@orlp - C'est C pour vous. Certes, cette solution échoue plus tôt que les autres en raison du calcul intermédiaire entre parenthèses, mais elle ne gérerait de toute façon que quelques étapes supplémentaires, sauf si je change le type de données. Vaut-il la peine de changer explicitement la question pour donner la gamme que vous comptez prendre en charge? Probablement trop tard maintenant.

Alchymist

Il n'y a pas de plage à prendre en charge, une solution appropriée devrait fonctionner pour toute entrée. En C, cela signifie que vous devrez implémenter des entiers de largeur arbitraire, désolé = /

orlp

Suggérer à la a[*a=1]=0place de*a=1,a[1]=0

plafondcat

0

(non concurrent) Gelée, 10 octets

31,53Dæ*³Ḣ

Essayez-le en ligne!

Utilise la matrice. Calcule ([[3,1], [5,3]] ** input ()) [0].

Leaky Nun
la source

Calcul (3 + sqrt (5)) ^ n exactement

Réponses:

Dyalog APL, 18 octets

Octave, 26 octets

Python 2, 50

Julia, 22 20 octets

J, 20 octets

Pyth, 20 octets

APL (22)

Gelée , 13 octets

Comment ça marche

Mathematica, 31

CJam, 21 octets

Comment ça marche

Javascript, 63 61 octets

C, 114 octets

k2 - 22 car

isé, 25 octets (20 caractères)

Sérieusement, 32 octets, sans compétition

Haskell, 41 octets

K, 37 octets

Python 3, 49 octets

Schéma, 97 octets

(non concurrent) Gelée, 10 octets