17
\$\begingroup\$

Write a program or function that fulfills the following

  • Scores less than 101 bytes under normal rules

  • Takes no input1 and always outputs a single integer.

  • Every integer is a possible output.

Your score will be the probability of the most frequent integer occurring, with a lower scoring being the goal. That is \$\mathrm{sup}\left\{P(x)|x\in\mathbb{Z}\right\}\$.

Since a few of these properties are not program decidable, you should be ready to provide a proof that your answer is valid and obtains the score it claims.


1 You may optionally take a stream of random bits, or a subroutine which produces random bits on each call as an input to provide randomness. Each bit will be uniform and independent of other bits.

\$\endgroup\$
0

7 Answers 7

10
\$\begingroup\$

Python 3, score \$\approx \frac{1}{\sqrt{8\pi\lambda}}\$ where \$\lambda \approx 9\uparrow\uparrow (9\uparrow \uparrow (9 \uparrow \uparrow (9 \uparrow \uparrow (9\uparrow\uparrow 9)))))\$

This is g(9), approximately 10^(10^(10^(10^(10^(10^(10^8.567841344463464)))))); I'm doing g(g(g(g(g(9))))) to get the \$\lambda\$ above.

\$a \uparrow b\$ (Knuth's up-arrow notation) is a to the power of b. \$a \uparrow\uparrow b\$ is a to the power of itself, b times. So \$9\uparrow\uparrow 3 = 9^{9^9}\$ and \$9\uparrow\uparrow 9 = 9^{9^{9^{9^{9^{9^{9^{9^{9}}}}}}}}\$

from numpy.random import*
g=lambda n:n and 9**g(n-1)
print(choice([-1,1])*poisson(g(g(g(g(g(9)))))))

DON'T Try it online! Blows the recursion limit, of course.

How it works:

The Poisson distribution is a random distribution that, by itself, already generates random positive integers from 0 to infinity. This distribution takes a parameter, \$\lambda \$, that affects how likely the smaller integers are. What we have to do is set \$\lambda\$ in such a way that small numbers become very unlikely.

Then we use the wiki page again to realize the mode of the distribution is related to its parameter and then we plug the mode into the probability density function to get the program's score. After that we use Sterling's approximation to simplify the expression to something that is only slightly more digestible.

If I really can't waive the recursion limit then a similar approach with a loop gives

Python 2, score \$\approx \frac{1}{\sqrt{8\pi\lambda}}\$ where \$\lambda = 9\uparrow\uparrow (9 \uparrow\uparrow 7)\$

from numpy.random import*
print(choice([-1,1])*poisson(eval('**'.join(`9`*9**9**9**9**9**9**9**9))))

Don't try it online! Got some more bigness because @xnor taught me how join works when used directly on strings.

\$\endgroup\$
15
  • 1
    \$\begingroup\$ You could add another 9 as your code-golf score is only 99. \$\endgroup\$
    – Noodle9
    Commented Mar 9, 2020 at 18:05
  • 2
    \$\begingroup\$ Because Python imposes a hard limit on recursion depth, regardless of RAM. You can override it with sys.setrecursionlimit. \$\endgroup\$
    – Grimmy
    Commented Mar 9, 2020 at 18:26
  • 3
    \$\begingroup\$ I've written plenty of answers in Python that hit the default recursion limit. Usually this is once input gets large enough. Here we take no input, but answers to this question cannot complete in reality as we know it anyway, so I can't see what's extra special about a recursion limit, over say time or space. If people feel there needs to be clarification then head to meta. I'm using recursion in my Jelly answer too and Jelly does sys.setrecursionlimit(1 << 30) so it would come under the same ruling; I don't feel one should write an interpreter in another language just to avoid this. \$\endgroup\$ Commented Mar 9, 2020 at 19:17
  • 1
    \$\begingroup\$ ...actually looping gained me a byte to use in the end. \$\endgroup\$ Commented Mar 9, 2020 at 19:34
  • 2
    \$\begingroup\$ My experience has been that's its standard in Python golfing here to ignore the recursion limit as a machine limit like memory. \$\endgroup\$
    – xnor
    Commented Mar 9, 2020 at 22:50
9
\$\begingroup\$

05AB1E, score 0.5 / 1000!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

bug fix thanks to FryAmTheEggman

+1 ! thanks to ExpiredData

 [₄!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!LΩ#¼]¾D±)Ω

(dont't) Try it online! (will timeout).

Try it online without the factorials

[           ]            # loop:
 ₄                       #  1000
  !!...!                 #  take the factorial, 88 times
        LΩ               #  pick a random number from 1 to that many
          #              #  if the number was 1, exit the loop
           ¼             #  increment counter_variable
             ¾           # after the loop: push counter_variable
              D±         # push its bitwise negation
                )        # wrap the two in a list
                 Ω       # pick a random element of that list

Any integer would work instead of 1000!!...!, so this approach could score as low as 0.5 / BB(89), where BB is 05AB1E's Busy Beaver function.

\$\endgroup\$
12
  • \$\begingroup\$ Sorry, from your explanation I failed to understand how your program can generate arbitrarily large numbers. \$\endgroup\$
    – RGS
    Commented Mar 9, 2020 at 17:32
  • 1
    \$\begingroup\$ @RGS Think "number of consecutive heads until you get tails". This can be 0, but it can also be arbitrarily large if you get a lot of heads in a row. This is the same, but instead of flipping a 2-sided coin, we flip a 1000!!!... sided dice (and only stop on 1, so that 0, the most likely number, has probability 1/1000!!!...). \$\endgroup\$
    – Grimmy
    Commented Mar 9, 2020 at 17:35
  • \$\begingroup\$ @ExpiredData indeed, that saves one byte. \$\endgroup\$
    – Grimmy
    Commented Mar 9, 2020 at 18:50
  • 1
    \$\begingroup\$ @FryAmTheEggman that's a bug in legacy 05AB1E, i switched to modern 05AB1E to work around it. \$\endgroup\$
    – Grimmy
    Commented Mar 9, 2020 at 18:50
  • \$\begingroup\$ @Grimmy starting to think a construction like ∞₄ùJ will grow faster but I'm not sure.. or even just ₄LJLJLJLJLJLJ... \$\endgroup\$ Commented Mar 9, 2020 at 19:16
3
\$\begingroup\$

Jelly, 1 / 2M ?*,

* Any help scoring this appreciated, 0 and -1 are the two equally most likely answers at \$\frac{1}{2M}\$ - see code breakdown.

Inspiration taken from Grimmy's 05AB1E answer.

‘ɼµ⁹!!!!;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊ;”!ẋ$VƊX’µ¿~2X¤¡

No point trying this online!

Try incrementing with 4 increment tetrations (with incrementing the self-referential tetration is just doubling, also start with 2 rather than 256 so n=(2+1+1+1+1)*2*2*2*2=96, much more likely to terminate)

How?

‘ɼµ⁹!!!!;”!ẋ$VƊ;”!ẋ$VƊ ... X’µ¿~2X¤¡ - Link, no arguments
                              ¿      - while...
  µ                          µ       - ...condition: monadic chain (f(0)):
   ⁹                                 -     256
    !                                -     factorial = 256*255*...*1 = a
     !                               -     factorial = a*(a-1)*...*1 = b
      !                              -     factorial = b*(b-1)*...*1 = c
       !                             -     factorial = c*(c-1)*...*1 = A
              Ɗ                      -     last three links as a monad:
            $                        -       last two links as a monad:
         ”!                          -         literal '!' character
           ẋ                         -         repeated A times
        ;                            -       concatenate to A -> number A with A '!' after it
             V                       -       evaluate as Jelly code -> A!!..! * (A!!..!-1) * ... * 1
               ;”!ẋ$VƊ               -     call that B and repeat that process
                       ...           -     repeat 10 more times giving us M
                           X         -     choose a random integer in [1..M] inclusive
                            ’        -     decrement (i.e. while random choice != 1)
                                   ¡ - repeat...
                                  ¤  - ...number of times:
                                2    -   two
                                 X   -   random integer in [1,2] inclusive
                               ~     - ...action: bitwise NOT
\$\endgroup\$
2
  • \$\begingroup\$ What is M here? \$\endgroup\$ Commented Mar 9, 2020 at 18:46
  • \$\begingroup\$ See the code breakdown - I don't know how to measure it - take \$A=256!!!\$ and apply factorial \$A\$ times to \$A\$ to yield \$B\$, now apply factorial \$B\$ times to \$B\$ to yield \$C\$ ... etc. to yield \$M\$. \$\endgroup\$ Commented Mar 9, 2020 at 18:56
3
\$\begingroup\$

C (gcc), 99 bytes

f(b,t)long b(),t;{for(b()/4503599627370496&&printf("-");t-9007199254740992;t=b())putchar(t%10+48);}

b is a function returning 52 random bits in the form of an integer in the range of [0, 9007199254740992).

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ Yup, this looks valid now. As far as I can tell, the most likely output is now 0, with probability 1/112, so that's your score. \$\endgroup\$
    – Grimmy
    Commented Mar 9, 2020 at 21:26
  • \$\begingroup\$ You can improve this to 1/230, if you take a full byte from your random function. Try it online! \$\endgroup\$
    – Wheat Wizard
    Commented Mar 9, 2020 at 21:36
  • 1
    \$\begingroup\$ @PostRockGarfHunter I can improve it a lot more if I take numbers in a range of [0, -LONG_MIN/4) assuming LONG_MIN/4 % 10 == -2. \$\endgroup\$
    – S.S. Anne
    Commented Mar 9, 2020 at 21:37
  • \$\begingroup\$ @Post Also, that 8 is intentionally (15+1)/2, so the probability of the number being positive or negative is equal. \$\endgroup\$
    – S.S. Anne
    Commented Mar 10, 2020 at 0:08
3
\$\begingroup\$

Pyth, score of the order \$f_{\varphi(\omega,0)+1}(10^{10^{64}})^{-1}\$

M,-.<hG@H1.<hH@G1+@G1@H1D%ZYI<hZ0R,_hZ@Z1J,1 0V.<1Y=J%gZJY)R,hJ+@J1YVC*GCG=T@%TT1)K0WOT=+K1)IO2K.?_K

