User hugo van der sanden - MathOverflow

Answer by Hugo van der Sanden for A balls-and-colours problem

2010-10-13T15:31:33Z

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$.

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 $k'/n$ , where $k'$ is the number of balls coloured $c$ after this selection.

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)}$.

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)$.

The required expectation, $E_1$, now resolves to:

$E_1 = \sum_{i=1}^{n-1}{w_i(n)}$

$ = 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} } }) }$

$ = 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)} }) }$

$ = 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})) }$

$ = n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{n} }$

$ = (n-1)^2$.

(Sorry, couldn't find how to get working multiline equations under jsMath, so I split them up.)

Answer by Hugo van der Sanden for How to characterize a Self-avoiding path.

2010-10-10T08:08:47Z

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.

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.

Answer by Hugo van der Sanden for What's the simplest rational not expressible as a sum of a given number of unit fractions?

2010-09-14T11:43:36Z

$s(8) = \frac{27538}{27539}$.

I have made the code I used available at http://crypt.org/hv/maths/least_eg-0.01.tar.gz, with a README file at http://crypt.org/hv/maths/least_eg-0.01-README.

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.

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.)

Answer by Hugo van der Sanden for Diophantine equation: Egyptian fraction representations of 1

2010-06-12T10:29:52Z

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.)

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}$.

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.

Answer by Hugo van der Sanden for other examples of composition of functions

2010-06-09T09:00:07Z

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.

(I think you also need to mention that the purpose of the method is to "generate a list of distinct unit fractions.)

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 are equal.

Hugo

Are there primes p, q such that p^4+1 = 2q^2 ?

2010-05-14T12:13:08Z

$\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.

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.

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.

Comment by Hugo van der Sanden

2010-10-17T07:19:56Z

q.v. = quod vide, Latin for "Google it".

Comment by Hugo van der Sanden

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.

Comment by Hugo van der Sanden

2010-09-04T09:12:47Z

Moving the played cards to the bottom of the winner's stack in random order makes it much 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.

Comment by Hugo van der Sanden

2010-08-17T10:21:36Z

Oops, I misread it, my apologies.

Comment by Hugo van der Sanden

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?

Comment by Hugo van der Sanden

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.

Comment by Hugo van der Sanden

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.

Comment by Hugo van der Sanden

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.

Comment by Hugo van der Sanden

2010-07-28T09:25:28Z

I think you must additionally require $r < 1$ , else the denominators will all be 2 (or 1).

Comment by Hugo van der Sanden

2010-06-30T08:31:49Z

@Max: thanks, I've corrected it to -q (mod p).

Comment by Hugo van der Sanden

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$.

Comment by Hugo van der Sanden

2010-06-17T10:26:16Z

What do you mean by "so few"? 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?

Comment by Hugo van der Sanden

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 pairlist.net/pipermail/retros 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.

Comment by Hugo van der Sanden

2010-06-11T09:14:26Z

You say: "The point is: Just because something is beyond the grasp of <i>a formal system</i>, does not mean it is beyond our comprehension."; I assume you mean here "a particular formal system" rather than "any formal system".

Comment by Hugo van der Sanden

2010-05-14T15:42:08Z

Thanks, this does solve it. I also found the infinite descent proof of the lemma at planetmath.org/encyclopedia/…