User hugo van der sanden - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T23:33:31Z http://mathoverflow.net/feeds/user/6089 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41939/a-balls-and-colours-problem/42029#42029 Answer by Hugo van der Sanden for A balls-and-colours problem Hugo van der Sanden 2010-10-13T15:31:33Z 2010-10-13T15:31:33Z <p>Consider just those sequences of selections that result in the final colour being $c$. If at some point during a sequence we have $k$ of the balls being this colour, we can define $E_k$ as the expected number of selections from here before all the balls are coloured $c$.</p> <p>Doing this, we need to take account of the fact that not all selections are equally probable: each selection must be multiplied by the probability that it results in $c$ being the eventual colour. Happily, this probability is simply <code>$k'/n$</code>, where <code>$k'$</code> is the number of balls coloured $c$ <em>after</em> this selection.</p> <p>That gives us: $E_k = 1 + \frac{(k+1)(n-k)E_{k+1} + (k-1)(n-k)E_{k-1} + (n(n-1)-2k(n-k))E_k}{n(n-1)}$.</p> <p>This simplifies to $2kE_k = \frac{n(n-1)}{n-k} + (k+1)E_{k+1} + (k-1)E_{k-1}$. We find from this that $E_1 = n/2 + E_2$, and generally if $E_{k-1} = w_{k-1}(n) + E_k$ then $E_k = w_k(n) + E_{k+1}$ with $w_k(n) = \frac{n(n-1)}{(n-k)(k+1)} + \frac{k-1}{k+1}w_{k-1}(n)$.</p> <p>The required expectation, $E_1$, now resolves to:</p> <p>$E_1 = \sum_{i=1}^{n-1}{w_i(n)}$</p> <p>$= n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{(n-i)(i+1)}(1 + \sum_{j=i+1}^{n-1}{ \prod_{k=i+1}^j{ \frac{k-1}{k+1} } }) }$</p> <p>$= n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{(n-i)(i+1)}(1 + \sum_{j=i+1}^{n-1}{ \frac{i(i+1)}{j(j+1)} }) }$</p> <p>$= n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{(n-i)(i+1)}(1 + i(i+1)(\frac{n-1}{n} - \frac{i}{i+1})) }$</p> <p>$= n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{n} }$</p> <p>$= (n-1)^2$.</p> <p>(Sorry, couldn't find how to get working multiline equations under jsMath, so I split them up.)</p> http://mathoverflow.net/questions/41543/how-to-characterize-a-self-avoiding-path/41663#41663 Answer by Hugo van der Sanden for How to characterize a Self-avoiding path. Hugo van der Sanden 2010-10-10T08:08:47Z 2010-10-10T08:08:47Z <p>In describing the relative moves, I think you need to say "turn right (left)" rather than "move right (left)". The question then becomes, in my interpretation: given a string of moves, by what rule can you determine if the sequence takes you back to your starting point? The question of a self-avoiding path is then answered by applying the rule to every substring of the path.</p> <p>The rule you give for absolute moves is simply expressed, but really only encapsulates the process of "track the coordinates you are at - you are back where you started when the coordinates reach (0, 0)"; it is only because one coordinate happens to be exactly "number of Up moves minus number of Down moves", and similarly for Right - Left, that it appears any simpler than the process it represents. The rule for relative moves isn't so simply expressed, but will also resolve to exactly the same thing: tracking your absolute position to see if you get back to your starting point.</p> http://mathoverflow.net/questions/33628/whats-the-simplest-rational-not-expressible-as-a-sum-of-a-given-number-of-unit-f/38675#38675 Answer by Hugo van der Sanden for What's the simplest rational not expressible as a sum of a given number of unit fractions? Hugo van der Sanden 2010-09-14T11:43:36Z 2010-09-14T11:43:36Z <p>$s(8) = \frac{27538}{27539}$.</p> <p>I have made the code I used available at <a href="http://crypt.org/hv/maths/least_eg-0.01.tar.gz" rel="nofollow">http://crypt.org/hv/maths/least_eg-0.01.tar.gz</a>, with a README file at <a href="http://crypt.org/hv/maths/least_eg-0.01-README" rel="nofollow">http://crypt.org/hv/maths/least_eg-0.01-README</a>.</p> <p>The package includes both PARI/GP code and C code using the GNU GMP library to calculate the results, as well as a synopsis of the results for each denominator from 2 to 27539 which may be of use for further analysis.</p> <p>I estimate the PARI code would have taken about a CPU-year to find the result; the C code runs over 20 times faster on my machine, and I don't understand why the difference is so great. (I'd appreciate email if someone can explain.)</p> http://mathoverflow.net/questions/27896/diophantine-equation-egyptian-fraction-representations-of-1/27925#27925 Answer by Hugo van der Sanden for Diophantine equation: Egyptian fraction representations of 1 Hugo van der Sanden 2010-06-12T10:29:52Z 2010-06-30T08:30:55Z <p>As far as I know, the only significant result to speed up these calculations is that $E_2(\frac{p}{q}) = \frac{1}{2}|\lbrace d: d | q^2, d \equiv -q (mod p) \rbrace|$, where $E_2(p/q)$ represents the number of decompositions into 2 unit fractions, and each matching $d$ represents the decomposition $\frac{p}{q} = \frac{qp}{q(q+d)} + \frac{dp}{q(q+d)}$. (Take floor() or ceil() depending on whether you want to allow repeats.)</p> <p>When I've coded this in the past, I called one of 4 different functions depending on a) whether $p=1$ or not, and b) whether $q/p \ge min$ or not, where $min$ is the greatest denominator I'm already using. When $p=1$ and $q \ge min$, in particular, we can just calculate $\tau(q^2)/2$ from the factorisation of $q$; in the other cases I actually walked the factors from $q/p$ to $\sqrt{q}$.</p> <p>So: yes, you can count the number of matching sets without generating the 7 elements of each set, but computationally the elements are just a whisker away.</p> http://mathoverflow.net/questions/27519/other-examples-of-composition-of-functions/27568#27568 Answer by Hugo van der Sanden for other examples of composition of functions Hugo van der Sanden 2010-06-09T09:00:07Z 2010-06-09T09:00:07Z <p>I'm not sure what you mean by "$f,g,f\circ g,g\circ f,\cdots$ are never equal" - if you use this method to decompose 11/3, you'll see that $g(3)=f^9(3)$, for example.</p> <p>(I think you also need to mention that the purpose of the method is to "generate a list of <i>distinct</i> unit fractions.)</p> <p>The simplest related example that comes to mind is the study of Collatz-like functions, where in a sense the question of interest is precisely when two different compositions <i>are</i> equal.</p> <p>Hugo</p> http://mathoverflow.net/questions/24609/are-there-primes-p-q-such-that-p41-2q2 Are there primes p, q such that p^4+1 = 2q^2 ? Hugo van der Sanden 2010-05-14T12:13:08Z 2010-05-14T15:26:18Z <p>$\exists p, q \in \mathbb{P}: p^4+1 = 2q^2$? I suspect there is some simple proof that no such p, q can exist, but I haven't been able to find one.</p> <p>Solving the Pell equation gives candidates for p^2=x and q=y, with x=y=1 as the first candidate solution and subsequent ones given by x'=3x+4y, y'=2x+3y; chances of a prime square seem vanishingly unlikely as x increases, but I don't have a proof.</p> <p>Meta: how do you search for a question like this? I looked for a searching HOWTO here and on meta, and couldn't find one. That the search appears to strip '^' and '=' makes it all the harder.</p> http://mathoverflow.net/questions/42447/subset-higher-power-sum-question-related-to-quadratic-forms/42451#42451 Comment by Hugo van der Sanden Hugo van der Sanden 2010-10-17T07:19:56Z 2010-10-17T07:19:56Z q.v. = quod vide, Latin for &quot;Google it&quot;. http://mathoverflow.net/questions/39207/solve-in-positive-integers-nm2 Comment by Hugo van der Sanden Hugo van der Sanden 2010-09-18T10:17:37Z 2010-09-18T10:17:37Z m=1, n=0 or 1. For larger n, there is a prime between n/2 and n, which guarantees an unsquared prime factor in the factorial. http://mathoverflow.net/questions/11503/does-war-have-infinite-expected-length/31185#31185 Comment by Hugo van der Sanden Hugo van der Sanden 2010-09-04T09:12:47Z 2010-09-04T09:12:47Z Moving the played cards to the bottom of the winner's stack in random order makes it <i>much</i> harder to retain a stable cyclic formation, so this result seems not at all surprising, and minimally informative about the answer for any variant without the randomness. http://mathoverflow.net/questions/35787/upper-bound-on-number-of-lines-in-a-linear-space-given-degree-bounds Comment by Hugo van der Sanden Hugo van der Sanden 2010-08-17T10:21:36Z 2010-08-17T10:21:36Z Oops, I misread it, my apologies. http://mathoverflow.net/questions/35787/upper-bound-on-number-of-lines-in-a-linear-space-given-degree-bounds Comment by Hugo van der Sanden Hugo van der Sanden 2010-08-17T09:02:54Z 2010-08-17T09:02:54Z I see nothing in the definition to disallow for any q the case of each line consisting of just 2 points. Then given n points there are $C(n,2)-(n-1)$ lines not containing a given point, and you can always take n large enough to make this exceed $q^2$. What am I missing? http://mathoverflow.net/questions/35106/on-the-constants-in-the-cameron-erdos-conjecture-on-sum-free-subsets Comment by Hugo van der Sanden Hugo van der Sanden 2010-08-11T09:16:26Z 2010-08-11T09:16:26Z The OEIS sequence has a link to a table of the first 70 terms, and both Maple and Mathematica code to calculate more values. http://mathoverflow.net/questions/33628/whats-the-simplest-rational-not-expressible-as-a-sum-of-a-given-number-of-unit-f Comment by Hugo van der Sanden Hugo van der Sanden 2010-07-28T18:44:36Z 2010-07-28T18:44:36Z I haven't checked the intervening numbers, but by hand I found 289/299 = 1/2 + 1/3 + 1/8 + 1/156 + 1/552. I checked also just using the greedy algorithm, and that gives 1/2 + 1/3 + 1/8 + 1/122 + 1/39795 + 1/1935522680. So I have no idea what Pegg's numbers are supposed to represent, but I can't see any relation between them and the stated problem. Time permitting I'll try calculating the sequence, but I anticipate the correct denominators will grow much more rapidly, so it'll be hard to calculate more than 7-8 terms. http://mathoverflow.net/questions/33628/whats-the-simplest-rational-not-expressible-as-a-sum-of-a-given-number-of-unit-f Comment by Hugo van der Sanden Hugo van der Sanden 2010-07-28T10:52:30Z 2010-07-28T10:52:30Z 14/17 = 1/2 + 1/4 + 1/14 + 1/476 appears to be an error; I believe 16/17 = 1/2 + 1/3 + 1/10 + 1/128 + 1/32640 is the simplest requiring 5 terms. http://mathoverflow.net/questions/33628/whats-the-simplest-rational-not-expressible-as-a-sum-of-a-given-number-of-unit-f Comment by Hugo van der Sanden Hugo van der Sanden 2010-07-28T09:25:28Z 2010-07-28T09:25:28Z I think you must additionally require <code>$r &lt; 1$</code>, else the denominators will all be 2 (or 1). http://mathoverflow.net/questions/27896/diophantine-equation-egyptian-fraction-representations-of-1/27925#27925 Comment by Hugo van der Sanden Hugo van der Sanden 2010-06-30T08:31:49Z 2010-06-30T08:31:49Z @Max: thanks, I've corrected it to -q (mod p). http://mathoverflow.net/questions/12113/archaeogenetics Comment by Hugo van der Sanden Hugo van der Sanden 2010-06-20T09:21:42Z 2010-06-20T09:21:42Z Edit 3 has removed most of the recombination description. I think it should say: $C = \lbrace x \rbrace \cup \lbrace a: a \lt x, a \in A \rbrace \cup \lbrace b: b \gt x, b \in B \rbrace$. http://mathoverflow.net/questions/28462/why-are-there-usually-an-even-number-of-representations-as-a-sum-of-11-squares Comment by Hugo van der Sanden Hugo van der Sanden 2010-06-17T10:26:16Z 2010-06-17T10:26:16Z What do you mean by &quot;so few&quot;? Numerically, I find 6,802 of the first 20,000 $n \equiv 3 \bmod 8$ have an odd number of representations as $x_0^2+2x_1^2+8x_3^2$. Are you asking why this is 34% rather than 50%, or am I misunderstanding the question? http://mathoverflow.net/questions/27944/do-there-exist-chess-positions-that-require-exponentially-many-moves-to-reach Comment by Hugo van der Sanden Hugo van der Sanden 2010-06-12T16:59:51Z 2010-06-12T16:59:51Z The retros mailing list has discussed record-length retroanalysis problems on a normal chessboard in the past; exploring those might offer ideas at least - see <a href="http://www.pairlist.net/pipermail/retros/" rel="nofollow">pairlist.net/pipermail/retros</a> for the archives of the mailing list. I think the primary impediment is usually dodging the 50-move rule, and in any case proofs are likely to be simpler if you throw that one out. http://mathoverflow.net/questions/27755/knuths-intuition-that-goldbach-might-be-unprovable/27766#27766 Comment by Hugo van der Sanden Hugo van der Sanden 2010-06-11T09:14:26Z 2010-06-11T09:14:26Z You say: &quot;The point is: Just because something is beyond the grasp of &lt;i&gt;a formal system&lt;/i&gt;, does not mean it is beyond our comprehension.&quot;; I assume you mean here &quot;a particular formal system&quot; rather than &quot;any formal system&quot;. http://mathoverflow.net/questions/24609/are-there-primes-p-q-such-that-p41-2q2/24636#24636 Comment by Hugo van der Sanden Hugo van der Sanden 2010-05-14T15:42:08Z 2010-05-14T15:42:08Z Thanks, this does solve it. I also found the infinite descent proof of the lemma at <a href="http://planetmath.org/encyclopedia/X4Y4z2HasNoSolutionsInPositiveIntegers.html" rel="nofollow">planetmath.org/encyclopedia/&hellip;</a>