Sistema factorádico de numeración

José A. Alonso

19-02-2024

El sistema factorádico es un sistema numérico basado en factoriales en el que el n-ésimo dígito, empezando desde la derecha, debe ser multiplicado por n! Por ejemplo, el número "341010" en el sistema factorádico es 463 en el sistema decimal ya que

   3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0! = 463

En este sistema numérico, el dígito de más a la derecha es siempre 0, el segundo 0 o 1, el tercero 0,1 o 2 y así sucesivamente.

Con los dígitos del 0 al 9 el mayor número que podemos codificar es el 10!-1 = 3628799. En cambio, si lo ampliamos con las letras A a Z podemos codificar hasta 36!-1 = 37199332678990121746799944815083519999999910.

Definir las funciones

   factoradicoAdecimal :: String -> Integer
   decimalAfactoradico :: Integer -> String

tales que

(factoradicoAdecimal cs) es el número decimal correspondiente al número factorádico cs. Por ejemplo,

     λ> factoradicoAdecimal "341010"
     463
     λ> factoradicoAdecimal "2441000"
     2022
     λ> factoradicoAdecimal "A0000000000"
     36288000
     λ> map factoradicoAdecimal ["10","100","110","200","210","1000","1010","1100","1110","1200"]
     [1,2,3,4,5,6,7,8,9,10]
     λ> factoradicoAdecimal "3KXWVUTSRQPONMLKJIHGFEDCBA9876543210"
     37199332678990121746799944815083519999999

(decimalAfactoradico n) es el número factorádico correpondiente al número decimal n. Por ejemplo,

     λ> decimalAfactoradico 463
     "341010"
     λ> decimalAfactoradico 2022
     "2441000"
     λ> decimalAfactoradico 36288000
     "A0000000000"
     λ> map decimalAfactoradico [1..10]
     ["10","100","110","200","210","1000","1010","1100","1110","1200"]
     λ> decimalAfactoradico 37199332678990121746799944815083519999999
     "3KXWVUTSRQPONMLKJIHGFEDCBA9876543210"

Comprobar con QuickCheck que, para cualquier entero positivo n,

   factoradicoAdecimal (decimalAfactoradico n) == n

1. Soluciones en Haskell

module Sistema_factoradico_de_numeracion where

import Data.List (genericIndex, genericLength)
import qualified Data.Map as M ((!), Map, fromList)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

-- 1ª definición de factoradicoAdecimal
-- ====================================

factoradicoAdecimal1 :: String -> Integer
factoradicoAdecimal1 cs = sum (zipWith (*) xs ys)
  where xs = map caracterAentero cs
        n  = length cs
        ys = reverse (take n facts)

-- (caracterAentero c) es la posición del carácter c en la lista de
-- caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo,
--    caracterAentero '0'  ==  0
--    caracterAentero '1'  ==  1
--    caracterAentero '9'  ==  9
--    caracterAentero 'A'  ==  10
--    caracterAentero 'B'  ==  11
--    caracterAentero 'Z'  ==  35
caracterAentero :: Char -> Integer
caracterAentero c =
  head [n | (n,x) <- zip [0..] caracteres, x == c]

-- caracteres es la lista de caracteres
-- ['0', '1',..., '9', 'A', 'B',..., 'Z']
caracteres :: String
caracteres = ['0'..'9'] ++ ['A'..'Z']

-- facts es la lista de los factoriales. Por ejemplo,
--    λ> take 12 facts
--    [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800]
facts :: [Integer]
facts = scanl (*) 1 [1..]

-- 2ª definición de factoradicoAdecimal
-- ====================================

factoradicoAdecimal2 :: String -> Integer
factoradicoAdecimal2 cs = sum (zipWith (*) xs ys)
    where xs = map caracterAentero2 cs
          n  = length cs
          ys = reverse (take n facts)

