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

 Fibs and Mods. (Posted on 2016-03-30)

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.)
 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)

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

 Search: Search body:
Forums (0)