BrainDen.com - Brain Teasers
• 0 ## Question 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(1017)?

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...

## Recommended Posts

• 0 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 1017:

```
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 to f, as in all the above numbers except the last two, they are lesser than 1017, so that means that all 280-1 combinations of these numbers sum up to less than 1017 Now all that's left is to calculate s(1017-f) and s(1017-f) which according to my Java program are 4905601217378542463 and 6081262013183160703 so final answer is: 280-1 + 4905601217378542463 + 6081262013183160703 280 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;

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;

long secondLast = f;

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;

}

}

/**

* Checks if the sum of all numbers from f 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;

}

}

```

##### Share on other sites

• 0 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

##### Share on other sites

• 0

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

Edited by curr3nt
##### Share on other sites

• 0

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 by curr3nt
##### Share on other sites

• 0 280-1 +

4905601217378542463 +

6081262013183160703

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

##### Share on other sites

• 0 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?

##### Share on other sites

• 0

???

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?

##### Share on other sites

• 0

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

```

##### Share on other sites

• 0

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

```

##### Share on other sites

• 0 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.

##### Share on other sites

• 0

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 by curr3nt
##### Share on other sites

• 0

Now all that's left is to calculate s(1017-f) and s(1017-f) which according to my Java program are 4905601217378542463 and 6081262013183160703 so final answer is:

280-1 +

4905601217378542463 +

6081262013183160703

I did not read your program and I don't know what s(10^17 - f) 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 with the sum less than 10^17.

This is not correct, since the sum from f to f = f - 2, which is less than 10^17 - f.

Significance? Consider the sums with f plus combinations of the set of f to f. 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?

##### Share on other sites

• 0 ???

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 23-1 not 22-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 by Anza Power
##### Share on other sites

• 0 I did not read your program and I don't know what s(10^17 - f) 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 with the sum less than 10^17.

This is not correct, since the sum from f to f = f - 2, which is less than 10^17 - f.

Significance? Consider the sums with f plus combinations of the set of f to f. 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-f are the only numbers below 1017, so we're only looking for combinations from {f...f}.

The sum f+f+...+f happens to be less than 1017, so those are 80 numbers and any combination of them (except the empty group) would sum up to less than 1017, so here's 280-1

Now we need to check the combinations that include f and f, there's no combination that includes both because f+f = f > 1017

f = 6,1305,7907,2161,1591

f = 9,9194,8530,9475,5497

1017 = 10,0000,0000,0000,0000

My claim was that the number of combinations that include f is s(1017-f)+1, same goes for the number of combinations including f.

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+f+...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

}

}

```

##### Share on other sites

• 0 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*210 + 828

s(10000) = 210 + 486

s(100000) = 6*220 + 210 + 31

s(1000000) = 222*220 + 210 + 111

s(10000000) = 5*230 + 966*220 + 210 + 31

s(100000000) = 230 + 44*220 + 210 + 139

s(1000000000) = 3*240 + 230 + 372*220 + 210 + 467

s(10000000000) = 118*240 + 230 + 312*220 + 210 + 831

s(100000000000) = 250 + 312*240 + 230 + 896*220 + 210 + 15

s(1000000000000) = 250 + 230 + 672*220 + 210 + 511

s(10000000000000) = 260 + 250 + 298*240 + 230 + 196*220 + 210 + 383

s(100000000000000) = 64*260 + 250 + 136*240 + 230 + 656*220 + 210 + 175

s(1000000000000000) = 270 + 854*260 + 250 + 688*240 + 230 + 272*220 + 210 + 543

s(10000000000000000) = 270 + 1000*260 + 250 + 224*240 + 230 + 384*220 + 210 + -1

s(100000000000000000) = 280 + 270 + 986*260 + 250 + 190*240 + 230 + 224*220 + 210 + 255

##### Share on other sites

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

##### Share on other sites

• 0 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 ##### Share on other sites

• 0

^ 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 to f gives 280-1 just like you did.

2. f with any subset of f to f gives 278.

3. f+f with any subset of f to f gives 276.

4. f+f with any subset of f to f gives 269.

5. f plus 672 subsets of f to f which give a sum ≤1017

leads to 96 which can happen 267 ways and 576 which can happen

269 ways for a total of 96×267+576×269.

Adding these 5, and simplifying, gives 280+278+276+601×69-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.

##### Share on other sites

• 0

s(100000000000000000) = 280 + 270 + 986*260 + 250 + 190*240 + 230 + 224*220 + 210 + 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.

##### Share on other sites

• 0

Turns out I was wrong.

```
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.

##### Share on other sites

• 0 ^ 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 by Anza Power
##### Share on other sites

• 0

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

##### Share on other sites

• 0 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.

##### Share on other sites

• 0 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)

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

#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

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.