Phinary System. Numeric system based in Phi number

00 PhinarySystem.md

Sistema phinario (base $\phi$), un fascinante sistema de numeración con base irracional concebido originalmente por el matemático George Bergman en 1957. ¹² En este sistema, la base es el número áureo ($\phi \approx 1.61803...$), y sorprendentemente, cualquier número natural se puede escribir de forma exacta utilizando únicamente los dígitos 0 y 1. ²³

---

La propiedad fundamental de la Base $\phi$

Este sistema se basa en la propiedad algebraica de la proporción divina: $$\phi^2 = \phi + 1$$ Si trasladamos esto a un sistema de valor posicional (como el binario o decimal), significa que tener las potencias $\phi^1$ y $\phi^0$ consecutivas es exactamente lo mismo que tener una potencia $\phi^2$.

En código phinario: 11 equivale a 100. ²⁴

La forma estándar (Evitar el 11)

Para que la representación de cada número natural sea única, se aplica una regla idéntica a la del Teorema de Zeckendorf: no pueden existir dos unos (1) seguidos. Siempre que aparece un 11, se "simplifica" moviendo el valor hacia la izquierda como un 100. [2] Al ser la base un número irracional ($1.618...$), para representar números enteros exactos necesitamos usar potencias negativas (es decir, posiciones a la derecha del punto o coma decimal). ²³⁵

---

Ejemplos de números naturales en base $\phi$

Aquí puedes ver cómo se construyen los primeros números enteros según el Phi Numeral System en Wolfram MathWorld: ⁵

• 1 = $\phi^0$ $\rightarrow$ 1
• 2 = $\phi^1 + \phi^{-2}$ $\rightarrow$ 10.01 (ya que $1.618 + 0.382 = 2$)
• 3 = $\phi^2 + \phi^{-2}$ $\rightarrow$ 100.01
• 4 = $\phi^2 + \phi^0 + \phi^{-2}$ $\rightarrow$ 101.01
• 5 = $\phi^3 + \phi^{-1} + \phi^{-4}$ $\rightarrow$ 1000.1001 ⁴⁵⁶

A la izquierda del punto están las potencias positivas ($..., \phi^3, \phi^2, \phi^1, \phi^0$) y a la derecha las negativas ($\phi^{-1}, \phi^{-2}, \phi^{-3}, ...$). ⁵

---

¿Por qué es tan especial?

1. Suma sin acarreos complejos: las operaciones aritméticas se resuelven de forma puramente geométrica mediante sustituciones de patrones (11 $\rightarrow$ 100).
2. Conexión con los enteros: es el único sistema de base irracional que permite expresar todos los números enteros de forma finita y limpia sin infinitos decimales periódicos. ⁵⁷

Footnotes

1. https://francis.naukas.com ↩

2. https://en.wikipedia.org ↩ ↩² ↩³ ↩⁴

3. https://www.facebook.com ↩ ↩²

4. https://www.johndcook.com ↩ ↩²

5. https://mathworld.wolfram.com ↩ ↩² ↩³ ↩⁴ ↩⁵

6. https://www.reddit.com ↩

7. https://oeis.org ↩

How.md

Propuesta de una solución completa en Scala 3 para convertir un número entero positivo a su representación estándar en sistema phinario (base φ). Para lograrlo de forma exacta y sin perder precisión con números decimales flotantes, el algoritmo utiliza la representación aritmética exacta basada en la propiedad $\phi^n = F_{n-1} + F_n\phi$ (donde $F_n$ son los números de Fibonacci), o bien el algoritmo de "codificación codiciosa" (greedy) operando de manera simbólica, o mediante el método de sumas repetidas de 1 aplicando las reglas de reescritura. El enfoque más limpio y elegante en Scala es empezar desde el número 1 (1.0) e ir sumando de uno en uno mediante manipulación de cadenas de bits o listas, aplicando dos reglas de reescritura hasta que el código sea estable:

