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

(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