TNT
I agree with Sumana's answer to Hofstadter's problem of explaining what it means for a number to be a power of two. (There is no loophole there; an odd number times an odd number always yields another odd number.) Another possibility is to write
prime(x) = not exists a such that exists b such that a!=1 and b!=1 and a*b=x.
power_of_two(b) = not exists f such that exists d such that f!=2 and prime(f) and d*f=b.
