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

Home > Numbers
Fibo's zeroes repeated (Posted on 2017-12-14) Difficulty: 3 of 5
Does one of the first 10^8+1 Fibonacci numbers terminate with 4 zeroes?

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer-aided solution Comment 1 of 1
The Fibonacci numbers from F(3) to F(20) are:

3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
17 1597
18 2584
19 4181
20 6765

This is far enough that we have 4-digit numbers. From there on, it seems to be the case that the last 4 digits repeat in a cycle of 15,000. Actually the cycle of 15,000 starts from the very beginning, as F(15001) ends in 0001 and F(15002) also ends in 0001.

There are actually two Fibonacci's that end in 0000 within each cycle of 15,000. F(7500) ends in 0000 and F(15000) ends in 0000. So there are 13,333 Fibonacci numbers ending in four zeros within the first 10^8+1 Fibonacci numbers.

In the repeating cycle of 15,000, of the 10,000 possible sets of last four digits, 

3125 occur 0 times (i.e., not at all) 
2500 occur once 
1250 occur twice (including the requested 0000)
2500 occur 3 times 
625 occur 4 times.

F(7500) from UBASIC is

11423965231520587047220488928656904198487186633317560797959030595738263643588305
26396432108051699142993762888622955534014664444274447318546077830293474380700224
81096957412087824111591899946515209300912020351012693505236094172765422096822611
68150544790025062794209091503702088574338650460569295592498666443239807989522593
07256215864094746865688764587935620130159484187249149755638955581727750834905833
04980075838142701233297243532331560291279109683700527348111926604927333753944726
92191584489489590970254440914222778382439339334175624660291588778456250479185237
89830911231882998435821633734754901433651748649664322450277338004207117436059719
23430563184892870384470047309220739808700729907060675086240384078884712940489122
94153491398930715643640170172837379127969101176561450586945715460276780809807889
66427281831686571172498564655455930533434031899461218526071904200896031126900012
26725897312834196080983033672603823796604022618865749522117836831044533342816844
25994447306306414660032519055079504313562694958935754118796157632978970220780288
16899218169970892297141706773514492946119363908144520078688154933115038121607370
54175311667866346904692064186115246630138541980452848067207352737150468887049168
21855277543026346215355286395854263168251068150374988851620501196943905031285049
07762844380405213450702250468248329339621526818662012476237974466809216603531455
35417315372459462564228618525730062304923222596303422943508271848406075099692893
28320360093204783447860955806396350723341261564285649453007949089154165288839814
442677339344794691881510389855765582716774490000 

F(15,000) was too big for UBASIC, but from Mintoris Basic it's:

29182248242049138302364072236985132022309626557118287746171387351566244580791831
28895718558218554430571700189155441406738131392889920065194454205115225018718391
29697256085064947056503909529854158932872201875201399667128848417938314849451512
80251960808688232597349418604794382511597691711839374750439265336824593717294170
83036155111469356511900052820298859112265364211898572296023436366156951405784120
64630184957031169425874381333306782199854518478703841243438559001961942476419716
04943146139885206893749653270248478237783043082636421327892530850832454800155793
49360777155140035885188011249043993467859821472383029110957880470854642451535063
38016606869623553997201937064220291622262717935478025996550369392041093778032074
38477789457557773078460384099773421220006356579358462513968481276194426217627589
40055303978522742267406558375512779366721716170013216439020225432171175985299929
70057551787943572171175262896613570929057258741106916372769543386513808605761180
11790859849829136165123248053844353464465467072640390717903340313708291819754887
21389304077123834445870695438780990298271493518090592289188901951503845340770184
04146215681472025875766068729891987655254387174101578844808330116467762851448877
55166638123327793716822826193382532706399108385711032590830112491386676641040766
41108573417400066940838850572514071180179569089376179743576707808339959734047557
93454757776213733933029325002162671790383725810839223584319727751444653619212527
72289183363125212603246616137453501488150115174965470654181859797874741853803272
20023875779204894155667506825338985285068161037704759419742583773644640284254003
30064280519208784541012452161205695725205041539841970590789521162391228925401795
41200754259808525933116211972167058914917662470916001054298938922284579619744639
99503100504334189935611659533309538900039739205833457158460057179582428432260916
61882659750717437634079361927711565054620110900859791636070975947216677546937719
12072978408551926093229847600577154679576957287489586605541521630797147141709297
25545418555050200044392009304359154848478420329668823001271474038972726230992045
82004595855388008043208297987914915116669232439687141874091429449369803550137870
51521143099667203044287891757236822980374838854762351188279389182418431012559462
26811664953489575189445795968915863389780044517017264572850401549712653508985191
94486525672226125702900165135675283777194258607147558727730735917052683469304395
66775970880854911465227014137575774610416112394676679850525227280947542860809422
80959827271805687826734091677561853300348884062109014206178543779569538944174514
04316156563779507774067824149279372027410313468586412958654870462174116992864773
00364362824280983558352903869901795048263629137358073370262333684318965424474992
09876273563904559410199255585794894370213256312140729030832252393440233519665318
35713254402702444405165631589535469628719114302631638580677411935571507343153437
25169972548609075935716664757491287218595644497748836134835762459040151205558284
26996046220143025833140676736959813462032334663787968976924788130985098812423607
97278617948316663931666162574107570737272044374680294118782065306140908611007655
976683548980000





DefDbl A-Z
Dim crlf$, used(10000), ctr(100)


Private Sub Form_Load()
 Form1.Visible = True
 
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 
 f1 = 1: f2 = 1
 For i = 3 To 20
   f3 = f1 + f2
   f1 = f2: f2 = f3
   Text1.Text = Text1.Text & i & Str(f2) & crlf
   DoEvents
 Next
 
 For i = 1 To 10000
   f3 = f1 + f2
   f3 = f3 Mod 10000
   f1 = f2: f2 = f3
  ' Text1.Text = Text1.Text & i & Str(f2) & crlf
   DoEvents
 Next
 sf1 = f1: sf2 = f2
 
 
 Do
   f3 = f1 + f2
   f3 = f3 Mod 10000
   If f3 = 0 Then Text1.Text = Text1.Text & crlf & "found one" & crlf
   f1 = f2: f2 = f3
 '  Text1.Text = Text1.Text & Str(f2) & crlf
   ct = ct + 1
   DoEvents
 Loop Until f1 = sf1 And f2 = sf2
 
 f1 = 1: f2 = 1
 For i = 3 To 15002
   f3 = f1 + f2
   f3 = f3 Mod 10000
   used(f3) = used(f3) + 1
   
   If f3 = 0 Or i <= 20 Or i > 15000 And i < 15020 Then
      Text1.Text = Text1.Text & i - 2 & "-" & i & "  " & Str(f1) & Str(f2) & "    " & f3 & crlf
   End If
   f1 = f2: f2 = f3
 Next
  Text1.Text = Text1.Text & crlf & crlf
  
 For i = 0 To 10000
    ctr(used(i)) = ctr(used(i)) + 1
    DoEvents
 Next
 
 For i = 0 To 100
   If ctr(i) > 0 Then Text1.Text = Text1.Text & i & Str(ctr(i)) & crlf
 Next
 
 
 Text1.Text = Text1.Text & crlf & ct & " done"
  
End Sub

Manually corrected count of sets of four that don't appear (was 1 too high).

Edited on December 14, 2017, 12:42 pm
  Posted by Charlie on 2017-12-14 11:04:56

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


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

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