Powiedzmy, że podciąg to dowolna ciągła sekcja oryginalnego łańcucha. Na przykład catjest podciąg concatenate. Powiemy, że poprawny podciąg to podciąg, który nie jest równy oryginalnemu ciągowi. Na przykład concatenatejest podciągiem, concatenateale nie jest właściwym podciągiem. (ciągi jednoznakowe nie mają odpowiednich podciągów)

Teraz zdefiniujemy sekwencję na podstawie tych terminów. N p terminu w tej sekwencji będzie najmniejsza ilość tak, że nie jest to właściwy podciąg jego binarną, która nie jest podłańcuchem wcześniejszej terminu w sekwencji. Pierwszy termin to 10.

Jako ćwiczenie pozwala wygenerować pierwsze 5 haseł. Będę pracował w trybie binarnym, aby ułatwić.

Pierwszy termin to 10. Ponieważ 11kolejna najmniejsza liczba ma tylko jeden właściwy podciąg, 1który jest również podłańcuchem 10, 11nie ma go w sekwencji. 100zawiera jednak odpowiednie podciągi, 00które nie są podciągami, 10więc 100nasz następny termin. Dalej jest ten, 101który zawiera unikalny właściwy podciąg 01dodający go do sekwencji, a następnie 110zawiera właściwy podciąg, 11który jest nowy, dodając go do sekwencji.

Teraz mamy

10, 100, 101, 110

111jest następny, ale zawiera tylko podciągi 1i 11dlatego nie jest terminem. 1000zawiera jednak 000dodanie go do sekwencji.

Oto kilka pierwszych wyrażeń dziesiętnych

2, 4, 5, 6, 8, 9, 10, 11, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 30, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 50, 54, 56, 58

Zadanie

Zarówno

• Weź n jako dane wejściowe i wygeneruj n- ty termin w tej sekwencji (0 lub 1 indeksowany)

• Ciągłe wyprowadzanie terminów sekwencji

To jest odpowiedź na golfa kodowanego w bajtach, przy czym mniej bajtów jest lepszych.

Python 3 , 88 80 78 75 bajtów

^{-6 bajtów dzięki Wheat Wizard
-2 bajty dzięki RootTwo
-3 bajtów dzięki notjagan}

s={0}
n=1
while 1:n+=1;b=f"{n:b}";p={b[1:],b[:-1]};s|=p-s and{b,print(n)}|p

Wypróbuj online!

Galaretka , 22 bajty

BẆṖ
ṄÇ;ð⁹Çḟ¥?⁹⁸‘¤ß
2ç⁸

Wypróbuj online!

Mathematica, 116 110 bajtów

x={};f=Subsequences[#~IntegerDigits~2]&;Do[MemberQ[Most@f@n,s_/;FreeQ[f/@x,s,2]]&&x~AppendTo~Echo@n,{n,2,∞}]

Nieskończenie wyświetla parametry sekwencji.

Wyjaśnienie

x={};

x to lista terminów do tej pory.

f=Subsequences[#~IntegerDigits~2]&

fjest Functionliczbą całkowitą i zwraca całą Subsequencesjej podstawową 2reprezentację (w tym pustą listę {}i pełną listę IntegerDigitssamych siebie).

Do[...,{n,2,∞}]

Oszacuj ...wartość nod 2do ∞.

...&&x~AppendTo~Echo@n

Jeśli ...tak False, to drugi argument funkcji And( &&) nigdy nie jest oceniany. Jeśli ...tak True, to Echo@ndrukuje i zwraca n, a następnie AppendTolistę x.

MemberQ[Most@f@n,s_/;FreeQ[f/@x,s,2]]

Chcemy sprawdzić, czy niektóre poprawne podłańcuchy nnie są podciągami jakiegokolwiek poprzedniego terminu w sekwencji. Most@f@nlista odpowiednich podciągi o n, my wtedy sprawdzić, czy istnieją jakieś podciągi s_który jest MemberQz tej listy, tak że lista f/@xwykazów podciągi poprzednich pod względem sekwencji jest FreeQz sna poziomie 2.

Mathematica, 109 94 bajtów

s={};Do[!SubsetQ[s,(t=Subsequences@IntegerDigits[i,2])[[2;;-2]]]&&(s=s~Join~t;Echo@i),{i,∞}]

Ciągłe wyprowadzanie terminów sekwencji

Specjalne podziękowania dla @ngenisis za -15 bajtów

Mathematica, 123 bajty

(s=r={};For[i=2,i<2#,i++,If[!ContainsAll[s,(t=Subsequences@IntegerDigits[i,2])[[2;;-2]]],s=s~Join~t;r~AppendTo~i]];r[[#]])&

Weź n jako dane wejściowe i wygeneruj n-ty termin w tej sekwencji (1 indeksowany)

Wejście

[1000]

wynik

1342

Pyth , 20 bajtów

u+G
fP-Fm.:.Bd)+TG1Y

Spowoduje to wydrukowanie sekwencji w nieskończoność. W związku z tym można go używać tylko offline.

Objaśnienie (spacja jest znakiem nowej linii):

u+G fP-Fm.:.Bd)+TG1Y
u                  Y    Apply the following function to the previous output
                        until it stops changing (or forever, in this case),
                        starting with the empty list
    f             1     Find the first positive integer where
               +TG      The integer prepended to the current list
        m               Map to
           .Bd          Convert to binary
         .:   )         Form all subsequences
      -F                Fold the filter-out function over the list
                        This iteratively removes all subsequences already seen
                        from the candidate
     P                  Remove the last subsequence which is the whole number.
   (newline)            Print that first integer
 +G                     Prepend that first integer to the list

Pyth , 20 bajtów

.V2I-=ZP.:jb2)Yb=+YZ