Don't try it online!

Pyth, score of the order \$f_{\varphi(\omega,0)+\omega}(4)^{-1}\$

(More precisely around \$f_{\varphi(\omega,0)+4}(10)^{-1}\$)

M,-.<hG@H1.<hH@G1+@G1@H1D%dYI<hd0R,_hd@d1J,1 0V.<1Y=J%gdJY)R,hJ+@J1YVTVTVTVT=T@%TT1;WOT=+Z1)IO2Z.?_Z

Don't try it online!

Original python, but in the Pyth I made changes to increase size:

import random
g=lambda G,H:(G[0]<<H[1]-H[0]<<G[1],G[1]+H[1])
def C(Z,Y):
  if Z[0]<0: return -Z[0],Z[1]
  J=(1,0)
  for N in range(1<<Y):J=C(g(Z,J))
  return J[0],J[1]+Y
T=10
for N in range(T): T=C(T,T)[1]
K=0
while random.randint(0,T):
  K+=1
if random.randint(0,1):
  print(K)
else:
  print(-K)

Explanation

This uses the extremely fast growing functions \$M_n\$ defined here. They're actually my go-to when I need fast-growing functions, since they have a growth rate approaching \$\varphi(\omega,0)\$ and are simple to implement. Since they operate on fractions, I use the representation \$(a,b)=\frac{a}{2^b}\$. I iterate the operation \$n\mapsto M_{2^n}(n)\$ starting from 10 roughly \$10^{10^{64}}\$ times, then output integers in a geometric distribution with parameter \$\frac{1}{n}\$, with signs attached. Thus, the score is \$\frac{1}{n}\$. Yes, you can slightly improve it, but it's so big your improvements are negligible.

