Resto de la división $3^n$ por $2^n$ .

Question

Me gustaría encontrar el resto de dividir $3^n$ por $2^n$ Es decir, me gustaría encontrar el valor de $r$ en la expresión $$3^n=q2^n+r,$$ donde $q\in\mathbb{Z}$ y $0<r<2^n$ .

Sé que puede ser $$r=3^n-2^n\left\lfloor\frac{3^n}{2^n}\right\rfloor$$ Pero no es agradable. ¿Puedo hacerlo sin suelo?

Pensé que podría encontrarlo resolviendo esto $$\sum_{i=0}^{k}{n\choose i}2^i<2^n$$ donde $k\le n$ . Funcionará porque $$3^n=(1+2)^n=\sum_{i=0}^n{n\choose i}2^i,$$ pero no puedo encontrar el $k$ valor.

Answer 1

Esta secuencia aparece en la Enciclopedia Online de Secuencias de Números Enteros:

https://oeis.org/A002380

No parece haber una fórmula explícita para ello, y parece crecer exponencialmente, pero de forma desigual. A veces, disminuye, pero a la larga, se duplica aproximadamente cada vez $n$ incrementa en $1$ es decir, cuando $n$ aumenta a $n+k$ tenemos $f(n)$ aumentando en una proporción de aproximadamente $2^k$ más evidente en el caso de los grandes $k$ .