6
\$\begingroup\$

Introduction

I found a really interesting puzzle it was called Busy Brain Beaver. But it has been 3 years since the latest activity and there are some things I didn't like about it. So I decided to make a new one.

The Rules

I want this one to be more brainfuck focused:

  • Your goal is to make a brainfuck program that outputs the biggest number.
  • It has to output that number in finite time so you can't say +[+]. outputs infinity (it doesn't have to terminate ex: +.[+] is OK)
  • Your program can only be 500 useful characters(non-brainfuck characters don't count)
  • You can assume . outputs your number (in decimal notation).
  • Only the first output counts (so you can't say +[+.] outputs infinity)
  • You can't ask for input so , is ignored
  • This takes place in a special brainfuck environment:
    • There are an infinite amount of cell to the left and to the right.
    • All cells start at 0
    • All cells can hold any integer (so - at 0 becomes -1)
  • Give an approximation (lower bound) for which number your program would output (given an arbitrarily finite time) (if you are using a special notation please say which one or provide a link)
  • An explanation of your algorithm would be appreciated. (posting the formatted and commented version will be appreciated too)

Not a duplicate

It was marked as a possible duplicate of Largest Number Printable I think this is different because:

  • This question is brainfuck focused. And in largest number printable brainfuck isn't even allowed. Yes they are both a busy beaver. But if you think these two are duplicates then any two busy beavers are duplicates. The difference between a brainfuck contest and a non-brainfuck contest is really big. And before it got closed people seemed to have a lot of interest in this one.
  • The goal here is to output a long number not a lot of bytes

Leader Board (top 10)

  1. Gabriel Benamy 2↑↑↑411
  2. Mike Bufardeci 4277772 = 163*(162*162)
  3. fejfo 60762 = 246*247
\$\endgroup\$
36
  • 5
    \$\begingroup\$ I think without a character limit this is too broad because no matter what the current best answer is, I can copy it and add one + to the end to get an even better score. If recommend removing the section about "alternative goal" and adding a character limit. \$\endgroup\$
    – DJMcMayhem
    Commented Dec 19, 2016 at 14:06
  • 1
    \$\begingroup\$ I find the sandbox very useful for getting feedback on challenge ideas to fine tune them before posting. \$\endgroup\$ Commented Dec 19, 2016 at 14:38
  • 4
    \$\begingroup\$ @mbomb007, a better dupe target is codegolf.stackexchange.com/q/18028/194 \$\endgroup\$ Commented Dec 19, 2016 at 14:41
  • 1
    \$\begingroup\$ I didn't know of the sandbox. Is it to late to use it now and post an edited question later? \$\endgroup\$
    – fejfo
    Commented Dec 19, 2016 at 14:42
  • 2
    \$\begingroup\$ At this point, anything higher than what I provided will be purely theoretical, but you can test your algorithms by converting everything to COW and testing it here. + = MoO, - = MOo, < = mOo, > = moO, [ = MOO, ] = moo, . = OOM \$\endgroup\$ Commented Dec 19, 2016 at 19:47

4 Answers 4

9
\$\begingroup\$

22222222... (65536 twos) = 2↑↑↑4

Before I begin, this is not the largest number expressible using 500 bytes of New Brainfuck. It's simply where I gave up trying to wrap my head around how big the numbers were getting. This answer only uses 93 bytes and is therefore not the largest number, but it's proof of concept that mind-bogglingly large numbers are possible.

+++[->++[->+>+<<]>>[-<<+>>]+<[->[-<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<]>[-<+>]<<]>[-<+>]<<<]>>.

This is a modification of the exponentiation algorithm in Brainfuck.

This number is so large, it's almost impossible to describe in human terms. It isn't sufficient to say "the number has this many digits" because it has more digits than particles in the universe. In fact, the number of digits this number contains has more digits than the number of particles in the universe.

Let this number be x, and let f(0) = x. Recursively define f(n) = floor[log10[f(n-1)]]. The first n which is smaller than 1 googol is over 10,000.

This answer is 93 bytes.

If we removed removed a single leading +, the result would be 65536 = 2222. Removing another + gives us 4. This means that if we add another +, we would get a number tower with 2↑↑↑4 twos, which would be 2↑↑↑5. That answer would be 94 bytes. If I were to add another 406 plus signs to this, we would get 2↑↑↑411, which is mind-bogglingly big. Instead, if I were to add yet another outer loop, I could probably get something close to 2↑↑↑↑380. For the record, 2↑↑↑↑3 = 2↑↑↑4, and 2↑↑↑↑4 dwarfs 2↑↑↑4 much the same way that 2↑↑↑4 dwarfs 65536. In fact, it may just be possible to actually get close to Graham's Number using 500 bytes of brainfuck.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ you can go way past Graham's number in 500 bytes. I tried to make chain arrow notation my rough draft was around 350 bytes! \$\endgroup\$
    – fejfo
    Commented Dec 19, 2016 at 19:41
  • 1
    \$\begingroup\$ I would probably give this code credit for 2↑↑↑411 ? what does the rest think? \$\endgroup\$
    – fejfo
    Commented Dec 19, 2016 at 19:42
  • \$\begingroup\$ Well sure, but my brain hurt and the COW interpreter didn't even print this number (which I suspect may be smaller than I thought) \$\endgroup\$ Commented Dec 19, 2016 at 19:43
1
\$\begingroup\$

4277772 = 163*(162*162)

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-]<-]>>.

As a reaction to the 60762 solution this is another simple solution. Here we multiply just like that answer but inside of another loop. I am somewhat concerned that I am interpreting this nested loop incorrectly but I think that this is correct and the output would be 4,277,772.

The loop looks like the code below except the first + is replaced with 163 +s and the other two +s are replaced with 162 +s:

+[>+[>+<-]<-]>>.
\$\endgroup\$
0
\$\begingroup\$

499

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.

The naive approach, increments the starting cell 499 times before outputting that cell and terminating. I would submit a more complex answer, but there are no online testbeds for this variant of brainfuck and I do not want to post an answer that doesn't work.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I'm currently trying to set up a git hub pages for a custom interpreter. But I have never used git hub pages before so I might fail. \$\endgroup\$
    – fejfo
    Commented Dec 19, 2016 at 17:22
  • \$\begingroup\$ I probably won't be making that interpreter since Gabriel Benamy suggested the COW interpreter and git for windows doesn't want to install. \$\endgroup\$
    – fejfo
    Commented Dec 19, 2016 at 20:08
0
\$\begingroup\$

60762 = 246*247

As a reaction on the 499 solution I will do an other very simple solution it just multiplies 2 numbers

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-]>.

how it works is pretty self explanatory it uses the standard multiplication loop ++[>+++<-]>. would be 2*3 = 6

\$\endgroup\$

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