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).

See The Solution Submitted by K Sengupta    
Rating: 4.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
re: computer solution | Comment 2 of 3 |
(In reply to computer solution by Charlie)

I can see how but can't quite explain it, but what the function does is strip off consecutive 0's in the binary expression of a number and replaces it with a single 0, then does the same with 1's.
See https://oeis.org/A090079

For example f(28)=2 because 11100 becomes 10
f(2105)=5 because 11111011111 becomes 101

So we must count the number of binary numbers of the form (1)(0)(1)
Lets go by number of binary digits (bits):
1 digit  0
2 digits 0
3 digits 1
4 digits 3
5 digits 6
6 digits 10
7 digits 15
8 digits 21
9 digits 28
10 digits 36
now 2105 has 11 decimal digits but some numbers will be too big.
But if we look by number of zeros but under 2015 we count
1 zero 4
2 zeros 5
3 zeros 5
4 zeros 5
5 zeros 5
total
11 digits 24

Summing the count of each number of bits gives 154



  Posted by Jer on 2015-09-23 09:52: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 (12)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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