Jeszcze nieużywane pary

21

Zdefiniujmy sekwencję dodatnich liczb całkowitych. Zdefiniujemy sekwencję na liczbach parzystych, aby była podwójna w stosunku do poprzedniego terminu. Dziwne wskaźniki sekwencji będą najmniejszą dodatnią liczbą całkowitą, która nie pojawia się jeszcze w sekwencji.

Oto kilka pierwszych warunków.

1,2,3,6,4,8,5,10,7,14,9,18,11,22,12,24,13,26,15,30

Można to również traktować jako listę połączonych par (n, 2n), gdzie n jest jak dotąd najmniej niewykorzystaną liczbą całkowitą dodatnią.

Zadanie

Biorąc pod uwagę liczbę n jako dane wejściowe, obliczyć n- ty składnik w tej sekwencji.

To jest golf golfowy, więc powinieneś dążyć do zminimalizowania rozmiaru kodu źródłowego mierzonego w bajtach.

OEIS A036552

code-golf  sequence 
— Kreator pszenicy
źródło
Fakt, że nieparzyste wskaźniki sekwencji będą najmniejszą dodatnią liczbą całkowitą, która nie pojawi się jeszcze w sekwencji. jest nieistotne, prawda?
— Adám
1
Jakie pary ?
— Adám
@ Adám Nie, tak nie jest. Nie jestem pewien, co sprawia takie wrażenie, być może źle to sformułowałem.
— Wheat Wizard
1
@ Adám innym sposobem myślenia o sekwencji jest to, że składa się ona z połączonych par, (n,2n)a każda liczba pojawia się tylko raz. Każda para jest wybrana tak, aby była możliwie najmniejsza, przy jednoczesnym przestrzeganiu tego ostatniego ograniczenia.
— Martin Ender
3
2-adyczna wycena nieparzystych elementów serii jest zawsze parzysta. Może być komuś przydatny.
— CalculatorFeline

Odpowiedzi:

11

Haskell, 40 bajtów

l(a:r)=a:2*a:l[x|x<-r,x/=2*a]
(l[1..]!!)

Zero. lprzyrostowo buduje sekwencję z leniwej listy pozostałych liczb całkowitych.

— Christian Sievers
źródło
7

JavaScript (ES6), 92 82 69 67 65 bajtów

n=>(F=i=>i^n?F(a[b=i&1?2*b:(g=k=>a[k]?g(k+1):k)(1)]=-~i):b)(a={})

W jaki sposób?

Śledzimy:

  • Ostatnia wstawiona wartość b .
  • Wszystkie wcześniej napotkane wartości w tabeli odnośników a .

Wewnętrznie używamy indeksu 0 opartego I . Dziwne, a nawet zachowania są odwrócone:

  • W nieparzystych pozycjach następna wartość jest po prostu 2 * b.

  • W pozycjach parzystych używamy funkcji rekurencyjnej g () i tabeli odnośników a, aby zidentyfikować najmniejszą pasującą wartość:

    (g = k => a[k] ? g(k + 1) : k)(1)

Aby zaoszczędzić kilka bajtów, i jest inicjowany {}zamiast 0. Zmusza nas to do korzystania z:

  • i^nporównać I z n ponieważ ({}) ^ n === nnatomiast ({}) - nma wartość NaN.
  • -~izwiększyć i , ponieważ ({}) + 1wygenerowałoby ciąg.

Próbny

Pokaż fragment kodu

— Arnauld
źródło
— Kudłaty
5

Python 3 , 80 72 69 bajtów

-7 bajtów dzięki Mr. Xcoder !

f=lambda n:n and[f(n-1)*2,min({*range(n+1)}-{*map(f,range(n))})][n%2]

Wypróbuj online!

— notjagan
źródło
1
Możesz zmienić na set(...)„{* ...} dla 78 bajtów
— Mr. Xcoder,
@ Zacharý Czy odnosiłeś się do mojego komentarza? Jeśli tak, to zamiast tego można ustawić zestaw w Pythonie 3 . {*...}set(...)
— Pan Xcoder,
Komentowałem bez zastanowienia, kilka chwil później zdałem sobie sprawę, że {...for...in...}będzie więcej pożegnań.
— Zacharý
W rzeczywistości pozwoliłoby to zaoszczędzić 4 bajty, ponieważ używasz go dwa razy
— Mr. Xcoder,
— Wheat Wizard
3

PHP, 56 bajtów

while($$n=$i++<$argn)for($n*=2;$i&$$k&&$n=++$k;);echo$n;

PHP, 75 72 bajtów

