Last active
May 9, 2026 15:54
-
-
Save ScriptRaccoon/4d43e8ae90df5b5dcd7714f4dfceb827 to your computer and use it in GitHub Desktop.
Can every positive integer be reached from 3 by repeatedly applying n! or floor(sqrt(n))?
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * {@link https://math.stackexchange.com/questions/5136135} | |
| */ | |
| /** | |
| * Returns the factorial of a big integer | |
| */ | |
| function factorial(n: bigint): bigint { | |
| let result = 1n | |
| for (let i = 2n; i <= n; i++) { | |
| result *= i | |
| } | |
| return result | |
| } | |
| /** | |
| * Computes the floor square root of a big integer using Heron's method. | |
| */ | |
| function floor_sqrt(n: bigint): bigint { | |
| if (n < 2n) return n | |
| let x = n | |
| let y = (x + 1n) >> 1n | |
| while (y < x) { | |
| x = y | |
| y = (x + n / x) >> 1n | |
| } | |
| return x | |
| } | |
| /** | |
| * Checks if a set of big integers contains all integers 1,2,...,d. | |
| */ | |
| function covers_all(reached: Set<bigint>, d: number): boolean { | |
| for (let i = 1; i <= d; i++) { | |
| if (!reached.has(BigInt(i))) return false | |
| } | |
| return true | |
| } | |
| /** | |
| * Checks if all positive integers <= d are reachable from 3 by applying the | |
| * operations P(n) := n! and M(n) := floor(sqrt(n)) over and over again. | |
| * Prints a minimal proof in a human-readable way. | |
| */ | |
| function show_reachable_numbers(d: number) { | |
| let max_factorial_input = 10n // dynamic bound of factorial to prevent overflow | |
| const reached = new Set<bigint>([3n]) | |
| const queue: bigint[] = [3n] | |
| const mappings: { from: bigint; to: bigint; op: 'M' | 'P' }[] = [] | |
| let done = false | |
| while (!done) { | |
| for (let i = 0; i < queue.length; i++) { | |
| const n = queue[i] | |
| const sqrt_n = floor_sqrt(n) | |
| if (!reached.has(sqrt_n)) { | |
| mappings.push({ from: n, to: sqrt_n, op: 'M' }) | |
| reached.add(sqrt_n) | |
| queue.push(sqrt_n) | |
| } | |
| if (n <= max_factorial_input) { | |
| const fact = factorial(n) | |
| if (!reached.has(fact)) { | |
| mappings.push({ from: n, to: fact, op: 'P' }) | |
| reached.add(fact) | |
| queue.push(fact) | |
| } | |
| } | |
| if (covers_all(reached, d)) { | |
| done = true | |
| break | |
| } | |
| } | |
| max_factorial_input *= 2n | |
| } | |
| const relevant_numbers = new Set<bigint>() | |
| for (let i = 1; i <= d; i++) { | |
| relevant_numbers.add(BigInt(i)) | |
| } | |
| for (let i = mappings.length - 1; i >= 0; i--) { | |
| const { from, to } = mappings[i] | |
| if (relevant_numbers.has(to) && !relevant_numbers.has(from)) { | |
| relevant_numbers.add(from) | |
| } | |
| } | |
| for (const { from, to, op } of mappings) { | |
| if (relevant_numbers.has(from) && relevant_numbers.has(to)) { | |
| console.info(`${op}(${from}) = ${to}`) | |
| } | |
| } | |
| } | |
| // Example | |
| show_reachable_numbers(9) |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Interactive Codepen:
https://codepen.io/scriptraccoon/pen/zxoqNEJ