The intution for this solution was when i was trying my hands on the Collatz conjecture, which basically is to get the series for a given number(n) by doing n/2 if even and 3n+1 if odd. Its found that the series always stops with the continuos sequence 4-2-1. For example consider the series for 21 would be 21-64-32-16-8-4-2-1-4-2-1.... There is no proof for this but for the largest number they could compute they found that the sequence always ends with 4-2-1. So how is this related to even power of 2, getting there, patience.

Now while thinking about the problem you find that for the series to converge to 4-2-1, odd n should either reach to 4 or 16 or 64 …, why not 8, 32 ? for n to reach 8,32 its predecessor in the series should be 7/3 or 31/3 which is not possible. So we observe that even powers of 2 can be written as 3n+1. This can be proved easily.

consider 2^(2n+2) => 4*(2^2n) => 3(2^2n) + (2^2n) => 3(2^2n) + 3*(2^(2n-2)) +.....+ 4 => 3(2^2n + 2^(2n-2) + ... + 1) + 1 => 3x + 1 So any even power of 2 can be written as 3n + 1

Now given any number n and we have to check if the number is a power of 2 or not, then we can square the number, substract one and check reminder with 3 is zero or not.

If u want to know more about Collatz conjecture, check out the youtube video