For each positive integer n, let k(n) be the number of ones in the binary representation
of 2023 * n.
What is the minimum value of k(n)?
Bonus: Same question for 2024*n.
Source: Putnam 2023
The first digit must be 1 and the last digit must be 1.
The next question is whether only one intermediate 1 is possible.
Start by considering (2^n+1) mod2023.
Small values: {3,5,9,17,33,65,...)
The rule is that (2^(n+1)+1) mod2023 = 2*[(2^n+1) mod2023]-1, mod2023
It is now easy to complete the full congruence cycle for (2^n+1) mod2023 which has 408 terms {2,3,5,9,...2005,2011}
Next we need to look for those terms such that the residue, when deducted from 2024, is one more than a power of 2, mod2023.
These are 2^277 (residue 1767, and 2024-1767 = 257) and 2^280 (residue 1991, and 2024-1991=33). In binary, these will produce 10.....100000001, and 10....100001 respectively.
Note: There may exist smaller values of 2^n for which the intermediate 1 is larger that 2^10.
So the smallest value of k(n) is 3.
Nice problem.
Edited on March 21, 2024, 8:19 am
|
|
Posted by broll
on 2024-03-21 03:07:28 |
Some thoughts
