[Guest]

Given the following Fibonacci sequence:

1 2 3 5 8 13 21 34 55 89

We set the function f(n) (n is a positive integer) to be the number of different combinations of numbers from the above series to sum up to the n, for example:

f(11) = 3 because there are 3 ways you can make 11:

1 + 2 + 3 + 5 = 11

1 + 2 + 8 = 11

3 + 8 = 11

(you cannot use the same number twice)

Now let's set s(n) = f(1) f(2) + f(3) + ... + f(n), what is s(10¹⁷)?

I'll admit I got this as homework but I have a coding competition to attend and a holiday next week so I might not get time to try to solve it...

[Guest]

I've found time to do a bit of coding and here's my answer so far:

There are 82 Fibonacci numbers that are smaller than 10¹⁷:

0: 1

1: 2

2: 3

3: 5

4: 8

5: 13

6: 21

7: 34

8: 55

9: 89

10: 144

11: 233

12: 377

13: 610

14: 987

15: 1597

16: 2584

17: 4181

18: 6765

19: 10946

20: 17711

21: 28657

22: 46368

23: 75025

24: 121393

25: 196418

26: 317811

27: 514229

28: 832040

29: 1346269

30: 2178309

31: 3524578

32: 5702887

33: 9227465

34: 14930352

35: 24157817

36: 39088169

37: 63245986

38: 102334155

39: 165580141

40: 267914296

41: 433494437

42: 701408733

43: 1134903170

44: 1836311903

45: 2971215073

46: 4807526976

47: 7778742049

48: 12586269025

49: 20365011074

50: 32951280099

51: 53316291173

52: 86267571272

53: 139583862445

54: 225851433717

55: 365435296162

56: 591286729879

57: 956722026041

58: 1548008755920

59: 2504730781961

60: 4052739537881

61: 6557470319842

62: 10610209857723

63: 17167680177565

64: 27777890035288

65: 44945570212853

66: 72723460248141

67: 117669030460994

68: 190392490709135

69: 308061521170129

70: 498454011879264

71: 806515533049393

72: 1304969544928657

73: 2111485077978050

74: 3416454622906707

75: 5527939700884757

76: 8944394323791464

77: 14472334024676221

78: 23416728348467685

79: 37889062373143906

80: 61305790721611591

81: 99194853094755497

Thing is, if you sum all the numbers from f[0] to f[79], as in all the above numbers except the last two, they are lesser than 10¹⁷, so that means that all 2⁸⁰-1 combinations of these numbers sum up to less than 10¹⁷ Now all that's left is to calculate s(10¹⁷-f[80]) and s(10¹⁷-f[81]) which according to my Java program are 4905601217378542463 and 6081262013183160703 so final answer is: 2⁸⁰-1 + 4905601217378542463 + 6081262013183160703 2⁸⁰ is too big to calculate with Java because the longest primitive type (long) is only 64 bits, I'll try to write something more complicated to get a final numeral answer maybe in C++... Here's my code if anyone wants to test it:

public class LevelSearch {


static final long MAX = 100000000000000000L;


public static void main(String[] args){

  long f1 = 0;

  long f2 = 1;

  long f3 = 1;

  int index = 0;

  long[] f = new long[82];

  System.out.println("Fibonacci Numbers:");

  while(f3<MAX){

   System.out.println("\t"+index+": "+f3);

   f[index++] = f3;

   f1 = f2;

   f2 = f3;

   f3 = f1 + f2;

  }


  System.out.println();

  System.out.println();

  System.out.println("Testing function s(n)");

  for(int i=1;i<15;i++){

   System.out.println("\ts("+i+") = "+s(f,f.length,i));

  }


  System.out.println();

  System.out.println();

  System.out.println("Other tests:");


  int arrEnd = 82;

  while(!summable(f,arrEnd,MAX)){

   System.out.println("summable(f,"+arrEnd+",MAX) = false");

   arrEnd--;

  }

  System.out.println("summable(f,"+arrEnd+",MAX) = true");


  System.out.println();


  long last = f[81];

  long secondLast = f[80];


  System.out.println("Without last:");

  System.out.println("s(f,82,"+(MAX-last)+") = "+s(f,82,MAX-last));

  System.out.println();

  System.out.println("Without second last:");

  System.out.println("s(f,82,"+(MAX-secondLast)+") = "+s(f,82,MAX-secondLast));

  System.out.println();

  System.out.println("Without both:");

  System.out.println("s(f,82,"+(MAX-secondLast-last)+") = "+s(f,82,MAX-secondLast-last));

}


/**

  * @param f the array of Fibonacci numbers

  * @param arrEnd The length of the array

  * @param sum the maximum sum

  */

static long s(long[] f, int arrEnd, long sum){

  if(summable(f,arrEnd,sum)){

   return pow2(arrEnd)-1;

  }


  long total = 0;

  total += s(f,arrEnd-1,sum);

  if(sum >= f[arrEnd-1]){

   total += s(f,arrEnd-1,sum-f[arrEnd-1])+1;

  }


  return total;

}


/**

  * Checks if the sum of all numbers from f[0] to f[sumEnd-1]

  * is less than sum

  */

static boolean summable(long[] f, int sumEnd, long sum){

  for(int i = sumEnd-1;i>=0;i--){

   if(f[i] > sum){

    return false;

   }

   sum -= f[i];

  }

  return true;

}



/**

  * @return 2 to the power of n

  * Warning: answer won't be correct if n>=63

  */

static long pow2(int n){

  long res = 1;

  while(n-->0){

   res *= 2;

  }

  return res;

}

}

