The function f is defined on the positive integers as follows:
- f(1) = 1, and:
- f(2n) = f(n), if n is even, and:
- f(2n) = 2*f(n), if n is odd, and:
- f(2n + 1) = 2*f(n) + 1, if n is even, and:
- f(2n + 1) = f(n), if n is odd, and:
Determine the number of positive integers n which are less than 2015 and
have the property that f(n) = f(2015).
(In reply to
re: computer solution by Jer)
Working from the function Jer found, and then toward this recursive definition:
If f(x) is defined as the binary version with strings of successive 1's replaced by a single 1 and strings of 0's replaced by a single 0, each. Then:
If n is even, f(n) ends in a single zero, and f(2n) will also end in a single zero, as the zero created by the shift left will be absorbed into however long a series of zeros n ended in. Also f(2n+1) will have a 1 appended to f(n), so that's a shift left(temporarily creating a double zero) and add of 1, which is just 2*f(n)+1.
If n is odd it ends with a binary 1. Doubling it shifts it left leaving a zero bit appended to the original f(n), so f(2n)=2*f(n). And f(2n)+1 just creates one more in any string of 1's at the end, but that's converted to a single 1 anyway, leaving f(2n+1) = f(n).
f(1) indeed is 1, and the rules allow finding f(n) for any n. QED.
Edited on September 23, 2015, 3:58 pm
|
|
Posted by Charlie
on 2015-09-23 15:56:46 |
re(2): computer solution -- trying to explain it
