Wikipedia:Reference desk/Archives/Mathematics/2009 December 12

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 12

Is This Problem Intractable?

I'm back with another question related to the ones I've mentioned lately. I'll be brief, but not assume the reader has been following what I've said. The specific question I have involves a tree search in number theory. I doubt my own ability to resolve the question, which is whether my computer is ever going to cease the search it's doing right now.

The question is one that I mentioned, the base-ten question, except that I thought I'd start with the first interesting base for the question, which turns out to be base nine. So, the problem is to find the largest number all of whose rightmost segments (including itself) are composite and relatively prime to each other. What we have in base nine is a choice of two final digits--4 & 8--an odd digit preceding it that generates a composite number, and then a string of digits of some fairly large length chosen from the even digits. The constraint that the numbers not be prime creates some uniformity for the problem and cuts down the tree significantly in the final digits, but doesn't affect the higher order digits very much. Every terminal node in the tree is more likely for the larger numbers to be final on account of small prime factors arising for all four choices of digit. There are really effectively only three digits available in any branch where a number divisible by 5 has cropped up, and for every small prime that shows up, there is a significant factor reduction in the size of the part of the tree emanating from it. One can be reasonably certain that there is a finite number to be found, but at present I have no clue how long a computer running optimally will take in finding it (another hour, two days, five months, or 10^87 times the age of the Universe). Would someone mind taking a look at whether I should shut this down?Julzes (talk) 06:26, 12 December 2009 (UTC)

I've concluded that I don't actually need help on this after all. A simple modification of the program is to count the number of numbers of each length up to a reasonable point and then I can rely on some empirical analysis to get the length of time I can expect this to take. One thing I have noticed is that there is significant slowing due to primality testing. Only actual primes don't have to be checked for relative primality, so numbers with only large prime factors are taking a double hit in terms of time. What this may mean is that the problem without the restriction to composites may actually be as tractable or more so than the original, so I'll have to investigate both. The problem skirts the boundaries of tractability also, so the question may have a different outcome for different bases. A lot to work on, but I should be able to get my own answers.Julzes (talk) 00:21, 13 December 2009 (UTC)

I've definitely settled the question of whether the problem allowing primes is tractable--it certainly is not. While not having to check primality dramatically speeds things up, in the smaller to moderate size numbers, the fact that a number is relatively prime to all of its predecessors so often means the number is prime; and by the time the ratio between successive counts of how many numbers fill the conditions is relatively close between the two cases, the size of the tree with primes allowed is certain to be many, many orders of magnitude larger than in the case without primes. Already at twelve digits, with primes allowed, just counting the number takes ten minutes. That amount of time for counting, even with all of the slow primality testing, gets the other smaller tree up around thirty digits. One thing has crossed my mind in the interest of getting a final result, and that is that the primality testing need only be done up to a certain depth until candidate final values are presented. Cutting out all the time spent on numbers that only have large prime factors and aren't part of candidate numbers for the final result is bound, though more complicated to implement, to be the most efficient route. Once candidate numbers are complete is the time for primality testing.Julzes (talk) 07:28, 13 December 2009 (UTC)

Since my last post here I have done all that is possible with the smaller bases vis a vis allowing primes. Base 2 is trivial: 111₂=7. Base 3 gives nine terminal nodes and a value of 18709 in base ten. Base 4 has 10608 terminal nodes and gives a 44-digit base-ten number. Base 5 has 490 terminal nodes, with evaluation 7444858551025390541 in base ten. Base six is intractable with values exceeding 10¹⁵⁰⁰; and base seven is the last solvable case, with 99 base-ten digits for the solution and 29735375 maximal numbers.Julzes (talk) 05:38, 14 December 2009 (UTC)

Expectation

Resolved

If E(X) = E(X²) = 1 then what may be concluded about E(X¹⁰⁰)?. Thanks-Shahab (talk) 09:48, 12 December 2009 (UTC)

