P-adic number computation

The p-adic expansion is a way of representing rational numbers as an infinite series of digits in base p, where p is a prime number. It is used in number theory and can be used to efficiently calculate the modular inverse of a number modulo a prime.

Here's a step-by-step description of the p-adic expansion algorithm:

1. `calc` function:

   - Parameters: `p`, `a`, `b`, and an optional parameter `expands` (defaulted to 10).

   - If `expands` is equal to 0 or `b` is equal to 0, the function returns an empty array `[]`.

   - Calculates `i` as `(a * modPow(b, p - 2, p) + 2 * p) % p`. The `modPow` function calculates `b` raised to the power `(p - 2)` modulo `p`, which is used to find the modular inverse of `b`.

   - Logs the value of `Math.floor((a - b * i) / p)` to the console. This value represents the next digit in the p-adic expansion.

   - Recursively calls `calc` with the updated values of `a`, `b`, and `expands - 1`, and concatenates the result with `[i]`.

   - The recursion continues until `expands` becomes 0 or `b` becomes 0.

2. `modPow` function:

   - Parameters: `base`, `exponent`, and `modulus`.

   - Calculates `base` raised to the power `exponent` modulo `modulus` using a binary exponentiation algorithm.

   - Returns the calculated result.

3. In the final line, the `calc` function is called with `p=5`, `a=1`, and `b=3`, and the result is printed to the console using `console.log`.

The algorithm recursively calculates the p-adic expansion of `a` with respect to `b` for a given prime `p`. The expansion gives a representation of the rational number `a/b` in base `p` with an infinite series of digits. However, in this implementation, the recursion is limited to `expands` iterations, which gives a finite approximation of the p-adic expansion.

Here’s a javascript snippet of computing p-adic expansion.

function calc(p, a, b, expands = 10) {

    if (expands === 0 || b === 0) {

      return [];

    }

    const i = (a * modPow(b, p - 2, p)+2*p) % p;

    console.log(Math.floor((a - b * i) / p));

    return [i].concat(calc(p, Math.floor((a - b * i) / p), b, expands - 1));

  }

  function modPow(base, exponent, modulus) {

    let result = 1;

    base = base % modulus;

    while (exponent > 0) {

      if (exponent % 2 === 1) {

        result = (result * base) % modulus;

      }

      exponent = Math.floor(exponent / 2);

      base = (base * base) % modulus;

    }

    return result;

}

console.log(calc(5, 1, 3));

A detailed demo can be found In the following:

Compute p-adic expansion.