Reputation
307
Top tag
Next privilege 500 Rep.
Access review queues
Badges
2 10
Impact
~7k people reached

  • 0 posts edited
  • 0 helpful flags
  • 4 votes cast
Aug
30
awarded  Nice Question
Aug
27
awarded  Yearling
Aug
23
comment How do I get rid of the coefficient in this congruence?
Also interested in this. What does your last sentence mean?
Aug
15
accepted $\binom{n}{k}$ modulo prime power for large $n$ and small $k$
Aug
15
comment $\binom{n}{k}$ modulo prime power for large $n$ and small $k$
So with the edit to p^a I now use inverse mod (extended gcd), answers still do not seem to match the correct results (I am comparing against a slow but correct n choose k mod p^e implementation)
Aug
15
comment $\binom{n}{k}$ modulo prime power for large $n$ and small $k$
I tested it and it does not seem to work (although the error may be mine). For the line "currentans * numer / denom (mod p)" I tried "currentans * numer * denom^(p-2) mod p"
Aug
15
comment $\binom{n}{k}$ modulo prime power for large $n$ and small $k$
I have to compute the coefficients over many $k$ (so for example for $k=1$ to $10^5$, for some unchanging $n$), and so if max $k$ is $10^5$ then that's $O(k^2)$ runtime for $10^5$. I also tested it for speed.
Aug
15
comment $\binom{n}{k}$ modulo prime power for large $n$ and small $k$
Although I thought it was $\binom{n}{k} = \binom{n}{k-1}\frac{n-k+1}{k}$ ?
Aug
15
comment $\binom{n}{k}$ modulo prime power for large $n$ and small $k$
As mentioned in the original post, iterative identities like these are prone to coprimality issues when the denominator $k$ is not invertible mod $p^a$. I am not sure what you mean by tracking exponents separately.
Aug
15
revised $\binom{n}{k}$ modulo prime power for large $n$ and small $k$
added 116 characters in body
Aug
15
comment $\binom{n}{k}$ modulo prime power for large $n$ and small $k$
I should add that $k$ is small, but not so small where I can store all values of $k!$ in memory (without modulus applied). Otherwise I'd have a solution for this.
Aug
15
asked $\binom{n}{k}$ modulo prime power for large $n$ and small $k$
Aug
3
comment Solutions to ax = by mod m?
@GregMartin There isn't a complete solution anywhere, either in a book or online
Aug
3
asked Solutions to ax = by mod m?
Apr
4
accepted Can this congruence be reduced?
Apr
4
comment Can this congruence be reduced?
@JBKing Oh, in this case, no I don't think that applies here
Apr
4
comment Can this congruence be reduced?
@JBKing I am not sure what you are asking, but it is possible for there to be no solutions to this congruence depending on the value of $x$ I suppose
Apr
4
asked Can this congruence be reduced?
Apr
2
awarded  Curious
Apr
1
comment How to compute this limit with different operations of $x$?
Wouldn't that just be 0?