Python 2, 88 83 72 bytes
You may want to read the programs in this answer in reverse order...
Slower and shorter still, thanks to Dennis:
L=1,;exec'L+=2*L[0]+1,3*L[0]-1;L=sorted(set(L))[1:];'*input()
print L[0]
Try it online
This doesn't run as fast, but is shorter (83 bytes.) By sorting and removing duplicates each iteration, as well as removing the first element, I remove the need for an index into the list. The result is simply the first element after n
iterations.
I may have out-golfed Dennis. :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]
Try it online
This version below (88 bytes) runs really fast, finding the 500000th element in about two seconds.
It's pretty simple. Compute elements of the list until there are three times more elements than n
, since every element added may add at most 2 more unique elements. Then remove duplicates, sort, and print the n
th element (zero-indexed.)
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]
Try it online
x ϵ A → (2*x) + 1 ϵ A
andx ϵ A → (3*x)-1 ϵ A
, whereϵ
means "is a member of" and→
can be understood as "implies". \$\endgroup\$