Ihre Aufgabe ist ziemlich einfach, berechnen Sie das n-te Element von A190810 .

Elemente von A190810 werden nach folgenden Regeln berechnet:

1. Das erste Element ist 1
2. Die Reihenfolge nimmt zu
3. Wenn xin der Sequenz vorkommt, dann 2x+1und 3x-1auch

Sie können eine 1-basierte oder eine 0-basierte Indizierung verwenden. Wenn Sie jedoch eine 0-basierte Indizierung verwenden, geben Sie dies bitte in der Antwort an.

Testfälle

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

Da dies Codegolf ist, gewinnt die kürzeste Antwort in Bytes!

Gelee , 16 Bytes

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

Sehr ineffizient. Probieren Sie es online!

Wie es funktioniert

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 Bytes

Vielleicht möchten Sie die Programme in dieser Antwort in umgekehrter Reihenfolge lesen ...

Noch langsamer und kürzer dank Dennis:

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

Probieren Sie es online aus

Dies läuft nicht so schnell, ist aber kürzer ( 83 Byte ). Durch Sortieren und Entfernen von Duplikaten bei jeder Iteration sowie durch Entfernen des ersten Elements ersparen wir mir einen Index in der Liste. Das Ergebnis ist einfach das erste Element nach nIterationen.

Vielleicht habe ich Dennis herausgolfen. : D

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]

Probieren Sie es online aus

Diese Version unten ( 88 Bytes ) läuft sehr schnell und findet das 500000. Element in ungefähr zwei Sekunden.

Es ist ziemlich einfach. Berechnen Sie die Elemente der Liste, bis es dreimal mehr Elemente als gibt n, da jedes hinzugefügte Element höchstens 2 weitere eindeutige Elemente hinzufügen kann. Entfernen Sie dann Duplikate, sortieren Sie und drucken Sie das nth-Element (null-indiziert)

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]

Probieren Sie es online aus

Python 2, 59 Bytes

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

Basierend auf der Python-Antwort von @ mbomb007 . Teste es auf Ideone .

Haskell, 76 73 69 Bytes

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

Verwendet einen 0-basierten Index. Anwendungsbeispiel: (filter t[1..]!!) 54-> 255.

Anstatt die Liste durch wiederholtes Einfügen zu erstellen 2x+1und 3x-1wie in den meisten anderen Antworten zu sehen, gehe ich alle ganzen Zahlen durch und überprüfe, ob sie 1durch wiederholtes Anwenden (x-1) / 2oder (x+1) / 3falls teilbar, auf reduziert werden können .

Haskell, 77 74 Bytes

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

Dies bietet eine Funktion afür den n-ten Eintrag. Es ist null indiziert. Alternativ a=nub$f[1]wird die ganze Liste (träge) erstellt.

Es ist eine Listenvariante von Reinhard Zumkellers SetCode.

Python 2, 88 84 Bytes

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)

Teste es auf Ideone .

Pyth, 20 bis 19 Bytes

hutS{+G,hyhGt*3hGQ0

Probieren Sie es online aus. Testsuite.

Verwendet nullbasierte Indizierung.

Brachylog , 45 Bytes

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

Berechnet N = 1000in ca. 6 Sekunden auf meinem Computer.

Dies ist 1-indiziert, z

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

Erläuterung

• Hauptprädikat:

  :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
  

• Prädikat 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
         )
  

Möglicherweise stellen Sie fest, dass wir beim Aufruf keine Eingabe an Prädikat 1 übergeben y - Yield. Aufgrund der Weitergabe von Bedingungen wird die richtige Eingabe gefunden, sobald die 1.Klausel erreicht ist, die die korrekten Eingabewerte weitergibt .

MATL, 19, 18 17 Bytes

1w:"tEQy3*qvSu]G)

Dies ist ein äußerst ineffizienter Algorithmus. Der Online-Interpreter verfügt nicht über genügend Speicher für Eingaben über 13.

Ein Byte gespart, dank Luis Mendo!

Probieren Sie es online!

Diese Version ist länger, aber effizienter (21 Bytes)