-- (caracterAentero2 c) es la posición del carácter c en la lista de
-- caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo,
--    caracterAentero2 '0'  ==  0
--    caracterAentero2 '1'  ==  1
--    caracterAentero2 '9'  ==  9
--    caracterAentero2 'A'  ==  10
--    caracterAentero2 'B'  ==  11
--    caracterAentero2 'Z'  ==  35
caracterAentero2 :: Char -> Integer
caracterAentero2 c = caracteresEnteros M.! c

-- caracteresEnteros es el diccionario cuyas claves son los caracteres y
-- las claves son los números de 0 a 35.
caracteresEnteros :: M.Map Char Integer
caracteresEnteros = M.fromList (zip (['0'..'9'] ++ ['A'..'Z']) [0..])

-- 3ª definición de factoradicoAdecimal
-- ====================================

factoradicoAdecimal3 :: String -> Integer
factoradicoAdecimal3 cs =
  sum (zipWith (*) facts (reverse (map caracterAentero3 cs)))

-- (caracterAentero3 c) es la posición del carácter c en la lista de
-- caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo,
--    caracterAentero3 '0'  ==  0
--    caracterAentero3 '1'  ==  1
--    caracterAentero3 '9'  ==  9
--    caracterAentero3 'A'  ==  10
--    caracterAentero3 'B'  ==  11
--    caracterAentero3 'Z'  ==  35
caracterAentero3 :: Char -> Integer
caracterAentero3 c =
  genericLength (takeWhile (/= c) caracteres)

-- 4ª definición de factoradicoAdecimal
-- ====================================

factoradicoAdecimal4 :: String -> Integer
factoradicoAdecimal4 =
  sum . zipWith (*) facts . reverse . map caracterAentero4

-- (caracterAentero4 c) es la posición del carácter c en la lista de
-- caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo,
--    caracterAentero4 '0'  ==  0
--    caracterAentero4 '1'  ==  1
--    caracterAentero4 '9'  ==  9
--    caracterAentero4 'A'  ==  10
--    caracterAentero4 'B'  ==  11
--    caracterAentero4 'Z'  ==  35
caracterAentero4 :: Char -> Integer
caracterAentero4 =
  genericLength . flip takeWhile caracteres . (/=)

-- 1ª definición de decimalAfactoradico
-- ====================================

decimalAfactoradico1 :: Integer -> String
decimalAfactoradico1 n = aux n (reverse (takeWhile (<=n) facts))
  where aux 0 xs     = ['0' | _ <- xs]
        aux m (x:xs) = enteroAcaracter (m `div` x) : aux (m `mod` x) xs

-- (enteroAcaracter k) es el k-ésimo elemento de la lista
-- ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo,
--    enteroAcaracter 0   ==  '0'
--    enteroAcaracter 1   ==  '1'
--    enteroAcaracter 9   ==  '9'
--    enteroAcaracter 10  ==  'A'
--    enteroAcaracter 11  ==  'B'
--    enteroAcaracter 35  ==  'Z'
enteroAcaracter :: Integer -> Char
enteroAcaracter k = caracteres `genericIndex` k

-- 2ª definición de decimalAfactoradico
-- ====================================

decimalAfactoradico2 :: Integer -> String
decimalAfactoradico2 n = aux n (reverse (takeWhile (<=n) facts))
  where aux 0 xs     = ['0' | _ <- xs]
        aux m (x:xs) = enteroAcaracter2 (m `div` x) : aux (m `mod` x) xs

-- (enteroAcaracter2 k) es el k-ésimo elemento de la lista
-- ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo,
--    enteroAcaracter2 0   ==  '0'
--    enteroAcaracter2 1   ==  '1'
--    enteroAcaracter2 9   ==  '9'
--    enteroAcaracter2 10  ==  'A'
--    enteroAcaracter2 11  ==  'B'
--    enteroAcaracter2 35  ==  'Z'
enteroAcaracter2 :: Integer -> Char
enteroAcaracter2 k = enterosCaracteres M.! k

-- enterosCaracteres es el diccionario cuyas claves son los número de 0
-- a 35 y las claves son los caracteres.
enterosCaracteres :: M.Map Integer Char
enterosCaracteres = M.fromList (zip [0..] caracteres)

