martes, 13 de febrero de 2018

1515. Exótica numeración. RESOLUCIÓN

     El teorema fundamental de la Aritmética no surte el efecto esperado en el alumnado... No alcanzan a ver su importancia... ¿Qué más da que los naturales se puedan descomponer de forma única como producto de primos (ordenados de menor a mayor por eso de la conmutatividad)?
    También son importantes las descomposiciones únicas de los naturales como sumas. Es la base de los sistemas de numeración... Pero este tema llama aún menos la atención...
    Pepe Chapuzas es una excepción que confirma la regla...

    Mire, profe. Cuando escribimos un número natural en un sistema de numeración posicional, lo estamos descomponiendo de forma única como combinación lineal de potencias de la base del sistema, siempre que los coeficientes sean naturales menores que la base y los exponentes sean enteros no negativos. Así, con potencias de 3,


1·35 + 2·34 + 2·32 + 1·31 2·30 =  428

lo que nos permite escribir 428 en base 3, con trits o dígitos ternarios (0,1 y 2). Es como un polinomio...
428 = 1202123

 donde el 0 indica la ausencia de una potencia como en la regla de Ruffini...

    Comenté que el propio número 428 escrito así estaba en base 10 evidentemente:

428 = 42810 = 4·100 + 2·10 + 8

    Pepe nos intrigó con la siguiente pregunta...

    ¿Se puede utilizar la descomposición de Zeckendorf para establecer un sistema de numeración?

SOLUCIÓN

    Nunca se había mencionado antes en clase la descomposición de Zeckendorf... Al día siguiente Nina Guindilla tenía algo que contar...

    Mire, profe. A partir del segundo término de la sucesión de Leonardo Pisano (Fibonacci)...


F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, F8 = 21, ...

podemos descomponer de forma única un número natural como suma finita de estos términos, siempre que no aparezca en la suma ni dos términos iguales ni dos términos consecutivos. Dicho de otro modo, como combinación lineal de términos,


B1·F2 + B2·F3 + B3·F4 +B4·F5 + B5·F6 + ...

donde los coeficientes Bk son 0 o 1 (bits) y los productos Bk·Bk+1 son siempre nulos, esto es, uno de los dos factores ha de ser 0...
    Esto es una codificación de los naturales en bits, inyectiva porque es exclusiva para cada natural pero no suprayectiva porque no puede haber dos unos seguidos en la codificación... Un exótico sistema de numeración donde... ¡está prohibido el ...11...!


428  =  377 + 34  + 13 + 3 + 1  =  F14 + F9 + F7 + F4 + F2   1000010100101Z

    (El subíndice Z de Zeckendorf.)
    He aquí los 20 primeros naturales escritos en sistema binario y en código Zeckendorf

1 = 12 = 1Z
2 = 102 = 10Z
3 = 112 = 100Z
4 = 1002 = 101Z
5 = 1012 1000Z
1102 = 1001Z
7 = 1112 = 1010Z
8 = 10002 = 10000Z
10012 = 10001Z
10 10102 = 10010Z
11 = 10112 = 10100Z
12 = 11002 = 10101Z
13 = 11012 = 100000Z
14 = 11102 = 100001Z
15 = 11112 = 100010Z
16 = 100002 = 100100Z
17 = 100012 = 100101Z
18 = 100102 = 101000Z
19 = 100112 = 101001Z
20 = 101002 = 101010Z
...


    Solo añadí que la descomposición de Zeckendorf tiene muchas propiedades... exóticas.
    Hay un sistema de numeración más exótico todavía: la numeración factorial,,, ¿Quién quiere hablarnos de ella?

RESOLUCIÓN

    No podía ser otro que Yoyó Peluso...

    Profe, mire. Todo número se puede descomponer de forma única como combinación lineal de los números factoriales...

A1·1! + A2·2! + A3·3! + A4·4! + A5·5! + A6·6! + ...

siempre que los coeficientes sean enteros que cumplan  –1 < A< k+1 , o sea, Aes un dígito binario (un bit), Aes un dígito ternario (un trit), Aes un dígito cuaternario...
    Por ejemplo,
3·4! + 1·3! + 2·2! + 1·1!  =  3·24+ 1·6 + 2·2 + 1·1  =  83
83 = 3121F
    (El subíndice F de factorial.)
    Los veinte primeros naturales:
1 = 1F
2 = 10F
3 = 11F
4= 20F
5 = 21F
6 = 100F
7 = 101F
8 = 110F
9 = 111F
10 = 120F
11 = 121F
12 = 200F
13 = 201F
14 = 210F
15 = 211F
16 = 220F
17 = 221F
18 = 300F
19 = 301F
20 = 310F
...

    El lector puede entretenerse demostrando la unicidad de las descomposiciones...

1 comentario: