3 ms·
Here's a fairly slow obfuscated Fibonacci function in Python I wrote a long time ago: f=lambda n:(4<<n*(3+n))//((4<<2*n)-(2<<n)-1)&~-(2<<n) As you can see
by nightcracker 8y ago
Here's a fairly slow obfuscated Fibonacci function in Python I wrote a long time ago:
f=lambda n:(4<<n*(3+n))//((4<<2*n)-(2<<n)-1)&~-(2<<n)
As you can see it's a strictly integer arithmetic closed form. Bonus points to those who can figure out how it works.
- edflsafoiewq 8y agoAmazing!! I had fun figuring it out. My analysis: https://pastebin.com/8hzSmxBu https://pastebin.com/8hzSmxBu
- nightcracker 8y agoYou 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.