Antecedentes

Una secuencia fractal es una secuencia de enteros donde puede eliminar la primera aparición de cada entero y terminar con la misma secuencia que antes.

Una secuencia muy simple de este tipo se llama paráfrasis de Kimberling . Empiezas con los números naturales positivos:

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

Luego, revuelves algunos espacios en blanco:

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

Y luego rellena repetidamente los espacios en blanco con la secuencia misma (incluidos los espacios en blanco):

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

Esa es nuestra secuencia fractal! Ahora tomemos las sumas parciales:

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

Pero, ¿qué pasa si iteramos este proceso? "Fractalice" la nueva secuencia (es decir, las sumas parciales obtenidas de los pasos anteriores):

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

Y tome nuevamente las sumas parciales:

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

Enjuague, repita. Resulta que este proceso converge. Cada vez que repita este proceso, un prefijo más grande de la secuencia permanecerá fijo. Después de una cantidad infinita de iteraciones, terminaría con OEIS A085765 .

Dato curioso: este proceso convergería a la misma secuencia incluso si no comenzáramos desde los números naturales siempre que la secuencia original comience con 1. Si la secuencia original comienza con cualquier otra x, obtendríamos en su x*A085765lugar.

El reto

Dado un entero positivo N, genera el Nelemento th de la secuencia convergente.

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), valor de retorno de la función o parámetro de función (out).

Puede elegir si el índice Nestá basado en 0 o 1.

Casos de prueba

La secuencia comienza con:

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

Entonces la entrada 5debería dar como resultado la salida 9.

Aquí hay una ingenua implementación de referencia de CJam que genera los primeros Nnúmeros (dados Nen STDIN). Tenga en cuenta que su código solo debe devolver el Nelemento th, no el prefijo completo.

CJam ( 23 22 bytes)

Las sumas parciales se dan en los índices pares de la secuencia fractal, que es A086450 . La recurrencia dada allí como la definición de A086450 es la base de estas implementaciones.

Usando una "pila" explícita (entre comillas de miedo porque no es LIFO):

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

Demostración en línea

Disección

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

Con 23 bytes hay un enfoque mucho más eficiente, con la memorización:

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

Demostración en línea

Pitón 2, 55 49 42

No tengo idea de lo que está sucediendo, pero parece difícil superar la fórmula de Maple de la página OEIS. Esto usa indexación basada en 0.

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

Gracias 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

Plantillas consideradas dañinas , 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 es una función anónima. Es más o menos lo mismo que mi respuesta de Python la fórmula Maple en la página OEIS, excepto que no implementé el módulo, por lo que tuve que usar nn / 2 * 2 en lugar 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

Estoy usando el hecho de que la serie deseada es la suma parcial de https://oeis.org/A086450

Pero la complejidad de cálculo de mi implementación está lejos de ser óptima, incluso para esta simple recurrencia.

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