Twoje zadanie jest dość proste, oblicz n-ty element A190810 .

Elementy A190810 są obliczane zgodnie z następującymi zasadami:

1. Pierwszym elementem jest 1
2. Sekwencja rośnie
3. Jeśli xwystępuje w sekwencji, to 2x+1i 3x-1również

Możesz użyć indeksowania 1 lub 0, ale jeśli używasz indeksowania 0, powiedz to w odpowiedzi.

Przypadki testowe

a(1) = 1
a(2) = 2
a(3) = 3
a(4) = 5
a(5) = 7
a(10) = 17
a(20) = 50
a(30) = 95
a(55) = 255

Ponieważ jest to kod-golf, wygrywa najkrótsza odpowiedź w bajtach!

Galaretka , 16 bajtów

×3’;Ḥ‘$;
1Ç¡ṢQ³ị

Bardzo nieefektywne. Wypróbuj online!

Jak to działa

1Ç¡ṢQ³ị   Main link. Argument: n (integer)

1         Set the return value to 1.
 Ç¡       Execute the helper link n times.
   Ṣ      Sort the resulting array.
    Q     Unique; deduplicate the sorted array.
     ³ị   Retrieve its n-th element.


×3’;Ḥ‘$;  Helper link. Argument: A (array)

×3        Multiply all elements of A by 3.
  ’       Decrement the resulting products.
      $   Combine the two links to the left into a monadic chain.
    Ḥ     Unhalve; multiply all elements of A by 2.
     ‘    Increment the resulting products.
   ;      Concatenate 3A-1 and 2A+1.
       ;  Concatenate the result with A.

Python 2, 88 83 72 bajty

Możesz przeczytać programy w tej odpowiedzi w odwrotnej kolejności ...

Wolniej i krócej dzięki Dennisowi:

L=1,;exec'L+=2*L[0]+1,3*L[0]-1;L=sorted(set(L))[1:];'*input()
print L[0]

Wypróbuj online

To nie działa tak szybko, ale jest krótsze ( 83 bajty ). Sortując i usuwając duplikaty każdej iteracji, a także usuwając pierwszy element, usuwam potrzebę indeksowania na liście. Wynik jest po prostu pierwszym elementem po niteracjach.

Mogłem wygrać z Dennisiem. :RE

L=[1]
n=input()
while n:L+=[2*L[0]+1,3*L[0]-1];n-=1;L=sorted(set(L))[1:]
print L[0]

Wypróbuj online

Ta wersja poniżej ( 88 bajtów ) działa naprawdę szybko, znajdując 500 000-ty element w około dwie sekundy.

To całkiem proste. Oblicz elementy listy, aż będzie ich trzy razy więcej niż n, ponieważ każdy dodany element może dodać maksymalnie 2 więcej unikalnych elementów. Następnie usuń duplikaty, posortuj i wydrukuj nelement th (indeksowany od zera).

L=[1]
i=0
n=input()
while len(L)<3*n:L+=[2*L[i]+1,3*L[i]-1];i+=1
print sorted(set(L))[n]

Wypróbuj online

Python 2, 59 bajtów

t={1}
exec'm=min(t);t=t-{m}|{2*m+1,3*m-1};'*input()
print m

Na podstawie odpowiedzi Python @ mbomb007 . Przetestuj na Ideone .

Haskell, 76 73 69 bajtów

a#b=mod a b<1&&t(div a b)
t x=x<2||(x-1)#2||(x+1)#3
(filter t[1..]!!)

Korzysta z indeksu 0. Przykład użycia: (filter t[1..]!!) 54-> 255.

Zamiast budować listę poprzez wielokrotne wstawianie 2x+1i 3x-1jak widać w większości innych odpowiedzi, przeglądam wszystkie liczby całkowite i sprawdzam, czy można je zredukować 1poprzez wielokrotne stosowanie (x-1) / 2lub (x+1) / 3czy można je podzielić.

Haskell, 77 74 bajty

import Data.List
i=insert
f(x:y)=x:f(i(2*x+1)$i(3*x-1)y)
a=(!!)(nub$f[1])

Zapewnia to funkcję adla n-tego wpisu. Jest indeksowany na zero. Alternatywnie a=nub$f[1]utworzy całą listę (leniwie).

