fork download
copy 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <stdint.h>
  4.  
  5.  
  6.  
  7. uint64_t binom(uint64_t n, uint64_t k)
  8. {
  9.     uint64_t c = 1u;
  10.     uint64_t i;
  11.  
  12.     for (i = 0; i < k; i++) {
  13.         c *= n - i;
  14.         c /= i + 1;
  15.     }
  16.  
  17.     return c;
  18. }
  19.  
  20. uint64_t possibilities(uint64_t n)
  21. {
  22.     uint64_t sum = 0u;
  23.  
  24.     for (uint64_t i = 0; i <= n / 2; i++) {
  25.         sum += binom(n - i, i);
  26.     }
  27.  
  28.     return sum;
  29. }
  30.  
  31. int main(void)
  32. {
  33.     for (uint64_t n = 1; n < 81; n++) {
  34.         uint64_t p = possibilities(n);
  35.  
  36.         printf("%llu: %llu\n",
  37.             (long long unsigned) n,
  38.             (long long unsigned) p);
  39.     }
  40.  
  41.     return 0;
  42. }
  43.  
Success #stdin #stdout 0s 9424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1: 1
2: 2
3: 3
4: 5
5: 8
6: 13
7: 21
8: 34
9: 55
10: 89
11: 144
12: 233
13: 377
14: 610
15: 987
16: 1597
17: 2584
18: 4181
19: 6765
20: 10946
21: 17711
22: 28657
23: 46368
24: 75025
25: 121393
26: 196418
27: 317811
28: 514229
29: 832040
30: 1346269
31: 2178309
32: 3524578
33: 5702887
34: 9227465
35: 14930352
36: 24157817
37: 39088169
38: 63245986
39: 102334155
40: 165580141
41: 267914296
42: 433494437
43: 701408733
44: 1134903170
45: 1836311903
46: 2971215073
47: 4807526976
48: 7778742049
49: 12586269025
50: 20365011074
51: 32951280099
52: 53316291173
53: 86267571272
54: 139583862445
55: 225851433717
56: 365435296162
57: 591286729879
58: 956722026041
59: 1548008755920
60: 2504730781961
61: 4052739537881
62: 6557470319842
63: 10610209857723
64: 17167680177565
65: 27777890035288
66: 44945570212853
67: 72723460248141
68: 117669030460994
69: 190392490709135
70: 308061521170129
71: 498454011879264
72: 806515533049393
73: 1304969544928657
74: 2111485077978050
75: 3416454622906707
76: 5527939700884757
77: 8944394323791464
78: 14472334024676221
79: 23416728348467685
80: 37889062373143906
https://ideone.com/7YEGsz
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!