1`tEQy3*qvSutnG3*<]G)

Probieren Sie es online aus

Erläuterung:

Der logische Weg, dies zu tun, besteht darin, dem Array Elemente hinzuzufügen, bis es lang genug ist, um das i-te Element zu erfassen. So funktioniert der Effiziente. Der golferische (und ineffiziente) Weg, dies zu tun, besteht darin, die Array-Größe i- mal zu erhöhen .

Also zuerst definieren wir den Start Array: 1. Dann tauschen wir die beiden oberen Elemente aus, sodass die Eingabe oben liegt. w. Nun durchlaufen wir die Eingabe mit :". Also ich mal:

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.

Jetzt haben wir eine gigantische Reihe von Sequenzen. (Viel mehr als zur Berechnung benötigt wird) Also hören wir auf zu schleifen ]und nehmen die i-te Zahl aus diesem Array mit G)(1-indiziert)

JavaScript (ES6), 63 Byte

 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)

Wahrscheinlich gibt es aufgrund der Rekursion schnell auf.

Retina, 57

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

Probieren Sie es online!

0-indiziert. Befolgen Sie den häufig verwendeten Algorithmus: Entfernen Sie den Minimalwert aus der aktuellen Menge, rufen Sie ihn auf xund addieren Sie 2x+1und 3x-1zur Menge eine Anzahl von Malen, die der Eingabe entsprechen. Dann ist die führende Zahl das Ergebnis. Die "Menge" in Retina ist nur eine Liste, die wiederholt sortiert und so erstellt wird, dass sie nur eindeutige Elemente enthält. Der Algorithmus für Golf enthält einige raffinierte Details, die ich später erläutern werde.

Vielen Dank an Martin für die rund 20 Bytes!

Clojure, 114 108 Bytes

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

Es würde mich nicht überraschen, wenn dies um einen signifikanten Betrag reduziert werden könnte, aber die Tatsache, dass dies setnicht unterstützt wird, schadet meinem Gedankengang wirklich.

Probieren Sie das online

Version mit Leerzeichen:

#(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 Bytes

Verwendet die CP-1252- Codierung.

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

Erläuterung

$                  # 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

Probieren Sie es online für kleine Zahlen

Sehr langsam.
Verwendet eine 0-basierte Indizierung.

C ++, 102 Bytes

[](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;};

Diese Lambda-Funktion benötigt #include <map>und using std::map.

Das maphier ist nur eine Sammlung von Schlüsseln; ihre Werte werden ignoriert. Ich benutze map, um vom Kurzcode zum Einfügen zu profitieren:

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

Dank der sortierten Reihenfolge von mapwird das kleinste Element von extrahiert k.begin()->first.

Eigentlich 27 Bytes

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

Probieren Sie es online!

Dieses Programm verwendet eine 0-basierte Indizierung. Der Ansatz ist sehr brachial. Erwarten Sie daher nicht, dass er im Online-Interpreter für größere Eingaben funktioniert.

Erläuterung:

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

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

Online-Demo . Beachten Sie, dass hierbei eine auf Null basierende Indizierung verwendet wird.

Dies verwendet einen ähnlichen Ansatz wie die meisten anderen: Wenden Sie die Transformationszeiten nan und sortieren und extrahieren Sie dann das ndritte Element. Aus Gründen der Effizienz wird die Deduplizierung innerhalb der Schleife und die Sortierung außerhalb der Schleife angewendet.

Netzhaut , 48 Bytes

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

Probieren Sie es online!

Inspiriert von Nimis Antwort dachte ich, ich würde einen anderen Ansatz für Retina ausprobieren und die Rückverfolgung der Regex-Engine nutzen, um herauszufinden, ob eine bestimmte (unäre) Nummer in der Sequenz enthalten ist oder nicht. Es stellt sich heraus, dass dies mit einem 27-Byte-regulären Ausdruck festgestellt werden kann, aber die Verwendung kostet ein paar mehr, ist jedoch immer noch kürzer als der generative Ansatz.

Hier ist eine alternative 48-Byte-Lösung:

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

Und mit unary I / O können wir 42 Bytes machen, aber ich versuche das zu vermeiden und die andere Retina-Antwort verwendet auch Dezimalzahlen:

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

Ruby, 70 Bytes

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

Erläuterung

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

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

Verwendet nullbasierte Indizierung. Sehr speicherineffizient.

Erläuterung

{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

Oktave, 68 Bytes

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 Byte +1 für -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];

Ungolfed:

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];

Ich kann es wahrscheinlich besser machen, wenn ich mehr darüber nachdenke, aber das ist es, worauf ich nach nur wenigen Minuten gekommen bin. Ich habe das erste Mal Golf gespielt, also hat das ziemlich Spaß gemacht!

Vielen Dank an @Dada und @ TùxCräftîñg (und ein paar kleinere Byte-Optimierungen) für -40 Byte

JavaScript (ES6), 58

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

Weniger golfen

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
}

Prüfung

Über Zeit und Speicher: Element 500000 in ~ 20 Sekunden und 300 MB, die von meinem FireFox 64-Bit-Alpha verwendet werden

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>