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.
=> 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