93 karma · joined September 20, 2025
def fibonacci(k):
a,b=(0,1)
for i in range(k.bit_length()-1,-1,-1):
d=a**2
c=2*a*b-d
d+=b**2
(a,b)=(d,c+d) if k>>i&1 else (c,d)
return a
see https://oeis.org/wiki/User:Natalia_L._Skirrow/linear_recurre... (warning: old and bad and in need of revision), https://github.com/sympy/sympy/pull/30452 and https://github.com/sympy/sympy/pull/30541 for details of how to make similarly fast programs for arbitrary linear-recurrent sequences.you can also encode polynomials into integers; see https://mathstodon.xyz/@peterluschny/116320199782572958 and the following prog from https://codegolf.stackexchange.com/a/279771
lambda n:pow(p:=2<<n,n,p*p+~p)//p
both of these would be more intensive on the arithmetic side rather than control flowalso you could at least wrap the existing one in a `functools.cache`
is a particularly humorous instance of https://en.wikipedia.org/wiki/RAS_syndrome
cf. Mozilla Firefox Is Dying (2025) https://news.ycombinator.com/item?id=44939271 and a list of posts from 2024 https://news.ycombinator.com/item?id=39303736
(and also know whether the safeguards they're trying to implement/improve towards have been achieved or are theoretical)
(recall that OpenAI thought GPT-2 was too powerful to release for approximately tantamount reasons)
it is still O(n) weight to transport, so O(n^2) amortised; if you liken having a stronger hand that can carry more spaghetti to parallelisation, it's beaten by O(log^2 n) sorting algorithms on parallelised classical computers.
see the asymptotic formulae by Vaclav Kotesovec and Natalia L. Skirrow (me!) on https://oeis.org/A000110; the former (together with Stirling's approximation) says bell(n)/n! ~ exp(n/W(n) - nlog(W(n)) - 1) / √(τ(1+W(n))), and the latter says that the average number of subsets in a partition on [n] counted by the Bell number is ~ n/log(n), while for a permutation it's only = H_n ~ log(n).
(using W(n) ~ log(n), although it's more precisely log(n) - log(log(n)) + o(1); its appearance here comes from solving for the radius from the origin at which |exp(exp(z)-1) / z^(n+1)| has a saddle point in the complex plane, which lets you pretend your contour integral from Cauchy's formula is a Gaussian and approximate it in terms of the generating function's logarithmic second derivative)
another cool adjacent result that comes out of saddlepointery on e.g.f.s is that (# of sets of lists on [n], A000262(n))/(# of sets of cycles on [n], n!) ~ exp(2√n - 1/2)/(2√π * n^(3/4)); this is also the expected number of preimages under the surjection A000262(n) -> n! from closing lists into cycles, or equivalently the expected product of cycle lengths in a random permutation ∈ Sₙ, and is my favourite example of a function whose growth is between polynomial and exponential
and the F keys come back on the touch bar if you hold the fn button
especially if it's something that the major companies had already stumbled upon (something equivalent to) and regarded as a trade secret.
> He turned to Google’s Gemini AI for advice and decided to create a “hot girl” crafted specifically for the “MAGA/conservative niche,” after the software told him that “the conservative audience (especially older men in the US) often has higher disposable income and is more loyal,” according to Wired.
i have undergone an undergrad differential equations module that taught exclusively ad-hoc methods for certain families of equation that no working mathematician needs to know since they were all subsumed into and superseded by computer algebra systems, but the subject i would enjoy replacing it with (generating functions) is similarly old in origin (perhaps even earlier, since Euler used most of the techniques that an undergrad class would cover before diffeqs were considered an object of study) but has happened to become more useful with the advent of CASes instead of less.