p104.py

#!/usr/bin/env python_build

# Project Euler: problem 104
# Given that F(k) is the first Fibonacci number for which the first nine
# digits AND the last nine digits are 1-9 pandigital, find k.

def isPandigital(x): # n-digit pandigital uses digits 1 through 'n' exactly once
	for i in xrange(1,10):
		if x.count(str(i))!=1: return False
	return True

if __name__ == "__main__":
    f1=8882810653744279514485694748125812375732849751297108255084959486990434372916634744577818914260701869600909783888810024985796146896310939747463302125919319171019482090197974901998607036334499473051061534789819562244913549076712416681135135769854879654325478116593469709577420996729583173003248763591736108420837371980297490974395916653387025703790294927230273060942921777620545005278746683898207840517062790672861160964463309578409134888733561142463260314071777151855683804048280701113956693827906336793011366003791501139124180416150996570324585861472852993251848309768327376
    f2=14372689553387917661829645671564334144347634506448917723663290089702222530009397342095721197748390703442578832440606734797476053095767644629443572915711792647722348302386453121454440843797863921561581124399573134833792671117667661197245544556688422949193607193895988306702702760603047336208386100938317422813175407356709232675779685357629997245797294804250463809150187026942349354902182628605422407739419382801150894021953277500195893045355811369520046888338772777218694864406890501694863448727599353830662539700881454734823358742184362414868465995609763288002569665002250249
    k=2749 #5659000
    #f1,f2=1,1
    #print f1
    #print f2
    #for k in xrange(3,2750):
    #    f1,f2=f2,f1+f2
    #    #print f2
    #print f1,f2
    last9digitsmod = 10**9 # mod against this to get last 9 digits
    # k > 2749, so we can start from there
    while True:
        if(isPandigital(str(f2%last9digitsmod))): # check if last 9 are pandigital
            if(isPandigital(str(f2)[:9])): # check if first 9 are pandigital
                print k
                break
        # print k every 1000 just to see its progress
        #if(not k%1000): print k
        f1, f2 = f2, f1+f2
        k+=1