find the shortest addition chain for n

find_addition_chain.go

package main

import (
	"fmt"
	"sort"
)

// for play.golang.org
// https://play.golang.org/p/xJqi8EPIfSi
func main() {
	n := 15
	result5 := findAdditionChain(n)
	fmt.Println("addition chain of ", n, " => ", result5, " - steps: ", len(result5)-1)
}

// find the shortest addition chain for n
func findAdditionChain(n int) (result []int) {
	for {
		if odd(n) {
			if n == 1 {
				break
			}
			n = n - 1
			result = append(result, n)
		} else {
			n = n / 2
			result = append(result, n)
		}
	}

	sort.Ints(result)
	return
}

func odd(n int) bool {
	if n&0x1 == 1 {
		return true
	}
	return false
}