| >> |
12/17/11(Sat)13:56 No.4154074>>4153997
So here's my analysis:
Represent the input n as a binary string.
If
you ever apply the rule f(2n) = f(n) or f(2n+1) = f(n), the original
number n will be longer, in binary, than f(n). f(2n+1) = 2 f(n) + 1
means the input, 2n+1, is exactly one bit longer than f(n), and
similarly with f(2n) = 2 f(n). Therefore, if n is odd, n-1 must be even,
and if n is even, n/2 must be odd.
The strings of length 1 that
meet the criterion that f(n) is the same length as n are 1. The strings
of length 2 are exactly 10_2, since f(11_2) = f(2*1 + 1) = f(1) = 1,
which is shorter. Then the strings of length 3 which are fixed-length
have to be either 4 or 5, because f(6) or f(7) both reduce down to f(3),
which is shorter in length than 3.
Rigorously: |f(n)|<|n|, as
represented in binary, with equality iff n odd, (n-1)/2 even or n even,
n/2 odd, and |f(n/2)| = |n/2| (using integer truncation division here).
Therefore, exactly one number of each length can have this property
(because only one number of length 1 has it, and by induction if there's
a string m of length i, it's either odd or even, and a string n of
length i+1 must satisfy n/2 = m (by integer arithmetic) and n is odd if m
is even, and vice versa).
Then you can see that those are the 11
numbers up to 2011 that have the same length as their image through
function f, and in fact it's easy to check for all of them that f(n) =
n:
f(1) = 1, f(2) = 2 f(1) = 2, f(5) = 2 f(2) + 1 = 5, f(10) = 2 f(5)
= 10, f(21) = 2 f(10) + 1 = 21, and so on. I don't want to write the
other 11. |