Yes, this absolutely dominates every other entry so far.

\$\endgroup\$
1
  • \$\begingroup\$ can we have link to test online :-) \$\endgroup\$ Commented Sep 20, 2022 at 2:12
1
\$\begingroup\$

Charcoal, 26 bytes, score 0.0005

W‽φ⊞υωI⎇‽²Lυ±⊕Lυ

Try it online! Link is to verbose version of code. 0 and -1 have probabilities of 0.0005, then each subsequent integer has a probability 0.999 times that of the previous. Obviously there are still 75 bytes with which to create some form of arbitrary large expression in order to obtain a lower score, but the resulting code would take longer than the heat death of the universe to run, so it's not quite suitable for TIO. Explanation:

W‽φ

While a random number 0..999 is non-zero...

⊞υω

...push the empty string to the empty list.

I⎇‽²Lυ±⊕Lυ

Randomly print either the length of the list or -1 minus that length.

\$\endgroup\$
-1
\$\begingroup\$

bash + linux, 1 / big number

cat /dev/random | hexdump -n `b` -ve '/1 "%02u"'

This program will print out 'b' bytes of decimal digits, where b is a program producing a random input number.

(edited to try to be more infinity-ish, although technically still limited by the bash shell)

\$\endgroup\$
3
  • 2
    \$\begingroup\$ The spec explicitly requires Every integer is a possible output. A very large number of possible integers != every integer. \$\endgroup\$
    – Grimmy
    Commented Mar 10, 2020 at 13:04
  • \$\begingroup\$ sorry! thats what i get for coding at 3 am. \$\endgroup\$
    – don bright
    Commented Mar 11, 2020 at 3:09
  • \$\begingroup\$ looking at this again, other solutions have limited output as well. ?? \$\endgroup\$
    – don bright
    Commented Jun 14, 2023 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.