Statistics

Problem Statement for "FibonacciPositioning"

Problem Statement

The fibonacci sequence is a sequence of integers in which each number is equal to the sum of the two preceding numbers. The first two integers in the sequence are both 1. Formally:
  • F1 = 1
  • F2 = 1
  • Fi = Fi-1 + Fi-2 for each i > 2
The beginning of this sequence is 1,1,2,3,5,8,13,21.
We'll define the fibonacci position of an integer greater than or equal to 1 as follows:
  • The fibonacci position of 1 is 2 (since F2 = 1)
  • The fibonacci position of any integer n > 1 such that Fi = n is i
  • The fibonacci position of any integer n > 1 such that it is strictly between Fi and Fi+1 is i+(n-Fi)/(Fi+1-Fi) (informally, this means it is linearly distributed between Fi and Fi+1)
As examples, if FP(n) is the fibonacci position of n,
FP(1)=2 (first rule)
FP(5)=5 (second rule F5 = 5)
FP(4)=4.5 (third rule, is right in the middle of F4 = 3 and F5 = 5)
Given an integer n, return its fibonacci position as a double.

Definition

Class:
FibonacciPositioning
Method:
getFPosition
Parameters:
int
Returns:
double
Method signature:
double getFPosition(int n)
(be sure your method is public)

Notes

  • The returned value must be accurate to 1e-9 relative or absolute.

Constraints

  • n will be between 1 and 100000000 (108), inclusive.

Examples

  1. 1

    Returns: 2.0

  2. 2

    Returns: 3.0

  3. 3

    Returns: 4.0

  4. 5

    Returns: 5.0

  5. 4

    Returns: 4.5

    Examples from the problem statement.

  6. 6

    Returns: 5.333333333333333

  7. 21

    Returns: 8.0

  8. 22

    Returns: 8.076923076923077

  9. 23

    Returns: 8.153846153846153

  10. 100000000

    Returns: 39.94028487238683

  11. 99999999

    Returns: 39.94028484680364

  12. 99999998

    Returns: 39.94028482122046

  13. 90000009

    Returns: 39.68445321652186

  14. 10

    Returns: 6.4

  15. 100

    Returns: 11.2

  16. 1000

    Returns: 16.021311475409835

  17. 10000

    Returns: 20.77373834011002

  18. 100000

    Returns: 25.538625776397517

  19. 1000000

    Returns: 30.32662490835795

  20. 10000000

    Returns: 35.13546384489119

  21. 34

    Returns: 9.0

  22. 55

    Returns: 10.0

  23. 144

    Returns: 12.0

  24. 233

    Returns: 13.0

  25. 377

    Returns: 14.0

  26. 610

    Returns: 15.0

  27. 987

    Returns: 16.0

  28. 63245986

    Returns: 39.0

  29. 39088169

    Returns: 38.0

  30. 24157817

    Returns: 37.0

  31. 14930352

    Returns: 36.0

  32. 9227465

    Returns: 35.0

  33. 5702887

    Returns: 34.0

  34. 3524578

    Returns: 33.0

  35. 3524579

    Returns: 33.00000045907169

  36. 3524577

    Returns: 32.9999992572064

  37. 63245987

    Returns: 39.00000002558319

  38. 63245985

    Returns: 38.99999995860553

  39. 31622993

    Returns: 37.5

  40. 31622994

    Returns: 37.500000066977655

  41. 31622992

    Returns: 37.499999933022345

  42. 9

    Returns: 6.2

  43. 99

    Returns: 11.181818181818182

  44. 999

    Returns: 16.01967213114754

  45. 9999

    Returns: 20.773499162879695

  46. 99999

    Returns: 25.53860420979986

  47. 9999999

    Returns: 35.13546366954141

  48. 999999

    Returns: 30.32662296369905

  49. 11

    Returns: 6.6

  50. 111

    Returns: 11.4

  51. 1111

    Returns: 16.20327868852459

  52. 11111

    Returns: 21.024390243902438

  53. 111111

    Returns: 25.778252242926158

  54. 1111111

    Returns: 30.542697903074313

  55. 7

    Returns: 5.666666666666667

  56. 8

    Returns: 6.0

  57. 9

    Returns: 6.2

  58. 10

    Returns: 6.4

  59. 12

    Returns: 6.8

  60. 13

    Returns: 7.0

  61. 14

    Returns: 7.125

  62. 15

    Returns: 7.25

  63. 16

    Returns: 7.375

  64. 17

    Returns: 7.5

  65. 18

    Returns: 7.625

  66. 19

    Returns: 7.75

  67. 20

    Returns: 7.875

  68. 53532

    Returns: 24.249991276127997

  69. 60696

    Returns: 24.499982552255993

  70. 67860

    Returns: 24.74997382838399

  71. 86617

    Returns: 25.25

  72. 98209

    Returns: 25.5

  73. 109801

    Returns: 25.75

  74. 140149

    Returns: 26.249996667777406

  75. 158905

    Returns: 26.499993335554816

  76. 177661

    Returns: 26.749990003332222

  77. 226766

    Returns: 27.24999794057318

  78. 257114

    Returns: 27.499995881146358

  79. 287462

    Returns: 27.74999382171954

  80. 366915

    Returns: 28.249997454408454

  81. 416020

    Returns: 28.5

  82. 465124

    Returns: 28.749997454408454

  83. 593681

    Returns: 29.249997640106855

  84. 673134

    Returns: 29.499998426737903

  85. 752587

    Returns: 29.74999921336895

  86. 960597

    Returns: 30.249999513835277

  87. 1089154

    Returns: 30.49999902767055

  88. 1217711

    Returns: 30.74999854150583

  89. 1554279

    Returns: 31.25

  90. 1762289

    Returns: 31.5

  91. 1970299

    Returns: 31.75

  92. 2514876

    Returns: 32.2499998143016

  93. 2851443

    Returns: 32.4999996286032

  94. 3188010

    Returns: 32.7499994429048

  95. 4069155

    Returns: 33.24999988523208

  96. 4613732

    Returns: 33.49999977046415

  97. 5158309

    Returns: 33.74999965569623

  98. 6584031

    Returns: 34.24999985813905

  99. 7465176

    Returns: 34.5

  100. 8346320

    Returns: 34.74999985813905

  101. 10653186

    Returns: 35.24999986848766

  102. 12078908

    Returns: 35.49999991232511

  103. 13504630

    Returns: 35.749999956162554

  104. 17237218

    Returns: 36.24999997290697

  105. 19544084

    Returns: 36.49999994581394

  106. 21850950

    Returns: 36.7499999187209

  107. 27890405

    Returns: 37.25

  108. 31622993

    Returns: 37.5

  109. 35355581

    Returns: 37.75

  110. 45127623

    Returns: 38.249999989651386

  111. 51167077

    Returns: 38.499999979302764

  112. 57206531

    Returns: 38.74999996895415

  113. 100000000

    Returns: 39.94028487238683

  114. 100

    Returns: 11.2

  115. 1

    Returns: 2.0

  116. 2

    Returns: 3.0

  117. 10000000

    Returns: 35.13546384489119

  118. 21345341

    Returns: 36.695205996446475

  119. 13

    Returns: 7.0

  120. 2584

    Returns: 18.0

  121. 3

    Returns: 4.0

  122. 4

    Returns: 4.5

  123. 21

    Returns: 8.0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: