10
\$\begingroup\$

This challenge is for the largest finite number you can get BrainFuck programs of given lengths to contain in memory.

We must use one of the BF versions that uses big integers for the cells rather than byte values as not to be capped at 255. Do not use negative positions and values in memory. Do not use the BF instruction to input memory, also the output instruction is not needed.

Challenge:

Write Brainfuck programs with lengths from 0 to 50. Your score is the sum of each programs maximum value in memory.

As they may well be trivial feel free to omit the programs listed below and start from a length of 16, I'll use the following for the smaller sizes:

Length, Score, Program

 0,  0
 1,  1, +
 2,  2, ++
 3,  3, +++
Pattern Continues
10, 10, ++++++++++
11, 11, +++++++++++
12, 12, ++++++++++++
13, 16, ++++[->++++<]
14, 20, +++++[->++++<]
15, 25, +++++[->+++++<]

Total Score: 139

Related but different:

Large Numbers in BF

Largest Number Printable

Busy Brain Beaver

See the comments below for more info.

The combined results so far, being the sum of the best of each size:

length: 16 to 24
by sligocki

100, 176, 3175, 3175, 4212
4212, 6234, 90,963, 7,467,842

length: 25 to 30
by sligocki

239,071,921

length: 31, 32, 33, (34 to 37)
by sligocki

        380,034,304
     30,842,648,752
 39,888,814,654,548
220,283,786,963,581

length: 38
based on code by l4m2, by alan2here

(4 ^ 1366 - 4) / 3

"(4 ^ 1366 - 4) / 3" in full

length: 39 to 47
based on code by l4m2, by alan2here

Σ (n = 4 to 12) of (fn(0) | f(x) := (4x+2 - 4) / 3)

length: 48
based on code by l4m2, by alan2here

(172) - 2

length: 49, 50
by l4m2

(<sup>21</sup>2) - 2
(<sup>26</sup>2) - 2
Improve this question
\$\endgroup\$
15
  • 2
    \$\begingroup\$ How is this challenge different from Large Numbers in BF ? \$\endgroup\$
    – TFeld
    Nov 15, 2018 at 15:22
  • 4
    \$\begingroup\$ The other question says cells which can take on any integer value without overflowing, though it's impossible to actually get above 255 anyway. This extension seems like a more interesting question (that bans negative positions as well. I don't think eiher should be closed \$\endgroup\$
    – Jo King ♦
    Nov 15, 2018 at 22:22
  • 3
    \$\begingroup\$ There's a close connection between true busy beavers (counting execution time) and largest value computers. Clearly calculating a large value by incrementation implies a long execution, but also a long execution implies the possibility of counting the steps to get a large number. Perhaps the closest previous question is in fact codegolf.stackexchange.com/q/4813/194 . \$\endgroup\$
    – Peter Taylor
    Nov 16, 2018 at 23:04
  • 1
    \$\begingroup\$ Unfortunately, only the last program really counts for anything with the bigger busy beavers, as there's no point adding the smaller programs to the total. It gets to the ppint where the number is so large that doubling or tripling it doesn't really matter \$\endgroup\$
    – Jo King ♦
    Nov 21, 2018 at 13:59
  • 1
    \$\begingroup\$ Indeed, I wouldn't be surprised if that were the case. \$\endgroup\$
    – lirtosiast
    Nov 26, 2018 at 20:53

5 Answers 5

Reset to default
6
\$\begingroup\$

(262)-2

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

Where (42) = 2222

f20(0), where f(x):=(4x+2-4)/3

