 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Less Than 2015 (Posted on 2015-09-22) The function f is defined on the positive integers as follows:
1. f(1) = 1, and:
2. f(2n) = f(n), if n is even, and:
3. f(2n) = 2*f(n), if n is odd, and:
4. f(2n + 1) = 2*f(n) + 1, if n is even, and:
5. 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).

 No Solution Yet Submitted by K Sengupta Rating: 4.0000 (1 votes) Comments: ( Back to comment list | You must be logged in to post comments.) re(2): computer solution -- trying to explain it Comment 3 of 3 | (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 Please log in:

 Search: Search body:
Forums (0)