def utopianTree(n):
    # Set the initial height of the tree
    height = 1
    # Let's setup a range that'll cover every cycle and iterate through it.
    for cycle in range(0, n + 1):
        # Nothing happens during the first cycle, so we skip the rest of the loop.
        if cycle == 0: continue
        # Odd cycles are 'spring', so we add height to itself, otherwise add 1.
        height += height if cycle % 2 == 1 else 1
    return height

    public static int utopianTree(int n) {
        int closestOdd = n % 2 == 0 ? n + 1: n;
        int i = ((closestOdd-1)/2) + 2;
        int res = (int)Math.pow(2, i) - 2;
        
        if(n%2 == 0) {
            res /= 2;
        }
        
        return res;
    }

function utopianTree(n) {
    let height = 1;
    for(let i=1; i <= n; i++){
        
    if(i%2 == 0){
            height++;
        }
    else  height = height * 2;
        
    }
    return height
}

function utopianTree(n) {
    let height = 1;
    for (let i = 1; i <= n; i++) {
        if (i % 2 === 0) {
            height++
        } else {
            height *= 2
        }
    }
    return height
}

def utopianTree(n):
    out = []
    for i in range(n+1):
        if i==0:
            out.append(1)
        elif i%2==0 and i!=0:
            out.append(out[-1]+1)
        else:
            out.append(out[-1]*2)
    
    return out[n]