coding.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyNgQM0Gzn4eUQ7p8gY2KTmd",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/lmoss/onesharp/blob/main/coding.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Coding words by numbers"
      ],
      "metadata": {
        "id": "ykm2VfJX3SfP"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Shortlex ordering on words\n",
        "\n",
        "Here are definitions of the length function on numbers. We also have the function ```s(n)``` giving the nth word in the shortlex order on words, starting with n = 0.  We have the inverse of ```s``` also."
      ],
      "metadata": {
        "id": "k2GcQpQE3upM"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "We can check that ```s``` and ```s_inverse``` really are inverses."
      ],
      "metadata": {
        "id": "4g4JaTo436LS"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "import math\n",
        "\n",
        "def log2int(x):\n",
        "  return(math.frexp(x)[1] - 1)\n",
        "\n",
        "def length(n):\n",
        "  return(log2int(n+1))\n",
        "\n",
        "def index(n,m): ## this is what I write as (n)_m\n",
        "  a = (n+1)%(2**(m+1))\n",
        "  b = 2**m\n",
        "  if a < b:\n",
        "    return(0)\n",
        "  else:\n",
        "    return(1)\n",
        "\n",
        "def convert_numeral_to_onesharp(x):\n",
        "   if x == 0:\n",
        "     return('#')\n",
        "   else:\n",
        "     return('1')    \n",
        "\n",
        "def s(n):\n",
        "  k = length(n)  \n",
        "  s = [convert_numeral_to_onesharp(index(n,k-i-1)) for i in range(k)] \n",
        "  t = \"\".join(s) \n",
        "  return(t)\n",
        "\n",
        "def s_inverse(w):\n",
        "  n = len(w)\n",
        "  a = (2**n - 1)\n",
        "  b = [(2** (n-i-1)) for i in range(n) if (w[i] == '1')]\n",
        "  c = sum(b)\n",
        "  d = c+a\n",
        "  return(d)\n"
      ],
      "metadata": {
        "id": "2HXsd8AK9ffS"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "s_inverse(s(4234))"
      ],
      "metadata": {
        "id": "Vk6UfopQ39G0"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "s(s_inverse('##111##1'))"
      ],
      "metadata": {
        "id": "H3FaOChH9jHW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "for n in range(256):\n",
        "  print((n,s(n), s_inverse(s(n))))\n",
        " "
      ],
      "metadata": {
        "id": "pGg4JYEA4CCD"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "001zh25v4CMQ"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}