Recall the Cauchy-Schwarz inequality: E(XY)² ≤ E(X² ) E(Y²) , with equality if and only if X and Y are linearly dependent. Take Y=1.... --pma (talk) 11:11, 12 December 2009 (UTC)

Also consider: what is the variance of X ? What does that tell you about it probability distribution ? Abecedare (talk) 12:03, 12 December 2009 (UTC)

Variance is zero and so the distribution is degenerate at 1. Hence the E(X¹⁰⁰) = 1. Thanks.-Shahab (talk) 12:42, 12 December 2009 (UTC)

Convergence of the boundary for this series

Hi all,

how would I go about investigating the convergence of the series $\sum ^{\infty }{\frac {n!}{n^{n}}}z^{n},z\in \mathbb {C}$ on the boundary of the R.O.C? I calculated the R.O.C as e, so on the boundary |z|=e, we could write z as $e^{i\theta +1}$, but that doesn't really help me.

Suggestions?

Many thanks, 86.26.6.36 (talk) 16:08, 12 December 2009 (UTC)

If, as you say, z is an element of the real numbers, there are exactly two points on the boundary of the region of convergence, z=±e. (I haven't verified your solution that |z| = e, but I'm trusting you here...) In this case, the solution is trivially checked with just two cases. Are you sure that you don't mean to say z is a complex number? Nimur (talk) 16:51, 12 December 2009 (UTC)

Yes sorry, I do of course mean $\mathbb {C}$, it seems my brain's not working today (changed now)! So yes sorry, for |z|=e in the complex plane, what's the best way to approach the problem? Thanks, 86.26.6.36 (talk) 17:18, 12 December 2009 (UTC)

Use $t=z/e$ and Abel's test to show this converges for every $z\neq e,|z|=e$. For $z=e$, this diverges by the limit comparison test (and Stirling's approximation, of course). -- Meni Rosenfeld (talk) 19:26, 12 December 2009 (UTC)

STEP papers

Hi, I would be very very grateful if anyone can tell me how I might get past STEP papers and their mark schemes... the more the better! Desperately need them! Thanks LOADS!!! :) —Preceding unsigned comment added by 121.202.252.24 (talk) 16:12, 12 December 2009 (UTC)

Why did you post this twice? --COVIZAPIBETEFOKY (talk) 18:26, 12 December 2009 (UTC)

[1] may be what you are looking for. Sussexonian (talk) 20:00, 12 December 2009 (UTC)

re: COVIZAPIBETEFOKY: sorry about that, it wasn't intentional, i guess i pressed the button twice...

re: Sussexonian: Thanks loads!!! :) —Preceding unsigned comment added by 121.202.253.190 (talk) 06:45, 13 December 2009 (UTC)

A very simple question

How do I solve 2^x - x =2 for x. I know the solution (at least one of them) is x = 2. But how do I arrive at it through the general process?--71.91.58.62 (talk) 19:13, 12 December 2009 (UTC)

This equation is harder than it may appear. To solve it you need some familiarity with the Lambert W function - you'll find that the substitution $u=(x+2)\ln 2\;\!$ solves it. The other real solution is -1.69009..., and there are infinitely many complex solutions. -- Meni Rosenfeld (talk) 19:39, 12 December 2009 (UTC)

Yes. I also got that from the software but I want the process to reach the real solution.--71.91.58.62 (talk) 20:17, 12 December 2009 (UTC)

Staring at the graph it's instantly obvious that one solution is 2, and another is between −1 and −2. Reasonable numerical methods like Newton's method should approximate the negative solution quite well after a few steps, but if you want a closed form, that's more problematic. Simple algebra alone won't do it, but notice that you've got x in an exponent in one term and as a base in another term. When that happens, it seems algebra often reduces it to something expressible in terms of Lambert's W. Whether you consider that closed form is probably not worth arguing about for most purposes. Michael Hardy (talk) 22:52, 12 December 2009 (UTC)