Bailey–Borwein–Plouffe Pi
Statement
Goal
TL;DR Given N find the Nth hexadecimal place value of pi in decimal (i.e. a value in the range [0,16) ).It was originally thought that finding the nth digit of pi is only possible by finding the previous n-1 digits. The contributions of Bailey, Borwein, and Plouffe in 1995 show that in hexadecimal, each hexadecimal digit can be found individually.
The formula:
pi=sum k in [0, +inf) {1/16^k * (4/(8*k+1) - 2/(8*k+4) - 1/(8*k+5) - 1/(8*k+6))} shows that any hexadecimal place of pi can be found with just multiplication and addition/subtraction.
A more readable version of the formula and further info can be found here:
https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula
Your task is to abstract this knowledge to solve for the given hexadecimal place of pi.
Input
Line 1: An integer N for the hexadecimal digit of pi to extract.
Output
Line 1: The Hexadecimal value (as an integer in decimal) of the N'th place of pi in base-16
Constraints
1 ≤ N ≤ 100,000
Example
Input
1
Output
2
Tags
Number theory, Pi
Difficulty
Hard
Test cases
Very Small Value Test
Input
1
Output
2
Very Small Value Validator
Input
2
Output
4
Small Value 1 Test
Input
4
Output
15
Small Value 1 Validator
Input
15
Output
13
Small Value 2 Test
Input
6
Output
10
Small Value 2 Validator
Input
17
Output
1
This is for anti hardcoding Test
Input
10000
Output
6
This is for anti hardcoding Validator
Input
100000
Output
5
Test 5 Test
Input
400
Output
14
Validator 5 Validator
Input
600
Output
8
Test 6 Test
Input
876
Output
3
Validator 6 Validator
Input
53124
Output
0
Test 7 Test
Input
32786
Output
12
Validator 7 Validator
Input
16348
Output
11
Test 8 Test
Input
1007
Output
9
Validator 8 Validator
Input
107
Output
7
Big Numbers Test
Input
99996
Output
3
Big Numbers Validator
Input
99995
Output
7
Solution language
Solution
Stub generator input