Wypróbuj online!

Haskell, 172 bajty

import Data.List
b 0=""
b n=b(n`div`2)++(show$n`mod`2)
s=nub.(tails=<<).inits
p x=s x\\[x]
n(_,l)x|(p.b)x\\l/=[]=(x,l++(s.b)x)|1<2=(0,l)
filter(>1)$fst<$>scanl n(1,[])[1..]

Wypróbuj online.

Wyjaśnienie

Kod generuje sekwencję w sposób ciągły.

• bzwraca binarną reprezentację Intjako jakoString
• s zwraca wszystkie podciągi ciągu
• p zwraca wszystkie poprawne podłańcuchy łańcucha
• n jest funkcją, która jest stosowana iteracyjnie i zwraca krotkę zawierającą:
  • bieżący element, jeśli jest on członkiem sekwencji, w przeciwnym razie 0
  • lista wszystkich podciągów do sprawdzenia dla wszystkich następujących liczb
• wreszcie scanljest używany do wywoływania nw kółko, a jego wynik jest filtrowany, aby zawierał tylko elementy większe niż 1

Oto nieco bardziej czytelna wersja przed golfem:

import Data.List

binary :: Int -> String
binary 0=""
binary n|(d,r)<-divMod n 2=binary d++["01"!!r]

substrings :: String -> [String]
substrings xs = nub$inits xs>>=tails

properSubstrings :: String -> [String]
properSubstrings xs = substrings xs\\[xs]

sb  = substrings.binary
psb = properSubstrings.binary

g = scanl step (1,[]) [1..]
  where step (_,l) x | psb x \\ l /= [] = (x,l++sb x)
                     | otherwise        = (0,l)

f=filter(>1)$fst<$>g

JavaScript, 57 bajtów

for(x=1;;x++)/^10|10(00)*$/.test(x.toString(2))&&alert(x)

alert=x=>{if(x>100)throw 'Let we stop here.';document.write(x+'<br/>');};

for(x=1;;x++)/^10|10(00)*$/.test(x.toString(2))&&alert(x)

Napiszmy podaną liczbę nw postaci binarnej, a następnie:

• Jeśli numer zaczyna się od 10, n musi w sekwencji:
  • usuń pierwszy 1, pozostały ciąg binarny nie może być widoczny, ponieważ n jest najmniejszą liczbą, która może zawierać taki ciąg
• Jeśli numer zaczyna się od 11 :
  • Usuwając pierwszy 1z niego, pozostały ciąg binarny (przekażmy go, jak 1xtrzeba zobaczyć, ponieważ:
    • numer 1xjest w sekwencji, lub
    • liczba 1x0jest w sekwencji, ponieważ zawiera unikatowy ciąg podrzędny1x
  • Jeśli jest nieparzyste (kończy się na 1), nie może być w sekwencji, ponieważ:
    • ( n - 1) / 2 w sekwencji, lub
    • ( n - 1) w sekwencji, ponieważ zawiera unikatowy ciąg podrzędny ( n - 1) / 2
  • Jeśli jest parzyste (kończy się na 0), to jest w sekwencji iff n / 2 nie jest w sekwencji
    • z tym samym pomysłem n / 2 nie znajduje się w sekwencji iff n / 2 jest nieparzysty lub n / 4 jest w sekwencji

Wniosek:

binarna postać liczby zaczyna się od 10lub kończy, 1po której następuje liczba nieparzysta 0. Lub opisz w regex: x match /^10|10(00)*$/.