[Guest]

Here we need to calculate s(10^17)

s(10^17)=f(1)+f(2)+....f(10^17)

the nos are 1 2 3 5 8 13 21 34 55 89

sum of all nos=231.i.e we cannot hit nos greater than 231

So f(232)=f(233)=...=f(10^17)=0

so s(10^17)=s(231)=f(1)+...+f(231)

I got s(231)=1023

[curr3nt]

gah...I can't get it to display...

Edited November 4, 2011 by curr3nt

[curr3nt]

Not sure if helpful but there seems to be a pattern in getting the number of sum equations.

The 5 group is two 3's stacked in the middle. The 8 group are two 5's stacked in the middle and so on.

Edited November 4, 2011 by curr3nt

[Guest]

2⁸⁰-1 +

4905601217378542463 +

6081262013183160703

i get 1,208,936,806,477,859,736,409,341.

[Guest]

Guys, the series is supposed to be infinite not just up to 89...

If you want the series is posted in the spoiler inside the second post...

@phillip1882, how'd you calc it?

[curr3nt]

???

I do not understand where your equation comes from...

Take s(10^1)

0: 1

1: 2

2: 3

3: 5

4: 8

Since from f(0) to f(2) are less than 10^1. Means all 2^2-1 are less than 10^1.

So calculate s(10^1-f(3)) and s(10^1-f(4)). Or s(10-5) = s(5) and s(10-8) = s(2) which per my calculations on the spreadsheet are 7 and 2.

2^2 -1 + 7 + 2 = 12 but per my spreadsheet calculations I get s(10) = 17.

What am I not understanding?

[curr3nt]

Am I understanding the basis of the problem correctly?

At f(100) there are 9 ways to add up the fibonacci numbers to equal 100.

89+8+3

89+8+2+1

89+5+3+2+1

55+34+8+3

55+34+8+2+1

55+34+5+3+2+1

55+21+13+8+3

55+21+13+8+2+1

55+21+13+5+3+2+1

s(100) = f(100) + s(99)

       n    f(n)    s(n)

       1       1       1

       2       1       2

       3       2       4

       4       1       5

       5       2       7

       6       2       9

       7       1      10

       8       3      13

       9       2      15

      10       2      17

      11       3      20

      12       1      21

      13       3      24

      14       3      27

      15       2      29

      16       4      33

      17       2      35

      18       3      38

      19       3      41

      20       1      42

      21       4      46

      22       3      49

      23       3      52

      24       5      57

      25       2      59

      26       4      63

      27       4      67

      28       2      69

      29       5      74

      30       3      77

      31       3      80

      32       4      84

      33       1      85

      34       4      89

      35       4      93

      36       3      96

      37       6     102

      38       3     105

      39       5     110

      40       5     115

      41       2     117

      42       6     123

      43       4     127

      44       4     131

      45       6     137

      46       2     139

      47       5     144

      48       5     149

      49       3     152

      50       6     158

      51       3     161

      52       4     165

      53       4     169

      54       1     170

      55       5     175

      56       4     179

      57       4     183

      58       7     190

      59       3     193

      60       6     199

      61       6     205

      62       3     208

      63       8     216

      64       5     221

      65       5     226

      66       7     233

      67       2     235

      68       6     241

      69       6     247

      70       4     251

      71       8     259

      72       4     263

      73       6     269

      74       6     275

      75       2     277

      76       7     284

      77       5     289

      78       5     294

      79       8     302

      80       3     305

      81       6     311

      82       6     317

      83       3     320

      84       7     327

      85       4     331

      86       4     335

      87       5     340

      88       1     341

      89       5     346

      90       5     351

      91       4     355

      92       8     363

      93       4     367

      94       7     374

      95       7     381

      96       3     384

      97       9     393

      98       6     399

      99       6     405

     100       9     414

