Contexte

La séquence 1-2-3-Tribonacci

Imaginez une seconde que vous pourriez faire une séquence de fibonacci en remplaçant la formule d'itération standard par ce qui suit:

Fondamentalement, au lieu de additionner les deux derniers pour obtenir le suivant, vous additionnez les trois derniers. C'est la base de la séquence 1-2-3-Tribonacci.

Critère de Brown

Le critère de Brown indique que vous pouvez représenter n'importe quelle valeur entière comme une somme de membres d'une séquence à condition que:

1. 

2. Pour tout nsupérieur à 1,

Ce que cela signifie pour le défi

Vous pouvez décrire tout entier positif comme une somme de membres de la séquence 1-2-3-Tribonacci formée par les conditions initiales suivantes:

Ceci est connu car, pour chaque valeur de cette séquence, le rapport entre les termes n'est jamais supérieur à 2 (le rapport s'établit en moyenne à environ 1,839).

Comment écrire dans ce système de représentation numérique

Disons que vous utilisez une représentation peu endienne. Alignez les membres de la séquence comme suit:

1  2  3  6 11 20 37 68

Ensuite, vous prenez votre nombre pour être représenté (pour nos tests, disons que c'est 63) et trouvez les valeurs des 1-2-3-Tribonacci données qui totalisent 63 (en utilisant les plus grandes valeurs en premier!) . Si le nombre fait partie de la somme, mettez un 1 en dessous, 0 sinon.

1  2  3  6 11 20 37 68
0  0  0  1  0  1  1  0

Vous pouvez le faire pour n'importe quel entier donné - vérifiez simplement que vous utilisez d'abord les plus grandes valeurs sous votre entrée donnée!

Définition (enfin)

Écrivez un programme ou une fonction qui fera ce qui suit étant donné une entrée entière positive n(écrite dans n'importe quelle base standard) entre 1 et la valeur maximale de votre langue:

1. Convertissez la valeur dans la représentation numérique définie de 1-2-3-Tribonacci.
2. Utilisez cette représentation de type binaire et lisez-la comme si elle était binaire. Cela signifie que les chiffres restent les mêmes, mais ce qu'ils signifient change.
3. Prenez ce nombre binaire et convertissez-le en base du nombre d'origine.
4. Sortez ou renvoyez ce nouveau numéro.

Cependant, tant que la sortie est valide, vous n'avez pas besoin de suivre ces étapes. Si vous trouvez comme par magie une formule plus courte (et mathématiquement équivalente), n'hésitez pas à l'utiliser.

Exemples

Soit la fonction fêtre la fonction décrite par la définition, et []représentons les étapes prises (en petit-boutien, même si cela ne devrait pas avoir d'importance) (vous n'avez pas besoin de suivre ce processus, c'est juste le processus décrit):

>>> f(1)
[1]
[1]
[1]
1

>>> f(5)
[5]
[0, 1, 1]
[6]
6

>>> f(63)
[63]
[0, 0, 0, 1, 0, 1, 1]
[104]
104

Javascript 117 111 octets

Merci à @theonlygusti pour avoir aidé le golf sur 5 octets

x=>{r=0;a=[1,2,3];i=1;while(a[++i]<x)a[i+1]=a[i]+a[i-1]+a[i-2];for(;x;i--)if(x>=a[i]){r+=1<<i;x-=a[i]}return r}

Comment ça fonctionne

Tout d'abord, la fonction génère tous les nombres de tribonacci jusqu'à ce qu'elle en trouve un de plus que l'entrée

a=[1,2,3];i=1;for(;a[++i]<x;)a[i+1]=a[i]+a[i-1]+a[i-2];

Ensuite, il inverse la recherche dans la liste des numéros. Si un nombre est inférieur à l'entrée, il ajoute 2 ^ (index de ce nombre) à la valeur de retour et réduit l'entrée de ce nombre.

for(;x;i--)if(x>=a[i]){r+=1<<i;x-=a[i]}

Enfin, il renvoie le résultat.

Essayez-le en ligne

Python 2 , 110 102 octets

-3 octets grâce à Rod (astuce pour lancer un booléen idans un int avec +ipour que le repr `+i`fonctionne)

n=input()
x=[3,2,1]
r=''
while x[0]<n:x=[sum(x[:3])]+x
for v in x:i=n>=v;n-=v*i;r+=`+i`
print int(r,2)

Essayez-le en ligne!

JavaScript (ES6), 97 93 octets

Ici, nous utilisons reduce()une fonction récursive. Nous supposons que la sortie est de 31 bits (ce qui est de toute façon la plus grande quantité non signée avec laquelle JS peut facilement travailler pour les opérations au niveau du bit).

n=>[...Array(x=31)].reduce(p=>(c=(F=k=>k<4?k:F(--k)+F(--k)+F(--k))(x--))>n?p:(n-=c,p|1<<x),0)

En termes de performances, ce n'est clairement pas très efficace.

Pour les curieux:

• Le rapport entre le nombre d'appels à F()N + 1 reduce()itérations vs N itérations converge rapidement vers la constante de Tribonacci (≈ 1.83929). Par conséquent, chaque bit supplémentaire dans la sortie coûte environ deux fois plus de temps que le précédent.
• Avec 31 bits, la F()fonction est appelée 124 millions de fois.

Tester

NB: Cela peut prendre 1 ou 2 secondes.

let f =

n=>[...Array(x=31)].reduce(p=>(c=(F=k=>k<4?k:F(--k)+F(--k)+F(--k))(x--))>n?p:(n-=c,p|1<<x),0)

console.log(f(63))

Mathematica, 78 74 octets

Fold[#+##&,#~NumberDecompose~Reverse@LinearRecurrence[{1,1,1},{1,2,3},#]]&

LinearRecurrence[{1,1,1},{1,2,3},#]génère une liste, de longueur égale à l'entrée, des nombres tribonacci 1-2-3. (Le {1,1,1}représente la somme des trois termes précédents, tandis que {1,2,3}sont les valeurs initiales.) #~NumberDecompose~Trouve ensuite la manière la plus gourmande d'écrire l'entrée sous la forme d'une somme d'éléments de la liste (c'est la même fonction qui décomposerait un montant monétaire en multiples de les devises disponibles, par exemple). Enfin, Fold[#+##&,...]convertit la liste binaire résultante en un entier (base-10).

Soumission précédente:

Fold[#+##&,#~NumberDecompose~Reverse@Array[If[#<4,#,Tr[#0/@(#-Range@3)]]&,#]]&

Comme c'est souvent le cas (mais pas ci-dessus), cette version golfée est super lente sur des entrées supérieures à 20 environ, car elle génère (avec une récursion non optimisée) une liste de tribus dont la longueur est l'entrée; le remplacement de la finale #par une borne plus raisonnable Round[2Log@#+1]donne de bien meilleures performances.

Haskell, 95 octets

(a!b)c=a:(b!c)(a+b+c)
e#(r,c)|c-e<0=(2*r,c)|1<2=(2*r+1,c-e)
f n=fst$foldr(#)(0,n)$take n$(1!2)3

Exemple d'utilisation: f 63-> 104. Essayez-le en ligne! .

Comment ça marche: !construit la séquence 1-2-3-Tribonacci. Étant donné 1, 2et 3comme paramètres de départ, nous prenons les premiers néléments de la séquence. Ensuite , nous plions de la fonction droite #qui soustrait l'élément suivant ede net définit le bit de la valeur de retour rsi eest nécessaire ou laisse le unset bits. Régler le bit est doubler ret ajouter 1, le laisser non réglé est juste doubler.

Gelée , 31 octets

S=³
3RUµḣ3S;µ<³Ạµ¿µŒPÇÐfṀe@ЀµḄ

Essayez-le en ligne!

Je suis presque certain qu'il existe un moyen BEAUCOUP plus court d'y parvenir dans Jelly.

Comment?

S=³ - Link 1, compare sum to input: list
S   - sum
  ³ - 3rd command line argument which is 1st program argument.
 =  - equal?

3RUµḣ3S;µ<³Ạµ¿µŒPÇÐfṀe@ЀµḄ - Main link: n
3RU                         - range(3) upended -> [3,2,1]
   µ    µ   µ¿              - while
         <³                 - less than input (vectorises)
           Ạ                - all?
    ḣ3S;                    -     head(3), sum, and concatenate
                                  [3,2,1] -> [6,3,2,1] -> [11,6,3,2,1] -> ...
              µ             - monadic chain separation, call the result x
               ŒP           - power set of x - e.g. for [6,3,2,1] -> [[],[6],[3],[2],[1],[6,3],[6,2],[6,1],[3,2],[3,1],[2,1],[6,3,2],[6,3,1],[6,2,1],[3,2,1],[6,3,2,1]]
                  Ðf        - filter keep
                 Ç          -     last link (1) as a monad (those that sum to the input)
                    Ṁ       - maximum (e.g. an input of 63 would yield [[37,20,6],[37,20,3,2,1]], the maximum of which is [37,20,6], the one with the largest numbers used)
                         µ  - monadic chain separation (to have x as the right argument below)
                     e@Ѐ   - exists in with reversed arguments mapped over x (e.g. [37,20,6] with x = [68,37,20,11,6,3,2,1] yields [0,1,1,0,1,0,0,0])
                          Ḅ - convert from binary to integer.        

Perl 6 , 93 91 octets

-2 octets grâce à b2gills

{my@f=1,2,3,*+*+*...*>$^n;sum @f».&{$_~~any first *.sum==$n,@f.combinations}Z*(2 X**^∞)}

Comment ça fonctionne

• Tout d'abord, il génère la séquence 1-2-3-Tribonacci jusqu'au premier élément plus grand que l'entrée:

  my @f = 1, 2, 3, *+*+* ... * > $^n;

• Sur cette base, il trouve le sous-ensemble de la séquence qui s'ajoute à l'entrée:

  first *.sum==$n, @f.combinations

• Sur cette base, il construit une liste de booléens spécifiant si chaque élément de la séquence fait partie de la somme:

  @f».&{$_~~any ...}

• Et enfin, il interprète cette liste de valeurs True = 1, False = 0 comme base 2 et la renvoie comme un nombre (base 10):

  sum ... Z* (2 X** ^∞)

JavaScript (ES6), 61 60 octets

n=>(g=(x,y,z)=>(n>x&&g(y,z,x+y+z)*2)+!(n<x||![n-=x]))(1,2,3)

Calcule les nombres 1-2-3-Tribonacci jusqu'à ce qu'ils atteignent le nombre d'origine, puis au fur et à mesure que la récursivité se déroule, essaie de soustraire chacun à son tour, doublant le résultat au fur et à mesure.

Edit: 1 octet enregistré grâce à @Arnauld.

Lot, 151 148 145 octets

@set/ar=0,n=%1
@call:c 3 2 1
@echo %r%
@exit/b
:c
@set/as=%1+%2+%3
@if %n% gtr %3 call:c %s% %*
@set/ar*=2
@if %n% geq %3 set/an-=%3,r+=1

Port de ma réponse JavaScript. Edit: enregistré 3 octets en passant mes arguments de sous-programme dans l'ordre inverse et 3 autres octets en utilisant des @s individuels sur chaque ligne au lieu de @echo off.

Gelée , 19 18 17 octets

Ḣx3+
BÇL¡2ị
²Ç€»ċ

Essayez-le en ligne!

Contexte

Au lieu d'essayer de convertir un entier en base 1,2,3-Tribonacci, puis de binaire en entier, nous ferons le contraire: convertir des entiers en binaire, puis de base 1,2,3-Trionacci en entier, et retourner le plus élevé qui correspond à l'entrée. Cela se fait facilement.

Nous allons illustrer le processus pour l'entrée 63 , en particulier l'étape où 104 est testé. En binaire, du chiffre le plus significatif au moins significatif, 104 est égal à

 1  1  0  1  0  0  0
37 20 11  6  3  2  1

où la deuxième ligne représente les valeurs de position de ces chiffres.

Nous pouvons étendre la séquence 1,2,3-Tribonacci vers la droite, en observant que les chiffres ajoutés répondent à la même formule récursive. Pour trois chiffres mre, cela donne

 1  1  0  1  0  0  0  0  0  0
37 20 11  6  3  2  1  0  1  0

Maintenant, pour calculer la valeur du nombre de base 1,2,3-Tribonacci, nous pouvons utiliser la formule récursive. Puisque chaque nombre est la somme des trois nombres à sa droite (dans le tableau ci-dessus), nous pouvons supprimer le premier chiffre et l'ajouter aux trois premiers chiffres du tableau restant. Après 7 étapes, ce qui équivaut au nombre de chiffres binaires de 104 , nous sommes rarement partis avec seulement trois chiffres.

 1  1  0  1  0  0  0  0  0  0
37 20 11  6  3  2  1  0  1  0

    2  1  2  0  0  0  0  0  0
   20 11  6  3  2  1  0  1  0

       3  4  2  0  0  0  0  0
      11  6  3  2  1  0  1  0

          7  5  3  0  0  0  0
          6  3  2  1  0  1  0

            12 10  7  0  0  0
             3  2  1  0  1  0

               22 19 12  0  0
                2  1  0  1  0

                  41 34 22  0
                   1  0  1  0

                     75 63 41
                      0  1  0

Maintenant, puisque le premier et le dernier chiffre restant ont tous deux la valeur de position 0 , le résultat est le chiffre du milieu, c'est-à-dire 63 .

Comment ça fonctionne

²Ç€»ċ   Main link. Argument: n

²       Yield n². Since 1.839² = 3.381921 > 2, the range [1, ..., n²] will contain
        the answer. Better bounds, at the cost of additional bytes are possible.
 Ç€     Map the the second helper link over [1, ..., n²].
   »    Take the maximum of n and each result.
    ċ   Count the occurrences of n.


BÇL¡2ị  Second helper link. Left argument: k. Right argument: n

B       Convert k to binary. Let's call the result A.
  L     Length; count the number of binary digits. Let's call the result l.
 Ç ¡    Apply the first helper link l times to A.
    2ị  Retrieve the second element.


Ḣ×3+    First helper link. Argument: A (array)

Ḣ       Head; pop and yield the first element of A.
 x3     Repeat it thrice.
   +    Add the result, component by component, to the beheaded A.

Gelée ( fourchette ), 17 16 octets

ḣ3S;µ¡
3RṚdzæFṪḄ

Enregistré 1 octet grâce à @Dennis qui l'a joué sans même l'exécuter.

Cela repose sur une fourchette de Jelly où je travaille décevant toujours sur la mise en œuvre d'un atome de résolution Frobenius efficace. Pour ceux qui sont intéressés, je voudrais faire correspondre la vitesse de Mathematica FrobeniusSolveet heureusement il y a une explication de leur méthode dans le document "Making Change and Finding Repfigits: Balancing a Knapsack" de Daniel Lichtblau.

Explication

ḣ3S;µ¡  Helper link. Input: a list
    µ   Create monadic chain
ḣ3        Take the first 3 items
  S       Sum
   ;      Prepend to the list
     ¡  Repeat it n (initial argument from main) times

3RṚdzæFṪḄ  Main link. Input: integer n
3          The constant 3
 R         Range. Makes [1, 2, 3]
  Ṛ        Reverse. Makes [3, 2, 1]
   Ç       Call the helper link on that list.
           Generates the first (n+3) 123-Tribonacci values in reverse
    ³      Get n
     æF    Frobenius solve for n using the first n 123-Tribonacci values in reverse
       Ṫ   Tail. Take the last value. The results of Frobenius solve are ordered
           where the last result uses the least
        Ḅ  Unbinary. Convert digits from base 2 to base 10

cc , 110 102 octets

?se1sa2sb3sc_1sf[laddSdlbdsalcdsb++sclf1+sfle>y]dsyx0sk[lk2lf^+skler-se]sr[Lddle!<rlf1-dsf0!>z]dszxlkp

Eh bien, semble que les grands esprits ne se rencontrent. Apparemment, l'algorithme que j'ai trouvé pour contourner les limites de dcest par coïncidence exactement le même que celui utilisé dans la réponse de @ LliwTelrac. Intéressant.

Essayez-le en ligne!

Python 2 , 93 octets

n=input();y=k=n*n
while y>n:
 x=y=z=0;k-=1
 for t in bin(k):x+=t=='1';x,y,z=y+x,z+x,x
print k

Ceci est un port de ma réponse Jelly .

Essayez-le en ligne!

utilitaires bash + BSD (OS X, etc.), 53 octets

jot $[2#$1**4]|egrep -v '[2-9]|11(1|$)'|sed $[2#$1]!d

utilitaires bash + GNU (fonctionne également sous BSD), 59 octets

seq -f2o%.fp $[2#$1**2]|dc|egrep -v '11(1|$)'|sed $[2#$1]!d

L'entrée et la sortie dans les deux ci-dessus sont en binaire.

Essayez la version GNU sur TIO. (L'exemple lié à illustre l'entrée de 111111, qui est 63 en binaire, et la sortie de 1101000, qui est de 104 en binaire.)

Je ne pense pas que TIO propose une option BSD, mais si vous avez un Mac disponible, vous pouvez les essayer tous les deux. (Le programme de 59 octets est beaucoup plus rapide que le programme de 53 octets.)

Malheureusement, seqne peut pas simplement être déposé dans la solution BSD à la place de jot, car le format de sortie de seqest différent pour les sorties supérieures à 999999. (Cela commence à être un problème pour les entrées autour de 32, puisque 32 ^ 4> 1000000.)

Vous pouvez remplacer jotci-dessus par seq -f%.fpour que cela fonctionne avec les utilitaires GNU, mais pour les mêmes 59 octets, vous pouvez utiliser la solution GNU ci-dessus, qui est beaucoup plus rapide.