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
Author
Here is the output for
M(3) = 1
P(3) = 6
M(6) = 2
P(6) = 720
M(720) = 26
M(26) = 5
P(5) = 120
M(120) = 10
P(26) = 403291461126605635584000000
M(403291461126605635584000000) = 20082117944245
M(20082117944245) = 4481307
M(4481307) = 2116
M(2116) = 46
P(46) = 5502622159812088949850305428800254892961651752960000000000
M(5502622159812088949850305428800254892961651752960000000000) = 74179661362209580727623742159
M(74179661362209580727623742159) = 272359434134765
M(272359434134765) = 16503315
M(16503315) = 4062
M(4062) = 63
M(63) = 7
P(63) = 1982608315404440064116146708361898137544773690227268628106279599612729753600000000000000
P(7) = 5040
M(1982608315404440064116146708361898137544773690227268628106279599612729753600000000000000) = 44526490041372451122965980435912297622389065
M(5040) = 70
M(44526490041372451122965980435912297622389065) = 6672817249211344250611
M(70) = 8
P(70) = 11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000
M(6672817249211344250611) = 81687313881
P(8) = 40320
M(11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000) = 109446661301155695857080695109221322834464193656741
M(81687313881) = 285809
M(40320) = 200
M(109446661301155695857080695109221322834464193656741) = 10461675836172505677753392
M(285809) = 534
M(10461675836172505677753392) = 3234451396477
M(534) = 23
M(3234451396477) = 1798458
M(23) = 4
M(1798458) = 1341
M(1341) = 36
P(36) = 371993326789901217467999448150835200000000
M(371993326789901217467999448150835200000000) = 609912556675054213027
M(609912556675054213027) = 24696407768
M(24696407768) = 157150
M(157150) = 396
M(396) = 19
P(19) = 121645100408832000
M(121645100408832000) = 348776576
M(348776576) = 18675
M(18675) = 136
M(136) = 11
P(120) = 6689502913449127057588118054090372586752746333138029810295671352301633557244962989366874165271984981308157637893214090552534408589408121859898481114389650005964960521256960000000000000000000000000000
M(6689502913449127057588118054090372586752746333138029810295671352301633557244962989366874165271984981308157637893214090552534408589408121859898481114389650005964960521256960000000000000000000000000000) = 2586407337108586045310991770677553531245102834944805618026162911581903627374073073000747058630903971
M(2586407337108586045310991770677553531245102834944805618026162911581903627374073073000747058630903971) = 50856733449058503656314809531995029745228977864739
M(50856733449058503656314809531995029745228977864739) = 7131390709325811694018113
M(7131390709325811694018113) = 2670466384234
M(2670466384234) = 1634156
M(1634156) = 1278
M(1278) = 35
P(35) = 10333147966386144929666651337523200000000
M(10333147966386144929666651337523200000000) = 101652092779175702171
M(101652092779175702171) = 10082266252
M(10082266252) = 100410
M(100410) = 316
P(200) = 788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000
P(316) = 2056410584625275766114028688447474898050031704140968880610463735137473228595357640756197482760266023554168997586263919592886961249203349409557483536185374089092162349203260295131995580244836442680530520584901224764154954784360196586343451176126732634017946352199073308615878945685598982935022304287390316815402451985028639469728043315654079013700475646408464715509484032392283497998462422163717482998384498259564343998428185026720745307477933434532173854771549240804120160837896163757248489877840750268102837798901571619347642477742032446259650901942078749554461423850941631692800000000000000000000000000000000000000000000000000000000000000000000000000000
M(788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000) = 28083053027845645962655542024840215459780668143793671276126114133334476200709161144991477678742178649423370174077063921842590153852083862678565168456160342383791151833029688044250792326939
M(2056410584625275766114028688447474898050031704140968880610463735137473228595357640756197482760266023554168997586263919592886961249203349409557483536185374089092162349203260295131995580244836442680530520584901224764154954784360196586343451176126732634017946352199073308615878945685598982935022304287390316815402451985028639469728043315654079013700475646408464715509484032392283497998462422163717482998384498259564343998428185026720745307477933434532173854771549240804120160837896163757248489877840750268102837798901571619347642477742032446259650901942078749554461423850941631692800000000000000000000000000000000000000000000000000000000000000000000000000000) = 1434019032169822969994302295741702959549232308030578802263484145386775671802400191427627063736178830737130265250521845904547212359677277360096604308653528605013410565561149999416141058468125172891933868347517780536991685497110404534289799804727645031317380036087805845969801037222972059671652109110021665949572537162058514026701
M(28083053027845645962655542024840215459780668143793671276126114133334476200709161144991477678742178649423370174077063921842590153852083862678565168456160342383791151833029688044250792326939) = 5299344584743064805587607050345498649863997957412314599324199336653619323352184630533550640736
M(1434019032169822969994302295741702959549232308030578802263484145386775671802400191427627063736178830737130265250521845904547212359677277360096604308653528605013410565561149999416141058468125172891933868347517780536991685497110404534289799804727645031317380036087805845969801037222972059671652109110021665949572537162058514026701) = 37868443751622840752356884003639477556235973135944183628712019569737975929917714328430460064842845995925616917144535391591993357362616696885946007599022080221714933
M(5299344584743064805587607050345498649863997957412314599324199336653619323352184630533550640736) = 72796597343166148877979840971149199347681712778
M(37868443751622840752356884003639477556235973135944183628712019569737975929917714328430460064842845995925616917144535391591993357362616696885946007599022080221714933) = 6153734130722811845938039172242490258578519487068534908110352071239461739053900359
M(72796597343166148877979840971149199347681712778) = 269808445648326859186435
M(6153734130722811845938039172242490258578519487068534908110352071239461739053900359) = 78445740041909298351839436302717002647067
M(269808445648326859186435) = 519430886305
M(78445740041909298351839436302717002647067) = 280081666736524006911
M(519430886305) = 720715
M(280081666736524006911) = 16735640613
M(720715) = 848
M(16735640613) = 129366
M(848) = 29
M(129366) = 359
P(29) = 8841761993739701954543616000000
M(359) = 18
M(8841761993739701954543616000000) = 2973510046012910
P(18) = 6402373705728000
M(2973510046012910) = 54529900
M(6402373705728000) = 80014834
M(54529900) = 7384
M(80014834) = 8945
M(7384) = 85
M(8945) = 94
M(85) = 9
P(94) = 108736615665674308027365285256786601004186803580182872307497374434045199869417927630229109214583415458560865651202385340530688000000000000000000000
M(108736615665674308027365285256786601004186803580182872307497374434045199869417927630229109214583415458560865651202385340530688000000000000000000000) = 10427685057848376925507942191442630012584828624363222101172323570579332599
M(10427685057848376925507942191442630012584828624363222101172323570579332599) = 3229192632508685897009252938495265606
M(3229192632508685897009252938495265606) = 1796995445878671640
M(1796995445878671640) = 1340520587
M(1340520587) = 36613
M(36613) = 191
M(191) = 13
P(13) = 6227020800
M(6227020800) = 78911
M(78911) = 280
P(280) = 16772277799452185316008559642481690996154162653443224216229144166533010495138176552175779628900866154937655467080893509725117402094786797430449965992591855047863335070498197537053948882096262565780315504934744482331080425680552490971597062111349307447058139219943834846427081475234675780303186241495364354473220247981334182737896146496569057168205263172422932268545207065230644665792052186286503978375114413827309599287477421264601465575912229816923404173201977337878379210932930098887603481739264000000000000000000000000000000000000000000000000000000000000000000000
M(16772277799452185316008559642481690996154162653443224216229144166533010495138176552175779628900866154937655467080893509725117402094786797430449965992591855047863335070498197537053948882096262565780315504934744482331080425680552490971597062111349307447058139219943834846427081475234675780303186241495364354473220247981334182737896146496569057168205263172422932268545207065230644665792052186286503978375114413827309599287477421264601465575912229816923404173201977337878379210932930098887603481739264000000000000000000000000000000000000000000000000000000000000000000000) = 4095397147951854658566344451214616088122117897947064078228252960315387432217927974764854842657091588540434362295535631956707351383878740409817959601766511751115542225350927803373774855720364924177199841180358061925489610019454499684570079020562439657528088955149689372399079672036560
M(4095397147951854658566344451214616088122117897947064078228252960315387432217927974764854842657091588540434362295535631956707351383878740409817959601766511751115542225350927803373774855720364924177199841180358061925489610019454499684570079020562439657528088955149689372399079672036560) = 2023708760655014474053396025719424437516065360941505190775278251150938848107629610752243589602624725995789454977631466595280501381307516910876
M(2023708760655014474053396025719424437516065360941505190775278251150938848107629610752243589602624725995789454977631466595280501381307516910876) = 44985650608333036245828536851761484608364045767004689172952883368246592
M(44985650608333036245828536851761484608364045767004689172952883368246592) = 212098209818784270298625802076688836
M(212098209818784270298625802076688836) = 460541214028434452
M(460541214028434452) = 678631869
M(678631869) = 26050
M(26050) = 161
M(161) = 12
Author
Interactive Codepen:
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Usage:
pnpm add -g tsx(or npm, etc.), thentsx script.ts.