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

Home > Numbers
Fibs and Mods. (Posted on 2016-03-30) Difficulty: 2 of 5

Consider the Fibonacci numbers , F(n) mod N. At some point, N divides F(n) for the first time. Eventually, at F(n+m), N divides F(n+m) for the second time.

Claim 1: F(n+m) /F(n) is always a Lucas number, L(k).

Examples:
N=2: F(n) = 2, F(n+m) = 8; 8/2 = 4 = L(3)
N=3: F(n) = 3, F(n+m) = 21; 21/3 = 7 = L(4)
N=4: F(n) = 8, F(n+m) = 144: 144/8 = 18 = L(6)
N=5: F(n) = 5, F(n+m) = 55: 55/5 = 11 = L(5)
N=6: F(n) = 144, F(n+m) = 46368: 46368/144 = 322 = L(12)
N=7: F(n) = 21, F(n+m) = 987: 987/21 = 47 = L(8)
etc.

It looks as though those Lucas numbers are hopping about, so let's instil some discipline to the order of their appearance:

Claim 2: F(n+m) /F(n) =L(m).

Prove both claims, or find counter-examples.

See The Solution Submitted by broll    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Hints/Tips no proof here, just some verification, and a new fact Comment 1 of 1
A table was made of the first 74 Fibonacci numbers and the first 72 Lucas numbers (actually 75 and 73 respectively, counting the zeroth). Fibonacci or Lucas numbers beyond these have more than 15 digits and so would not be reliable to the accuracy of double precision floating point.

Then, various N were looked up in the Fibonacci numbers for use as a factor, for the first and second times, producing this table.  Not shown are N for which a second multiple was not found below F(74). But all those accounted for verify the claims of the puzzle.

One fact not previously disclosed is that in all these cases, n = m, so that F(n+m) is in fact F(2*n).

  N    n   F(n+m)    m     L(m)
            / F(n)
   2   3        4     3        4
   3   4        7     4        7
   4   6       18     6       18
   5   5       11     5       11
   6  12      322    12      322
   7   8       47     8       47
   8   6       18     6       18
   9  12      322    12      322
  10  15     1364    15     1364
  11  10      123    10      123
  12  12      322    12      322
  13   7       29     7       29
  14  24   103682    24   103682
  15  20    15127    20    15127
  16  12      322    12      322
  17   9       76     9       76
  18  12      322    12      322
  19  18     5778    18     5778
  20  30  1860498    30  1860498
  21   8       47     8       47
  22  30  1860498    30  1860498
  23  24   103682    24   103682
  24  12      322    12      322
  25  25   167761    25   167761
  26  21    24476    21    24476
  27  36 33385282    36 33385282
  28  24   103682    24   103682
  29  14      843    14      843
  30
  31  30  1860498    30  1860498
  32  24   103682    24   103682
  33  20    15127    20    15127
  34   9       76     9       76
  35
  36  12      322    12      322
  37  19     9349    19     9349
  38  18     5778    18     5778
  39  28   710647    28   710647
  40  30  1860498    30  1860498
  41  20    15127    20    15127
  42  24   103682    24   103682
  43
  44  30  1860498    30  1860498
  45
  46  24   103682    24   103682
  47  16     2207    16     2207
  48  12      322    12      322
  49
  50
  51  36 33385282    36 33385282
  52
  53  27   439204    27   439204
  54  36 33385282    36 33385282
  55  10      123    10      123
  56  24   103682    24   103682
  57  36 33385282    36 33385282
  58
  59
  60
  61  15     1364    15     1364
  62  30  1860498    30  1860498
  63  24   103682    24   103682
  64
  65  35 20633239    35 20633239
  66
  67
  68  18     5778    18     5778
  69  24   103682    24   103682
  70
  71
  72  12      322    12      322
  73  37 54018521    37 54018521
  74
  75
  76  18     5778    18     5778
  77
  78
  79
  80
  81
  82
  83
  84  24   103682    24   103682
  85
  86
  87  28   710647    28   710647
  88  30  1860498    30  1860498
  89  11      199    11      199
  90
  91
  92  24   103682    24   103682
  93
  94
  95
  96  24   103682    24   103682
  97
  98
  99
 100
 101
 102  36 33385282    36 33385282
 103
 104
 105
 106  27   439204    27   439204
 107  36 33385282    36 33385282
 108  36 33385282    36 33385282
 109  27   439204    27   439204
 110  30  1860498    30  1860498
 111
 112  24   103682    24   103682
 113  19     9349    19     9349
 114  36 33385282    36 33385282
 115
 116
 117
 118
 119
 120
 121
 122  15     1364    15     1364
 123  20    15127    20    15127
 124  30  1860498    30  1860498
 125
 126  24   103682    24   103682
 127
 128
 129
 130
 131
 132
 133
 134
 135
 136  18     5778    18     5778
 137
 138  24   103682    24   103682
 139
 140
 141  16     2207    16     2207
 142
 143
 144  12      322    12      322
 145
 146
 147
 148
 149  37 54018521    37 54018521
 150
 151
 152  18     5778    18     5778
 153  36 33385282    36 33385282
 154
 155  30  1860498    30  1860498
 156
 157
 158
 159
 160
 161  24   103682    24   103682
 162
 163
 164
 165  20    15127    20    15127
 166
 167
 168  24   103682    24   103682
 169
 170
 171  36 33385282    36 33385282
 172
 173
 174
 175
 176
 177
 178  33  7881196    33  7881196
 179
 180
 181
 182
 183
 184  24   103682    24   103682
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199  22    39603    22    39603
 200

DefDbl A-Z
Dim crlf$,  fib(100), luc(100)


Private Sub Form_Load()
 Form1.Visible = True
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 
 fib(0) = 0: fib(1) = 1
 For i = 2 To 100
   fib(i) = fib(i - 2) + fib(i - 1)
   If fib(i) > 1E+15 Then mxf = i: Exit For
 Next
 Text1.Text = Text1.Text & i & crlf
 
 luc(0) = 2: luc(1) = 1
 For i = 2 To 100
   luc(i) = luc(i - 2) + luc(i - 1)
   If luc(i) > 1E+15 Then mxl = i: Exit For
 Next
 Text1.Text = Text1.Text & i & crlf
 
 For n = 2 To 200
    prev = 0
    hit = 0
    For i = 1 To mxf
      If md(fib(i), n) = 0 Then
        If prev > 0 Then
          m = i - previ
          Text1.Text = Text1.Text & mform(n, "###0") & mform(previ, "###0") & mform(fib(i) / prev, "########0") & "  " & mform(m, "###0") & mform(luc(m), "########0") & crlf
          hit = 1
        End If
        If prev > 0 Then Exit For
        prev = fib(i)
        previ = i
      End If
    Next
    If hit = 0 Then Text1.Text = Text1.Text & mform(n, "###0") & crlf
 Next
  
 Text1.Text = Text1.Text & crlf & " done"
  
End Sub

Function mform$(x, t$)
  a$ = Format$(x, t$)
  If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
  mform$ = a$
End Function

Function md(a, b)
  q = Int(a / b)
  md = a - q * b
End Function


  Posted by Charlie on 2016-03-30 11:28:53
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 (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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