Generating nth Non-Fibonacci Number

nthnonfib.cc

#include <bits/stdc++.h>
using namespace std;

uint64_t nthnonfib(int32_t n) {
    vector<uint64_t> fibs = {2, 3, 5};
    for (int x = 3; x < 50; ++x)
        fibs.push_back(fibs[x - 1] + fibs[x - 2]);
    vector<uint64_t> gaps = {0, 1, 2};
    for (int x = 3; x < 50; ++x)
        gaps.push_back(gaps[x - 1] + gaps[x - 2] + 1);
    partial_sum(gaps.begin(), gaps.end(), gaps.begin());
    uint64_t result;
    for (int32_t x = 1; x < gaps.size(); ++x) {
        if (gaps[x] >= n) {
            result = fibs[x] + n - gaps[x - 1];
            break;
        }
    }
    return result;
}

int main() {
    for (int32_t x = 1; x < 40; ++x)
        cout << nthnonfib(x) << ((x == 39)?'\n':' ');
    return 0;
}

nthnonfib.py

#!/usr/bin/python
# -*- encoding: utf-8 -*-
# pylint: disable=invalid-name,missing-docstring,bad-builtin

def nthnonfib(n):
    fibs = [2, 3, 5]
    gaps = [0, 1, 2]
    for x in xrange(50):
        fibs.append(fibs[-1] + fibs[-2])
    for x in xrange(50):
        gaps.append(gaps[-1] + gaps[-2] + 1)
    for x in xrange(1, len(gaps)):
        gaps[x] += gaps[x - 1]
    result = None

    # linear search, can be replaced with binary search
    for x in xrange(1, len(gaps)):
        if gaps[x] >= n:
            result = fibs[x] + n - gaps[x - 1]
            break
    return result

for i in xrange(1, 40):
    print nthnonfib(i),