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.
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 |
no proof here, just some verification, and a new fact
