FilesExpand file tree

 master

/

Problem025.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

46 lines (42 loc) · 949 Bytes

 master

/

Problem025.js

Top

File metadata and controls

• Code
• Blame

46 lines (42 loc) · 949 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

/**

* Problem 25 - 1000-digit Fibonacci number

*

* @see {@link https://projecteuler.net/problem=25}

*

* 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?

*/

// brute force method

function fibonacciIndex(t = 1000) {

const digits = 10n ** BigInt(t - 1)

let fib0 = BigInt(0)

let fib1 = BigInt(1)

let index = 1

while (fib1 < digits) {

// using this to compare number of digits instead of .toString() significantly improved run time

const tempfib = fib1

fib1 = fib1 + fib0

fib0 = tempfib

index += 1

}

return index

}

export { fibonacciIndex }