Largest Number Printable

  • Your goal is to write a program that prints a number. The bigger the number, the more points you'll get. But be careful! Code length is both limited and heavily weighted in the scoring function. Your printed number will be divided by the cube of the number of bytes you used for your solution.



    So, let's say you printed 10000000 and your code is 100 bytes long. Your final score will be 10000000 / 100^3 = 10.



    There are other rules to follow, in order to make this challenge a bit harder.




    • You cannot use digits in your code (0123456789);

    • You can use mathematical/physical/etc. constants, but only if they are less than 10. (e.g. You can use Pi ~= 3.14 but you can't use the Avogadro constant = 6e23)

    • Recursion is allowed but the generated number needs to be finite (so infinite is not accepted as a solution. Your program needs to terminate correctly, assuming unbounded time and memory, and generate the requested output);

    • You cannot use the operations * (multiply), / (divide), ^ (power) nor any other way to indicate them (e.g. 2 div 2 is not allowed);

    • Your program can output more than one number, if you need it to do that. Only the highest one will count for scoring;

    • However, you can concatenate strings: this means that any sequence of adjacent digits will be considered as a single number;

    • Your code will be run as-is. This means that the end-user cannot edit any line of code, nor he can input a number or anything else;

    • Maximum code length is 100 bytes.






    Leaderboard






    1. Steven H., Pyth ≈ fφ(1,0,0)+7(25626)/1000000[1]

    2. Simply Beautiful Art, Ruby ≈ fφ121(ω)(126)[1]

    3. Peter Taylor, GolfScript ≈ fε0+ω+1(17)/1000 [1]

    4. r.e.s., GolfScript ≈ fε0(fε0(fε0(fε0(fε0(fε0(fε0(fε0(fε0(126))))))))) [1]

    5. Simply Beautiful Art, Ruby ≈ fωω2+1(1983)

    6. eaglgenes101, Julia ≈ fω3(127)

    7. col6y, Python 3, ≈ (127→126→...→2→1) / 993 [1][3]

    8. Toeofdoom, Haskell,a20(1) / 993 [1]

    9. Fraxtil, dc, ≈ 15 ↑¹⁶⁶⁶⁶⁶⁵ 15 / 1003 [3]

    10. Magenta, Python, ≈ ack(126,126)/1003 ≈ 10 ↑124 129

    11. Kendall Frey, ECMAScript 6, ≈ 10 3 ↑4 3 / 1003 [1]

    12. Ilmari Karonen, GolfScript, ≈ 10 ↑3 10377 / 183 [1]

    13. BlackCap, Haskell, ≈ 10↑↑65503/1003

    14. recursive, Python, ≈ 2↑↑11 / 953 ≈ 10↑↑8.63297 [1][3]

    15. n.m., Haskell, ≈ 2↑↑7 / 1003 ≈ 10↑↑4.63297 [1]

    16. David Yaw, C, ≈ 10104×1022 / 833 ≈ 10↑↑4.11821 [2]

    17. primo, Perl, ≈ 10(12750684161!)5×227 / 1003 ≈ 10↑↑4.11369

    18. Art, C, ≈ 10102 × 106 / 983 ≈ 10↑↑3.80587

    19. Robert Sørlie, x86, ≈ 102219+32 / 1003 ≈ 10↑↑3.71585

    20. Tobia, APL, ≈ 1010353 / 1003 ≈ 10↑↑3.40616

    21. Darren Stone, C, ≈ 101097.61735 / 983 ≈ 10↑↑3.29875

    22. ecksemmess, C, ≈ 102320 / 1003 ≈ 10↑↑3.29749

    23. Adam Speight, vb.net, ≈ 105000×(264)4 / 1003 ≈ 10↑↑3.28039

    24. Joshua, bash, ≈ 101015 / 863 ≈ 10↑↑3.07282





    Footnotes




    1. If every electron in the universe were a qubit, and every superposition thereof could be gainfully used to store information (which, as long as you don't actually need to know what's being stored is theoretically possible), this program requires more memory than could possibly exist, and therefore cannot be run - now, or at any conceiveable point in the future. If the author intended to print a value larger than ≈3↑↑3.28 all at once, this condition applies.

    2. This program requires more memory than currently exists, but not so much that it couldn't theoretically be stored on a meager number of qubits, and therefore a computer may one day exist which could run this program.

    3. All interpreters currently available issue a runtime error, or the program otherwise fails to execute as the author intended.

    4. Running this program will cause irreparable damage to your system.






    Edit @primo: I've updated a portion of the scoreboard using a hopefully easier to compare notation, with decimals to denote the logarithmic distance to the next higher power. For example 10↑↑2.5 = 1010√10. I've also changed some scores if I believed to user's analysis to be faulty, feel free to dispute any of these.



    Explanation of this notation:



    If 0 ≤ b < 1, then a↑↑b = ab.



    If b ≥ 1, then a↑↑b = aa↑↑(b-1).



    If b < 0, then a↑↑b = loga(a↑↑(b+1)).


    Has someone explicitly said "base 10" yet?

    Does the large number count if it's say `12e10` (12*10^10) as `12*10^10`?

    I think a better constraint instead of forbidding *, /, and ^, would've been to _allow_ only _linear_ operations, _e.g._ +, -, ++, --, +=, -=, etc. Otherwise, coders can take advantage of Knuth's up-arrow/Ackermann library functions if made available in their language of choice, which seems like cheating.

    I'm still waiting to see someone earn footnote [4].

    @hichris123 I think that counts as exponentiation.

    Say, if my program prints `500b`, is this invalid? That is, may we ignore all non-numeric things a program prints? And if so, would something like `50r7` count as `507`?

    I cannot find a language nor a constant that does, but what about a constant `x` that is `x<-10`?

    Requesting change of accept votes someday.

    Can we output in base-256 (if our language is allowed to output in Unicode numbers normally)

  • Peter Taylor

    Peter Taylor Correct answer

    7 years ago

    GolfScript; score at least fε_0+ω+1(17) / 1000



    Following r.e.s.'s suggestion to use the Lifetime of a worm answer for this question, I present two programs which vastly improve on his derivation of Howard's solution.



    They share a common prefix, modulo the function name:



    ,:z){.[]+{\):i\.z={.z+.({<}+??\((\[email protected]<i*\+}{(;}if.}do;}:g~g


    computes g(g(1)) = g(5) where g(x) = worm_lifetime(x, [x]) grows roughly as fε0 (which r.e.s. notes is "the function in the fast-growing hierarchy that grows at roughly the same rate as the Goodstein function").



    The slightly easier (!) to analyse is



    ,:z){.[]+{\):i\.z={.z+.({<}+??\((\[email protected]<i*\+}{(;}if.}do;}:g~g.{.{.{.{.{.{.{.{.{.{g}*}*}*}*}*}*}*}*}*}*


    .{foo}* maps x to foo^x x.



    ,:z){[]+z\{\):i\.z={.z+.({<}+??\((\[email protected]<i*\+}{(;}if.}do;}:g~g.{g}*


    thus gives g^(g(5)) ( g(5) ); the further 8 levels of iteration are similar to arrow chaining. To express in simple terms: if h_0 = g and h_{i+1} (x) = h_i^x (x) then we calculate h_10 (g(5)).



    I think this second program almost certainly scores far better. This time the label assigned to function g is a newline (sic).



    ,:z){.[]+{\):i\.z={.z+.({<}+??\((\[email protected]<i*\+}{(;}if.}do;}:
    ~
    {.['.{
    }*'n/]*zip n*~}:^~^^^^^^^^^^^^^^^^


    This time I make better use of ^ as a different function.



    .['.{
    }*'n/]*zip n*~


    takes x on the stack, and leaves x followed by a string containing x copies of .{ followed by g followed by x copies of }*; it then evaluates the string. Since I had a better place to burn spare characters, we start with j_0 = g; if j_{i+1} (x) = j_i^x (x) then the first evaluation of ^ computes j_{g(5)} (g(5)) (which I'm pretty sure already beats the previous program). I then execute ^ 16 more times; so if k_0 = g(5) and k_{i+1} = j_{k_i} (k_i) then it calculates k_17. I'm grateful (again) to r.e.s. for estimating that k_i >> fε_0+ω+1(i).




    If I'm not mistaken, the number your program computes (call it n) can be written n = f^9 (g(3)), where f(x) = g^(4x) (x), and g(x) is the lifetime of worm [x]. If we treat g as being approximately the same as f_eps_0 in the fast-growing hierarchy, then my "back-of-envelope" calculations show that f_(eps_0 + 2)(9) < n < f_(eps_0 + 2)(10). Of course it's the current winner -- by far.

    @r.e.s., I think that's underestimating it quite a lot. `.{foo}*` maps `x` to `foo^x (x)`. If we take `h_0 (x) = g^4 (x)` and `h_{i+1} (x) = h_i^x (x)` then the value calculated is `h_9 (g(3))`. Your `f(x) = g^(4x) (x) = h_0^x (x) = h_1 (x)`.

    (This pertains to your original program -- I just saw that you've made some edits.) Ohhh... I misunderstood how the `*` works. It is safe to say that h_0(x) = g^4(x) >> f_eps_0(x); consequently, the relation h_{i+1} (x) = h_i^x (x) effectively defines an "accelerated" fast-growing hierarchy such that h_i(x) >> f_(eps_0 + i)(x). I.e., the computed number h_9 (g(3)) is certainly much greater than f_(eps_0 + 9)(g(3)). As for g(3), I think I can show that it's greater than g_4, the fourth number in the g_i sequence used to define Graham's number (which is g_64).

    @r.e.s., so `j_i ~ f_{eps_0 + i}`; does that make `k_i ~ f_{eps_0 + i omega + i^2}`?

    Given what you wrote, I get `k_i ~ f_{ε_0 + ω}^i (k_0)`. Here's the reasoning: k_{i+1} = j_{k_i} (k_i) = j_ω (k_i) ~ f_{ε_0 + ω} (k_i) ~ f_{ε_0 + ω}^2 (k_{i-1}) ... ~ f_{ε_0 + ω}^{i+1} (k_0), so k_i ~ f_{ε_0 + ω}^i (k_0). A very conservative lower bound on k_i, entirely in terms of the fast-growing hierarchy, is then `k_i >> f_{ε_0 + ω}^i (i) = f_{ε_0 + ω + 1} (i)`.

    About the scoring (dividing by 100^3) ... The funny thing is that this computed number (call it C) is **so big** that operations like C/G or C^(1/G), etc., where G is Graham's number, result in numbers that are *still approximately equal to C*.

    Is there a mistake in your second program (the string copying part)? According to the description, if `3` were on the stack, it should produce `3.{.{.{g}*}*}*` -- but it seems to produce `3.{g}*.{g}*.{g}*` instead.

    @r.e.s., are you sure? I just tested `3{.['.{ }*'n/]*zip'g'*]p}:^~` (i.e. replacing the `~` which evaluates the string with `]p` to print the contents of the stack) and got `[3 ".{.{.{g}*}*}*"]`

    @r.e.s. PS Thanks for your comment on your question about starting the age at `x` rather than `0`: hadn't occurred to me!

    I can't seem to reproduce what you just did, but I'm sure that's just my ignorance of the syntax. However, the description seems to say `3.['.{g}*'n/]*zip n*` (replacing the newline with g) should produce `3.{.{.{g}*}*}*` -- but it produces `3.{g}*.{g}*.{g}*`.

    @r.e.s., you also need to replace that `g` with a newline so that the `n/` splits the string into prefix and suffix.

    Ok, got it. BTW, I think your core program will also give a winning answer to the Shortest terminating program whose output size exceeds Graham's number. (The current winner is 63 bytes of Haskell code.) E.g., at 51 bytes, *something like* (since I hardly know the syntax) `9.[]+{\):i\.0={.0+.({<}+??\((\[email protected]> Graham's number. You may know how to golf it even more.

    In the same spirit, you and @r.e.s. might be interested in Golf a number bigger than TREE(3).

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM