Fórmula para la secuencia que repite dos veces cada potencia de $2$

Question

Estoy trabajando en un proyecto que necesita calcular lo que $a_n$ elemento del conjunto de números $$1, 1, 2, 2, 4, 4, 8, 8, 16, 16 \ldots$$ será.

$n$ puede ser un número bastante grande por lo que por cuestiones de rendimiento tengo que calcular la fórmula para este conjunto de números ( Nota: primer elemento puede ser diferente). Lo que he hecho hasta ahora es que he conseguido averiguar cómo calcular el siguiente elemento utilizando el elemento anterior. Mi fórmula para esto es

$$a_n = a_{n-1}\cdot 2^{\frac{1 + (-1)^{n-1}}2}$$

Ahora, a partir de esto, quiero calcular $a_n$ elemento utilizando $a_1$ elemento. con esto estoy atascado.

Answer 1

$a_n$ se denomina "secuencia" y no serie. Volviendo a la pregunta, $$a_n = 2^{\lfloor n/2 \rfloor}$$ debería hacer el trabajo, donde $\lfloor x \rfloor$ es el mayor número entero $\leq x$ , donde $n$ va de $0$ . Normalmente la función para hacer esto, está disponible a través del comando floor() en la mayoría de los idiomas. Si su primer elemento es $a$ y no $1$ , su $$a_n = a \times 2^{\lfloor n/2 \rfloor}$$

Answer 2

Supongo que está pensando en $a_1,a_1,2a_1,2a_1,4a_1,4a_1, \dots$ . Entonces funcionará lo siguiente: $$a_n=a_1\times 2^{\lfloor \frac{n-1}{2} \rfloor}.$$ Aquí $\lfloor x\rfloor$ es la función "suelo", donde $\lfloor x\rfloor$ es el mayor número entero que es $\le x$ .

Parece que está etiquetando su secuencia como $a_1,a_2,a_3,\dots$ . Muchos matemáticos prefieren que el primer índice sea $0$ . En ese caso, tendrá $a_n=a_0\times 2^{\lfloor \frac{n}{2} \rfloor}$ .

Answer 3

Además de la función Greatest Integer, esta secuencia también generará la serie requerida. $$ \huge 2^{ \frac 1 2 \left ( n + \frac{1 + (-1)^{n+1}}{2} \right )} $$ Compruébelo en Wolframalpha.

Answer 4

un ejemplo de código en c++ (con la fórmula $a_n = 2^{\lfloor n/2 \rfloor}$ que ya dio Marvis):

a_n = a << (n >> 1)

El operador de turno << le dará una implementación rápida para calcular $2^m$ . El operador >> dará una implementación rápida del cálculo de $\lfloor n/2 \rfloor$ .

Esto podría implementarse de forma muy eficiente en el lenguaje C/assembly. Los propios desplazamientos de bits ya son instrucciones x86, y como ambas operaciones son por potencias de dos, se puede utilizar lo siguiente:

#include<stdio.h>
#include<stdlib.h>
int main(int argc, char\*argv\[\])
{
        int i=0;
        int a=atoi(argv\[1\]);
        int n=atoi(argv\[2\]);

        for( i = 0; i<n; i++)
        {
                printf("%d,%d,%d\\n",i,i>>1,a<<(i>>1));
        }
        return 0;
}

Corriendo gcc -O2 -S seq.c para inspeccionar el código generado en ensamblador, la 'matemática' se completa en dos instrucciones de cpu: sarl %ecx y sall %cl, %r8d . No puede ser más rápido que esto.

Answer 5

Cuando se tiene una secuencia desconocida, lo mejor es consultar el Enciclopedia en línea de las secuencias de números enteros (OEIS) . Este es A016116 . En esa página se ofrecen varios foros para ello, entre ellos el $2^{\lfloor n/2 \rfloor}$ respuesta dada anteriormente.