Georgina's Sequence

adder.swift

//Playground
typealias StringBinary = String

///Converts a UInt to a binary string representation
func binary(_ v:UInt,_ rest:StringBinary="")->StringBinary {
  switch v {
  case v where v == 0:
    return "0" + rest
  case v where v == 1:
    return "1" + rest
  default:
    return binary(v >> 1,  "\(v % 2)" + rest)
  }
}
binary(0x3)
binary(0x4)
binary(0x5)
binary(0x6)




///Adds two string binary numbers
func addBinary(_ shortest:StringBinary,_ possiblyLonger:StringBinary, _  rest:StringBinary = "", carry:Bool=false)->StringBinary{

  //make sure shortest is at least as short as the other
  guard shortest.count <= possiblyLonger.count else {
    //print("swapping")
    return addBinary(possiblyLonger,shortest,rest,carry:carry)
  }

  //end when carry and places exhausted
  let longer = possiblyLonger
  guard longer.count > 0 else {
      guard !carry else {
        return addBinary("0", "1", rest, carry: false)
      }
      return rest //tail recursion
  }

  //ensure equal length
  let shorter = shortest
  guard shorter.count == longer.count else {
    return addBinary("0"+shorter,longer,rest,carry:carry)
  }

  //print("Adding \(shorter) and \(longer) [rest:\(rest), carry:\(carry)]")

  let shorterLast = String(shorter.last!)
  let longerLast = String(longer.last!)

  let shorterValue = Int(shorterLast)!
  let longerValue = Int(longerLast)!
  let carryValue = carry ? 1 : 0

  let sum = shorterValue + longerValue + carryValue

  let nextDigit = { onesDigit, carryBit in
    return addBinary(String(shorter.dropLast()), String(longer.dropLast()),onesDigit + rest, carry:carryBit)
  }

  switch sum {
  case 0:
    return nextDigit("0",false)
  case 1:
    return nextDigit("1",false)
  case 2:
    return nextDigit("0",true)
  case 3:
    return nextDigit("1",true)
  default:
    fatalError("there should only be 1 and 0 in these: \(shorter), \(longer)")
  }

}

///returns the nth (1 indexed) in her sequence
func georginasNth(_ n:UInt, rest:StringBinary = "") -> StringBinary{
  switch n{
  case n where n <= 1:
    return binary(1) + rest
  case n where n == 2:
    return binary(2)
  case n where n == 3:
    return binary(4)
  case n where n == 4:
    return binary(8)
  case n where n % 2 == 0:
    //print("shift g(\(n-1))<<1")
    return georginasNth(n-1) + "0" //mult 2 by shifting
  default:
    //print("add 2 g(\(n-1))")
    return georginasNth(n-1).dropLast(2) + "10" //For this particular sequence, this is the same as adding 2 (once past the first couple)
  }
}


//let originalSequence = [1,2,4,8,10,20,22,44,46, 92, 94, 188, 190, 380]


//print (addBinary("101","10"))

//addBinary("111110","000001")

//addBinary("11111101001010110","000001")

//addBinary("111110","1000100101001000100101")



print("Checking binary encoding")
for n in (1...150){
  let mine = binary(UInt(bitPattern:n))
  let theirs = String(n,radix:2)
  guard mine == theirs else {
    fatalError("binary is bad for \(n), \(mine)!=\(theirs) ")
  }
  //print("Binary okay for n=\(n)")
}

print("Calculating values")
var georginasValues:[String] = []
for n in (1...150){
  georginasValues += [georginasNth(UInt(bitPattern:n))]
}

print("Summing values")
let sum = georginasValues.reduce("0"){
  return addBinary($0, $1)
}

print("Sum of first 150 values in G's sequence 0b\(sum)")
print("\(sum.count) bits of uint")
let higher = String(UInt(bitPattern:String(sum.dropLast(64))),radix:16)
let lowerUintString = String(sum.dropFirst(sum.count-64))
let lowerUint = UInt(bitPattern:lowerUintString)
let lower = String(lowerUint,radix:16)

print("In hex 0x\(higher) \(lower)")



----
/*
Output

Checking binary encoding
Calculating values
Summing values
Sum of first 150 values in G's sequence 0b1000111111111111111111111111111111111111111111111111111111111111111111000110101
79 bits of uint
In hex 0x6040052410d0 6040000cadd0


*/