7 votos

Teoría de números y los números d-autónomo

Dado cualquier número natural $N = a_{n}a_{n-1}\ldots a_{1}$, nos vamos a asociar a es el conjunto de $S_{N} = \bigcup_{j=1}^{n}\{(a_{j},j)\}$. Vamos a definir un d-auto-contenida número como cualquier número natural que cumple la regla: \begin{align*} &\forall k\leq n,\exists\sigma\subset S_{N}\setminus\{(a_{k},k)\}; a_{k} = \sum_{s\in\sigma}(-1)^{e_{s}}\|p_{1}(s)\|^{d},\\ &\text{where}\,\,n\geq 3,\,\,e_{s}\in\{0,1\}\,\,\text{and}\,\,\#\sigma\geq 2 \end{align*} En otras palabras, un número d-auto-contenida , si cada uno de sus dígitos pueden ser obtenidos a partir de los otros como una combinación lineal de sus d-ésima potencia (donde d es natural y fija) cuyos coeficientes pertenecen al conjunto {-1,0,1}, donde al menos dos de estos coeficientes son cero términos. Vale la pena decir que $p_{1}$ es la proyección de mapeo en la primera coordenada. Vamos a trabajar a través de ejemplos. El número 101 es de 2-auto-contenida, ya podemos reescribir sus dígitos como: $1 = 0^{2} + 1^{2}$$0 = 1^{2} - 1^{2}$. Además, el número 101 es d-auto-contenida para cada d. En efecto, tenemos: $$1 = 0 + 1 = 0^{d} + 1^{d}\,\,\text{and}\,\,0 = 1 - 1 = 1^{d} - 1^{d}$$ Por otro lado, el número 121 no es 2-auto-contenido, dado que: $$1 \neq 2^{2} - 1^{2}\,\,\text{and}\,\,1\neq 2^{2} + 1^{2}$$ Aunque está a 1-auto-contenida. ¿Qué acerca de la 3-auto-contenida números? Aquí se trata de un ejemplo que demuestra que existen: 111111112. Sin duda, su dígitos satisfacen las siguientes relaciones: $$1 = 2^{3} - 1^{3} - 1^{3} - 1^{3} - 1^{3} - 1^{3} - 1^{3} - 1^{3}\,\,\text{and}\,\,2 = 1^{3} + 1^{3}$$ Aún más, este número también es 1,2-auto-contenida. Realmente, tenemos: $$1 = 2 - 1\,\,\texto{y}\,\,2 = 1 + 1;\quad 1 = 2^{2} - 1^{2} - 1^{2} - 1^{2}\,\,\texto{y}\,\,2 = 1^{2} + 1^{2}$$ Además de eso, este ejemplo nos da una manera de construir cualquier d-auto-contenida número: $$N = \overbrace{11\ldots 1}^{2^{d}}2\Rightarrow 2^{d} = \overbrace{1^{d} + 1^{d} + \ldots + 1^{d}}^{2^{d}}\,\,\text{and}\,\,1 = 2^{d} - \overbrace{1^{d} - 1^{d} - \ldots - 1^{d}}^{2^{d} - 1}$$ Puesto que la definición que ha quedado claro, me gustaría hacer algunas preguntas. Primero de todo, no cualquiera puede proponer cualquier criterio para identificar rápidamente? En segundo lugar, ¿hay alguna fórmula que genera todos ellos? Y, por último, si se denota el conjunto de d-auto-contenida números por $A_{d}$, hace la siguiente proposición: se $A_{1}\supset A_{2}\supset\ldots\supset A_{k}\supset\ldots$? De antemano muchas gracias por cualquier aporte.

4voto

John Coleman Puntos 121

No sé de ninguna comprobación fácil, pero aquí es un programa en Python que se puede encontrar todo autónomo de los números en un rango determinado:

mem = dict() #global dictionary for memoization

def expressible(m,digits,k):
    if (m,digits,k) in mem:
        return mem[(m,digits,k)]
    elif m == 0 and k == 0:
        mem[(m,digits,k)] = True
        return True
    elif len(digits) == 0 or k > len(digits):
        mem[(m,digits,k)] = False
        return False
    else:
        for d in set(digits):
            i = int(d)
            remaining = digits.replace(d,'',1)
            if expressible(m + i,remaining, k-1) or expressible(m - i,remaining, k-1):
                mem[(m,digits,k)] = True
                return True
        #if we reach here:
        mem[(m,digits,k)] = False
        return False

def selfContained(a,b):
    nums = []
    for n in range(a,b+1):
        digits = ''.join(sorted(str(n)))
        contained = True #until a counter-example found
        for d in set(digits):
            i = int(d)
            remaining = digits.replace(d,'',1)
            if not expressible(i,remaining,2):
                contained = False
                break
            if not contained: break
        #if we reach here and contained is still true, no counterxamples, so:
        if contained: nums.append(n)
    mem.clear()
    return nums

Por ejemplo,

>>> selfContained(1,360)
[101, 110, 112, 121, 123, 132, 134, 143, 145, 154, 156, 165, 167, 176, 178, 187, 189, 198, 202, 211, 213, 220, 224, 231, 235, 242, 246, 253, 257, 264, 268, 275, 279, 286, 297, 303, 312, 314, 321, 325, 330, 336, 341, 347, 352, 358]

esta lista está de acuerdo con los números de 3 dígitos en el OEIS secuencia vinculada por @RobertSoupe .

La evaluación

nums = selfContained(0,1000000)

tarda unos 3 segundos y devuelve una lista de 322378 números, el último de los cuales 10 son

999909, 999918, 999927, 999936, 999945, 999954, 999963, 999972, 999981, 999990

En Edit: he ajustado el código un poco, para hacer que se ejecute más rápido. Ahora puede ejecutar a 10,000,000 en menos de un minuto. Al hacerlo se convierte 4,768,482 autónomo de los números en ese rango. El porcentaje va en aumento. Es fácil ver que la densidad asintótica de auto-contenida de los números es 1. De hecho, la prueba parece casi trivial: cualquier número en el que cada dígito se produce al menos 2 veces es auto-contenida, y el asintótica de la densidad de dichos números es 1. Algo curiosamente, esta prueba se cumple para cualquier base (y no sólo en base 10). Sin duda, la tasa a la cual la densidad de los enfoques de 1 depende de la base.

En Más de Edición: a 100,000,000 (alrededor de 9 minutos para que mi programa) hay 63,750,290 autónomo de los números. No estoy seguro de si es factible ir a 1 mil millones de dólares con el programa en mi máquina. Sería interesante escribir un optimizado C versión y ver lo lejos que se puede tomar.

2voto

Erick Wong Puntos 12209

Aquí es fácil la respuesta a la última pregunta: $10127$ $3$- autónomo ($7 = 2^3 - 1^3$, $2^3 = 1^3+1^3$, $1^3 = 1^3+0^3$, $0=1^3-1^3$), pero no $2$-auto-contenida debido a que $7 > 1^2+0^2+1^2+2^2$. Del mismo modo creo $10129$$111129$$A_3 \setminus A_2$. Por lo tanto $A_2 \not\supset A_3$, por lo que el infinito descendente de la cadena de la proposición es falsa.

Sospecho que, al igual que la OEIS la secuencia en la que Robert Sopa puntos a, la estructura de $A_d$ fijos $d$ es bastante simple y puede descrita por un autómata finito. Pero no me atrevo a hacer ninguna hipótesis en cuanto a cómo la complejidad crece con $d$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by: