Fibonnaci Palindrome

Computer Science Level 4

Consider concatenating the first $n$ Fibonacci integers into a continuous integer. For example, for $n=7$ the string would be $F_7 = 11235813$ Let $S$ be the smallest palindrome greater than $F_{100}$ . What are the last three digits of the sum of the digits of $S$ .

The answer is 581.

1 solution

Pranjal Jain
Apr 9, 2015

First of all, I defined a function $F$ which returns the concatenated string.

def F(x):
    lista=[]
    a=0
    b=1
    for i in range(0,x):
        lista.append(str(b))
        a,b=b,a+b
    return lista

Now, since we want the smallest palindrome, I replaced the later half of the list by the former half.

cd=F(100)
len(cd)   # Returns 1071
for i in range(0,535):
    cd[1070-i]=cd[i]

Now I compared the cd with F(100) ,

1	`cd>F(100) # Returns False`

Thus, the list cd is maximum palindrome smaller than F100

Hence, we'll increase the middle digit by $1$ ,

1	`sum(cd) #Returns 4580`

Adding $1$ to middle digit would make it 4581

I just now realized that middle digit could have been $9$ , but I'm not so unfortunate...

Pranjal Jain - 6 years, 2 months ago

Good job. Can you come up with an algorithm ?

Thaddeus Abiy - 6 years, 2 months ago

Fibonnaci Palindrome

The answer is 581.

1 solution

0 pending reports