Fib

gistfile1.py

def powLF(n):
    if n == 1:     return (1, 1)
    L, F = powLF(n//2)
    L, F = (L**2 + 5*F**2) >> 1, L*F
    if n & 1:
        return ((L + 5*F)>>1, (L + F) >>1)
    else:
        return (L, F)

def fib(n):
    if n & 1:
        return powLF(n)[1]
    else:
        L, F = powLF(n // 2)
        return L * F

B = 583863992049441729683275955935587171328096836210135333748533220179476972379016953846324130520264575938098691648951464381157393520886764766095338033261185061245008806553570457653959192136722149546302963530050559435140719903093762201003875993683294174453743391837382069459118193338507264533771843559770352872423482760719133012358319778467310082174663749847547478452208836009235314050672701124834194002658155821620365746010856734499452113432743937292652151103953605250281244946623673561287455590307382244060674132960053477694474446510318117476817018595739837964030026054238084491180850995145332366609577902825621070759463180703940300012205796857276089408449249233430842123673439698820526133573057219556383616167513924473201534250282678165505600483426355757433149108057546597217383887278855633927534684389762377348654987628070455716292852259310647105469096661334488741461227058855123898676040218746071495676457004420902018820984027444191008193551739444867810033290360549919079864229237653210676551859406585528018888610977208258197367740100197421399065643853540144494401816939301634734169034515932278897941669119471403825528426341760884588190496106376212688821766575177910798404412253539751456325105790758333622021088797242989155339077641106422092755807190435155013854371129145972925591356109027468695078418333529972751235239352923751390365422852561363997065638620135624518313025266019842864874481472974919688499585565674137504805643074781772023323252449611373226947518742614234513995984096803966256726145434589438805362893910045079705531143888390830888723870352211481745067152196765773060687936168567118601695839961282759177442241920445994022861419807991718832774205808124833616369256245194429378085162582343163130829480058092511011866310678204623132088810697545659312682635268545210585868158467317291689602889281571909567021207049970973539350783012790869084523396416554587649622658452707137533709867329087475531170884790422786874963277807132878579514684558686940917786690444690885368632932766593340680440826635037569548635536638811368385939865703005561092423723087416300650359630027177494908344065573711554955021534108732430980096573304333321613435983190574513903180537356318147502566896049022581845045707583392196994673015831252066538599731302144671674212345655538424965669229336747043461
i = 100
while 1:
  if fib(i) == B:
    print "Yes! " + str(i)
    break
  elif fib(i) > B:
    print "No!"
    break
  else:
    i += 1