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

Home > Just Math
Binomial GCDs (Posted on 2016-08-08) Difficulty: 3 of 5
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!:

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Heuristic solution Comment 2 of 2 |
   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
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