/* YELLOWSTONE The Yellowstone permutation/sequence: * Y(n) = n, if 1 <= n <= 3 * otherwise the smallest number not already in the sequence having at least one common factor other than 1 with Y(n-2), but is relatively prime with Y(n-1). (add edit: For n > 3, gcd(Y(n), Y(n-1)) = 1 and gcd(Y(n), Y(n-2)) > 1) Write a program that outputs the first 100 terms of the sequence. Also, output the 1000th, 2000th, 3000th ... terms, upto the maximum your algorithm and/or language can calculate on SL. Notes: The sequence is called also permutation because it is a permutation of natural numbers (positive integers). The graph of the sequence shows smooth periods of alternating even and odd numbers, interrupted by small downward spikes followed by large upward spikes, suggesting the eruption of geysers in Yellowstone Park. https://www.sololearn.com/post/247241/?ref=app Note: One may need to run the program multiple times to get the output. */ #include #include #include #include using namespace std; int main() { unordered_set seen; vector Y{1,2,3}; seen.reserve(6000); int _2 = 2, _1 = 3, nxt = 4; for(int i = 0; i < 2500; ++i) { int av = nxt; while(true) { if(gcd(_1, av) == 1 && gcd(_2, av) > 1 && !seen.count(av)) { Y.emplace_back(av); seen.emplace(av); _2 = _1; _1 = av; while(seen.count(nxt)) { seen.erase(nxt); ++nxt; } break; } ++av; } } //print first 100 terms only for(int i = 0; i < 100; ++i) cout << Y[i] << ' '; cout << "\n\n"; cout << "Yellowstone[100] = " << Y[99] << '\n'; cout << "Yellowstone[1000] = " << Y[999] << '\n'; cout << "Yellowstone[2000] = " << Y[1999] << '\n'; cout << "Yellowstone[2500] = " << Y[2499] << '\n'; }

[Challenge] Yellowstone.cpp