1. Arrastrar (Carry): 011 → 100 (ya que $\phi^{n+1} + \phi^n = \phi^{n+2}$)
2. Empujar (Glitch/Borrow): 100 → 011 (se usa al sumar para abrir espacios si es necesario, o en su defecto la inversa de la regla anterior).

---

Explicación del funcionamiento

1. Estructura Phinario: Almacena los dígitos separados en dos colecciones (parteEntera y parteFraccionaria) para evitar lidiar con la imprecisión del tipo Double de la computadora.
2. Método normalizar: Es el motor del programa. Utiliza un mapa dinámico donde las claves son las potencias (por ejemplo, 0 es φ⁰=1, -2 es φ⁻²). Ejecuta un bucle iterativo buscando el patrón prohibido de dos unos seguidos (mapa(i) y mapa(i-1)) y lo sustituye por un uno en la posición superior (mapa(i+1)).
3. Manejo del número 2: Cuando sumas 1 + 1 en la posición φ⁰, obtienes un dígito 2. El algoritmo matemáticamente sabe que 2 = φ¹ + φ⁻², por lo que reparte ese valor sumando un 1 dos posiciones arriba y un 1 una posición abajo. Luego las pasadas de limpieza eliminan cualquier residuo indeseado.

---

Detalles de la implementación inversa (toInteger)

Para reconstruir el entero desde el String, el programa separa la parte entera de la fraccionaria y evalúa algebraicamente las potencias de $\phi = \frac{1 + \sqrt{5}}{2}$. Dado que la conversión original es matemáticamente exacta para números naturales, el resultado flotante acumulado estará infinitamente cerca del entero real (por ejemplo, 4.99999999994), por lo que un redondeo estándar (Math.round) devuelve el número natural exacto sin errores de precisión.

PhinarySystem.scala

object PhinarySystem:

  // Represents a phinary number using two lists of bits:
  // - integerPart: powers of phi starting from 0 (ordered from lowest to highest: phi^0, phi^1, phi^2...)
  // - fractionalPart: negative powers starting from -1 downwards (phi^-1, phi^-2, phi^-3...)
  case class Phinary(integerPart: List[Int], fractionalPart: List[Int]):
    override def toString: String =
      val intStr = integerPart.reverse.map(_.toString).mkString
      val fracStr = if fractionalPart.isEmpty then "" else "." + fractionalPart.map(_.toString).mkString
      val cleanIntStr = if intStr.isEmpty then "0" else intStr
      s"$cleanIntStr$fracStr"

  // Normalizes the phinary number by iteratively applying 011 -> 100 and handling digits >= 2
  def normalize(p: Phinary): Phinary =
    val grid = scala.collection.mutable.Map[Int, Int]().withDefaultValue(0)
    
    p.integerPart.zipWithIndex.foreach((b, i) => grid(i) = b)
    p.fractionalPart.zipWithIndex.foreach((b, i) => grid(-(i + 1)) = b)

    var hasChanges = true
    while hasChanges do
      hasChanges = false
      val keys = grid.keys.toList.sorted

      if keys.nonEmpty then
        val minKey = keys.head - 2
        val maxKey = keys.last + 2
        
        for i <- maxKey downTo minKey do
          // Rule 1: Eliminate consecutive 1s (011 -> 100)
          if grid(i) >= 1 && grid(i - 1) >= 1 then
            val pairs = Math.min(grid(i), grid(i - 1))
            grid(i) -= pairs
            grid(i - 1) -= pairs
            grid(i + 1) += pairs
            hasChanges = true
          
          // Rule 2: Handle digits greater than 1 using the identity: 2 = phi^1 + phi^-2
          if grid(i) >= 2 then
            val amount = grid(i) / 2
            grid(i) %= 2
            grid(i + 1) += amount
            grid(i - 2) += amount
            hasChanges = true

    val finalKeys = grid.filter(_._2 > 0).keys.toList
    if finalKeys.isEmpty then return Phinary(List(0), List())

    val maxInt = Math.max(0, finalKeys.max)
    val minFrac = Math.min(-1, finalKeys.min)

    val newInteger = (0 to maxInt).map(grid).toList
    val newFractional = (-1 downTo minFrac).map(grid).toList
    val cleanFractional = newFractional.reverse.dropWhile(_ == 0).reverse

    Phinary(newInteger, cleanFractional)

  // Adds 1 to the phinary representation at the phi^0 position
  def addOne(p: Phinary): Phinary =
    val newInteger = p.integerPart match
      case Nil => List(1)
      case head :: tail => (head + 1) :: tail
    normalize(Phinary(newInteger, p.fractionalPart))

  // Converts a positive integer to its standard Phinary representation
  def fromInteger(n: Int): Phinary =
    require(n >= 0, "Standard phinary system requires non-negative integers.")
    if n == 0 then Phinary(List(0), List())
    else
      var current = Phinary(List(1), List())
      for _ <- 2 to n do
        current = addOne(current)
      current

  // Converts a Phinary string representation back to an integer rounding to nearest whole number
  // Since standard representation of integers in base-phi is exact, we map powers mathematically
  def toInteger(phinaryStr: String): Int =
    val parts = phinaryStr.split('.')
    val intStr = parts(0).reverse
    val fracStr = if parts.length > 1 then parts(1) else ""

    // Lucas numbers sequence (L_n) is ideal here because phi^n + (-phi)^-n = L_n
    // However, since we know the input represents a clean integer, we can compute using standard powers of phi
    val phi = (1.0 + Math.sqrt(5.0)) / 2.0
    var total = 0.0

    // Sum positive powers (including phi^0)
    for i <- 0 until intStr.length do
      if intStr(i) == '1' then total += Math.pow(phi, i)

    // Sum negative powers
    for i <- 0 until fracStr.length do
      if fracStr(i) == '1' then total += Math.pow(phi, -(i + 1))

    // Round safely to handle any micro precision floating point noise
    Math.round(total).toInt

  @main def runTests(): Unit =
    println("=== Running Phinary System Tests ===")
    
    // Test 1: Integer to Phinary Conversion
    val numbersToTest = List(1, 2, 3, 4, 5, 10, 20)
    println("\n[Test 1] Converting Integers to Phinary:")
    val phinaryResults = numbersToTest.map(n => n -> fromInteger(n))
    phinaryResults.foreach((integer, phinary) => 
      println(s"Integer: $integer \t-> Phinary string: $phinary")
    )

    // Test 2: Phinary to Integer Conversion (Inverse function)
    println("\n[Test 2] Converting Phinary back to Integers:")
    val standardPairs = List(
      "1" -> 1,
      "10.01" -> 2,
      "100.01" -> 3,
      "101.01" -> 4,
      "1000.1001" -> 5,
      "10100.0101" -> 10
    )
    
    var allTestsPassed = true
    standardPairs.foreach: (phinaryStr, expectedInt) =>
      val computedInt = toInteger(phinaryStr)
      val status = if computedInt == expectedInt then "PASS" else "FAIL"
      if computedInt != expectedInt then allTestsPassed = false
      println(s"String: $phinaryStr \t-> Expected: $expectedInt \t-> Got: $computedInt \t[$status]")

    // Test 3: Round-trip Verification
    println("\n[Test 3] Round-trip Consistency Check (Int -> Phinary -> Int):")
    for i <- 1 to 50 do
      val phinary = fromInteger(i)
      val backToId = toInteger(phinary.toString)
      if i != backToId then
        println(s"❌ Symmetry failed for number $i: got $backToId")
        allTestsPassed = false
    
    if allTestsPassed then 
      println("\n✅ All tests passed successfully!")
    else 
      println("\n❌ Some tests failed.")