Easy algorithms to produce big numbers

[Loren Booda]

How can a novice simply generate a large number > 10¹⁰ in a few steps?

 

[dodo]

By writing down a '1', followed by nine '0's, followed by a '1' ?

Not sure of what you really want, though.

 

[Loren Booda]

By writing down a '1', followed by nine '0's, followed by a '1' ?

Not sure of what you really want, though.

There are simple means of generating a series which, by the third step say, creates a huge number, on the order of greater than 10¹⁰⁰. In other words, how are the significant, very big numbers created, other than pasting together some smaller numbers?

I recall one of the best such algorithms was created by a Turing-like machine. Within three steps it easily reached over 10¹⁰⁰.

 

[Xitami]

9^9^9 has 369'693'100 decimal digits

 

[dodo]

It's probably not a coincidence that string-processing machines are able to make exponentially bigger numbers; adding a digit to a string is like incrementing its order of magnitude on each step... which is like adding one to its logarithm, thus multiplying by a constant on each step... thus exponentiation. (... Now imagine a machine doubling the number of digits on each step.)

 

[SteveL27]

How can a novice simply generate a large number > 10¹⁰ in a few steps?

f(x) = 10¹⁰ + 1

That's how you would do it mathematically. You have a function that outputs a number that's literally greater than 10¹⁰ for any input.

Can you explain what you mean by "generate?" For example if you are using a computer, you would perhaps first install a bignum package -- specialized software to handle arbitrary-sized numbers. Then you could just write a loop to count up to your large number by 1; or you could just take your large number and store it in memory.

It's not clear to me what else you might be asking.

 

[SteveL27]

I recall one of the best such algorithms was created by a Turing-like machine. Within three steps it easily reached over 10¹⁰⁰.

As I indicated, f(x) = 10¹⁰⁰ does it in one step.

But perhaps you are thinking of the Busy Beaver function. or the Ackermann function.

http://en.wikipedia.org/wiki/Busy_beaver

http://en.wikipedia.org/wiki/Ackermann_function

Those are functions used in computer science that grow very quickly. Ah you must be talking about functions that GROW very quickly, not just functions that output large numbers. Got it!

You see, f(x) = 10¹⁰⁰ doesn't grow at all. So it's big, but it doesn't get any bigger.

Check out the Wiki links above, I think that's what you're talking about.

 

[Loren Booda]

You got it! Noncomputable growth. Busy beaver.

Thanks SteveL27.

 

[checkitagain]

googleplex^{googleplex^{...}}, where there are a googleplex

number of tiers is something I was thinking of recently.

 

[Loren Booda]

Does this make sense:

What is the most "efficient" algorithm for generating a largest possible (computable) number?

 

[jedishrfu]

In math, there's some large number generators like knuth's arrows, bowers operators, Graham's numbers and friedmans TREE sequence. Each of these is dwarfed by the one following for generating large numbers.

 

[Deveno]

oh my goodness TREE(3) is huge!

 

[Imaginer1]

There's an interesting sequence that creates tons of large numbers before reaching zero:

-Take an arbitrary number N and express it in base-2 hereditary notation (that all coefficients are less than or equal to 2, eg 35= 2⁵+2¹+1 however the exponent 5 is greater than 2, we will express that part as 2²+1 giving instead 2²²⁺¹+2¹+1)

-Then take all 2's and replace them with 3's and subtract 1 from the result, expressing this in base-3 hereditary notation
-Then take all Ns and replace them with N+1s and subtract 1, expressing them in base-N+1 hereditary notation (3 to 4, 4 to 5, 5 to 6...)

Eventually you'll reach one but you'll hit enormous numbers on the way.