Asintóticas de la suma del indicador cuadrado para subsecuencias de dígitos

Question

Introducir la función de $g(n)$ definido por entero positivo argumentos $n$ como el recuento de los cuadrados de los enteros positivos entre los números que se pueden formar tomando algunas larga de los dígitos de la representación binaria de $n$ y la interpretación de esta larga como un número binario. Todas las subsecuencias contribuir.

Por ejemplo, $5 = (101)_2$ y las subsecuencias de los dígitos de $$ (1)_2 = 1, (0)_2 = 0, (1)_2 = 1, (10)_2 = 2, (11)_2 = 3, (01)_1 = 1, (101)_2 = 5$$ y esto incluye a la plaza "uno" tres veces, por lo $g(5) = 3.$

Al $n = 9 = (1001)_2$, se obtienen los siguientes subsecuencias: $$ (1)_2 = 1, (0)_2 = 0, (0)_2 = 0, (1)_2 = 1, (10)_2 = 2, (10)_2 = 2, (11)_2 = 3, (00)_2 = 0, (01)_2 = 1, (01)_2 = 1$$ y $$ (100)_2 = 4, (101)_2 = 5, (101)_2 = 5, (001)_2 = 1, (1001)_2 = 9$$ y esto incluye siete plazas, por lo $g(9) = 7.$

El comportamiento de $g(n)$ es muy errático, que van desde lineal para $n=2^k$ a logarítmica para$n=2^k-1,$, lo que nos motiva a hacer la siguiente pregunta. ¿Cuál es el primer término de la asintótica de expansión de la orden promedio de $g(n)$? I. e. encontrar el asymptotics de $$ \frac{1}{n} \sum_{k=1}^n g(k).$$

Podría ser útil para establecer y demostrar la forma cerrada de expresiones para valores especiales de $g(n)$, por ejemplo, tenemos $g(2^k) = 2^{k-1}$ $g(2^k-1) = k$ como se señaló anteriormente (probar estos). Aquí están los primeros términos de $g(n):$ $$1, 1, 2, 2, 3, 2, 3, 4, 7, 4, 5, 4, 4, 3, 4, 8, 15, 9, 12, 8, 9, 6, 7, 8, 11$$

Este problema no es adecuado para la experimentación numérica debido a $g(n)$ fluctúa rápidamente. Para aquellos que quieran probar de todos modos aquí está un poco de C código. (Iba a memoize esto de la misma manera en que yo memoized el Arce de rutina, pero nunca llegó a hacerlo. Esta es la razón por la que el código se ve como se hace).

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <readline/readline.h>

unsigned long long isqrt(unsigned long long n)
{
 si(!n) return 0;

 unsigned long long a = 1, b = n, a mediados;

 do {
 mid = (a+b)/2;
si(mediados de*a mediados de>n){
 b = centro;
}
else{
 un = centro;
}
 } while(b-a>1);

 de regreso a;
}

unsigned long long g(unsigned long long n)
{
 int bits[256], len = 0;
while(n>0){
 bits[len++] = n%2;
 n >>= 1;
}

 unsigned long long res = 0, ind;
 para(ind=0; ind<(1<<len); ind++){
 unsigned long long varind = ind;
 int subseq[256], srcpos=0, pos=0;
mientras(varind>0){
si(varind%2){
 subseq[pos++] = bits[srcpos];
}
srcpos++;
 varind >>= 1;
}

 unsigned long long val = 0;
 int seqpos = 0;
mientras(seqpos<pos){
 val += (1<<seqpos)*subseq[seqpos];
seqpos++;
}

 unsigned long long cs = isqrt(val);
 if(val>0 && cs*cs == val){
res++;
}
}

 return res;
}

unsigned long long gavg(unsigned long long max)
{
 unsigned long long res = 0, n;

 para(n=1; n<=max; n++){
 res += g(n);
}

 return res;
}

int main(int argc, char *argv)
{
 unsigned long long max;
 char *línea;

 while((linea = readline("> ")) != NULL){
 if(sscanf(linea, "%llu", &max)==1){
 unsigned long gsum = gavg(máx.);

 long double asympt = (long double)gsum;
 asympt = asympt/(long double)max;

 printf("%llu %lle\n", gsum, asympt);
}
libre(en línea);
}

exit(0);
}

Este es el Arce de código, que es notablemente más lento.

g :=
proc(n)
 opción de recordar;
 local dlist, ind, flind, sseq, len, sel, val, r, res;

 dlist := convert(n, base, 2);
 len := nops(dlist);

 res := 0;
 para la ind de 0 a 2^len-1 hacer
 sel := convert(ind, base, 2);

 sseq := [];
 para flind a nops(sel) ¿
 si sel[flind] = 1 entonces
 sseq := [op(sseq), dlist[flind]];
fi;
od;

 val := añadir(sseq[k]*2^(k-1), k=1..nops(sseq));

 r := floor(sqrt(val));
 si val>0 y r*r = val, a continuación,
 res := res+1;
fi;
od;

res;
end;

avg := n -> add(g(k), k=1..n);

Answer 1

Esta es una respuesta a la (corregido) recompensa pregunta, pero todavía me gustaría saber si hay una fórmula asintótica para el valor promedio de $g(k)$ o si fluctúa entre los múltiplos de $n^b$.

Deje $n = 2^m$ ser una potencia de dos, y deje $F(n)$ el número de plazas se encuentra como subsecuencias de todas las cadenas binarias de longitud $m$, y deje $G(n)$ ser el valor exacto de $\sum_{k=0}^{n-1} g(k)$. (Es conveniente empezar a contar a $0$ en lugar de $1$ pero no afecta a la asymptotics.)

Ciertamente, no es cierto que $F(n) = G(n)$, pero es una útil aproximación de dos maneras. Por un lado, $F(n) \ge G(n)$, debido a que cada cadena binaria de longitud $m$ corresponde a un número entero en $[0,2^m-1]$ pero tiene terminantemente más subsecuencias porque de cero de relleno. Por otro lado, $F(n) \le \sum_{k=n}^{2n-1} g(k) = G(2n) - G(n)$, debido a la adición de un líder de $1$ a cada una cadena binaria de longitud $m$ rendimientos legítimo entero binario en $[2^m,2^{m+1}-1]$.

La ventaja de este modelo simplificado es que es muy fácil para estimar el $F(n)$. Para cada longitud de $1 \le \ell \le m$, $m\choose\ell$ subsecuencias de longitud $\ell$ dentro de cualquiera de las $m$-cadena de bits. Para cada elección habrá cerca de $\sqrt{2^\ell}$ (más precisamente, $\lfloor \sqrt{2^\ell-1}\rfloor+1$) de las formas para elegir un cuadrado perfecto que llene larga. Luego hay $2^{m-\ell}$ maneras de rellenar el resto de los bits. Por lo tanto

$$F(n) \approx \sum_{\ell=1}^m {m\choose\ell} (\sqrt{2})^{\ell} 2^{m-\ell} = (\sqrt{2}+2)^m - 2^m,$$ por la fórmula binominal. Por lo tanto $F(n) \sim n^c$ donde $c = \log_2(2+\sqrt{2})$, e $\tfrac1n F(n) \sim n^b$ donde $b = c-1 = 0.77155\ldots$.

Recordemos que $G(n) \le F(n) \le G(2n)-G(n)$. Desde $F(n) \sim n^c$, el de la izquierda de la desigualdad fácilmente da $G(n) = O(n^c)$, mientras que el derecho de la desigualdad de los rendimientos de $G(n) \ge G(n)-G(n/2) \ge F(n/2) = \Omega(n^c)$. Por lo tanto, $G(n) = \Theta(n^c)$ al $n$ es una potencia de $2$, y dado que es monótonamente creciente, esta tasa de crecimiento se puede ver que se extienden a todos los $n$. La función deseada $q(n)$ es lo $n^b$.