-- 3ª definición de decimalAfactoradico
-- ====================================

decimalAfactoradico3 :: Integer -> String
decimalAfactoradico3 n = aux "" 2 (n, 0)
  where aux s _ (0, 0) = s
        aux s m (d, r) = aux (enteroAcaracter3 r: s) (m + 1) (d `divMod` m)

-- (enteroAcaracter3 k) es el k-ésimo elemento de la lista
-- ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo,
--    enteroAcaracter3 0   ==  '0'
--    enteroAcaracter3 1   ==  '1'
--    enteroAcaracter3 9   ==  '9'
--    enteroAcaracter3 10  ==  'A'
--    enteroAcaracter3 11  ==  'B'
--    enteroAcaracter3 35  ==  'Z'
enteroAcaracter3 :: Integer -> Char
enteroAcaracter3 n =
  caracteres !! fromInteger n

-- 4ª definición de decimalAfactoradico
-- ====================================

decimalAfactoradico4 :: Integer -> String
decimalAfactoradico4 = f "" 2 . (, 0)
  where f s _ (0, 0) = s
        f s n (d, r) = f (enteroAcaracter4 r: s) (n + 1) (d `divMod` n)

-- (enteroAcaracter4 k) es el k-ésimo elemento de la lista
-- ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo,
--    enteroAcaracter4 0   ==  '0'
--    enteroAcaracter4 1   ==  '1'
--    enteroAcaracter4 9   ==  '9'
--    enteroAcaracter4 10  ==  'A'
--    enteroAcaracter4 11  ==  'B'
--    enteroAcaracter4 35  ==  'Z'
enteroAcaracter4 :: Integer -> Char
enteroAcaracter4 = (caracteres `genericIndex`)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG1 :: (String -> Integer) -> Spec
specG1 factoradicoAdecimal = do
  it "e1" $
    factoradicoAdecimal "341010" `shouldBe` 463
  it "e2" $
    factoradicoAdecimal "2441000" `shouldBe` 2022
  it "e3" $
    factoradicoAdecimal "A0000000000" `shouldBe` 36288000

specG2 :: (Integer -> String) -> Spec
specG2 decimalAfactoradico = do
  it "e1" $
    decimalAfactoradico 463 `shouldBe` "341010"
  it "e2" $
    decimalAfactoradico 2022 `shouldBe` "2441000"
  it "e3" $
    decimalAfactoradico 36288000 `shouldBe` "A0000000000"

spec :: Spec
spec = do
  describe "def. 1" $ specG1 factoradicoAdecimal1
  describe "def. 2" $ specG1 factoradicoAdecimal2
  describe "def. 3" $ specG1 factoradicoAdecimal3
  describe "def. 4" $ specG1 factoradicoAdecimal4
  describe "def. 1" $ specG2 decimalAfactoradico1
  describe "def. 2" $ specG2 decimalAfactoradico2
  describe "def. 3" $ specG2 decimalAfactoradico3
  describe "def. 4" $ specG2 decimalAfactoradico4

-- La verificación es
--    λ> verifica
--
--    24 examples, 0 failures

-- Propiedad de inverso
-- ====================

prop_factoradico :: Integer -> Property
prop_factoradico n =
  n >= 0 ==>
  factoradicoAdecimal1 (decimalAfactoradico1 n) == n &&
  factoradicoAdecimal2 (decimalAfactoradico2 n) == n &&
  factoradicoAdecimal3 (decimalAfactoradico3 n) == n &&
  factoradicoAdecimal4 (decimalAfactoradico4 n) == n

-- La comprobación es
--    λ> quickCheck prop_factoradico
--    +++ OK, passed 100 tests; 101 discarded.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (decimalAfactoradico1 (10^300000))
--    68191
--    (2.46 secs, 9,088,634,744 bytes)
--    λ> length (decimalAfactoradico2 (10^300000))
--    68191
--    (2.36 secs, 9,088,634,800 bytes)
--    λ> length (decimalAfactoradico3 (10^300000))
--    68191
--    (2.18 secs, 4,490,856,416 bytes)
--    λ> length (decimalAfactoradico4 (10^300000))
--    68191
--    (1.98 secs, 4,490,311,536 bytes)
--
--    λ> length (show (factoradicoAdecimal1 (show (10^50000))))
--    213237
--    (0.93 secs, 2,654,156,680 bytes)
--    λ> length (show (factoradicoAdecimal2 (show (10^50000))))
--    213237
--    (0.51 secs, 2,633,367,168 bytes)
--    λ> length (show (factoradicoAdecimal3 (show (10^50000))))
--    213237
--    (0.93 secs, 2,635,792,192 bytes)
--    λ> length (show (factoradicoAdecimal4 (show (10^50000))))
--    213237
--    (0.43 secs, 2,636,996,848 bytes)

2. Soluciones en Python

from itertools import count, takewhile
from math import factorial
from typing import Iterator

from hypothesis import given
from hypothesis import strategies as st

# 1ª definición de factoradicoAdecimal
# ====================================

# caracterAentero(c) es la posición del carácter c en la lista de
# caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo,
#    caracterAentero('0')  ==  0
#    caracterAentero('1')  ==  1
#    caracterAentero('9')  ==  9
#    caracterAentero('A')  ==  10
#    caracterAentero('B')  ==  11
#    caracterAentero('Z')  ==  35
def caracterAentero(c: str) -> int:
    if c.isdigit():
        return int(c)
    return ord(c) - ord('A') +  10

def factoradicoAdecimal1(cs: str) -> int:
    xs = map(caracterAentero, cs)
    n  = len(cs)
    ys = reversed([factorial(k) for k in range(n)])
    return sum((x * y for (x, y) in zip(xs, ys)))

# 2ª definición de factoradicoAdecimal
# ====================================

# caracteres es la cadena de los caracteres.
caracteres: str = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'

# caracteresEnteros es el diccionario cuyas claves son los caracteres y
# los valores son los números de 0 a 35.
caracteresEnteros: dict[str, int] = {c: i for i, c in enumerate(caracteres)}

# caracterAentero2(c) es la posición del carácter c en la lista de
# caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo,
#    caracterAentero2('0')  ==  0
#    caracterAentero2('1')  ==  1
#    caracterAentero2('9')  ==  9
#    caracterAentero2('A')  ==  10
#    caracterAentero2('B')  ==  11
#    caracterAentero2('Z')  ==  35
def caracterAentero2(c: str) -> int:
    return caracteresEnteros[c]

def factoradicoAdecimal2(cs: str) -> int:
    xs = map(caracterAentero2, cs)
    n  = len(cs)
    ys = reversed([factorial(k) for k in range(n)])
    return sum((x * y for (x, y) in zip(xs, ys)))

# 3ª definición de factoradicoAdecimal
# ====================================

# caracterAentero3(c) es la posición del carácter c en la lista de
# caracteres ['0', '1',..., '9', 'A', 'B',..., 'Z']. Por ejemplo,
#    caracterAentero3('0')  ==  0
#    caracterAentero3('1')  ==  1
#    caracterAentero3('9')  ==  9
#    caracterAentero3('A')  ==  10
#    caracterAentero3('B')  ==  11
#    caracterAentero3('Z')  ==  35
def caracterAentero3(c: str) -> int:
    return len(list(takewhile(lambda x: x != c, caracteres)))

def factoradicoAdecimal3(cs: str) -> int:
    return sum(x * y for x, y in zip([factorial(k) for k in range(len(cs))],
                                     reversed(list(map(caracterAentero3, cs)))))

# 1ª definición de decimalAfactoradico
# ====================================

# enteroAcaracter(k) es el k-ésimo elemento de la lista
# ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo,
#    enteroAcaracter(0)   ==  '0'
#    enteroAcaracter(1)   ==  '1'
#    enteroAcaracter(9)   ==  '9'
#    enteroAcaracter(10)  ==  'A'
#    enteroAcaracter(11)  ==  'B'
#    enteroAcaracter(35)  ==  'Z'
def enteroAcaracter(k: int) -> str:
    return caracteres[k]

# facts() es la lista de los factoriales. Por ejemplo,
#    >>> list(takewhile(lambda x : x < 900, facts()))
#    [1, 1, 2, 6, 24, 120, 720]
def facts() -> Iterator[int]:
    return (factorial(n) for n in count())

def decimalAfactoradico1(n: int) -> str:
    def aux(m: int, xs: list[int]) -> str:
        if m == 0:
            return "0" * len(xs)
        y, *ys = xs
        print(m, y, m // y)
        return enteroAcaracter(m // y) + aux(m % y, ys)
    return aux(n, list(reversed(list(takewhile(lambda x : x <= n, facts())))))

# 2ª definición de decimalAfactoradico
# ====================================

# enterosCaracteres es el diccionario cuyas claves son los número de 0
# a 35 y las claves son los caracteres.
enterosCaracteres: dict[int, str] = dict(enumerate(caracteres))

# enteroAcaracter2(k) es el k-ésimo elemento de la lista
# ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo,
#    enteroAcaracter2(0)   ==  '0'
#    enteroAcaracter2(1)   ==  '1'
#    enteroAcaracter2(9)   ==  '9'
#    enteroAcaracter2(10)  ==  'A'
#    enteroAcaracter2(11)  ==  'B'
#    enteroAcaracter2(35)  ==  'Z'
def enteroAcaracter2(k: int) -> str:
    return enterosCaracteres[k]

def decimalAfactoradico2(n: int) -> str:
    def aux(m: int, xs: list[int]) -> str:
        if m == 0:
            return "0" * len(xs)
        y, *ys = xs
        return enteroAcaracter2(m // y) + aux(m % y, ys)
    return aux(n, list(reversed(list(takewhile(lambda x : x <= n, facts())))))

# 3ª definición de decimalAfactoradico
# ====================================

# enteroAcaracter3(k) es el k-ésimo elemento de la lista
# ['0', '1',..., '9', 'A', 'B',..., 'Z']. . Por ejemplo,
#    enteroAcaracter3(0)   ==  '0'
#    enteroAcaracter3(1)   ==  '1'
#    enteroAcaracter3(9)   ==  '9'
#    enteroAcaracter3(10)  ==  'A'
#    enteroAcaracter3(11)  ==  'B'
#    enteroAcaracter3(35)  ==  'Z'
def enteroAcaracter3(n: int) -> str:
    return caracteres[n]

def decimalAfactoradico3(n: int) -> str:
    def aux(m: int, xs: list[int]) -> str:
        if m == 0:
            return "0" * len(xs)
        y, *ys = xs
        return enteroAcaracter3(m // y) + aux(m % y, ys)
    return aux(n, list(reversed(list(takewhile(lambda x : x <= n, facts())))))

# Verificación
# ============

def test_factoradico() -> None:
    for factoradicoAdecimal in [factoradicoAdecimal1,
                                factoradicoAdecimal2,
                                factoradicoAdecimal3]:
        assert factoradicoAdecimal("341010") == 463
        assert factoradicoAdecimal("2441000") == 2022
        assert factoradicoAdecimal("A0000000000") == 36288000
    for decimalAfactoradico in [decimalAfactoradico1,
                                decimalAfactoradico2,
                                decimalAfactoradico3]:
        assert decimalAfactoradico(463) == "341010"
        assert decimalAfactoradico(2022) == "2441000"
        assert decimalAfactoradico(36288000) == "A0000000000"
    print("Verificado")

# La verificación es
#    >>> test_factoradico()
#    Verificado

# Propiedad de inverso
# ====================

@given(st.integers(min_value=0, max_value=1000))
def test_factoradico_equiv(n: int) -> None:
    assert factoradicoAdecimal1(decimalAfactoradico1(n)) == n
    assert factoradicoAdecimal2(decimalAfactoradico3(n)) == n
    assert factoradicoAdecimal3(decimalAfactoradico3(n)) == n

# La comprobación es
#    >>> test_factoradico_equiv()
#    >>>