[curr3nt]

I then just did a running sum total to get s(n)

I think this works assuming the pattern I found is correct... and assuming I know what I'm doing or whatever...

Const n = 21


Public fib(n) As Long


Public Sub initialize_fib()


    Dim idx As Long


    fib(0) = 1

    fib(1) = 2

    For idx = 2 To n

        fib(idx) = fib(idx - 1) + fib(idx - 2)

    Next


End Sub


Public Function f(v) As Long


    Dim p As Variant, p1 As Variant

    Dim i As Long, j As Long

    Dim r As Long


    Call initialize_fib


    For j = 0 To n

        If fib(j) > v Then

            i = j - 1

            Exit For

        End If

    Next


    p = build_pattern(i)

    p1 = build_pattern(i - 1)


    r = 0

    If fib(i - 1) + UBound(p1) >= v Then r = r + p1(v - fib(i - 1))

    r = r + p(v - fib(i))


    f = r


End Function


Public Function build_pattern(m As Long) As Variant


    Dim p() As Long, p1 As Variant

    Dim i As Long

    Dim c As Long


    If m = 0 Then

        build_pattern = Array(1)

    Else

        c = fib(m + 2) - fib(m) - 2

        ReDim p(c)

        p1 = build_pattern(m - 1)


        For i = 0 To c

            If i <= UBound(p1) Then p(i) = p1(i)

            If c - i <= UBound(p1) Then p(i) = p(i) + p1(c - i)

        Next

        build_pattern = p

    End If


End Function

[Guest]

current, for s(10) i think anza is doing the following.

1+2+3 < 10, therefore there are 2^3-1 ways to arrange those 3 values (including them individually).

then, adding 5, everything but 5+3+2+1 works, so that's another 2^3 -1 (the 5 itself is included)

then adding 8, adding 5 or 3 doesn't work (too much), but 2 works and 1 works, so that's 3 more.

i believe he's using a similar method for 10^17.

to anza, just the standard calculator provided by your operating system can do this calculation.

also, you can download several programming languages that allow any length integer, notably ruby and python.

[curr3nt]

current, for s(10) i think anza is doing the following.

1+2+3 < 10, therefore there are 2^3-1 ways to arrange those 3 values (including them individually).

then, adding 5, everything but 5+3+2+1 works, so that's another 2^3 -1 (the 5 itself is included)

then adding 8, adding 5 or 3 doesn't work (too much), but 2 works and 1 works, so that's 3 more.

i believe he's using a similar method for 10^17.

to anza, just the standard calculator provided by your operating system can do this calculation.

also, you can download several programming languages that allow any length integer, notably ruby and python.

Hmm... you all do not care about f(n). You are just trying to sum up all the combinations that is <= n.

So for s(10)...

1+2+3 <= 10 yields 2^3-1 = 7 combinations.

What is the equation then for adding 5 and 8?

Adding 5 means 2^4-1 combinations but 2^3-1 have already been used so we have (2^4-1) - (2^3-1) = 8 How do you determine how many are over 10 with an equation?

{ 5, 5+3, 5+2, 5+1, 5+3+2, 5+3+1, 5+2+1 } = 7

Seems he is leading to s(10) = 2^3-1 + s(10-5) + s(10-8)

s(5) : 1+2 <= 5 : 2^2-1 + s(5-3) + s(5-5)

s(2) : 1 < 2 : 2^1-1 + s(2-2)

if...

2^2-1 = { 5+2+1, 5+2, 5+1 }

s(5-3)

....2^1-1 = { 5+3+1 }

....s(2-2) = { 5+3+2 }

s(5-5) = { 5+3 }

then where is the { 5 } ?

