What is known about the parity of floor of 2^n / n , for general values of n? Some information is given

a small observation: it seems that this is equivalent to knowing the remainder of 2^n modulo 2n ; if the remainder is 0, 1, 2, ... , n - 2 or n - 1 , then floor(2^n / n) is even, while if the remainder is n, n + 1, n + 2, ... , 2n - 2 or 2n - 1 , then floor(2^n / n) is odd. perhaps this formulation makes the problem more tractable; it certainly *looks* more promising. of course, the odd remainders cannot occur. more generally, if n = 2^k m , where m is odd, then the remainder modulo 2^(k+1) m is a multiple of 2^(k+1) , so it "suffices" to know the remainder modulo m , by the chinese remainder theorem. unfortunately, it does not appear immediately obvious how to determine from the remainder modulo m , whether the remainder modulo 2^(k+1) m is in {0, 1, ... , 2^k m - 1} .

The entry in the OEIS mentions that the parity is always even when n is prime; this is a nice little application of the binomial theorem. E.g., for n = 5, (1+1)^5 = 1+5+10+10+5+1, so the floor of 2^5 / 5 is 1+2+2+1, which is even.

that's cute. that also holds for any pseudoprime to base 2, by the above remarks. indeed, if n is such a pseudoprime, then 2^n = 2 mod 2n . mike