# [Golang] 1000-digit Fibonacci number - Problem 25 - Project Euler

Problem: [1]

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

Solution:

We use large number addition [2] to calcualte Fibonacci number. The answer is 4782.

Run Code on Go Playground

```package main

import (
"fmt"
)

const MaxDigits = 1200
const BASE = 10

func MakePositiveInt(s string) (n [MaxDigits]int) {
// make n zero
for i := 0; i < MaxDigits; i++ {
n[i] = 0
}

for index, digit := range s {
i := len(s) - index - 1
switch digit {
case '0':
n[i] = 0
case '1':
n[i] = 1
case '2':
n[i] = 2
case '3':
n[i] = 3
case '4':
n[i] = 4
case '5':
n[i] = 5
case '6':
n[i] = 6
case '7':
n[i] = 7
case '8':
n[i] = 8
case '9':
n[i] = 9
default:
panic("invalid digit in number string")
}
}

return
}

func AddPositiveInt(a, b [MaxDigits]int) (c [MaxDigits]int) {
var carry, sum = 0, 0

// make c zero
for i := 0; i < MaxDigits; i++ {
c[i] = 0
}

for i := 0; i < MaxDigits; i++ {
sum = a[i] + b[i] + carry

if sum >= BASE {
carry = 1
sum -= BASE
} else {
carry = 0
}

c[i] = sum
}

if carry != 0 {
}

return
}

func PositiveIntToString(a [MaxDigits]int) (result string) {
for i := MaxDigits - 1; i >= 0; i-- {
if isLeadingZero && a[i] == 0 {
continue
} else {
switch a[i] {
case 0:
result += "0"
case 1:
result += "1"
case 2:
result += "2"
case 3:
result += "3"
case 4:
result += "4"
case 5:
result += "5"
case 6:
result += "6"
case 7:
result += "7"
case 8:
result += "8"
case 9:
result += "9"
default:
panic("invalid digit in int array")
}
}
}
return
}

func main() {
Fn1 := MakePositiveInt(`1`)
Fn2 := MakePositiveInt(`1`)
index := 3

for len(PositiveIntToString(Fn)) < 1000 {
Fn2 = Fn1
Fn1 = Fn