I guess this is more permutations and computations then.
I understand how to calculate it if the social networks are constant and non-overlapping (like, everybody knows 20 people and none of those people know each other). But if the social networks overlapped, and/or if their sizes weren't uniform, can you show a couple of calculations for the Degrees of Separation?
Incidentally, I have no idea if the concept is true, or an urban myth; I'm just interested in the math behind it.
Well if you've already been able to determine the social network (which is an empirically difficult problem)
Oh no, I didn't mean that; I meant that I just knew something about the social network, like that it was a normal distribution with a known mean and standard deviation.
This one should be easy:
Prove that there exist real numbers with an infinite kolmogorov complexity.
In other words, that there exist real numbers which can not be printed out by a program of finite size (even if we assume an infinite amount of available memory) by any possible mean.
The set of programs of finite size is countable. Hence, the set of computable numbers is countable. Since the set of real numbers is uncountable, it follows that the set of uncomputable numbers is uncountable. In other words, uncomputable numbers exist.
The set of computable numbers is countable
All computable numbers are real numbers
The real numbers are uncountable
The countable real numbers are a strict subset of the uncountable real numbers
Therefore the computable numbers are a strict subset of the real numbers. That is, there is at least one number in the real numbers that is not in the computable numbers.
Therefore not all numbers are computable.
This is just a rephrasing of FractalFusion's approach. I'd be more worried about "Hence, the set of computable numbers is countable."
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
To expand on what Derakon was saying:
Countable subsets of uncountable sets are always strict subsets. An uncountable set minus a countable subset is always uncountable (since by reverse, the union of two countable sets is countable).
Also, a subset of a countable subset is countable.
I took "computable numbers" and "real numbers which can be printed out by a program of finite size" to mean the same thing. I wouldn't think otherwise.
Assume the following game:
You toss a coin, and if you get heads, you win 1 dollar and the game ends, else the game continues with another toss. If you get heads on the second throw, you get 2 dollars, and the game ends, else it continues. If you get heads on the third throw, you get 4 dollars. In general, if you get heads on the nth throw, you get 2^(n-1) dollars.
How many dollars are won in this game, in average?
(If the possibility of a game continuing to infinity presents a problem, then the maximum number of throws can be limited to a very large number, such as eg. 10^1000, after which you win nothing. Of course the probability of this happening is so vanishingly small that it shouldn't affect the answer in practice.)
This is just a summation of an infinite series: .5*1 + .25*2 + .125*4 + .0625*8...
Each term is the probability of getting heads on that throw (which is just 1/2^n) times the value of getting heads on that throw (2^(n-1)).
2^(n-1)) / (2^n) = 1 / (2^1) = .5
The exponents cancel out, so each term has a value of .5. That means the series does not converge, so the average expected return is infinite (or .5 * 10^1000 given your backup rule).
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Yet if you simulate this with a program which plays the game billions of times and averages the wins, you get something around 16 dollars in average. Why would that be?
Maybe because the program uses a PRNG instead of a true RNG. Some quick testing revealed that, of 1,000,000,000 games played, the maximum number of tails in a row was 32. So by Derakon's reasoning, 0.5 * 32 = 16.
More results:
$ ./cointoss 100000000
average value: 15.435800
average tosses: 1.999994
largest tosses: 29.000000
$ ./cointoss 1000000000
average value: 16.371762
average tosses: 1.999988
largest tosses: 32.000000
Currently working on:
SNES Star Fox, Level 3 (100%, published)
SNES Star Fox, Level 2 (33%, after Sector X)
SNES Star Fox 2, Expert mode (100%, published)
Maybe because the program uses a PRNG instead of a true RNG.
It has nothing to do with a PRNG vs. a true RNG. Even if a true RNG was used, it would, for all intents and purposes, give the same result.
The real reason is because, given the number of games that are done, at some point, the probability of getting a streak of m tails or more is so small that it can be considered non-existent. Then, for the games played, the expected value is .5*1+.25*2+.125*4+...+ 2^(-1-(m-1)) * 2^(m-1) = .5 * (m-1).
For 10^9, the expected longest streak is around log2(10^9) ~ 30 (which verifies the result from YtterbiJum).
The important thing is that repeated tests will not cause the mean to statistically converge; in fact it will diverge to infinity.
This is a math problem I actually need help for TASing...
X is the current value of the RNG, a 16 bit unsigned integer. C is the value of the controller input, and can range from 1 to 255, and must be odd.
X = Remainder((X+C)*13 + 7)/2^16) is the next value of the RNG.
Y is the target value for N executions.
So, the question is, How do you get Y in a minimal N executions and solve for C1, C2, C3....
How can you mathematically solve for Cs? I've been using for loops for guess and check... but it ends up computationally complex, for something that should be easy to solve mathematically...
Sage advice from a friend of Jim: So put your tinfoil hat back in the closet, open your eyes to the truth, and realize that the government is in fact causing austismal cancer with it's 9/11 fluoride vaccinations of your water supply.
I'm fairly sure I answered this in IRC sometime last year. The important thing to note is that the integers modulo 65536 form a ring. As a result, the value of X after two iterations is (X*169 + C1*169 + C2*13 + 98) mod 65536, and so forth.
If the only constraint on C is that it must be odd and in the specified range, then it is fairly simple to determine the range of possible X values after any number of iterations (after dividing by 13 / multiplying by 20165 to make the possible transformed X values a contiguous range). It turns out that any number with the same parity as the original X can be reached within 4 iterations, and any number with the opposite parity can never be reached if C is always odd.
I remember you tried to convince me it was mathematically possible, but due to the modulus, I didn't believe you.
I'm still confused how you solve Y = mod(X/65536). Or, is what you are saying that you determine all values of Y given X and the range of C1/C2/C3/C4?
Sage advice from a friend of Jim: So put your tinfoil hat back in the closet, open your eyes to the truth, and realize that the government is in fact causing austismal cancer with it's 9/11 fluoride vaccinations of your water supply.
I remember you tried to convince me it was mathematically possible, but due to the modulus, I didn't believe you.
I'm still confused how you solve Y = mod(X/65536). Or, is what you are saying that you determine all values of Y given X and the range of C1/C2/C3/C4?
Sage advice from a friend of Jim: So put your tinfoil hat back in the closet, open your eyes to the truth, and realize that the government is in fact causing austismal cancer with it's 9/11 fluoride vaccinations of your water supply.
Since this thread has been silent for a long time, here's a small problem to warm you up a bit again:
Prove that the factorization of any natural number is unique (except for a possible reordering of the factors).
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Warp wrote:
Since this thread has been silent for a long time, here's a small problem to warm you up a bit again:
Prove that the factorization of any natural number is unique (except for a possible reordering of the factors).
I assume you mean prime factorization, otherwise it's not unique, because 12=3*4 and 12=2*2*3.
I'm gonna give this a try: Let's call the number x. Assume that x has two different prime factorizations, namely:
x = a(1)*a(2)*...*a(k) (1)
x = b(1)*b(2)*...*b(n) (2)
Now, because both of these a representations of x, we can set:
a(1)*a(2)*...*a(k) = b(1)*b(2)*...*b(n)
Because a(1) is a factor of x according to (1), we can divide by a(1), while still having having integers on both sides. a(1) disappears from the LHS, and because the LHS is an integer, the RHS has to have a(1) as a factor too, otherwise it wouldn't be an integer, giving us a contradiction. Lets call the factor in the RHS that was equal to a(1) for b(i).
a(2)*...*a(k) = b(1)*b(2)*...*b(i-1)*b(i+1)*...*b(n)
Because a(2) is a factor of the LHS, we can divide by a(2) while still having an integer in the LHS. Because the LHS is an integer, a(2) has to be a factor of the RHS. Continuing this way, after having divided with all the factors of the LHS, we have divided with all the factors of the right hand side too (because we are left with 1 in the RHS), showing that the prime factors in the RHS of eq. (1) and (2) are in fact the same.
EDIT: Here's a problem for you: Let's assume you have a sequence of numbers satisfying a(k+1) = (5*a(k)+5)mod256, with a(0)=0. As it turns out, if you look at all the numbers a(0), a(1), a(2), ..., a(255), they take every value between 0 and 255 exactly once. Why is this? If you have the sequence a(k+1) = (c*a(k) + b)mod256, a(0)=d, for what values of b,c and d does this property hold? (I don't know the answer to this, but I'd really like to know)
EDIT: Here's a problem for you: Let's assume you have a sequence of numbers satisfying a(k+1) = (5*a(k)+5)mod256, with a(0)=0. As it turns out, if you look at all the numbers a(0), a(1), a(2), ..., a(255), they take every value between 0 and 255 exactly once. Why is this? If you have the sequence a(k+1) = (c*a(k) + b)mod256, a(0)=d, for what values of b,c and d does this property hold? (I don't know the answer to this, but I'd really like to know)
I didn't know the answer myself either, but since you need this information, I made a bit of research to find out. I recognize that formula to be a linear congruential generator, and the wikipedia article kindly tells us exactly when a LCG has maximal period (which is what you are looking for).
Let m be your modulo, ie. in this case 256. The period will be maximal if and only if:
1) b and m are relatively prime,
2) c - 1 is divisible by all prime factors of m,
3) c - 1 is a multiple of 4 if m is a multiple of 4.
