def C(n,k):
    return fac(n+1,n+k)*(n-k+1)//(fac(0,k))
def fac(k,n):
    f=1
    for i in range(k+1,n+1):
        f*=i
    return f

def P(n):
    L=set([])
    i=2
    while i**2 <= n:
        p=2
        while i**p <= n:
            m=i**p
            L.add(m)
            p+=1
        i+=1
    return L

def intrt(x,r):
    m=r
    n=0
    while m-n > 1:
        k=(m+n)//2
        kx=k**x
        if kx > r:
            m = k
        elif kx == r:
            return k
        else:
            n=k
    return n

def intlog4(r):
    i=1
    while r/(4**i) >1:
        i+=1
    return i

def g(c,r):
    if c==2:
        i= int(intrt(2,2*r+2)-1)
    elif c >= 3:
        i= int(intrt(3,6*r)-3)
    while C(i,c) < r:
        i+=1
    return i

def gg(s,c,r):
    n=s
    x=C(n,c)
    while x > r:
        x=(x*(n+1)*(n-c))/((n+c)*(n-c+1))
        n+=(-1)
    return n

def h(r):
    i=intlog4(r)
    x=C(i,i-1)
    while x < r:
        x=(x*2*(2*i+1))/(i+2)
        i+=1
    return i

def R(c,r):
    m=h(r)
    s=g(c,r)
    S=set()
    j=c
    while j<=m:
        S.add(C(s,j))
        j+=1
        s=gg(s,j,r)
    return S

def U(c,r): #c is column where checking begins
    U=[]
    L=P(r)
    for i in L:
        S=R(c,i)
        for j in S:
            if j==i:
                U.append(i)
                break
    U.sort()
    return U

print("perfect powers less than five billion appearing more than once on the Catalan Triangle ")
print U(2,5000000000)