Reputation
6,073
Top tag
Next privilege 10,000 Rep.
Access moderator tools
Badges
6 22 44
Impact
~283k people reached

Aug
17
comment calculate $a/b\ mod\ p$ where p is a prime and a,b can be very large
Yes, use the max power of $p$ that divides both numerator and denominator. This max power can be found quickly with binary search.
Jul
14
comment What is the last digit of $\pi$?
@SimonS The best way to answer that question would be a web search. My research area is cryptography, so it's too far afield for me to have anything but recreational interest, but a lot of very interesting math isn't that well-used. It doesn't mean it's not cool or fun to think about. For example, here's a question: we know that $\pi$ is irrational in base 10; is 10 irrational in base $\pi$?
Jul
14
comment What is the last digit of $\pi$?
@SimonS I think I did above: $\pi = 10_\pi$. Irrational bases do lead to weird results, but I'm not the first one to suggest them. I first encountered the idea of irrational (and transcendental) bases in Knuth's 2nd book, but the idea predates even that: mathworld.wolfram.com/Base.html
Jul
2
comment proof by contradiction puzzle
Isn't this just en.wikipedia.org/wiki/Chomp ?
Jun
10
comment What is the worst-case running time of this algorithm?
@Henry That's a good suggestion. Or "unbounded" even.
Feb
5
comment Problem about combinations and permutations
The first customer has 14 choices, the next 13, and the last 12. It's 14P3, not 14C3.
Oct
14
comment $\gcd(p, (p-1)!) = 1$?
Wilson's theorem settles this in 1 step: en.wikipedia.org/wiki/Wilson's_theorem
Jul
15
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?
Aug
5
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.
Aug
4
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?
Jun
29
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.
Jun
28
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)$".
Jun
24
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.
Jun
15
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."
Jun
15
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. :)
Jun
15
comment How many even number in a sequence are there?
Your iff is false in both directions.
Jun
15
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.
Jun
15
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
Jun
15
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.
Jun
15
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.