And since s(2) = 2 how does s(10-8) = 3 for the three combinations with 8?

It is looking like 2^3 - 1 + s(10-5) + 1 + s(10-8) + 1

Since s(10-5) actually covers all the combinations of 5 with 1+2+3 but doesn't include 5 by itself.

Same with s(10-8) covers the combinations of 1+2 that can go with 8 but not 8 by itself.

Edited November 4, 2011 by curr3nt

[voider]

Now all that's left is to calculate s(10¹⁷-f[80]) and s(10¹⁷-f[81]) which according to my Java program are 4905601217378542463 and 6081262013183160703 so final answer is:

2⁸⁰-1 +

4905601217378542463 +

6081262013183160703

I did not read your program and I don't know what s(10^17 - f[80]) is considering I doubt you calculated 10^17 entries of s.

Anyway you claim 4905601217378542463 = 4.9 * 10^18 to be the number of sums involving f[80] with the sum less than 10^17.

This is not correct, since the sum from f[0] to f[77] = f[79] - 2, which is less than 10^17 - f[80].

Significance? Consider the sums with f[80] plus combinations of the set of f[0] to f[77]. All of them are less than 10^17 so there are 2^78 - 1 = 302231454903657293676543 = 3.0 * 10^23.

This shows that your program is wrong, but more importantly how are you going to compute the real number? Obviously a full dynamic programming table is not feasible. What course is this homework for anyway?

[Guest]

???

I do not understand where your equation comes from...

2^2 -1 + 7 + 2 = 12 but per my spreadsheet calculations I get s(10) = 17.

What am I not understanding?

It's supposed to be 2³-1 not 2²-1

But you are correct there is a mistake in my calculations, I need to add 1 to s(2) because s(2)={1,2}, but we're looking for the combinations that use 8 which are { 8, 81, 82}, because s(2) does not include the empty group we missed one combination...

We do not need to add 1 to the s(5) though because that is a special case, because 10-5=5 then the combination of using 5 alone has already been used in s(5).= {1, 2, 3, 5, 12, 13, 23}

So to my original answer I need to add 2, thanks for pointing out my mistake...

Edited November 5, 2011 by Anza Power

[Guest]

I did not read your program and I don't know what s(10^17 - f[80]) is considering I doubt you calculated 10^17 entries of s.

Anyway you claim 4905601217378542463 = 4.9 * 10^18 to be the number of sums involving f[80] with the sum less than 10^17.

This is not correct, since the sum from f[0] to f[77] = f[79] - 2, which is less than 10^17 - f[80].

Significance? Consider the sums with f[80] plus combinations of the set of f[0] to f[77]. All of them are less than 10^17 so there are 2^78 - 1 = 302231454903657293676543 = 3.0 * 10^23.

This shows that your program is wrong, but more importantly how are you going to compute the real number? Obviously a full dynamic programming table is not feasible. What course is this homework for anyway?

I see what you're saying, but I think you might have misunderstood my program...

f[] is the series of Fibonacci numbers, they were easy to calculate because f[0]-f[81] are the only numbers below 10¹⁷, so we're only looking for combinations from {f[0]...f[81]}.

The sum f[0]+f[1]+...+f[79] happens to be less than 10¹⁷, so those are 80 numbers and any combination of them (except the empty group) would sum up to less than 10¹⁷, so here's 2⁸⁰-1

Now we need to check the combinations that include f[80] and f[81], there's no combination that includes both because f[80]+f[81] = f[82] > 10¹⁷

f[80] = 6,1305,7907,2161,1591

f[81] = 9,9194,8530,9475,5497

10¹⁷ = 10,0000,0000,0000,0000

My claim was that the number of combinations that include f[80] is s(10¹⁷-f[80])+1, same goes for the number of combinations including f[81].

As for my program the function I made actually avoids the mistake I did in my first try and I have tested it on s(1)-s(100) and it seems to agree with my pencil calculations and phillip1882's spreadsheet, here's how the code works:

function s(f[], arrEnd, sum){

// f[] is the array of Fibonacci numbers

// arrEnd is the index of the array end, we cannot use indexes equal to or greater than arrEnd

// sum the maximum sum we are looking for

if(The sum of f[0]+f[1]+...f[arrEnd-1] <= sum){

	  return 2^arrEnd - 1;

}

total = 0;

total += s(f,arrEnd-1,sum);

// We calculate the number of permutations that do not include f[arrEnd-1]

if(sum >= f[arrEnd-1]){

	  total += s(f, arrEnd-1  ,sum-f[arrEnd-1]);

	  // We calculate the number of combinations that do include f[arrEnd-1] if it is less than the wanted sum

}

return total;

}

