Número de keith

En matemáticas recreativas , un número de Keith o número repfigit (abreviatura de dígito repetitivo similar a Fibonacci ) es un número natural en una base numérica dada con dígitos tales que cuando se crea una secuencia de modo que los primeros términos sean los dígitos de y cada término posterior sea la suma de los términos anteriores, es parte de la secuencia. Los números de Keith fueron introducidos por Mike Keith en 1987. ^[1] Son computacionalmente muy difíciles de encontrar, y solo se conocen alrededor de 100. ${\estilo de visualización n}$ ${\estilo de visualización b}$${\estilo de visualización k}$${\estilo de visualización k}$${\estilo de visualización k}$${\estilo de visualización n}$${\estilo de visualización k}$${\estilo de visualización n}$

Sea un número natural, sea el número de dígitos de en base , y sea ${\estilo de visualización n}$${\displaystyle k=\lfloor \log _{b}{n}\rfloor +1}$${\displaystyle n}$${\displaystyle b}$

${\displaystyle d_{i}={\frac {n{\bmod {b}}^{i+1}-n{\bmod {b}}^{i}}{b^{i}}}}$

sea ​​el valor de cada dígito de . ${\displaystyle n}$

Definimos la secuencia mediante una relación de recurrencia lineal . Para , ${\displaystyle S(i)}$${\displaystyle 0\leq i<k}$

${\displaystyle S(i)=d_{k-i-1}}$

y para${\displaystyle i\geq k}$

${\displaystyle S(i)=\sum _{j=0}^{k}S(i-k+j)}$

Si existe un tal que , entonces se dice que es un número de Keith . ${\displaystyle i}$${\displaystyle S(i)=n}$${\displaystyle n}$

Por ejemplo, 88 es un número de Keith en base 6 , como

${\displaystyle S(0)=d_{3-0-1}=d_{2}={\frac {88{\bmod {6}}^{2+1}-88{\bmod {6}}^{2}}{6^{2}}}={\frac {88{\bmod {2}}16-88{\bmod {3}}6}{36}}={\frac {88-16}{36}}={\frac {72}{36}}=2}$

${\displaystyle S(1)=d_{3-1-1}=d_{1}={\frac {88{\bmod {6}}^{1+1}-88{\bmod {6}}^{1}}{6^{1}}}={\frac {88{\bmod {3}}6-88{\bmod {6}}}{6}}={\frac {16-4}{6}}={\frac {12}{6}}=2}$

${\displaystyle S(2)=d_{3-2-1}=d_{0}={\frac {88{\bmod {6}}^{0+1}-88{\bmod {6}}^{0}}{6^{0}}}={\frac {88{\bmod {6}}-88{\bmod {1}}}{1}}={\frac {4-0}{1}}={\frac {4}{1}}=4}$

y toda la secuencia

${\displaystyle S(i)=\{2,2,4,8,14,26,48,88,162,\ldots \}}$

y . ${\displaystyle S(7)=88}$

Actualmente, se especula sobre si existen o no infinitos números de Keith en una base determinada . Los números de Keith son raros y difíciles de encontrar. Se pueden encontrar mediante una búsqueda exhaustiva y no se conoce ningún algoritmo más eficiente. ^[2] Según Keith, en base 10 , en promedio se esperan números de Keith entre potencias sucesivas de 10. ^[3] Los resultados conocidos parecen respaldar esto .${\displaystyle b}$${\displaystyle \textstyle {\frac {9}{10}}\log _{2}{10}\approx 2.99}$

14 , 19 , 28 , 47 , 61 , 75 , 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909, 31331, 34285, 34348, 55604, 62662, 86935, 93993, 120284, 129106, 147640, 156146, 174680, 183186, 298320, 355419, 694280, 925993, 1084051, 7913837, 11436171, 33445755, 44121607, 129572008, 251133297, ... ^[4]

En base 2 , existe un método para construir todos los números de Keith. ^[3]

Los números de Keith en base 12 , escritos en base 12, son

11, 15, 1Ɛ, 22, 2ᘔ, 31, 33, 44, 49, 55, 62, 66, 77, 88, 93, 99, ᘔᘔ, ƐƐ, 125, 215, 24ᘔ, 405, 42ᘔ, 654, 80ᘔ, 8ᘔ3, ᘔ59, 1022, 1662, 2044, 3066, 4088, 4ᘔ1ᘔ, 4ᘔƐ1, 50ᘔᘔ, 8538, Ɛ18Ɛ, 17256, 18671, 24ᘔ78, 4718Ɛ, 517Ɛᘔ, 157617, 1ᘔ265ᘔ, 5ᘔ4074, 5ᘔƐ140, 6Ɛ1449, 6Ɛ8515, ...

donde ᘔ representa 10 y Ɛ representa 11.

Un grupo de Keith es un conjunto relacionado de números de Keith de modo que uno es múltiplo de otro. Por ejemplo, en base 10 , , y son todos grupos de Keith. Estos son posiblemente los únicos tres ejemplos de un grupo de Keith en base 10. [ ^5]${\displaystyle \{14,28\}}$${\displaystyle \{1104,2208\}}$${\displaystyle \{31331,62662,93993\}}$

El siguiente ejemplo implementa la secuencia definida anteriormente en Python para determinar si un número en una base particular es un número de Keith:

def  is_repfigit ( x :  int ,  b :  int )  ->  bool : 
"""Determinar si un número en una base particular es un número de Keith.""" si x == 0 : devuelve Verdadero    
       
         

    secuencia  =  [] 
    y  =  x

    mientras  y  >  0 : 
        secuencia . append ( y  %  b ) 
        y  =  y  //  b

    digit_count  =  len ( secuencia ) 
    secuencia . reverse ()

    mientras  secuencia [ len ( secuencia )  -  1 ]  <  x : 
        n  =  0 
        para  i  en  rango ( 0 ,  número_de_dígitos ) : 
            n  =  n  +  secuencia [ len ( secuencia )  -  número_de_dígitos  +  i ] 
        secuencia .append ( n )

     secuencia de retorno [ len ( secuencia )  -  1 ]  ==  x

• Dinámica aritmética
• Número de Fibonacci
• Relación de recurrencia lineal