tło

Sekwencja 1-2-3-Tribonacciego

Wyobraź sobie przez sekundę, że możesz utworzyć sekwencję Fibonacciego, zastępując standardową formułę iteracji następującą:

Zasadniczo zamiast sumować dwa ostatnie, aby uzyskać następne, sumujesz ostatnie trzy. To jest podstawa sekwencji 1-2-3-Tribonacciego.

Kryterium Browna

Kryterium Browna stanowi, że możesz reprezentować dowolną liczbę całkowitą jako sumę elementów sekwencji, pod warunkiem że:

1. 

2. Dla wszystkich nwiększych niż 1

Co to oznacza dla wyzwania

Możesz opisać każdą dodatnią liczbę całkowitą jako sumę elementów sekwencji 1-2-3-Tribonacciego utworzonych przez następujące warunki początkowe:

Jest to znane jako, że dla każdej wartości w tej sekwencji stosunek między wyrazami nigdy nie jest większy niż 2 (stosunek wynosi średnio około 1,839).

Jak pisać w tym systemie reprezentacji numerycznej

Powiedzmy, że używasz reprezentacji little-endian. Ułóż elementy sekwencji w taki sposób:

1  2  3  6 11 20 37 68

Następnie bierzesz swój numer do reprezentacji (w naszych testach, powiedzmy, że to jest 63) i znajdujesz wartości danych 1-2-3-Tribonacci, które sumują się do 63 (najpierw używając największych wartości!) . Jeśli liczba jest częścią sumy, umieść pod nią 1, 0 jeśli nie.

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

Możesz to zrobić dla dowolnej liczby całkowitej - najpierw sprawdź, czy najpierw używasz największych wartości poniżej podanego wejścia!

Definicja (wreszcie)

Napisz program lub funkcję, która wykona następujące czynności, biorąc pod uwagę pewną dodatnią liczbę całkowitą n(zapisaną w dowolnej standardowej bazie) między 1 a maksymalną wartością twojego języka:

1. Przelicz wartość na zdefiniowaną reprezentację numeryczną 1-2-3-Tribonacciego.
2. Używając tej binarnej reprezentacji i czytaj ją tak, jakby była binarna. Oznacza to, że cyfry pozostają takie same, ale co oznaczają zmiany.
3. Weź ten numer binarny i przekonwertuj go na bazę pierwotnego numeru.
4. Wprowadź lub zwróć ten nowy numer.

Jednak dopóki dane wyjściowe są prawidłowe, nie musisz wykonywać tych kroków. Jeśli magicznie znajdziesz jakąś formułę, która jest krótsza (i matematycznie równoważna), nie krępuj się jej użyć.

Przykłady

Niech funkcja fbędzie funkcją opisaną w definicji i niech []reprezentuje podjęte kroki (jako little-endian, choć nie powinno to mieć znaczenia) (nie musisz wykonywać tego procesu, to tylko opisany proces):

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

Dzięki @theonlygusti za pomoc w golfie przy 5 bajtach

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}

Jak to działa

Po pierwsze, funkcja generuje wszystkie liczby tribonacciego, aż znajdzie jedną większą niż wartość wejściowa

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

Następnie przeszukuje listę numerów do tyłu. Jeśli liczba jest mniejsza niż wartość wejściowa, dodaje 2 ^ (indeks tej liczby) do wartości zwracanej i zmniejsza dane wejściowe o tę liczbę.

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

Wreszcie zwraca wynik.

Wypróbuj online

Python 2 , 110 102 bajtów

-3 bajty dzięki Rod (fajna sztuczka do rzucania wartości logicznej ina wartość int za +ipomocą repr `+i`działa)

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)

Wypróbuj online!

JavaScript (ES6), 97 93 bajtów

Tutaj używamy reduce()funkcji rekurencyjnej. Zakładamy, że dane wyjściowe są 31-bitowe (co jest największą niepodpisaną wielkością, z którą JS może z łatwością pracować dla operacji bitowych).

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)