for($a=range(1,$argn);$i++<$argn;)$a[~-$n=$i&1?min($a):2*$n]=INF;echo$n;

Wypróbuj online

— Tytus
źródło
3

05AB1E , 16 15 14 bajtów

1-indeksowany.
Wykorzystuje fakt, że binarna reprezentacja elementów o nieparzystych indeksach w sekwencji kończy się parzystą liczbą zer: A003159 .

Lʒb1¡`gÈ}€x¹<è

Wypróbuj online!

Wyjaśnienie

L                 # range [1 ... input]
 ʒ      }         # filter, keep only elements whose
  b               # ... binary representation
   1¡             # ... split at 1's
     `gÈ          # ... ends in an even length run
         €x       # push a doubled copy of each element in place
           ¹<è    # get the element at index (input-1)
— Emigna
źródło
3

Python 2 , 59 51 49 bajtów

f=lambda n,k=2:2/n%-3*(1-k)or f(n+~(k&-k)%-3,k+1)

Wypróbuj online!

tło

Każda dodatnia liczba całkowita n może być wyrażona jednoznacznie jako n = 2 o (n) c (n) , gdzie c (n) jest nieparzyste.

Niech ⟨a n ⟩ n> 0 mieć sekwencję spec prowokacji.

Twierdzimy, że dla wszystkich liczb całkowitych dodatnich n , o (a 2n-1 ) jest parzyste. Ponieważ o (a 2n ) = o (2a 2n-1 ) = o (a 2n-1 ) + 1 , jest to równoważne z twierdzeniem, że o (a 2n ) jest zawsze nieparzyste.

Załóżmy, że twierdzenie jest fałszywe i niech 2m-1 będzie pierwszym nieparzystym indeksem sekwencji, tak że o (a 2m-1 ) jest nieparzyste. Zauważ, że dzięki temu 2m jest pierwszym parzystym indeksem sekwencji, tak że o (a 2m-1 ) jest parzyste.

O (a 2m-1 ) jest nieparzyste i 0 nawet tak 2m-1 jest podzielna przez 2 . Z definicji, 2m-1 jest najmniejsza dodatnia jeszcze nie pojawia się w sekwencji , co oznacza, że 2m-1 /2 muszą pojawiły się wcześniej. Niech k będzie (pierwszy) indeks na 2m-1 /2 w .

Ponieważ o (a k ) = o (a 2m-1 /2) = o (a 2m-1 ) - 1 jest parzyste, minimalna liczba n oznacza, że k jest nieparzyste. To z kolei oznacza, że k + 1 = 2 a k = a 2 M 1 , w sprzeczności z definicją w 2m-1 .

Jak to działa

jeszcze przed nami

— Dennis
źródło
3

R , 70 69 65 bajtów

function(n){for(i in 2*1:n)F[i-1:0]=which(!1:n%in%F)[1]*1:2
F[n]}

Wypróbuj online!

Anonimowa funkcja, która bierze jeden argument. przyjmuje wartość Fdomyślną FALSElub 0taką, że algorytm poprawnie ocenia, że ​​w sekwencji nie ma jeszcze dodatnich liczb całkowitych.

Algorytm generuje pary w forpętli w następujący sposób (gdzie iprzechodzi od 2do 2nprzez 2):

           which(!1:n%in%l)[1]     # the missing value
                              *1:2 # keep one copy the same and double the next
l[i-1:0]=                         # store into l at the indices i-1 and i
— Giuseppe
źródło
2

Perl 6 , 50 bajtów

{(1,{@_%2??2*@_[*-1]!!first *∉@_,1..*}...*)[$_]}

Wypróbuj online!

  • 1, { ... } ... *jest leniwie generowaną nieskończoną sekwencją, w której każdy termin po pierwszym jest dostarczany przez blok kodu rozdzielany nawiasami klamrowymi. Ponieważ blok odwołuje się do @_tablicy, otrzymuje całą bieżącą sekwencję w tej tablicy.
  • Jeśli aktualna liczba elementów jest nieparzysta ( @_ % 2), mamy do generowania nawet indeksowane elementu, więc następnym elementem jest podwójna ostatni element mamy do tej pory: 2 * @_[*-1].
  • W przeciwnym razie, mamy pierwszą dodatnią liczbę całkowitą, która nie ma jeszcze pojawiają się w kolejności: first * ∉ @_, 1..*.
  • $_jest argumentem funkcji zewnętrznej. Indeksuje się w nieskończonej sekwencji, podając wartość zwracaną przez funkcję.