++++[->+++++<]>[->+[->+[->++<]>[-<++>]<<]<[->+<]>]
Improve this answer
\$\endgroup\$
8
  • \$\begingroup\$ It can of course be larger, but just hard to express then \$\endgroup\$
    – l4m2
    Nov 21, 2018 at 15:36
  • \$\begingroup\$ Your function appears to take 2 parameters? f<sup>n</sup>(m) What happens with the 16 in the calculation? Is this the same as (4^18 - 4) / 3 = about 23 billion? \$\endgroup\$
    – alan2here
    Nov 23, 2018 at 9:41
  • 1
    \$\begingroup\$ @alan2here That means the result is fed into the function repeatedly, e.g. f(f(f(f(... 0)))) \$\endgroup\$
    – Jo King ♦
    Nov 23, 2018 at 11:10
  • \$\begingroup\$ Thank you for the info. \$\endgroup\$
    – alan2here
    Nov 23, 2018 at 11:36
  • \$\begingroup\$ I think it's safe to assume that the 16 is generated by the 4*4 at the start of the code and credit you with a 5*4 version as well, what with the unnecessary last character, giving you best so far 49 and 50. :) \$\endgroup\$
    – alan2here
    Nov 23, 2018 at 12:32
5
\$\begingroup\$

There's been a lot posted about the top of the range (size ~ 50). But here are some high-scoring programs near the bottom:

  • Size 16: +[->++++++[-<]>] scores 100
  • Size 20: +[->++++++++++[-<]>] scores 4,212
  • Size 28: +[->++++++++++++++++++[-<]>] scores 804,576

In general, if we parameterize it so that there are N+1 +s in the middle, then this simulates the "Collatz-like" iteration:

  • $$C(2k) \to Halt(Nk)$$
  • $$C(2k+1) \to C(N(k+1))$$

Where C(m) = [0, *m*, 0 ...] (Data pointer looking at value m, at least one zero to the left, infinite 0s to the right).

It turns out that for $$N = 2^m + 1$$ this iterates exactly m+2 times (starting from C(1)) and scores

$$\frac{N}{2} (\frac{N^{m+1} - 2^{m+1}}{N - 2} + 1) \approx \frac{N^{m+1}}{2} \approx N^{\log_2(N)}$$

points using N + 12 size.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Sadly, this is just (slightly) too big to jam into l4m2's tetration machine: +[->++++++[-<]>]>[->+[->+[->++<]>[-<+>]<<]<[->+<]>] has size 51 and scores $$2\uparrow\uparrow 101 − 2$$ (If I understand correctly). \$\endgroup\$
    – sligocki
    Jul 9, 2022 at 18:15
  • 2
    \$\begingroup\$ Welcome to Code Golf, and nice answer! Always cool to see more stuff being done in BF. \$\endgroup\$
    – Rydwolf Programs
    Jul 9, 2022 at 18:35
  • \$\begingroup\$ Lol, It is also exactly to big to profit from using the alan2here's exponential mechine: +[->++++++[-<]>]>[->+[->++<]>[-<+>]<<] has size 38 and scores $$2^{101}-2$$ (IIUC). But Alan's size 38 is $$> 4 \uparrow\uparrow 3 = 2^{512}$$ \$\endgroup\$
    – sligocki
    Jul 10, 2022 at 14:28
3
\$\begingroup\$

total: (≈ & >) 172

more detail:

length: 0 to 12
see question
total: 78

length: 13 to 24
N × N
(N + 1) × N
16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90

++++[->++++<]
+++++[->++++<]
+++++[->+++++<]
Pattern Continues
+++++++++[->++++++++<]
+++++++++[->+++++++++<]
++++++++++[->+++++++++<]

total: 581

total so far: 659

each yeild: fn(0) | f(x) = x × m + 1

length: 25
(m, n) = (5, 4)
156
>+>+>+>+<[>[-<+++++>]<<]>

length: 26
(m, n) = (4, 5)
341
>+>+>+>+>+<[>[-<++++>]<<]>

total: 497

total so far: 1156

each yeild: fr or (r × s)(0) | f(x) = (x + 1) × (p × q)

length: 27
(p, q, r) = (2, 2, 5)
1364
+++++[->+[->++<]>[-<++>]<<]

length: 28
(p, q, r) = (2, 2, 6)
5460
++++++[->+[->++<]>[-<++>]<<]

length: 29
(p, q, r) = (2, 2, 7)
21,844
+++++++[->+[->++<]>[-<++>]<<]

length: 30
(p, q, r) = (2, 2, 8)
87,380
++++++++[->+[->++<]>[-<++>]<<]

total: 116,048

total so far: 117,204