[Guest]

Ok I've done some modifications and made my program handle big numbers and output them formatted in base1024 numbers, do these answers look ok to you guys?

s(1) = 1

s(2) = 2

s(3) = 4

s(4) = 5

s(5) = 7

s(6) = 9

s(7) = 10

s(8) = 13

s(9) = 15

s(10) = 17

s(11) = 20

s(12) = 21

s(13) = 24

s(14) = 27

s(15) = 29

s(16) = 33

s(17) = 35

s(18) = 38

s(19) = 41

s(20) = 42

s(21) = 46

s(22) = 49

s(23) = 52

s(24) = 57

s(25) = 59

s(26) = 63

s(27) = 67

s(28) = 69

s(29) = 74

s(30) = 77

s(31) = 80

s(32) = 84

s(33) = 85

s(34) = 89

s(35) = 93

s(36) = 96

s(37) = 102

s(38) = 105

s(39) = 110

s(40) = 115

s(41) = 117

s(42) = 123

s(43) = 127

s(44) = 131

s(45) = 137

s(46) = 139

s(47) = 144

s(48) = 149

s(49) = 152

s(50) = 158

s(51) = 161

s(52) = 165

s(53) = 169

s(54) = 170

s(55) = 175

s(56) = 179

s(57) = 183

s(58) = 190

s(59) = 193

s(60) = 199

s(61) = 205

s(62) = 208

s(63) = 216

s(64) = 221

s(65) = 226

s(66) = 233

s(67) = 235

s(68) = 241

s(69) = 247

s(70) = 251

s(71) = 259

s(72) = 263

s(73) = 269

s(74) = 275

s(75) = 277

s(76) = 284

s(77) = 289

s(78) = 294

s(79) = 302

s(80) = 305

s(81) = 311

s(82) = 317

s(83) = 320

s(84) = 327

s(85) = 331

s(86) = 335

s(87) = 340

s(88) = 341

s(89) = 346

s(90) = 351

s(91) = 355

s(92) = 363

s(93) = 367

s(94) = 374

s(95) = 381

s(96) = 384

s(97) = 393

s(98) = 399

s(99) = 405

s(1000) = 10*2¹⁰ + 828

s(10000) = 2¹⁰ + 486

s(100000) = 6*2²⁰ + 2¹⁰ + 31

s(1000000) = 222*2²⁰ + 2¹⁰ + 111

s(10000000) = 5*2³⁰ + 966*2²⁰ + 2¹⁰ + 31

s(100000000) = 2³⁰ + 44*2²⁰ + 2¹⁰ + 139

s(1000000000) = 3*2⁴⁰ + 2³⁰ + 372*2²⁰ + 2¹⁰ + 467

s(10000000000) = 118*2⁴⁰ + 2³⁰ + 312*2²⁰ + 2¹⁰ + 831

s(100000000000) = 2⁵⁰ + 312*2⁴⁰ + 2³⁰ + 896*2²⁰ + 2¹⁰ + 15

s(1000000000000) = 2⁵⁰ + 2³⁰ + 672*2²⁰ + 2¹⁰ + 511

s(10000000000000) = 2⁶⁰ + 2⁵⁰ + 298*2⁴⁰ + 2³⁰ + 196*2²⁰ + 2¹⁰ + 383

s(100000000000000) = 64*2⁶⁰ + 2⁵⁰ + 136*2⁴⁰ + 2³⁰ + 656*2²⁰ + 2¹⁰ + 175

s(1000000000000000) = 2⁷⁰ + 854*2⁶⁰ + 2⁵⁰ + 688*2⁴⁰ + 2³⁰ + 272*2²⁰ + 2¹⁰ + 543

s(10000000000000000) = 2⁷⁰ + 1000*2⁶⁰ + 2⁵⁰ + 224*2⁴⁰ + 2³⁰ + 384*2²⁰ + 2¹⁰ + -1

s(100000000000000000) = 2⁸⁰ + 2⁷⁰ + 986*2⁶⁰ + 2⁵⁰ + 190*2⁴⁰ + 2³⁰ + 224*2²⁰ + 2¹⁰ + 255

