fundo

Uma sequência fractal é uma sequência inteira, na qual é possível remover a primeira ocorrência de cada número inteiro e terminar com a mesma sequência de antes.

Uma sequência muito simples é chamada de paráfrases de Kimberling . Você começa com os números naturais positivos:

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

Então você riffle em alguns espaços em branco:

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

E então você preenche repetidamente os espaços em branco com a própria sequência (incluindo os espaços em branco):

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, ...

Essa é a nossa sequência fractal! Agora vamos pegar as somas parciais:

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

Mas e se iterarmos esse processo? "Fractalize" a nova sequência (ou seja, as somas parciais obtidas nas etapas acima):

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, ...

E pegue as somas parciais novamente:

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

Enxágüe, repita. Acontece que esse processo converge. Sempre que você repetir esse processo, um prefixo maior da sequência permanecerá fixo. Após uma quantidade infinita de iterações, você terminaria com o OEIS A085765 .

Curiosidade: esse processo convergiria para a mesma sequência, mesmo que não partíssemos dos números naturais, desde que a sequência original comece 1. Se a sequência original começar com qualquer outrox , x*A085765obteríamos.

O desafio

Dado um número inteiro positivo N, produza o Nth elemento da sequência convergida.

Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e emitindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).

Você pode escolher se o índice N é baseado em 0 ou 1.

Casos de teste

A sequência começa com:

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

Portanto, a entrada 5deve resultar em saída 9.

Aqui está uma implementação de referência ingênua do CJam que gera os primeiros Nnúmeros (fornecidos Nno STDIN). Observe que seu código deve retornar apenas o Nelemento th, não o prefixo inteiro.

CJam ( 23 22 bytes)

As somas parciais são fornecidas nos índices pares da sequência fractal, que é A086450 . A recorrência dada como a definição de A086450 é a base para essas implementações.

Usando uma "pilha" explícita (entre aspas, porque não é LIFO):

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

Demonstração online

Dissecação

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

Aos 23 bytes, há uma abordagem muito mais eficiente, com a memória:

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

Demonstração online

Python 2, 55 49 42

Eu não tenho idéia do que está acontecendo, mas parece difícil vencer a fórmula do Maple na página OEIS. Isso usa indexação baseada em 0.

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

Graças a @PeterTaylor por -6 bytes.

Haskell, 65

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

Modelos considerados prejudiciais , 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>>

Esta é uma função anônima. É mais ou menos o mesmo que minha resposta em Python à fórmula do Maple na página OEIS, exceto que eu não implementei o módulo, então tive que usar nn / 2 * 2 em vez de n% 2.

Expandido:

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 bytes

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

Matlab 108 103

Estou usando o fato de que a série desejada é a soma parcial de https://oeis.org/A086450

Mas a complexidade computacional da minha implementação está longe de ser ideal, mesmo para essa simples recorrência.

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