length: 37
(p, q, r, s) = (2, 3, 4, 4)
(≈ & >) (6 ^ 16 = 1,721,598,279,680)
++++[->++++<]>
[->+[->+++<]>[-<++>]<<]

total: (≈ & >) 1,721,598,279,680

total so far: (≈ & >) 1,721,598,396,884

Based a design by l4m2

each yeild: fn(0) | f(x) = (4x + 2 - 4) / 3

length: 38
n = 4
+++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 39
n = 4
++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 40
n = 5
+++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 41
n = 6
++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 42
n = 7
+++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 43
n = 8
++++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 44
n = 9
+++++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 45
n = 10
++++++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 46
n = 11
+++++++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 47
n = 12
++++++++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

Based a design by l4m2
length: 48
++++[->++++<]>[->+[->+[->++<]>[-<+>]<<]<[->+<]>]

total: <sup>17</sup>2 - 2

Honorary Mention
(3 × 3) ^ 4
>+<++++[->[->+++<]>[-<+++>]<<]
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Revision!

Even bigger numbers now!

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

Result: 1.1684220603446423e+69 or 116842206034464220000000000000000000000000000000000000000000000000000 (At least that's what the compiler says)

How?

How this works is that repeats the assignment v=v(4*3)^v 8 times(At least that's what I intended it to do.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Testing this the function looks as if it grows impressively, what function is it? Maybe you can win at one of the other sizes. \$\endgroup\$
    – alan2here
    Nov 29, 2018 at 18:36
1
\$\begingroup\$

Just found a more powerful family of programs in the 16-33 size range. These are programs that look like ++[>+++++[-<]>>] (M+1 +s at start and N+1 +s in middle).

Here are all the ones that beat existing champions (IIUC).

Size 16 / Params M= 1 N= 4 / Score =                  176 / ++[>+++++[-<]>>]
Size 17 / Params M= 1 N= 5 / Score =                3,175 / ++[>++++++[-<]>>]
Size 21 / Params M= 2 N= 8 / Score =                6,234 / +++[>+++++++++[-<]>>]
Size 22 / Params M= 2 N= 9 / Score =               90,963 / +++[>++++++++++[-<]>>]
Size 23 / Params M= 2 N=10 / Score =            7,467,842 / +++[>+++++++++++[-<]>>]
Size 24 / Params M= 2 N=11 / Score =          239,071,921 / +++[>++++++++++++[-<]>>]
Size 30 / Params M= 3 N=16 / Score =          380,034,304 / ++++[>+++++++++++++++++[-<]>>]
Size 31 / Params M= 3 N=17 / Score =       30,842,648,752 / ++++[>++++++++++++++++++[-<]>>]
Size 32 / Params M= 3 N=18 / Score =   39,888,814,654,548 / ++++[>+++++++++++++++++++[-<]>>]
Size 33 / Params M= 3 N=19 / Score =  220,283,786,963,581 / ++++[>++++++++++++++++++++[-<]>>]

Note: These programs all go one spot to left of the starting memory location ... if you want to disallow that, you'll need to prepend them with >.

This program follows the recurrence:

Start -> [M, N*]
[b+k,  b*]  -> Halt(max(Nb, k))
[a,   a+k+1*] -> [k, N(a+1)*]

In other words: if the register to the left has an equal or larger value, it will halt. If current register has greater value, iterate like the second line. All of these recurrences seem to eventually halt, but I don't have any deeper insight yet ...

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I think I'm still inching ahead of you at size 37 :) \$\endgroup\$
    – alan2here
    Jul 12, 2022 at 20:41
  • \$\begingroup\$ Sorry @alan2here, I think your size 37 (&36) program needs a > between the first and second line, right? \$\endgroup\$
    – sligocki
    Jul 13, 2022 at 1:08
  • 1
    \$\begingroup\$ Thanks, let this be a lesson in the importance of documentation because I cannot quite figure it out, but it'd do noting without the extra ">" and it seems to make a lot of sense so I've corrected my answer and the main scoreboard accordingly. The two of you now draw as grand masters of this challenge. :) \$\endgroup\$
    – alan2here
    Jul 14, 2022 at 10:57

Your Answer

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

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