Jest to wariant listy Setkodu Reinharda Zumkellera .

Python 2, 88 84 bajtów

g=lambda k:g(k%2*k/2)|g(k%3/2*-~k/3)if k>1else k
f=lambda n,k=1:n and-~f(n-g(k),k+1)

Przetestuj na Ideone .

Pyth, 20 19 bajtów

hutS{+G,hyhGt*3hGQ0

Wypróbuj online. Zestaw testowy.

Używa indeksowania zerowego.

Brachylog , 45 bajtów

:1-I,?:?*:1ydo:Im.
1.|:1-:1&I(:3*:1-.;I*:1+.)

Oblicza N = 1000za około 6 sekund na moim komputerze.

Jest to indeks 1, np

run_from_file('code.brachylog',1000,Z).
Z = 13961 .

Wyjaśnienie

• Główny predykat:

  :1-I,               I = Input - 1
       ?:?*           Square the Input
           :1y        Find the first Input*Input valid outputs of predicate 1
              do      Remove duplicates and order
                :Im.  Output is the Ith element
  

• Predykat 1:

  1.                  Input = Output = 1
  |                   Or
  :1-:1&I             I is the output of predicate 1 called with Input - 1 as input
         (            
           :3*:1-.      Output is 3*I-1
         ;            Or
           I*:1+.       Output is 2*I+1
         )
  

Możesz zauważyć, że nie przekazujemy żadnych danych wejściowych do predykatu 1, kiedy dzwonimy y - Yield. Z powodu propagacji ograniczeń znajdzie właściwe wejście po dotarciu do 1.klauzuli, która będzie propagować prawidłowe wartości wejściowe.

MATL, 19, 18 17 bajtów

1w:"tEQy3*qvSu]G)

Jest to niezwykle nieefektywny algorytm. W tłumaczu internetowym zabrakło pamięci dla danych wejściowych większych niż 13.

Jeden bajt zapisany, dzięki Luisowi Mendo!

Wypróbuj online!

Ta wersja jest dłuższa, ale bardziej wydajna (21 bajtów)

1`tEQy3*qvSutnG3*<]G)

Wypróbuj online

Wyjaśnienie:

Logicznym sposobem na to jest dodawanie elementów do tablicy, dopóki nie będzie wystarczająco długa, aby chwycić ity element. Tak działa ten wydajny. Golfy (i nieefektywne) sposób to zrobić, to po prostu zwiększyć rozmiar tablicy : i razy.

Więc po pierwsze, możemy zdefiniować tablicę startowy: 1. Następnie zamieniamy dwa górne elementy, aby dane wejściowe były na górze. w. Teraz zapętlamy wejście za pomocą :". Więc I czasy:

t             %Duplicate our starting (or current) array.
 EQ           %Double it and increment
   y          %Push our starting array again
    3*q       %Multiply by 3 and decrement
       v      %Concatenate these two arrays and the starting array
        Su    %Sort them and remove all duplicate elements.

Teraz mamy gigantyczny zestaw sekwencji. (O wiele więcej niż potrzeba do obliczenia) Więc przestajemy ]zapętlać i pobieramy i-tą liczbę z tej tablicy za pomocą G)(1-indeksowane)

JavaScript (ES6), 63 bajty

 f=(n,a=[1],i=0)=>a[i++]?--n?f(n,a,a[i*2]=a[i*3-2]=1):i:f(n,a,i)

Prawdopodobnie szybko się poddaje z powodu rekurencji.

Retina, 57

^.+
$*¶¶1
¶¶(1(1*))
¶1$1$1¶$2$1$1
O`
}`(¶1+)\1\b
$1
G2`
1

Wypróbuj online!

0-indeksowane. Postępuje zgodnie z często stosowanym algorytmem: usuń minimalną wartość z bieżącego zestawu, wywołaj ją xi dodaj 2x+1i 3x-1do zestawu liczbę razy równą wejściowej, to wynikiem będzie liczba wiodąca. „Zestaw” w Retinie jest tylko listą, która jest wielokrotnie sortowana i zawiera tylko unikalne elementy. Do algorytmu golfa dodano kilka podstępnych elementów, które wyjaśnię, gdy będę miał więcej czasu.