— Sean
źródło
1

Mathematica, 82 bajty

(s={};a=1;f=#;While[f>0,If[s~FreeQ~a,s~AppendTo~{a,2a}];a++;f--];Flatten[s][[#]])&

Wypróbuj online!

— J42161217
źródło
58 bajtów w Mathematica (chociaż prawdopodobnie powinienem po prostu opublikować osobną odpowiedź, ponieważ pomysł jest całkiem inny).
— notjagan
Czy skopiowałeś to z linku OEIS?
— J42161217,
Zmodyfikowałem go, aby pasował do zadania i bardziej grał w golfa, ale mniej więcej jest taki sam jak łącze OEIS.
— notjagan
1
@nie opublikuj nowej odpowiedzi, jeśli chcesz, i
— uznaj
1

C # (interaktywny kompilator Visual C #) , 82 bajty

x=>{int y=1;for(var s="";x>2;x-=2)for(s+=2*y+":";s.Contains(++y+""););return x*y;}

Wypróbuj online!

-6 bajtów dzięki @ASCIIOnly!

— dana
źródło
C # 8 może być na razie zbyt nowy, aby był powszechny w tłumaczach online, co dodatkowo dodaje fakt, że csi jest rzeczą mono, więc musisz poczekać, aż Mono go zaimplementuje i doda do stabilnej wersji (jeśli nie ma t już)
— tylko ASCII
niestety nie jest to łatwe do sprawdzenia tego w C #
— ASCII tylko
Użyj tego, aby rozpocząć? Ale tak, nie wydaje się to proste. docs.microsoft.com/en-us/dotnet/api/…
— dana
1
86? - nie sądzę, że :są potrzebne, ponieważ będzie to największa liczba na liście
— tylko ASCII
Również 2.0=>2f
— dana
0

Clojure, 102 bajty

#(nth(loop[l[0 1 2 3]i %](if(= i 0)l(recur(conj l(*(last l)2)(nth(remove(set l)(range))0))(dec i))))%)

Iteruje nrazy, aby zbudować sekwencję i zwraca ten nelement, 1-indeksowany.

— NikoNyrh
źródło
0

Rubinowy, 60 bajtów

->n,*a{eval"v+=1while a[v];a[v]=a[2*v]=v+v*n%=2;"*(n/2+v=1)}

0-indeksowane. Pętlujemy n/2+1czasy, generując za każdym razem dwie wartości i przechowując je, wypełniając tablicę przy ich indeksach. v+v*n%2daje wyjście, albo vczy v*2w zależności od parytetu n.

— histocrat
źródło
0

Ruby , 49 bajtów

->n{*s=t=0;s|[t+=1]==s||s<<t<<t*2until s[n];s[n]}

Zacznij od [0], dodawaj pary do tablicy, aż będziemy mieli co najmniej n + 1 elementów, a następnie weź n + 1 (na podstawie 1)

Wypróbuj online!

— GB
źródło
0

JavaScript (ES6), 60 65 bajtów

Iteracyjne rozwiązanie.

n=>eval("for(s={},i=0;n;)s[++i]?0:(s[i+i]=--n)?--n?0:i+i:i")

Mniej golfa

n=>{
  s = {}; //hashtable for used values
  for(i=0; n; )
  {
    if ( ! s[++i] )
    {
      s[i*2] = 1; // remember i*2 is already used
      if (--n)
        if (--n)
          0;
        else
          result = i*2;
      else
        result = i;
    }
  }
  return result;  
}

Test

F=
n=>eval("for(s={},i=0;n;)s[++i]?0:(s[i+i]=--n)?--n?0:i+i:i")

for (a=1; a < 50; a++)
  console.log(a,F(a))
Rozwiń fragment kodu

— edc65
źródło
0

Galaretka , 13 12 10 bajtów

ḤRọ2ḂĠZFị@

Wykorzystuje to obserwację z mojej odpowiedzi w języku Python .

Wypróbuj online!

Jak to działa

ḤRọ2ḂĠZFị@  Main link. Argument: n

Ḥ           Unhalve; yield 2n.
 R          Range; yield [1, ... , 2n].
  ọ2        Compute the order of 2 in the factorization of each k in [1, ..., 2n].
    Ḃ       Bit; compute the parity of each order.
     G      Group the indices [1, ..., 2n] by the corresponding values.
      Z     Zip/transpose the resulting 2D array, interleaving the indices of 0
            with the indices of 1, as a list of pairs.
       F    Flatten. This yields a prefix of the sequence.
        ị@  Take the item at index n.
— Dennis
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.