# Project Euler - Problem 73

Apr 29th, 2016
206
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. #include <math.h>
5. #include <string.h>
6. #include <stdlib.h>
7.
8. using namespace std;
9.
10. /*
11.     How many fractions lie between 1/3 and 1/2 in the sorted set of
12.     reduced proper fractions for d = 12,000?
13. */
14.
15. /*
16.     Data:
17.         1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 3, 3, 3, 3, 4, 3, 4, 4,
18.         4, 4, 5, 4, 5, 5, 5, 5, 6, 5, 6, 6, 6, 6, 7, 6, 7, 7, 7, 7, 8, 7,
19.         8, 8, 8, 8, 9, 8, 9, 9, 9, 9, 10, 9, 10, 10, 10, 10,
20.
21.     Formula:
22.         a(n) = floor(n/6)+1 unless n=1(mod6); if n=1(mod6), a(n) = floor(n/6)
23.
24.         Bob Selcoe, Sep 27 2014
25.
26.     Reference:
27.         https://oeis.org/A103221
28. */
29. long long A103221(long long n) {
30.     if(n % 6 == 1)
31.         return n / 6;
32.     else
33.         return (n / 6) + 1;
34. }
35.
36. long long countProperFractions(int l) {
37.     int i, j;
38.     long long r;
39.     vector<int> mu(l + 1, 0);
40.
41.     //Init
42.     r = 0;
43.
44.     mu[1] = 1;
45.
46.     for(i = 1; i <= l; i++) {
47.         //Generate Mobius
48.         for(j = 2 * i; j <= l; j += i)
49.             mu[j] -= mu[i];
50.
51.         //Calculate Mobius inverse values
52.         if(i >= 2)
53.             for(j = 2; i * j <= l; j++)
54.                 r += mu[i] * A103221(j);
55.
56.         if(i >= 4)
57.             r += A103221(i);
58.     }
59.
60.     return r;
61. }
62.
63. int main() {
64.     cout << "result = " << countProperFractions(12000) << endl;
65.
66.     return 0;
67. }
RAW Paste Data