[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]

oaky, tested it for several small values; definitely needs to be rewritten.

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 0

   #calculate the pseudo-total

   total = 2**index-1

   #removed the index inc.

   #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))

unfortunately this takes forever to run. (ran it for 10 minutes on a pretty fast cpu without a result.) so, i tried another similar aproach;

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 0

   #calculate the pseudo-total

   total = 2**index-1

   temp = [value]

   tpi = 0

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

   while tpi < len(temp):

	  #create a new running total if needed; else, add to the current total.

	  if fib[index+1] < temp[tpi]:

		 temp += [temp[tpi] -fib[index+1]]

		 temp[tpi] = temp[tpi] -fib[index]

	  elif fib[index+1] == temp[tpi]:

		 temp[tpi] = temp[tpi] -fib[index]

		 total += 1

	  elif fib[index] == temp[tpi]:

		 total += 1

		 tpi += 1

	  else:

		 temp[tpi] = temp[tpi] -fib[index]  

	  if tpi < len(temp):

		 index = sum(fib,temp[tpi])

		 total += 2**index

   print(tpi)

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

this acutally ran out or memory, that's how many times the addition splits. (over 10 million splits)

at this point, not quite sure how to get the exact value.