[Mathgod]

Originally Posted by psyang

This problem was part of an IMO (International Math Olympiad) problem. It requires a bit more math than some of the others I've posted, but I hope you try it as it has a neat idea behind it.

Define a function f over all positive integers as:

f(1) = 1
f(3) = 3
f(2n) = f(n)
f(4n+1) = 2f(2n+1) - f(n)
f(4n+3) = 3f(2n+1) - 2f(n)

Under which conditions does f(n) = n?

Spoiler!

Click for solution attempt:

Spoiler!

Tried replacing f(x) with x in the final 2 lines. The first one evaluates to n=1, so x=5 which implies n=5 as one of the solutions.

The 2nd one appears to be generally true.

So my guess for the solution is n=1, n=5, and n ≡ 3 mod 4

Edit: just realized the 2nd last line is generally true for powers of 2. So include all numbers that are 1 larger than powers of 2 in the solution.

n=1, n = 2^p + 1 for all integer p, and n ≡ 3 mod 4

Edit: that's probably wrong too because n=11 doesnt work in the final equation. Weird behaving function to say the least! Am I kind of on the right track at least?