123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130 |
- /*
- Daniel "Trizen" Suteu
- Date: 26 March 2019
- https://github.com/trizen
- Compute terms of the A307069 OEIS sequence.
- Defintion by Elliott Line, Mar 22 2019:
- Given a special version of Pascal's triangle where only Fibonacci numbers are
- permitted, a(n) is the row number in which the n-th Fibonacci number first appears.
- */
- #include <set>
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int main(int argc, char **argv) {
- set <int> is_fib;
- set <int> seen;
- is_fib.insert(1);
- is_fib.insert(2);
- is_fib.insert(3);
- is_fib.insert(5);
- is_fib.insert(8);
- is_fib.insert(13);
- is_fib.insert(21);
- is_fib.insert(34);
- is_fib.insert(55);
- is_fib.insert(89);
- is_fib.insert(144);
- is_fib.insert(233);
- is_fib.insert(377);
- is_fib.insert(610);
- is_fib.insert(987);
- is_fib.insert(1597);
- is_fib.insert(2584);
- is_fib.insert(4181);
- is_fib.insert(6765);
- is_fib.insert(10946);
- vector <int> row;
- row.push_back(1);
- auto end_of_fib = is_fib.end();
- auto end_of_seen = seen.end();
- bool printed_row = false;
- for (int n = 1; n < 10000000 ; ++n) {
- if (n % 10000 == 0) {
- printf("Processing row %d...\n", n);
- }
- vector <int> t;
- vector <int> fibs;
- int upper = ((n - (n % 2)) >> 1) - 1;
- for (int j = 0; j <= upper; ++j) {
- int v = row[j] + row[j + 1];
- //~ if (v == 610) {
- //~ printf("Found 610 on line %d\n", n);
- //~ }
- if ((v == 1) || (v == 2) || (v == 3) || (v == 5) || (is_fib.find(v) != end_of_fib)) {
- if (seen.find(v) == end_of_seen) {
- seen.insert(v);
- fibs.push_back(v);
- end_of_seen = seen.end();
- }
- t.push_back(v);
- }
- else {
- t.push_back(1);
- }
- }
- //~ if (n <= 10) {
- //~ for (auto k : row) {
- //~ printf("%d ", k);
- //~ }
- //~ printf("\n");
- //~ }
- vector <int> v;
- v.resize(t.size());
- reverse_copy(t.begin(), t.end(), v.begin());
- if (n % 2 == 0) {
- v.erase(v.begin());
- }
- for (int k : fibs) {
- printf("%d -> first appears in row %d\n", k, n);
- if (n > 2544 && !printed_row) {
- printf("The row is: \n");
- for (int z : row) {
- printf("%d ", z);
- }
- printf("\n");
- printed_row = true;
- printf("%d -> first appears in row %d\n", k, n);
- }
- }
- row.clear();
- row.reserve(t.size() + v.size() + 2);
- row.insert(row.end(), t.begin(), t.end());
- row.insert(row.end(), v.begin(), v.end());
- row.push_back(1);
- row.insert(row.begin(), 1);
- }
- return 0;
- }
|