Qual o menor número de compassadas que você precisa dar pra construir um número? Para n inteiro, f(2^n)=n, f(n) deve depender da quantidade de bits 1 no número em binário, mas eu tô indo almoçar daqui a pouco e não vou fazer a conta agora.
Uepaaa! Acabei de notar que o número mínimo de compassadas é equivalente à minimal addition chain, então não apenas não tem forma fechada, como é NP-completo. E isso só pros inteiros, pra sqrt() deve ser ainda pior.
Nenhum comentário:
Postar um comentário