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)