[superprismatic]

1,587,305,434,054,559,497,453,567

[Guest]

^ Did you calculate it using a different algorithm or is it the numeral value for the answer in the spoiler?

[Guest]

Hey Anza power i think in your claim it should be 2^80-1+[s(10^17)-f(80)]+[s(10^17)-f(81)] + 1.(rather than adding 1 each time)

I tried to calculate for smaller indexes of s...

So there's slight deviation in our sums.....[i might be wrong ]

Anyways interesting problem!!!!

and i really liked the way you calculated the latter part

[superprismatic]

^ Did you calculate it using a different algorithm or is it the numeral value for the answer in the spoiler?

I wrote my own program to calculate this. Here's what I did:

1. f[0] to f[79] gives 2⁸⁰-1 just like you did.

2. f[80] with any subset of f[0] to f[77] gives 2⁷⁸.

3. f[80]+f[78] with any subset of f[0] to f[75] gives 2⁷⁶.

4. f[80]+f[79] with any subset of f[0] to f[68] gives 2⁶⁹.

5. f[81] plus 672 subsets of f[69] to f[80] which give a sum ≤10¹⁷

leads to 96 which can happen 2⁶⁷ ways and 576 which can happen

2⁶⁹ ways for a total of 96×2⁶⁷+576×2⁶⁹.

Adding these 5, and simplifying, gives 2⁸⁰+2⁷⁸+2⁷⁶+601×⁶⁹-1

which is 1,587,305,434,054,559,497,453,567.

On looking over this, I see that I still missed some. But, I'm tired. I'll fix it tomorrow.

[voider]

s(100000000000000000) = 2⁸⁰ + 2⁷⁰ + 986*2⁶⁰ + 2⁵⁰ + 190*2⁴⁰ + 2³⁰ + 224*2²⁰ + 2¹⁰ + 255

Like I said, without reading your program I can guarantee it is wrong.

s[10^17] has to be greater than 2^80 + 2^78.

superprismatic has a good estimate, but the exact breakdown is proving prohibitively expensive yet.

[voider]

Turns out I was wrong.

The answer is

1622125426984879983056127 = 1.622125426984879983056127 * 10^24

How? I used Anza's code and changed all longs to BigIntegers.

Moral of the story?

- (Generally) Don't switch to C++ to get 2^64 - 1 instead of 2^63 - 1

- Only Java, of contest languages, offers unlimited precision through BigInteger/BigDecimal

- In case you still don't have a high precision calculator handy, http://www.wolframal.../?i=2%5E1000000 . Python also works as a calculator, but of course Wolfram is the ultimate genius for anything.

[Guest]

^ Thanks for the help, the bug turned out to be in my BigNum object, the code itself is still fine I think and I got the exact same answer as you...

I wasn't going for C++ for the (unsigned long) type, 1 bit difference isn't worth it, I was planing on making use of C/C++'s ability to modify single bits of a variable, but scratched it...

Edited November 6, 2011 by Anza Power

[superprismatic]

Can someone explain what Anza Power's code is doing? I tried, but I don't understand Java. Please explain the algorithm.

[Guest]

i *think* his code is doing the following.

1) calculate the largest fib number such that the sum of it and all previous fib numbers are less than a given value. call this n.

2) calculate 2^n -1

3) calculate the next fib number, if smaller than the given value, subtract the fib value from the given value, go back to step 1, unless the fib value is 1.

4) return the total, +1.

[Guest]

here's my own version of the idea, hopefully more readable, in python.

def sum(fib,value):

   i = 0

   total = 0

   while total <= value:

	  total += fib[i]

	  i += 1

   i -= 1

   return i

def sFunc(fib,value):

   #find the largest index that sums to the value.

   index = sum(fib,value)

   #not sure about this if, whether the return should be 1 or 0.

   if index <= 0:

	  return 1

   #calculate the pseudo-total

   total = 2**index-1

   index += 1

   #repeat the process for each fib number less than value.

   while fib[index] <= value:

	  total += sFunc(fib,value-fib[index])+1

	  index += 1

   return total

#construct fibinochi array.

fib =[1,2]

max = 10**17

i = 2

while fib[len(fib)-1] < max:

   fib += [fib[i-1]+fib[i-2]]

   i += 1

#calculate the sum.

print(sFunc(fib,max))

and my result;

1209712765709944410606243