As long as we're having fun with x^x, lets shed our dependence on positive real numbers. For complex z=x+i*y, find a closed form expression for z^z that has no complex exponents except of the form e^(i*a), where a is real.
z^z=e^((x+i*y)ln(x+i*y)).
ln(x+i*y)=ln(x²+y²)/2+i*tan⁻¹(y/x)+2nπi where n∈ℤ.
(x+i*y)ln(x+i*y)=x*ln(x²+y²)/2-y*tan⁻¹(y/x)-2nπy+i*(y*ln(x^2+y^2)/2+x*tan⁻¹(y/x)+2nπx).
Therefore, z^z=|z|^ℜ(z)*e^-(ℑ(z)arg(z))*e^(i*(ℑ(z)ln|z|+ℜ(z)arg(z))).
By the way, |z|=√(x²+y²), ℜ(z)=x, ℑ(z)=y, and arg(z)=tan⁻¹(y/x)+2nπ where n∈ℤ, with the principal value (n=0) as Arg(z)=tan⁻¹(y/x); it would be interesting to see where z^z is analytic, if anywhere.
On another note, Unicode is the greatest invention since sliced bread.
Exact form requires solving the transcendental equation 2^x=2+1/x, which I don't feel like doing, and suspect isn't possible anyways.
You forgot the word "algebraically" before "possible".
Well, yes. The fact that I solved it numerically immediately before saying that meant that that should have been implied.
Anyways, nice jobs, even remembered the branch cuts. Not sure about analyticity, but it's something to look into. In the meantime, here's another question.
Does |z^z| go to infinity as |z| goes to infinity in all directions (like x^a), or does it go to a finite or zero value for some direction (like a^x)? Shouldn't be too hard now that we have closed form expressions, but still an interesting question.
Exact form requires solving the transcendental equation 2^x=2+1/x, which I don't feel like doing, and suspect isn't possible anyways.
You forgot the word "algebraically" before "possible".
Well, yes. The fact that I solved it numerically immediately before saying that meant that that should have been implied.
Anyways, nice jobs, even remembered the branch cuts. Not sure about analyticity, but it's something to look into. In the meantime, here's another question.
Does |z^z| go to infinity as |z| goes to infinity in all directions (like x^a), or does it go to a finite or zero value for some direction (like a^x)? Shouldn't be too hard now that we have closed form expressions, but still an interesting question.
From my polar-coordinate expression for z^z, |z^z|=|z|^ℜ(z)/e^(ℑ(z)arg(z)).
Let z<0 and z→-∞, then z^z=(-z)^z*e^iπz and |z^z|=|z|^z=e^(z*ln|z|); in fact, z^z for z<0 spirals around the origin at a constant angular rate, and |z|^z at first glance looks like a very smooth function on ℝ.
Now, as in the proof that lim(z→0)z^z=1, use L'Hôpital's Rule to determine that lim(z→-∞)ln(-z)/(1/z)=lim(z→-∞)(-1/z)/(-1/z²)=lim(z→-∞)z=-∞, so lim(z→-∞)z^z=0.
Of course, it's obvious that z^z→+∞ as 0<z→∞ (an ever-larger base raised to an ever-larger exponent, or more analytically, the derivative is strictly positive for z>1/e), but now let's see what happens if ℜ(z)=0 and y=ℑ(z)≠0; then |z^z|=e^-(π|y|/2) on the principal branches, but in general |z^z|=e^-((2n+1/2)π|y|) where n∈ℤ. I should mention that this view of z^z is sufficient to show that it is not analytic at 0 and that if it has a limit at 0 its value must be 1; also it is obvious here that if z is pure imaginary and |z|→∞ then z^z→∞ for those branches with n<0 and z^z→0 otherwise. In either case z^z spirals ever faster as it becomes infinite or approaches 0, because arg(z^z)=y*ln|y|.
(This is an abuse of notation, because the branches with y<0 and y>0 for a given n are the same only when n=0; generally the branch with y>0 for a given n is also the branch with y<0 for -n.)
What if, more generally, Arg(z)=k, a constant? Then if r=|z|, |z^z|=r^(r*cos(k))*e^-((k+2nπ)r*sin(k)) and arg(z^z)=r*ln(r)sin(k)+(k+2nπ)r*cos(k) where n∈ℤ. The behavior of z^z as r→∞ then depends on ln|z^z|=r*ln(r)cos(k)-(k+2nπ)r*sin(k); the derivative is ln(r)cos(k)+cos(k)-(k+2nπ)sin(k), and in the previous special cases, k=π and this derivative is -1-ln(r)<0 for r>1/e, k=0 and this derivative is 1+ln(r)>0 for r>1/e, and k=±π/2 and the derivative is 2nπ+π/2<0 for n<0 and positive otherwise. In general, that derivative is positive for ln(r)>(k+2nπ)tan(k)-1 if |k|<π/2 and negative for such r if |k|>π/2, and as long as k≠±π/2 there will be a sufficiently large r for each n beyond which this derivative is always positive or always negative, respectively, so ln|z^z| approaches +∞ in the former case and -∞ in the latter.
Therefore, if Arg(z) is constant and |z|→∞, then z^z→0 if |Arg(z)|>π/2 (negative imaginary part), z^z→∞ if |Arg(z)|<π/2 (positive imaginary part), and either case is possible if Arg(z)=±π/2 (pure imaginary), depending on the branch chosen.
Of course, unless z>0, z^z spirals out to infinity or inward to 0; the derivative of arg(z^z) is ln(r)sin(k)+sin(k)+(k+2nπ)cos(k) where n∈ℤ. Once again, in the special cases I mentioned at the beginning, k=π and z^z spirals toward 0 at a constant angular rate dependent only on the branch, k=0 and z^z stays on the positive real axis, and k=±π/2 and z^z spirals faster and faster toward infinity or 0 depending on the branch, but the angular rate does not depend on the branch chosen.
Therefore, except for the special cases in which k=0 or k=π, the angular rate is either always increasing or always decreasing for sufficiently large r on any branch, so for imaginary z, z^z spirals faster and faster toward the origin or infinity as z→+∞ with constant argument.
Somehow I suspect that there exists a spiraling path toward infinity in the complex plane along which z^z approaches a finite nonzero value, and furthermore that such a path exists for any c∈ℂ; even more exciting would be to extend that to the extended complex plane, finding a path toward infinity along which z^z approaches any directed infinity, not just +∞.
Here's a problem. Find the last 10 digits of the following number:
It's easier than it looks.
I guessed the answer is 0. A little Python computation tells me I'm right. I don't have the appropriate math skills to tell you why, though.
EDIT: And, of course, I'm wrong. After fixing a bug, every inner part with n >= 1 gives the last ten digits as "0000000000". With n = 0, the inner part is 19. So the answer is "0000000019".
Alright, I'll give this a go. I'll call the inner part (with capital PI) "a_n".
Observe:
* a_0 is 19.
* a_1 is 1642188240000000000, or 164218824 * 10^10.
* For all n > 1, a_n has a factor of a_1, and thus a factor of 10^10.
Therefore, the only number in the sum that contributes to the last ten digits of the total is a_0, which is 19.
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)
Here's a problem. Find the last 10 digits of the following number:
It's easier than it looks.
I guessed the answer is 0. A little Python computation tells me I'm right. I don't have the appropriate math skills to tell you why, though.
I guess you need to find K, the first value of k for which the product of that expression from 3 to K has 10^10 as a factor; then show that the sum of those products for n between 0 and (K-3)/4 is also divisible by 10^10.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Topic revival! Here's a fun problem I thought of today:
Given 4 strictly positive integers a1,a2,a3 and a4 that satisfy a1<=a2<=a3<=a4, how many solutions are there for the equation a1+a2+a3+a4=x for an arbitrary positive integer x>=4? For example, with x=13, one solution is 1+1+2+9, and another is 1+2+3+7. Provide your answer as a function of x, and simplify f(x) as much as possible. You'll probably need to construct some helper-functions to simplify it as much as possible.
I solved this earlier today, and I found it pretty tricky to figure out. Perhaps it's not very hard at all, and it's just me who's making the problem harder than it is. Anyway, have fun! :)
This sounds like a job for the partition function!
Okay, so based on some results shown in that article, the number of partitions of x into exactly 4 parts is the same as the number of partitions of x-4 into no more than 4 parts, which is the same as the number of partitions of x-4 into parts no larger than 4.
The maximum number of parts equal to 4 is floor(x/4-1), and the number of partitions of x-4 into parts no larger than 4, with as many parts equal to 4 as possible, is x-4-4floor(x/4-1) unless x-4≡0 mod 4 in which case it is 1 (because 3=1+2=1+1+1, 2=1+1, and 1 and 0 are alone).
Then you can convert each part equal to 4 into a collection of lesser parts, down to the least collection that the previous one was converted to. Then after that there is a recursive decision tree to enumerate involving deciding among 4=1+3=2+2=1+1+2=1+1+1+1.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
That's not what I had in mind, but you seem to be right. :) However, it's possible to construct f(x) as an explicit function of x, or to be more accurate, a polynomial of degree 3, involving 3 parameters that in turn depend on x. So the function should look something like f(x) = g(p(x), q(x), r(x)), where p,q and r are functions of x, and f is, as before, the number of solutions.
EDIT: Hmm... I just noticed a flaw in my solution, so I'll have to revise it. So, umm, perhaps you can scratch my idea. :P I'll look into this some more, hopefully it's just a minor flaw.
EDIT2: Okay, scratch that part about polynomial solution. It is however possible to give an explicit solution f(x) to this problem, but it can't be simplified much, at least not that I can see.
This is an easy one, but got me puzzled for a while when I encountered it in something I was coding.
Assume you have an array of 24 integers. Each element of that array can get a value between 0 and 7. Thus the total amount of different contents for such as an array is
8^24 ~ 4*10^21
Now assume that you fill the array with some values and then calculate all the possible permutations of that array. The amount of permutations for 24 elements is:
24! ~ 6*10^23
Now here's the apparent paradox: The total amount of different contents is about 4*10^21, and naturally all those permutations should be among them as well. How come the total amount of permutations, 6*10^23, is way larger than the total amount of possible different array contents?
As a generalization of the situation, suppose you have an array of n elements, and each element can have a range of values between 0 and (m-1) (in other words, the total amount of possible array contents is m^n). Also suppose you fill it with consecutive values starting from 0, mod m (ie. each time you put the value (m-1) you start over from 0, etc).
How many unique permutations does the array have?
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
I don't know if anyone's still working on the problem I posted, but here's the solution if anyone's interested. :) (square brackets mean the floor function) This formula can easily be generalized for a sum of n variables.
There's a generating function solution.
According to arflech,
arflech wrote:
Okay, so based on some results shown in that article, the number of partitions of x into exactly 4 parts is the same as the number of partitions of x-4 into no more than 4 parts, which is the same as the number of partitions of x-4 into parts no larger than 4.
Let f(x) be the function which is the solution to the problem you described. So the generating function solution is:
Randil wrote:
Given 4 strictly positive integers a1,a2,a3 and a4 that satisfy a1<=a2<=a3<=a4, how many solutions are there for the equation a1+a2+a3+a4=x for an arbitrary positive integer x>=4?
I know you didn't mean it, but the way you worded it, the answer is always 1. Because, given positive a1, a2, a3, a4, there is exactly one x>=4 such that a1+a2+a3+a4=x.
What you meant is:
Randil wrote:
Given an arbitrary positive integer x>=4, how many solutions are there for the equation a1+a2+a3+a4=x for 4 strictly positive integers a1,a2,a3 and a4 that satisfy a1<=a2<=a3<=a4?
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
FractalFusion wrote:
Randil wrote:
Given 4 strictly positive integers a1,a2,a3 and a4 that satisfy a1<=a2<=a3<=a4, how many solutions are there for the equation a1+a2+a3+a4=x for an arbitrary positive integer x>=4?
I know you didn't mean it, but the way you worded it, the answer is always 1. Because, given positive a1, a2, a3, a4, there is exactly one x>=4 such that a1+a2+a3+a4=x.
What you meant is:
Randil wrote:
Given an arbitrary positive integer x>=4, how many solutions are there for the equation a1+a2+a3+a4=x for 4 strictly positive integers a1,a2,a3 and a4 that satisfy a1<=a2<=a3<=a4?
Ah, yes. Those were supposed to be variables, not constants. Thanks for clearing it up.
Here's a similar problem, easier than the one above but perhaps worth mentioning for its nice, elegant solution: determine the number of solutions to a1+a2+a3+...+an<=x for all n and x are non-negative integers.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
I think the answer is this. It can probably be simplified (it's a polynomial of degree n of the variable x) but I'm having a hard time calculating a formula for the polynomial. I'll look into this some more...
Here's a similar problem, easier than the one above but perhaps worth mentioning for its nice, elegant solution: determine the number of solutions to a1+a2+a3+...+an<=x for all n and x are non-negative integers.
That should actually be for all an and x are non-negative integers but I don't think this would have cause any confusion. As none seemed to have solved it yet, I'll put up a solution lest nobody else does. The answer is (x+n)C(n) = (x+n)!/(x!n!) which simply comes from a balls and urns argument. To visualise this, we imagine x+n objects in a row and we choose n of them to become dividers which will separate the x remaining objects into n+1 groups. The first n of these groups represent the different values of an while the final group can represent any of the integers less than or equal to x. For example, if we had a1+a2+a3+a4+a5<=10, we could have the sequence O_OO__OO_OO_OOO which represents the solution 1+2+0+2+2=(10-3)<=10. Here, the final group is 3 so the other groups combined equal 7 so you can see that by varying the final group, we can have a1+a2+...+an equalling any number from 0 to x and hence we have the solution set. (solution hidden in small font)
I have a sort of mathematical question that you guys can probably answer pretty easily.
You've probably heard of Six Degrees of Separation, which says very basically that everyone on earth personally knows someone else though a maximum of six different people.
If we assume that the Six Degrees concept is correct, what happens to the number of "degrees" as the population increases? I would intuitively think that the number decreases, but I'm wondering if it stays the same, or even gets higher.
I guess this is just basic probability/statistics, but I'm not so good at these things.
Thanks in advance.
You've probably heard of Six Degrees of Separation, which says very basically that everyone on earth personally knows someone else though a maximum of six different people.
If we assume that the Six Degrees concept is correct, what happens to the number of "degrees" as the population increases? I would intuitively think that the number decreases, but I'm wondering if it stays the same, or even gets higher.
I guess this is just basic probability/statistics, but I'm not so good at these things.
Thanks in advance.
The notion that it is "six degrees" is an urban myth; also, I understand from the article that the number of "degrees" would increase, and the question requires more sophisticated mathematics than basic probability or statistics...I think it's called "network theory" but still the question hasn't even been answered in a satisfactory way.
>If we assume that the Six Degrees concept is correct, what happens to the number of "degrees" as the population increases? I would intuitively think that the number decreases, but I'm wondering if it stays the same, or even gets higher.
If we assume that the Wikipedia article is correct, the number of links needed increases as the population increases. The page poses that in a population of US size (which is, actually, smaller than the world), only 3 links are needed. That it would be the other way around sounds completely illogical to me.
You have two fundamental assumptions here about your population: a) each person in the population knows a fixed number of other people (independent of the size of the total population), and b) the degree of overlap between personal social networks is constant and not absolute. In other words, if you know 20 people, but each of those 20 people only know each other and you, then you form a closed social group that can't be reached. You're going to find such social groups in e.g. isolated villages, which renders the "whole world" thing moot.
In any event, the former assumption forces you to increase the number of degrees of separation as the population increases. Obviously when you're talking about six degrees for 300 million people, the number of degrees of separation will increase only slowly. But if you assume each person knows 20 other people, and there's zero overlap (so social networks efficiently "cover" the population), then you can get from any one person to 20^6 other people in six steps -- a very large, but finite, number. Once you hit 20^6 + 1 you absolutely must increase the number of steps.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
It's easier than it looks.
