cpdef PowerSumGraph(int a, int s, int n):
    cdef int i,j,r,t
    G=Graph({})
    for i in range(1,a):
        r=i**(1/n)
        for j in range(r,s):
            t=j**n-i
            if t>0 and i<>t:
                G.add_edge(i,t)
    return G.is_connected()

sage: PowerSumGraph(13,6,2)
True
sage: PowerSumGraph(108,7,3)
True
sage: PowerSumGraph(2008,9,4)
True
sage: PowerSumGraph(49355,11,5)
True

sage: PowerSumGraph(1500000,13,6)
True