Print the intersection of sequences
Python 3, 590 639 characters

from itertools import count as C
D=lambda n,t='1':bin(n).count(t)
Y=range
def O():
 for n in C(0):yield from bin(n)[2:]
def B():
 s=i=0
 while 1:
  i+=s
  for j in Y(i,i+s+1):yield j
  s+=2;i+=s-1
def s(i):return D(i)==1
def F():
 a=[1]*3
 for n in C(3):a+=[a[n-a[n-1]]+a[n-a[n-2]]];yield a[-1]
L,R=input().split()
J=[x for x,U in zip([F(),(n for n in C(0)if s(D(n,'0')-1)and s(D(n))),B(),(i for i,c in enumerate(O())if'1'&gt;c)],"{0:04b}".format(int(L)))if U&gt;'0']
X=[set()for _ in J]
M=[]
Z=int(R);K=1
while len(M)&lt;Z:
 for x,j in zip(X,J):x.add(next(j))
 for _ in Y(K):X[0].add(next(J[0]));K+=1
 M=X[0]
 for x in X:M=M&amp;x
print(sorted(M)[:Z])


This is the straight-forward solution: use generators to define each of the infinite sequences, and so long as the intersection isn't large enough, add a step to each sequence.

To account for the non-monotonically-increasing Hofstadter sequence: at each step I generate twice as many for that sequence, e.g. 1, then 2, 4, 8, 16, 32, etc. I think that satisfies the bound stated in the question, and it's still fast enough for all the test cases presented there.