Contexte

Une séquence fractale est une séquence entière où vous pouvez supprimer la première occurrence de chaque entier et vous retrouver avec la même séquence qu'auparavant.

Une telle séquence très simple s'appelle les paraphrases de Kimberling . Vous commencez avec les nombres naturels positifs:

1, 2, 3, 4, 5, 6, 7, 8, 9, ...

Ensuite, vous riffle dans quelques blancs:

1, _, 2, _, 3, _, 4, _, 5, _, 6, _, 7, _, 8, _, 9, ...

Et puis vous remplissez à plusieurs reprises les blancs avec la séquence elle-même (y compris les blancs):

1, 1, 2, _, 3, 2, 4, _, 5, 3, 6, _, 7, 4, 8, _, 9, ...
1, 1, 2, 1, 3, 2, 4, _, 5, 3, 6, 2, 7, 4, 8, _, 9, ...
1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 4, 8, _, 9, ...
1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 4, 8, 1, 9, ...

C'est notre séquence fractale! Prenons maintenant les sommes partielles:

1, 2, 4, 5, 8, 10, 14, 15, 20, 23, 29, 31, 38, 42, 50, 51, 60, ...

Mais que se passe-t-il si nous répétons ce processus? "Fractalise" la nouvelle séquence (ie les sommes partielles obtenues à partir des étapes ci-dessus):

1, _, 2, _, 4, _, 5, _, 8, _, 10, _, 14, _, 15, _, 20, _, 23, ...
1, 1, 2, _, 4, 2, 5, _, 8, 4, 10, _, 14, 5, 15, _, 20, 8, 23, ...
1, 1, 2, 1, 4, 2, 5, _, 8, 4, 10, 2, 14, 5, 15, _, 20, 8, 23, ...
1, 1, 2, 1, 4, 2, 5, 1, 8, 4, 10, 2, 14, 5, 15, _, 20, 8, 23, ...
1, 1, 2, 1, 4, 2, 5, 1, 8, 4, 10, 2, 14, 5, 15, 1, 20, 8, 23, ...

Et reprenons les sommes partielles:

1, 2, 4, 5, 9, 11, 16, 17, 25, 29, 39, 41, 55, 60, 75, 76, 96, ...

Rincez, répétez. Il s'avère que ce processus converge. Chaque fois que vous répétez ce processus, un préfixe plus grand de la séquence reste fixe. Après une quantité infinie d'itérations, vous vous retrouveriez avec OEIS A085765 .

Fait amusant: ce processus convergerait vers la même séquence même si nous ne partions pas des nombres naturels tant que la séquence d'origine commence par 1. Si la séquence d'origine commence par une autre x, nous l'obtiendrons à la x*A085765place.

Le défi

Étant donné un entier positif N, sortez le Ne élément de la séquence convergée.

Vous pouvez écrire un programme ou une fonction, en prenant une entrée via STDIN (ou l'alternative la plus proche), un argument de ligne de commande ou un argument de fonction et en sortant le résultat via STDOUT (ou l'alternative la plus proche), la valeur de retour de la fonction ou le paramètre de la fonction (out).

Vous pouvez choisir si l'indice Nest basé sur 0 ou 1.

Cas de test

La séquence commence par:

1, 2, 4, 5, 9, 11, 16, 17, 26, 30, 41, 43, 59, 64, 81, 82, 108, 117, 147, 151, 192, 203, 246, 248, 307, 323, 387, 392, 473, 490, 572, 573, 681, 707, 824, 833, 980, 1010, 1161, 1165, 1357, 1398, 1601, 1612, 1858, 1901, 2149, 2151, 2458, 2517

Donc, l'entrée 5devrait se traduire par la sortie 9.

Voici une implémentation de référence CJam naïve qui génère les premiers Nnombres (donnés Nsur STDIN). Notez que votre code ne doit renvoyer que le Nth élément, pas le préfixe entier.

CJam ( 23 22 octets)

Les sommes partielles sont données aux indices pairs de la séquence fractale, qui est A086450 . La récurrence donnée ici comme la définition de A086450 est la base de ces implémentations.

Utiliser une "pile" explicite (entre guillemets effrayants car ce n'est pas LIFO):

{),){2md~)\),>+$)}h+,}

Démo en ligne

Dissection

{         e# Anonymous function body; for clarify, pretend it's f(x)
          e# We use a stack [x_0 ... x_i] with invariant: the result is sum_j f(x_j)
  ),      e# Initialise the stack to [0 ... x]
  )       e# Uncons x, because our loop wants one value outside the stack
  {       e# Loop. Stack holds [x_0 ... x_{i-1}] x_i
    2md   e# Split x_i into (x_i)/2 and (x_i)%2
    ~)\   e# Negate (x_i)%2 and flip under (x_i)/2
    ),>   e# If x_i was even, stack now holds [x_0 ... x_{i-1}] [0 1 ... (x_i)/2]
          e# If x_i was odd, stack now holds [x_0 ... x_{i-1}] [(x_i)/2]
    +     e# Append the two arrays
    $     e# Sort to get the new stack
    )     e# Uncons the greatest element in the new stack
  }h      e# If it is non-zero, loop
          e# We now have a stack of zeroes and a loose zero
  +,      e# Count the total number of zeroes, which is equivalent to sum_j f(0)
}

À 23 octets, il existe une approche beaucoup plus efficace, avec mémoisation:

{2*1a{2md~)\){j}%>:+}j}

Démo en ligne

Python 2, 55 49 42

Je n'ai aucune idée de ce qui se passe, mais il semble difficile de battre la formule Maple de la page OEIS. Cela utilise une indexation basée sur 0.

f=lambda n,t=0:n<1or f(n/2,n%2)-~-t*f(n-1)

Merci à @PeterTaylor pour -6 octets.

Haskell, 65

s l=[0..]>>=(\i->[l!!i,s l!!i])
r=1:(tail$scanl1(+)$s r)
f n=r!!n

Modèles considérés comme nuisibles , 124

Fun<If<A<1>,Add<Ap<Fun<Ap<If<Sub<A<1>,Mul<I<2>,Div<A<1>,I<2>>>>,A<0>,A<0,1>>,Div<A<1>,I<2>>>>,A<1>>,Ap<A<0>,Sub<A<1>,T>>>,T>>

Il s'agit d'une fonction anonyme. C'est plus ou moins la même chose que mon Python répond à la formule Maple sur la page OEIS, sauf que je n'ai pas implémenté de module, j'ai donc dû utiliser nn / 2 * 2 au lieu de n% 2.

Étendu:

Fun<If<
    A<1>,
    Add<
        Ap<
            Fun<Ap<
                If<
                    Sub<
                        A<1>,
                        Mul<
                            I<2>,
                            Div<A<1>,I<2> >
                        >
                    >,
                    A<0>,
                    A<0,1>
                >,
                Div<A<1>,I<2>>
            >>,
            A<1>
        >,
        Ap<
            A<0>,
            Sub<A<1>, T>
        >
    >,
    T
>> 

Mathematica, 47 44 octets

If[#<1,1,#0[Floor@#/2]+(1-2#~Mod~1)#0[#-1]]&

Matlab 108 103

J'utilise le fait que la série souhaitée est la somme partielle de https://oeis.org/A086450

Mais la complexité de calcul de mon implémentation est loin d'être optimale, même pour cette simple récurrence.

n=input('')+1;
z=zeros(1,n);z(1)=1;
for k=1:n;
z(2*k)=z(k);
z(2*k+1)=sum(z(1:k+1));
end;
disp(sum(z(1:n)))