(This may be asking way too much: I don't even know how to prove that the floor of 2^n / n is odd for infinitely many values of n.)
thinking about this some more, the technique i described shows this easily. let p be an odd prime, or even a pseudoprime to base 2. we will try to find such n of the form 2^k p . for k >= 0 , we have the congruence 2^(2^k p) = 2^2^k mod 2(2^k p) . thus, for the desired floor to be odd, it is sufficient to have 2^2^k >= 2^k p and 2^2^k < 2(2^k p) , which means that p must be in the range 2^(2^k - k - 1) < p <= 2^(2^k - k) . for each k >= 2 , there are primes in that range, by the theorem often called "bertrand's postulate". examples: 2^2 * 3 , 2^3 * 17, 2^4 * 2465 , ... (2465 is pseudoprime to base 2.) mike