Solving a simple code puzzle in Swift

Georgina loves making up weird sequences. Here is her latest: “1 2 4 8 10 20 22 44 46 92 94 188 190 380…” Write a program that finds the sum of the first 150 numbers in Georgina’s series.

There are three parts to the problem and a hidden one you will recognise when implementing.

• Figuring out that sequence doubles and adds two.
• Writing code to follow that sequence 150 times
• Summing the numbers in the sequence.

Once you have that, the naïve solution looks like this:

func georginaSum() -> Int {
    var current = 1
    var sum  = 0
    
    for i in 0 ..< 150 {
        sum += current
        if i % 2 == 0 {
            current *= 2
        } else {
            current += 2
        }
    }
    return sum
}

That will compile cleanly, but will not run – it will crash, because the number it generates is too big for Swift’s integers. Swift won’t tell you that’s why it crashed, of course, so instead you’ll get this one: EXC_BAD_INSTRUCTION (code=EXC_I386_INVOP, subcode=0x0).

However, even unsigned 64-bit integers are too small to hold the solution’s number. Keep in mind that the sequence is 150 items, of which half are produced through doubling, so you have 75 doubles. The largest number an unsigned 64-bit integer can hold is 18,446,744,073,709,551,615 – big, but still over 10,000 times too small for our needs.

You could thing about using Double to solve this challenge and Playground will print out “3.40010386766614e+23”. Annoyingly, Swift prints instances of Double using scientific notation, but we can print the full number using a string formatter, like this:

print(String(format: "%.0f", georginaSum()))

With that you will see the following output 340010386766614455386112. Nice… But hold on! The sum contains only even numbers and one. So the sum should be an a odd number – out result is WRONG! Floating point arithmetic found another victime…

Remember Swift Decimal that computes number in endless precision. This will give you the final correct result: 340010386766614455385653.

Last but not least this puzzle could be solved in a much “swifter” way. Nice or too complicated? What do you think?

struct GeorginaSequence: Sequence, IteratorProtocol {
 
    var current: Decimal = 1
    var multiply = true
    
    mutating func next() -> Decimal? {
        defer {
            if multiply {
                current *= 2
            } else {
                current += 2
            }
            multiply =  !multiply
        }
        return current
    }
    
}

print(GeorginaSequence().prefix(150).reduce(0) { $0 + $1 })