N is a positive integer.
Find the GCD of C(2n,1), C(2n,3), ….C(2n,2n-1)
where C(a,b) = a!/(a - b)!b!:
10 kill "bingcds.txt":open "bingcds.txt" for output as #2
20 for N=1 to 300
30 if N=1 then
40 :G=2
50 :else
60 :G=gcd(combi(2*N,1),combi(2*N,3))
70 :for I=5 to 2*N-1 step 2
80 :G=gcd(G,combi(2*N,I))
90 :next
100 print N,G
110 print #2,N,G
120 next
130 close #2
finds
1 2
2 4
3 2
4 8
5 2
6 4
7 2
8 16
9 2
10 4
11 2
12 8
13 2
14 4
15 2
16 32
17 2
18 4
19 2
20 8
21 2
22 4
23 2
24 16
25 2
26 4
27 2
28 8
29 2
30 4
31 2
32 64
33 2
34 4
35 2
36 8
37 2
38 4
39 2
40 16
41 2
42 4
43 2
44 8
45 2
46 4
47 2
48 32
49 2
50 4
51 2
52 8
53 2
54 4
55 2
56 16
57 2
58 4
59 2
60 8
61 2
62 4
63 2
64 128
65 2
66 4
67 2
68 8
69 2
70 4
71 2
72 16
73 2
74 4
75 2
76 8
77 2
78 4
79 2
80 32
81 2
82 4
83 2
84 8
85 2
86 4
87 2
88 16
89 2
90 4
91 2
92 8
93 2
94 4
95 2
96 64
97 2
98 4
99 2
100 8
101 2
102 4
103 2
104 16
105 2
106 4
107 2
108 8
109 2
110 4
111 2
112 32
113 2
114 4
115 2
116 8
117 2
118 4
119 2
120 16
121 2
122 4
123 2
124 8
125 2
126 4
127 2
128 256
129 2
130 4
131 2
132 8
133 2
134 4
135 2
136 16
137 2
138 4
139 2
140 8
141 2
142 4
143 2
144 32
145 2
146 4
147 2
148 8
149 2
150 4
151 2
152 16
153 2
154 4
155 2
156 8
157 2
158 4
159 2
160 64
161 2
162 4
163 2
164 8
165 2
166 4
167 2
168 16
169 2
170 4
171 2
172 8
173 2
174 4
175 2
176 32
177 2
178 4
179 2
180 8
181 2
182 4
183 2
184 16
185 2
186 4
187 2
188 8
189 2
190 4
191 2
192 128
193 2
194 4
195 2
196 8
197 2
198 4
199 2
200 16
201 2
202 4
203 2
204 8
205 2
206 4
207 2
208 32
209 2
210 4
211 2
212 8
213 2
214 4
215 2
216 16
217 2
218 4
219 2
220 8
221 2
222 4
223 2
224 64
225 2
226 4
227 2
228 8
229 2
230 4
231 2
232 16
233 2
234 4
235 2
236 8
237 2
238 4
239 2
240 32
241 2
242 4
243 2
244 8
245 2
246 4
247 2
248 16
249 2
250 4
251 2
252 8
253 2
254 4
255 2
256 512
257 2
258 4
259 2
260 8
261 2
262 4
263 2
264 16
265 2
266 4
267 2
268 8
269 2
270 4
271 2
272 32
273 2
274 4
275 2
276 8
277 2
278 4
279 2
280 16
281 2
282 4
283 2
284 8
285 2
286 4
287 2
288 64
289 2
290 4
291 2
292 8
293 2
294 4
295 2
296 16
297 2
298 4
299 2
300 8
which seems to indicate that the required gcd is twice the highest power of 2 that will divide evenly into n. I guess that's the same as the lowest power of 2 that does not divide evenly into n. For example, 16 divides evenly into 240, but 32 does not, so the gcd sought is 32.
|
|
Posted by Charlie
on 2016-08-08 14:34:12 |
Heuristic solution
