All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Fibonacci tail (Posted on 2019-09-05) Difficulty: 2 of 5
What is the smallest (positive) integer n such that the decimal representation of the nth Fibonacci number ends in four zeroes?

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
computer soln + a little more Comment 1 of 1
The answer I get is n=7500

But of note is the pattern:
 
# of 0's     smallest n
-------------------------
1               15
2              150
3              750
4             7500


indicating a pattern in the factorization of the nth Fib #
There is a "beat" where the factors include 2^i 5^j and the resulting "first time" for j 0's is when j=i  (while typically i>j) . This is not a great mathematical description, but I am pretty sure the pattern can be traced to a formula. 

Here are the patterns:
5^j is a factor of F(n) if and only if 5^j is a factor (in the sense of a divisor) of n

Now the pattern of 2^i is more complex. Consider that the F numbers go odd, odd, even, odd odd, even, etc...
If we look just at the even ones, the exponent (i) for 2 in its prime decomposition follows this pattern: 1, 3, 1, 4, 1, 3, 1, 5, ... 
The pattern is easier to see without the 1's and looking at the 2's exponent in each 6th F(n):
 
3 4 3 5 3 4 3 6 3 4 3 5 3 4 3 7 3 4 3 5 3 4 3 6 3 4 3 5 3 4 3 8...

It's at n = 7500 that the patterns first collide with a 5^4 in (n)'s factorization.  7500 = 12 * 5^4, (it is the twelfth occurrence) and fits with the 2^4 factors being separated in multiples of 12 n's. 

        program lo

        integer n,dig,digits,i1(2000),i2(2000),carry,dum(2000)

        data i1,i2/4000*0/

        digits=2000

        i1(digits)=1

        i2(digits)=1

           do n=3,8000

c          do n=3,10

                carry=0

                do dig=digits,1,-1

                dum(dig)=i1(dig)+i2(dig)+carry  

                   if(dum(dig).gt.9)then

                   carry=1

                   dum(dig)=dum(dig)-10

                   else

                   carry=0

                   endif


                   if(dig.eq.1.and.i1(1)+i2(1)+carry.gt.9)then

                   print*,' too big, n ',n

                   stop

                   endif

                enddo

           if(dum(digits).eq.0.and.dum(digits-1).eq.0.and.

        1   dum(digits-2).eq.0.and.dum(digits-3).eq.0)then

           print 1,n,(dum(j),j=1,digits)

1          format(i5,1x,4000i1)

           stop

           endif

                do dig=digits,1,-1

                i1(dig)=i2(dig)

                i2(dig)=dum(dig)

                enddo

           enddo

        print 1,n,(dum(j),j=1,digits)

2       format(i5,1x,1000i1)

           end  

        


 7500 

F(7500) = 

00000000000000114239652315205870472204

88928656904198487186633317560797959030

59573826364358830526396432108051699142

99376288862295553401466444427444731854

60778302934743807002248109695741208782

41115918999465152093009120203510126935

05236094172765422096822611681505447900

25062794209091503702088574338650460569

29559249866644323980798952259307256215

86409474686568876458793562013015948418

72491497556389555817277508349058330498

00758381427012332972435323315602912791

096837005273481119266049273337539447269

219158448948959097025444091422277838243

933933417562466029158877845625047918523

789830911231882998435821633734754901433

651748649664322450277338004207117436059

719234305631848928703844700473092207398

087007299070606750862403840788847129404

891229415349139893071564364017017283737

912796910117656145058694571546027678080

980788966427281831686571172498564655455

930533434031899461218526071904200896031

126900012267258973128341960809830336726

038237966040226188657495221178368310445

333428168442599444730630641466003251905

507950431356269495893575411879615763297

897022078028816899218169970892297141706

773514492946119363908144520078688154933

115038121607370541753116678663469046920

641861152466301385419804528480672073527

371504688870491682185527754302634621535

528639585426316825106815037498885162050

119694390503128504907762844380405213450

702250468248329339621526818662012476237

974466809216603531455354173153724594625

642286185257300623049232225963034229435

082718484060750996928932832036009320478

344786095580639635072334126156428564945

300794908915416528883981444267733934479

4691881510389855765582716774490000


Edited on September 5, 2019, 8:12 pm
  Posted by Steven Lord on 2019-09-05 10:48:07

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (2)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information