Fixee
Reputation
5,868
Top tag
Next privilege 10,000 Rep.
Access moderator tools
 Feb5 comment Problem about combinations and permutations The first customer has 14 choices, the next 13, and the last 12. It's 14P3, not 14C3. Oct14 comment $\gcd(p, (p-1)!) = 1$? Wilson's theorem settles this in 1 step: en.wikipedia.org/wiki/Wilson's_theorem Jul15 comment Finding rational points at rational distance in the plane @QiaochuYuan: Take $p$ to be $(1/\pi, \sqrt{1-1/\pi^2})$. Aren't both coordinates transcendental? And isn't $p$ unit distance from the origin? Aug5 comment Expected length of a sequence that contains all words of a given length. @ByronSchmuland I think that's the same ref leonbloy cited at the end of his answer below. Aug4 comment N white and black balls and N boxes Probability Given $N$ new users posting $N$ new questions which are worded as demands rather than questions, what is the probability they are all homework problems? Jun29 comment Fibonacci sequence - how to prove $a_n=\frac{1}{\sqrt{5}} ((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)$ without induction This is given as a warmup in the free text by Wilf called generatingfunctionology. Jun28 comment How to find generator in a finite group?what is generator? When I said, "suppose you can factor" the "you" is the OP who is (presumably) a human trying to solve a problem. I did not (and would not) say "suppose a factorization exists for $(p-1)$". Jun24 comment practical arithmetic in prime factorizations Ross, I don't get your answer. You seem to be reiterating his idea rather than answering his question regarding the use of this technique in actual software. Jun15 comment How to show that $\sum\limits_{k=1}^{n-1}\frac{k!k^{n-k}}{n!}$ is asymptotically $\sqrt{\frac{\pi n}{2}}$? @PeterR: Often mathematicians will use "elementary" to mean "does not use complex analysis". As you can see, "elementary" does not mean "easy." Jun15 comment Conjecture: The following sum is asymptotic to $\sqrt{9πm/8}$ Interesting. This immediately gives that three collisions occur in less than an expected $2 \sqrt{\pi m/2} = \sqrt{2\pi m}$. (In fact, I will guess that it's $15/8 \sqrt{\pi m/2}$.) Since $\sqrt{2\pi m}$ is the square root of the circumference of a circle of radius $m$, there is clearly a geometric proof we're missing. :) Jun15 comment How many even number in a sequence are there? Your iff is false in both directions. Jun15 comment Second pair of matching birthdays @ShreevatsaR: The reason my simulation made me believe the answer was not proportional to $\sqrt{M}$ was that--as your program shows--the multiplier starts above 2.1 and gradually settles to 1.88... But your argument in your answer that it must be a multiple of $\sqrt{M}$ is quite convincing. Jun15 comment How many expected people needed until 3 share a birthday? Following the link to your other question, and then to the Sedgewick/Flajolet book, and then a reference from there, I found a paper that gives the derivation for this result: sciencedirect.com/science/article/pii/S0021980067800759 Jun15 comment How many expected people needed until 3 share a birthday? Thanks, Byron. I had guessed that $E(T) \approx c M^{2/3}$, but simulations I ran showed $c$ growing slightly with $M$ so I thought the $2/3$ exponent was a tad low. It could instead be the effect of lower-order terms in the asymptotics. Jun15 comment How many expected people needed until 3 share a birthday? I am asking for the expected number of balls where a 3-way collision occurs. But I would be happy to learn the "median" value, which is the number of balls where the a 3-way collision has probability $\approx$ 1/2. Jun14 comment Second pair of matching birthdays I have worked (unsuccessfully) at finding a closed form for the constant $c \approx 1.88$ that you approximate via your python program above. Unfortunately the integral that so nicely turns into $\sqrt{\pi/2}$ ends up being much harder with the ${n \choose 2}$ multiplier. Jun10 comment Prove that if $n$ is a composite and $p \gt \sqrt[3]n$, then $n/p$ is a prime. If you look at the edit history, it used to say "composite" at the time my response was offered. Jun1 comment Second pair of matching birthdays Very nice! I have been working on this problem since I posted it and I followed virtually the exact same steps as you do above, but you are faster. I just last night wrote the same program you did (in C instead of Python, but they're almost identical!). I feel guilty seeing all the work you did on this... I'm doing this just for fun (it's summer after all!). Cheers. Jun1 comment Second pair of matching birthdays Well, I mostly understand what you did, but you approximated the median (tosses needed to get a 50% probability) rather than the mean, and they are not asymptotically equal for this problem (as you point out). Based on computer simulations I've run, your 55% estimate isn't quite right: for small $M$ we need about 60% more, and for larger $M$ (say 100,000) it's less than 50%. I don't think this 2-collision mean is proportional to $\sqrt{M}$ like the 1-collision mean is. May31 comment Second pair of matching birthdays I agree with you that this is the probability of obtaining 2 (or more) collisions throwing $n$ balls into $M$ bins, but I was asking for an expectation. Every technique I know of requires computing a sum.