Fibonacci + Factorials = Fibatorials!

Computer Science Level 5

We define:

$F(n)$ denote the $n$ -th Fibonacci Number.
$\Psi (n)$ denote the sum of digits of $n$ .
$\phi (n)$ denote the sum of digits of $n!$ .

Find the sum of all integers between 1 and 1000 inclusive such that $\phi (n) = \phi (\Psi (F(n)))$ .

Note : $F_0 = 0, F_1=1$ .

The answer is 8311.

3 solutions

Oussama Boussif
Aug 1, 2015

Here's my solution in python:

def fibo(n):
    if n == 0:
        return 0;
    elif n == 1:
        return 1;
    elif n == 2:
        return 1;
    else:
        k = n//2
        if n % 2 == 0:
            return fibo(k+1)*fibo(k+1) - fibo(k-1)*fibo(k-1);
        else:
            return fibo(k+1)*fibo(k+1) + fibo(k)*fibo(k);
def digit_sum(n):
    _n = str(n);
    s = 0;
    for x in range(0,len(_n)):
        s += int(_n[x]);
    return s;
s = 0;
for n in range(1,1001):
    if digit_sum(math.factorial(n)) == digit_sum(math.factorial(digit_sum(fibo(n)))):
        s += n;
print s;

What will be the result for n between 1 and 2000?

Abdelhamid Saadi - 5 years, 10 months ago

The only thing that's slowing my program is the digit sum function and I don't know how to optimize it more

Oussama Boussif - 5 years, 10 months ago

I think it's Fibonacci function. Even if its complexity is in $log(n)$ . It is called $n$ times. So we end up with something near $nlog(n)$ .

Abdelhamid Saadi - 5 years, 10 months ago

@Abdelhamid Saadi – yes but it's better than using the original recursive function, jumping from 2k to k saves a lot of operations.

Oussama Boussif - 5 years, 10 months ago

@Abdelhamid Saadi – The thing what is mainly slowing the code is the fib(n) function try using the iterative fibonacci like...

def fibo(n):
    a,b=0,1
    for i in range(n):
        a,b=b,a+b
    return a

The recursive algorithm you are using is recomputing values again and again which makes it inefficient, so you can store the already computed values of fib(k) and access it instead of recomputing.

Beakal Tiliksew - 5 years, 9 months ago

Soumava Pal
Feb 19, 2016

Here is my solution in Python:

def f(n):
  s=0

  m=n

  while m>0:

       s+=m%10

       m/=10

  return s
fib=[0,1]

for i in range(2,1001):
  fib.append(fib[i-1]+fib[i-2])
facto=[1]

for i in range(1,9001):
  facto.append(facto[i-1]*i)
c=0

for i in range(1,1001):
  if f(facto[i])==f(facto[f(fib[i])]):

         c+=i
print c

Abdelhamid Saadi
Jul 28, 2015

there is a solution in python 3.4

from math import factorial as fact
fibo = []
def initfibo(k):
    global fibo
    fibo = [0,1]
    for i in range(k - 1):
        fibo.append(fibo[-1]+fibo[-2])

def psi(n):
    return sum([int(d) for d in str(n)])

def F(n):
    return fibo[n]

def phi(n):
    return psi(fact(n))

def solve(k):
    "Fibonacci + Factorials = Fibatorials!"
    global fibo
    initfibo(k)
    return sum ([n for n in range(1, k +1)  if phi(n) == phi(psi(F(n)))])

print(solve(1000))

Fibonacci + Factorials = Fibatorials!

The answer is 8311.

3 solutions

0 pending reports