tło

Fraktali sekwencja stanowi sekwencje liczb całkowitych, gdzie można usunąć pierwsze wystąpienie każdej liczby całkowitej, a kończy się z tej samej kolejności, jak wcześniej.

Bardzo prosta taka sekwencja nazywa się parafrazami Kimberling . Zaczynasz od dodatnich liczb naturalnych:

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

Następnie przeglądasz puste pola:

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

A następnie wielokrotnie wypełniasz puste pola samą sekwencją (w tym puste):

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

To nasza sekwencja fraktalna! Teraz weźmy częściowe sumy:

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

Ale co jeśli powtórzymy ten proces? „Fraktalizuj” nową sekwencję (tj. Częściowe sumy uzyskane z powyższych kroków):

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

I ponownie weź częściowe sumy:

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

Spłucz, powtórz. Okazuje się, że proces ten jest zbieżny. Za każdym razem, gdy powtórzysz ten proces, większy prefiks sekwencji pozostanie stały. Po nieskończonej liczbie iteracji otrzymujesz OEIS A085765 .

Ciekawostka: ten proces zbiegnie się w tę samą sekwencję, nawet jeśli nie zaczniemy od liczb naturalnych, dopóki początkowa sekwencja zacznie się 1. Jeśli oryginalna sekwencja zaczyna się od innej x, otrzymalibyśmy x*A085765zamiast tego.

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą N, Nwyślij element th zbieżnej sekwencji.

Możesz napisać program lub funkcję, przyjmując dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Możesz wybrać, czy indeks Nma wartość 0 czy 1.

Przypadki testowe

Sekwencja zaczyna się od:

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

Więc wejście 5powinno dać wynik 9.

Oto naiwna implementacja CJam, która generuje pierwsze Nliczby (podane Nna STDIN). Zauważ, że twój kod powinien zwracać tylko ten Nelement, a nie cały prefiks.

CJam ( 23 22 bajtów)

Sumy częściowe podane są przy parzystych indeksach sekwencji fraktalnej, czyli A086450 . Podana tam powtarzalność jako definicja A086450 stanowi podstawę tych wdrożeń.

Używając wyraźnego „stosu” (w przestraszonych cytatach, ponieważ nie jest to LIFO):

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

Demo online

Sekcja

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

Przy 23 bajtach istnieje znacznie bardziej wydajne podejście z zapamiętywaniem:

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

Demo online

Python 2, 55 49 42

Nie mam pojęcia, co się dzieje, ale ciężko jest pokonać formułę Maple ze strony OEIS. Korzysta z indeksowania opartego na 0.

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

Dzięki @PeterTaylor za -6 bajtów.

Haskell, 65

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

Szablony uważane za szkodliwe , 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>>

To anonimowa funkcja. Jest mniej więcej taki sam, jak mój Python odpowiada na formułę klonu na stronie OEIS, tyle że nie wdrożyłem modułu, więc musiałem użyć nn / 2 * 2 zamiast n% 2.

Rozszerzony:

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 bajtów

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

Matlab 108 103

Korzystam z faktu, że pożądana seria jest częściową sumą https://oeis.org/A086450

Ale złożoność obliczeniowa mojej implementacji jest daleka od optymalnej, nawet w przypadku tej prostej rekurencji.

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