All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Less Than 2015 (Posted on 2015-09-22) Difficulty: 3 of 5
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:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information