/* A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given: 1/2 = 0.5 1/3 = 0.(3) 1/4 = 0.25 1/5 = 0.2 1/6 = 0.1(6) 1/7 = 0.(142857) 1/8 = 0.125 1/9 = 0.(1) 1/10 = 0.1 Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle. Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part. */ #include #include #include #include using namespace std; using DDList = map; auto recurring_cycle = [](int num) { // start with 10, starting with 1 will // only give 0 on the left of '.' div_t res{10,0}; // list of dividends that tells when the // cycle starts repeating. true // indicates dividend has been seen // earlier DDList ddlist{{10, true}}; // string of recurring digits string recds; // while the dividend has not been seen // earlier while (ddlist[res.rem] == false) { // set it to true, which means // dividend has been seen ddlist[res.rem] = true; res = div(res.quot, num); // add the quotient digit to the // recurring digit string recds += (res.quot+48); // make the remainder multiplied // by 10 as the new dividend res.quot = (res.rem *= 10); } return make_pair(recds, num); }; auto get_maxx = [](auto&& lhs, auto&& rhs) { return lhs.first.size() > rhs.first.size() ? lhs : rhs; }; int main() { // holds the number with maximum // recurring digits string pair max_recurr{"",-1}; for(int num{2}; num<=4065; ++num) { auto curr_rec = recurring_cycle(num); max_recurr = get_maxx(max_recurr, curr_rec); } cout << "number = " << max_recurr.second << '\n' << "0." << max_recurr.first << '\n' << "len = " << max_recurr.first.size() << "\n\n"; }

[Challenge] Longest_Non_Recurring_Sequence.cpp