Pod względem wydajności wyraźnie nie jest to zbyt wydajne.

Dla ciekawskich:

• Stosunek między liczbą połączeń F()dla N + 1reduce() iteracji iteracjami N szybko zbliża się do stałej Tribonacciego (≈ 1,83929). Dlatego każdy dodatkowy bit na wyjściu kosztuje około dwa razy więcej czasu niż poprzedni.
• Przy 31 bitach F()funkcja nazywa się dobrą 124 milionami razy.

Test

Uwaga: Wykonanie może zająć 1 lub 2 sekundy.

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

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

LinearRecurrence[{1,1,1},{1,2,3},#]generuje listę, o długości równej wejściowej, liczb tribonacci 1-2-3. ( {1,1,1}Przedstawia sumę poprzednich trzech terminów, podczas gdy {1,2,3}są wartościami początkowymi.) Następnie #~NumberDecompose~znajduje najbardziej zachłanny sposób, aby zapisać dane wejściowe jako sumę elementów listy (jest to ta sama funkcja, która rozkłada kwotę pieniężną na wielokrotności dostępne waluty, na przykład). Na koniec Fold[#+##&,...]konwertuje wynikową listę binarną na liczbę całkowitą (base-10).

Poprzednie zgłoszenie:

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

Jak to często bywa (choć nie wyżej), ta wersja gry w golfa jest super wolna na wejściach większych niż 20, ponieważ generuje (z niezoptymalizowaną rekurencją) listę plemion, których długość jest wejściowa; zastąpienie finału #bardziej rozsądnym ograniczeniem Round[2Log@#+1]skutkuje znacznie lepszą wydajnością.

Haskell, 95 bajtów

(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

Przykład użycia: f 63->104 . Wypróbuj online! .

Jak to działa: !buduje sekwencję 1-2-3-Tribonacci. Biorąc pod uwagę 1, 2a 3jako parametrów startowych, bierzemy pierwsze nelementy sekwencji. Następnie krotnie z prawej funkcji #, które odejmuje następny element ez ni ustawia bit w wartości zwracanej r, jeśli ejest potrzebna lub pozwala bitu rozbrojony. Ustawienie bitu podwaja się ri dodaje 1, a pozostawienie go rozbrojonego to tylko podwojenie.

Galaretka , 31 bajtów

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

Wypróbuj online!

Jestem prawie pewien, że istnieje O wiele krótszy sposób na osiągnięcie tego w Jelly.

W jaki sposób?

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

-2 bajty dzięki b2gills

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

Jak to działa

• Najpierw generuje sekwencję 1-2-3-Tribonacciego do pierwszego elementu większego niż wejście:

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

• Na tej podstawie znajduje podzbiór sekwencji, który składa się na dane wejściowe:

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

• Na tej podstawie konstruuje listę wartości logicznych określającą, czy każdy element sekwencji jest częścią sumy:

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

• I na koniec interpretuje tę listę wartości True = 1, False = 0 jako podstawę 2 i zwraca ją jako liczbę (podstawa 10):

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

JavaScript (ES6), 61 60 bajtów

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

Oblicza liczby 1-2-3-Tribonacciego, aż osiągnie pierwotną liczbę, a następnie, gdy rekurencja rozwija się, próbuje odjąć każdą z nich kolejno, podwajając wynik w miarę upływu czasu.

Edycja: Zapisano 1 bajt dzięki @Arnauld.

Partia, 151 148 145 bajtów

@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 mojej odpowiedzi JavaScript. Edycja: Zapisałem 3 bajty, przekazując moje argumenty podprogramu w odwrotnej kolejności, a kolejne 3 bajty, używając poszczególnych @s w każdym wierszu zamiast @echo off.

Galaretka , 19 18 17 bajtów

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

Wypróbuj online!

tło

Zamiast konwertować liczbę całkowitą na bazę 1,2,3-Tribonacciego, a następnie z wartości binarnej na liczbę całkowitą, zrobimy coś odwrotnego: konwertuje liczby całkowite na liczbę binarną, a następnie z wartości 1,2,3-podstawy Trionacciego na liczbę całkowitą, i zwracamy najwyższy, który pasuje do danych wejściowych. Można to łatwo osiągnąć.

Zilustrujemy proces wprowadzania 63 , w szczególności etap, w którym testowany jest 104 . W systemie dwójkowym, od najbardziej znaczącej do najmniej znaczącej cyfry, 104 jest równe

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

gdzie drugi rząd reprezentuje wartości pozycyjne tych cyfr.

Możemy rozszerzyć sekwencję 1,2,3-Tribonacciego w prawo, zauważając, że dodane cyfry są zgodne z tą samą rekurencyjną formułą. Dla trzech cyfr to daje

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

Teraz, aby obliczyć wartość podstawowej liczby 1,2,3-Tribonacciego, możemy użyć wzoru rekurencyjnego. Ponieważ każda liczba jest sumą trzech liczb po jej prawej stronie (w powyższej tabeli), możemy usunąć pierwszą cyfrę i dodać ją do pierwszych trzech cyfr pozostałej tablicy. Po 7 krokach, które są równe liczbie cyfr binarnych 104 , rzadko zostawiamy tylko trzy cyfry.

 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

Teraz, ponieważ pierwsza i ostatnia pozostała cyfra mają wartość pozycyjną 0 , wynikiem jest środkowa cyfra, tj . 63 .

Jak to działa

²Ç€»ċ   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.

Galaretka ( widelec ), 17 16 bajtów

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

Zaoszczędzono 1 bajt dzięki @Dennis, który grał w golfa, nawet go nie uruchamiając.

Opiera się to na rozwidleniu Galaretki, gdzie rozczarowuję, że wciąż pracuję nad wdrożeniem wydajnego atomu rozwiązania Frobeniusa. Dla tych, którzy są zainteresowani, chciałbym dopasować szybkość Mathematiki FrobeniusSolvei na szczęście wyjaśnienie ich metody znajduje się w artykule „Dokonywanie zmian i znajdowanie reprodukcji: wyważanie plecaka” Daniela Lichtblau.

Wyjaśnienie

ḣ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

DC , 110 102 bajtów

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

Cóż, wydaje się, że wielkie umysły nie myślą podobnie. Najwyraźniej algorytm, który wymyśliłem, aby obejść ograniczenia, dcjest dokładnie taki sam, jak ten zastosowany w odpowiedzi @ LliwTelrac. Ciekawy.

Wypróbuj online!

Python 2 , 93 bajty

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

To jest port mojej odpowiedzi na żelki .

Wypróbuj online!

narzędzia bash + BSD (OS X itp.), 53 bajty

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

narzędzia bash + GNU (działa również pod BSD), 59 bajtów

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

Wejścia i wyjścia w obu powyższych przypadkach są binarne.

Wypróbuj wersję GNU w TIO. (Przykład powiązany z pokazuje 111111, który ma 63 binarnie, i 1101000, który ma 104 binarnie.)

Nie sądzę, że TIO oferuje opcję BSD, ale jeśli masz dostępnego Maca, możesz wypróbować je oba. (Program 59-bajtowy jest znacznie szybszy niż program 53-bajtowy).

Niestety, seqnie można go po prostu wrzucić do rozwiązania BSD zamiast jot, ponieważ format wyjściowy dla seqjest różny dla wyjść powyżej 999999. (Zaczyna to stanowić problem dla danych wejściowych około 32, ponieważ 32 ^ 4> 1000000).

Możesz zamienić jotpowyżej seq -f%.fna, aby to działało z narzędziami GNU, ale dla tych samych 59 bajtów możesz użyć powyższego rozwiązania GNU, które jest znacznie szybsze.