Ogromne podziękowania dla Martina za grę w golfa około 20 bajtów!

Clojure, 114 108 bajtów

#(loop[a(sorted-set 1)n 1](let[x(first a)](if(= n %)x(recur(conj(disj a x)(+(* 2 x)1)(-(* 3 x)1))(inc n)))))

Nie zdziwiłbym się, gdyby można było to znacznie pograć w golfa / zmniejszyć, ale setnie wspieranie nth naprawdę zraniło mój tok myślenia.

Wypróbuj online

Wersja ze spacjami:

#(loop [a (sorted-set 1)
        n 1]
  (let [x (first a)]
    (if (= n %)
      x
      (recur (conj (disj a x) (+ (* 2 x) 1) (- (* 3 x) 1)) (inc n))
      )))

05AB1E, 18 17 bajtów

Wykorzystuje kodowanie CP-1252 .

$Fз>s3*<)˜Ù}ï{¹è

Wyjaśnienie

$                  # initialize with 1
 F          }      # input number of times do
  Ð                # triplicate current list/number
   ·>              # double one copy and add 1
     s3*<          # multiply one copy by 3 and subtract 1
         )˜Ù       # combine the 3 lists to 1 list and remove duplicates
             ï{    # convert list to int and sort
               ¹è  # take the element from the list at index input

Wypróbuj online dla małych liczb

Bardzo wolno.
Wykorzystuje indeksowanie 0.

C ++, 102 bajty

[](int i){int t;map<int,int>k;for(k[1];i--;k.erase(t))t=k.begin()->first,k[t*2+1],k[t*3-1];return t;};

Ta funkcja lambda wymaga #include <map>i using std::map.

mapTutaj jest po prostu zbiorem kluczy; ich wartości są ignorowane. Używam map, aby skorzystać z krótkiego kodu do wstawienia:

k[1]; // inserts the key 1 into the map

Dzięki posortowanej kolejności mapnajmniejszy element jest wydobywany przez k.begin()->first.

Właściwie 27 bajtów

╗1#╜`;;2*1+)3*1@-#++╔S`n╜@E

Wypróbuj online!

Ten program używa indeksowania opartego na 0. Podejście to jest bardzo brutalne, więc nie oczekuj, że zadziała w tłumaczu online przy większych nakładach.

Wyjaśnienie:

╗1#╜`;;2*1+)3*1@-#++╔S`n╜@E
╗                            save input (n) in register 0
 1#                          push [1]
   ╜                         push n
    `;;2*1+)3*1@-#++╔S`n     do the following n times:
     ;;                        make two copies of the list
       2*1+                    apply 2x+1 to each element in one copy
           )3*1@-              and 3x-1 to each element in the other copy
                 #             workaround for a weird list bug
                  ++           append those two lists to the original list
                    ╔S         uniquify and sort
                        ╜@E  get the nth element (0-indexed)

CJam (25 bajtów)

ri1a1${{_2*)1$3*(}%_&}*$=

Demo online . Zauważ, że używa to indeksowania zerowego.

To stosuje podobne podejście do większości: zastosuj nczasy przekształceń, a następnie posortuj i wyodrębnij ten nelement. Jako ukłon w stronę wydajności deduplikacja jest stosowana wewnątrz pętli, a sortowanie odbywa się na zewnątrz pętli.

Siatkówka , 48 bajtów

.+
$*
+1`^(((!*)!(!|\3)(?=\3!1))*!)1|\b
!$1
-2`.

Wypróbuj online!

Zainspirowany odpowiedzią nich pomyślałem, że spróbuję zastosować inne podejście do Retiny, korzystając z cofania się silnika regex, aby dowiedzieć się, czy którykolwiek (jednoznaczny) numer jest w sekwencji, czy nie. Okazuje się, że można to ustalić za pomocą wyrażenia regularnego o wielkości 27 bajtów, ale korzystanie z niego kosztuje kilka więcej, ale nadal jest krótsze niż podejście generatywne.

Oto alternatywne 48-bajtowe rozwiązanie:

.+
$*
{`1\b
1!
}T`1``1((!*)!(!|\2)(?=!\2$))*!$
!

I przy użyciu jednoargumentowego We / Wy możemy zrobić 42 bajty, ale staram się tego uniknąć, a druga odpowiedź Retina również używa dziesiętnych:

1\b
1!
}T`1``1((!*)!(!|\2)(?=!\2$))*!$
!
1

Rubinowy, 70 bajtów

->n{a=*1
n.times{a<<a.map{|i|([2*i+1,3*i-1]-a).min||1.0/0}.min}
a[-2]}

Wyjaśnienie

->n{
    # Magical, golfy way of initializing an array. Equivalent to a = [1].
    a=*1
    n.times{
        # Generate the next element in the sequence, by...
        a<<
            # ... finding the minimal term that will appear at some point.
            a.map{|i|
                ([2*i+1,3*i-1]-a).min||1.0/0
            }.min
    }
    # We generated n+1 elements, so we'll take the *second* to last one.
    a[-2]
}

J, 31 bajtów

{1(]]/:~@~.@,3&*,&:<:2*>:)^:[~]

Używa indeksowania zerowego. Bardzo nieefektywna pamięć.

Wyjaśnienie

{1(]]/:~@~.@,3&*,&:<:2*>:)^:[~]  Input: n
                              ]  Identity function, gets n
 1                               The constant 1
  (                      )^:[~   Repeat n times with an initial array a = [1]
                       >:          Increment each in a
                     2*            Multiply by 2 to get 2a+2
             3&*                   Multiply each in a by 3 to get 3a
                 &:<:              Decrement both x and y to get 2a+1 and 3a-1
                ,                  Join them
    ]                              Identity function, gets a
            ,                      Join a with 2a+1 and 3a-1
         ~.@                       Take the distinct values
     /:~@                          Sort up
   ]                               Return the sorted list
{                                Select the value from the list at index n and return it

Oktawa, 68 bajtów

function r=a(n)s=1;for(i=1:n)r=s(i);s=union(s,[r*2+1 r*3-1]);end;end

Perl, 173 132 bajtów +1 dla -n = 133

sub c{my$a=pop;return($a==1||($a%2&&c(($a-1)/2))?1:$a%3!=2?0:$a%3==2?c(($a+1)/3):1)}while($#b<$_){$i++;@b=(@b,$i)if c$i}say$b[$_-1];

Nie golfowany:

my @array = ();
my $n = <>;
sub chk {
    my $a = shift;
    return 1 if ($a == 1);
    if ($a % 2 == 0) {
        if ($a % 3 != 2) {
            return 0;
        } else {
            return chk(($a + 1) / 3);
        }
    } else {
        if (chk(($a - 1) / 2) == 0) {
            if ($a % 3 != 2) {
                return 0;
            } else {
                return chk(($a + 1) / 3);
            }
        } else {
            return 1
        }
    }
}
my $i = 1;
while ($#array < $n-1) {
    push(@array,$i) if (chk($i) == 1);
    $i++;
}
print $array[$n];

Prawdopodobnie poradziłbym sobie lepiej, gdybym się nad tym zastanowił, ale to właśnie wymyśliłem po kilku minutach. Mój pierwszy raz grałem w golfa, więc było całkiem fajnie!

Dzięki @Dada i @ TùxCräftîñg (i kilku drobnych optymalizacji bajtów) dla -40 bajtów

JavaScript (ES6), 58

n=>(a=>{for(;n;)a[++i]?a[i-~i]=a[3*i-1]=--n:0})([i=0,1])|i

Mniej golfa

n=>{
  a=[];
  a[1] = 1;
  for(i = 0; n;)
  {
    ++i
    if (a[i])
    {
      a[2*i+1] = 1;
      a[3*i-1] = 1;
      --n;
    }
  }
  return i
}

Test

O czasie i pamięci: element 500000 w ~ 20 sekund i 300 MB używane przez mój FireFox 64-bitowy alfa

F=
n=>(a=>{for(;n;)a[++i]?a[i-~i]=a[3*i-1]=--n:0})([i=0,1])|i

function test() {
  var n=+I.value, t0=+new Date
  O.textContent = F(n)
  console.log((+new Date-t0)/1000,'sec')
}  

test()

#I { width:5em}

<input id=I type=number value=10 oninput="test()"> 
<span id=O></span>