The recent discussion reminds me of another interesting problem I saw a few years ago.
Write the largest natural number you can. Any notation is acceptable as long as:
1) It is easily understood (this is subjective and depends on your readership, but I think posters in this thread will be reasonable)
2) The representation of your number (and any function definitions, explanations, etc.) must not exceed a certain number of characters. I don't remember the character limit on the original problem, but let's make it 500 characters.
f(x)=(x^x)!
n=(f◦f◦f◦f◦f◦f◦f......f◦f◦f)(9)
Type out the finite series (f◦f◦f..f◦f◦f) as many times as can be done.
Now, the quest for optimization is at hand.
EDIT: didn't read previous posts, so an optimization would be:
f(x)=(x↑↑↑↑↑x)!!
This competition could go on forever :)
"We observe the behaviour of simple folk, and derive pleasure from their defects."
-Aristotle - Book of Humour
Joined: 4/20/2005
Posts: 2160
Location: Norrköping, Sweden
Okay, here's how this is done:
The current biggest number posted in this thread == X;
New submitted number (defined for all new submitted numbers) == Y;
My number == Z;
If(Y>X){
Y = Z;
Z++;}
This means that my number Z will always be the current biggest number +1.
If you come up with a number that is bigger than Z, then Z will change value and become bigger than that number. I win!!! :)
I shall make sure you never win!
If(Z>Y){
Y = Z;
Y++;}
Now our comps will go into a moebius loop, in which we will never know the outcome, thus rendering any competition null and void.
Since you can only know the outcome of an operation when (if) it ends, noone wins and we both win. at the same time.
My conclusion is this: Pogo sticks make legs funny.
"We observe the behaviour of simple folk, and derive pleasure from their defects."
-Aristotle - Book of Humour
Joined: 4/20/2005
Posts: 2160
Location: Norrköping, Sweden
All right, both of us winning works fine with me. :) You can really get a headache if you think about these things too hard...
Your conclusion interests me, and I wish to know more.
http://en.wikipedia.org/wiki/Halting_problem
What this means, quite basically, is;
"You can never know if a computation will finish, and, if so, what the result is, before it actually finishes."
Since the scripts we listed never will finish (one script will act on the other's input and vice versa), there is never a sitation in which Z>Y or Z<Y, because every time we ask the question "is Z>Y?", another Y (or Z) will have come out which is large than the current Y (or Z), rendering any inquiry into the numbers useless.
Thus, it is impossible to determine who wins and who loses. The outcome of such an inquiry, however, will be "you both won AND lost."
"We observe the behaviour of simple folk, and derive pleasure from their defects."
-Aristotle - Book of Humour
Joined: 4/20/2005
Posts: 2160
Location: Norrköping, Sweden
And I was sure that I'd win this with my number Z... I guess this discussion could stop now, since the discussion doesn't suit the topic anymore.
By the way, thanks for the link MahaTmA, it was pretty interesting reading.
Hmm. I think part of the problem description is that you aren't supposed to refer to previous answers. So references to "the previous largest number in the thread" and such would be no good. That was clever, though :)
I like all of your answers. This forum has some interesting and intelligent people.
Here's an interesting problem to keep them gears cranking:
14 natural numbers are written down onto a piece of paper. Whichever number is crossed, the remaining numbers can be grouped into 3 groups with the same sum.
Is there a conclusive answer as to which numbers had been written down, and if so, which are they?
"We observe the behaviour of simple folk, and derive pleasure from their defects."
-Aristotle - Book of Humour
It's interesting you should bring up the halting problem, there is a closely related problem that more or less asks, "What is the most number of 1's an n-state Turing machine can spit out before halting?" This function is usually denoted Σ(n), and Σ is an interesting function. With a few clever twists, you can show that Σ grows faster than any computable function. What this means is that for any computable function or combination of computable functions (which is essentially what you guys are trying to come up with), the value of Σ will always be greater, after a point.
The first few values of Σ are known, or have had examples constructed to give a lower boundary:
Σ(1) = 1
Σ(2) = 4
Σ(3) = 6
Σ(4) = 13
Σ(5) >= 4098
Σ(6) >= 1.29 * 10^865
Joined: 4/20/2005
Posts: 2160
Location: Norrköping, Sweden
Two questions about this function:
1. Is it defined for Σ(0)?
2. Is it only defined for integers?
I don't quite understand what this function is all about, I've read your post a few times now, but I don't know what a turing machine is =/
Perhaps you could explain the function in an easier way, if you can do that.
A turing machine is the math concept of a computer.
(this is dumbed down a lot, but I don't think you want an introduction to formal languages)
You may think of it as the archetype of a computer, every nowadays computer is in theory compatible to a turing machine.
It works by reading input from an infinite band of 1s and 0s and writing it's output back onto that band. You can program it with expressions like "If you read a 0, write a 1". You can also tell to move the read/write position left or right.
However this allows for very little complexity in programs, so you can also assign it states.
Now a full command would be:
"If you are in state A and read a 0, then write a 1 and goto state B" or
"If you are in state A and read a 1, then move left and stay in state A"
With this you can write programs and the only thing that limits the machines power is the number of states.
The Σ(n) function is now the solution to the question xebra wrote.
To answer your questions:
Since a machine without a state to be in would make no sense, Σ(0) is not defined. And since it can't have half a state it only works for integers.
Here's an interesting problem to keep them gears cranking:
14 natural numbers are written down onto a piece of paper. Whichever number is crossed, the remaining numbers can be grouped into 3 groups with the same sum.
Is there a conclusive answer as to which numbers had been written down, and if so, which are they?
Gah, just reviewed this. The numbers needn't be natural, they just need to be whole (e.g. from Z, not N. - 0 and negatives are included)
"We observe the behaviour of simple folk, and derive pleasure from their defects."
-Aristotle - Book of Humour
Here's an interesting problem to keep them gears cranking:
14 natural numbers are written down onto a piece of paper. Whichever number is crossed, the remaining numbers can be grouped into 3 groups with the same sum.
Is there a conclusive answer as to which numbers had been written down, and if so, which are they?
Gah, just reviewed this. The numbers needn't be natural, they just need to be whole (e.g. from Z, not N. - 0 and negatives are included)
Does that change anything?
Assume you cross a number. Then the sum of the rest must be dividible by 3 or otherwise you couldn't group them into three groups with equal sum. So the number you crossed must have the same remainder module 3 as the sum of all numbers [1]. Since this applies to all numbers that can be crossed, all of them have to have the same remainder mod 3.
If we stay with the "sum must be dividible by 3" view, web can throw away everything but the remainder, and only consider them.
Assume now we have 13 numbers (and one crossed out) of the same remainder, where the remainder is one of 0, 1 or 2. It's clear that 13 times the remainder 1 is 13 and therefore not devidible by 3. Same goes for remainder 2. So every number in your problem hat to be dividible by 3 itself to keep it solvable.
But now if every single one of the 14 numbers has to be dividible by 3, and we find a solution, why don't we divide all numbers by 3? The result must be a solution itself, because you can just factor out 3 out of every sum. If that solution however contains values not dividible by 3 it can not be a solution because of the reasons above, so the solution we found can't be one either. Unfortunately this applies for any solutions containing non zero numbers because they can be divided until they are not dividible by 3 anymore.
The only solution to the problem is [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ] isn't it?
[1] commonly written as n mod m = r as in 4 mod 3 = 1 or 11 mod 3 = 2
I do believe it's widely accepted that it isn't.
For instance: Natural numbers can be divisors. 0 can't, since otherwise it would be a divisor to every other natural numer, much like 1 is.
Also, it would make 1 the only prime in the world (A prime being defined as a natural number with only 2 divisors)
"We observe the behaviour of simple folk, and derive pleasure from their defects."
-Aristotle - Book of Humour
Oh it's all a matter of convenience.
If you do anything with computer unsigned values, they start with a zero.
Lazy as people are they just call those "natural" in their work, and in terms of computers it's the most natural of all numbers. Unfortunately math people see that differently... :)
