3 ms·

Amazing!! I had fun figuring it out. My analysis: https://pastebin.com/8hzSmxBu https://pastebin.com/8hzSmxBu

• nightcracker 8y ago
  You pretty much got it, although the analysis becomes a lot simpler if you consider evaluating the generating function in base b by substituting x = b. I'll use multiples of 10 here for visual understanding: >>> import decimal >>> decimal.getcontext().prec = 50 >>> b = decimal.Decimal(10**3) >>> b/(b**2 - b - 1) Decimal('0.0010010020030050080130210340550891442333776109885996') For a large enough b we don't have to worry of overflow from the next terms. So then we can shift k terms, mod b to get rid of the earlier terms, and floor to get rid of (the infinite) later terms: >>> k = 6 >>> b**k * b/(b**2 - b - 1) Decimal('1001002003005008.0130210340550891442333776109885996') ^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mod b floor So for any sufficiently large b we have floor(b^(k+1)/(b^2 - b - 1)) % b. And if we let b = 2^(k+c) for a sufficiently large constant c we use asymptotics to find that this is a sufficiently large b for large k, and check the first couple numbers to find that b = 2^(k+1) works.