Getting the shortest sequence to reach a number

I want to get the shortest sequence to reach a number.

Rules:

• A[0] is always 1

• Either A[i] = A[i-1]*2 or A[i] = A[i-1]+1

For example, if my input number is 17, my output should be 6, because

A[0]=1, A[1]=2, A[2]=4, A[3]=8, A[4]=16, A[5]=17

The following code is not working properly for few inputs, such as 15.

public static int GetMinimumSequence(int n)
        {
            if (n == 1)
                return 1;

            int count = 1;
            int temp = 1;
            for (int i = 2; i = n)
                {
                    temp = temp/2;
                    temp = temp + 1;
                }
                count++;
                if(temp == n)
                    break;
            }
            return count;
        }

@CarySwoveland is on the right track. The original code and several other solutions so far get the wrong answer. For example, GetMinimumSequence(12) should not return 8, but rather 5, based on the optimal sequence 1, 2, 3, 6, 12.

One straightforward solution uses recursion:

public static int GetMinimumSequence(int n) {
    if (n <= 0) {
        throw new ArgumentOutOfRangeException();
    } else if (n == 1) {
        return 1;
    } else if ((n % 2) == 1) {
        return 1 + GetMinimumSequence(n - 1);
    } else {
        return 1 + Math.Min(GetMinimumSequence(n - 1),
                            GetMinimumSequence(n / 2));
    }
}

Add memoization to that for better performance with larger inputs. (I'll leave that to you as an exercise.) In technical terms, this solution uses dynamic programming, since the greedy algorithm leads you astray.

StackExchange Code Review Q#40910, answer score: 11