Results 1 to 5 of 5

Math Help - Weird function

  1. #1
    Junior Member
    Joined
    Nov 2007
    Posts
    33

    Weird function

    Let f be a function on the positive integers defined by
    f(n)=\begin{cases}<br />
\displaystyle\frac{n}{2}&\text{if }n\text{ is even}\\<br />
n+1&\text{if }n\text{ is odd}<br />
\end{cases}
    Now let g(n) be defined as the number of times f must be applied to n for it to first equal 1.
    For example, g(2)=1 because f(2)=1 and g(5)=5 because f(f(f(f(f(5)))))=1.
    How many solutions are there to the equation g(n)=20
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Mar 2008
    Posts
    39

    Smile

    I tried doing it reverse order, and came at a guess of 524288 or 38, don't suppose you have the answer do you? =)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2007
    Posts
    33
    Quote Originally Posted by Nyoxis View Post
    I tried doing it reverse order, and came at a guess of 524288 or 38, don't suppose you have the answer do you? =)
    The answer I got was 4181, but I need some confirmation.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,818
    Thanks
    316
    Awards
    1
    Quote Originally Posted by math sucks View Post
    The answer I got was 4181, but I need some confirmation.
    I've been playing with this for a bit and found out the following.

    We may derive an expression for g(x) by considering the decomposition of x into x = 2^n + r. In this way we may derive a recursively defined series that generates a value for any g(x) in terms of n and r. I have not carried out the full treatment, but have derived the following table:
    2^n~\implies~n \text{ steps}
    2^n + 1 ~\implies~2n + 1 \text{ steps}
    2^n + 2 ~\implies~2n \text{ steps}
    2^n + 3 ~\implies~2n \text{ steps}
    2^n + 4 ~\implies~2n - 1 \text{ steps}
    2^n + 5 ~\implies~2n - 1 \text{ steps}
    2^n + 6 ~\implies~2n - 1 \text{ steps}
    2^n + 7 ~\implies~2n - 1 \text{ steps}
    2^n + 8 ~\implies~2n - 2 \text{ steps}

    I think you can guess how the pattern goes from this.

    So to find g(5), for example, we do the following: x = 5 = 2^2 + 1. This is of the form x = 2^n + 1 where n = 2. So g(5) = 2(2) + 1 = 5. Thus g(5) = 5 as expected.

    We wish to find x such that g(x) = 20. We have several possibilities just in the small table I derived above:
    20 = n \implies n = 20 \implies x = 2^{20}
    20 = 2n \implies n = 10 \implies x = 2^{10} + 2 \text{ or } x = 2^{10} + 3
    20 = 2n - 2 \implies n = 11 \implies x = 2^{11} + 8
    etc.

    So I've got g(1048576) = g(2056) = g(1027) = g(1026) as just some possibilities.

    Once you derive the general relationship you should be able to just write x in terms of n and r.

    (By the way, double check 4181; I'm getting g(4181) = 18.)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2007
    Posts
    33
    By 4181, I meant that there are 4181 many solutions to the equation g(n)=20, not that g(4181)=20. The question does not require you to find the general form of the solutions, just how many there are.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. This is weird
    Posted in the LaTeX Help Forum
    Replies: 5
    Last Post: December 18th 2010, 10:52 AM
  2. how to integrate this weird function
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 8th 2009, 12:36 AM
  3. Weird Density function
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: December 7th 2007, 05:00 PM
  4. weird one
    Posted in the Math Challenge Problems Forum
    Replies: 6
    Last Post: November 18th 2006, 05:43 PM

Search Tags


/mathhelpforum @mathhelpforum