Reputation
1,871
Top tag
Next privilege 2,000 Rep.
Edit questions and answers
Badges
10 13
Newest
 Enlightened
Impact
~17k people reached

  • 0 posts edited
  • 0 helpful flags
  • 109 votes cast
Nov
8
awarded  Yearling
Nov
7
answered Cover a disk with thin rectangles
Nov
6
comment What would be complexity of computing $3^{n^n}$?
If you are computing $3^{n^n}$ modulo an integer $M$ and you know it's totient function $\varphi(M)$ then you can compute $n^n$ in $O(\log n)$ multiplications $\pmod{ \varphi(M)}$ and then rise $3$ to the result in $O(\log M)$ multiplications mod $M$ finding the result in polynomial time. The problem is to find $\varphi(M)$. Some times it can be done in polynomial time (for example if $M$ is prime then $\phi(M)=M-1$), but in general if $M$ is composite finding $\varphi(M)$ is equivalent to finding the factorization of $M$.
Nov
3
revised Half the rationals?
Added a generalization
Nov
3
answered Half the rationals?
Nov
1
comment Half the rationals?
A good candidate for your set $X$ with a very simple description is the set of reduced fractions $a/b$ with $$ a\cdot b \equiv 0 \pmod{3} $$
Nov
1
comment Half the rationals?
I think there something missing in the right hand side of the inequality $\sum_{k=1}^{n-1} a_k\phi(k) < 1/2$, I suppose you mean $<\frac{1}{2}\sum_{k=1}^{n-1} \phi(k)$? On the other hand, even if it is probably true, I can't see how to prove that this construction works for all the intervals $Y$.
Nov
1
comment Half the rationals?
I think that the proportion of fractions with even numerator and denominator bounded by $N$ is aproximately one third, and the same for even denominator.
Oct
15
revised Tiling a minimal perimeter region with $n$ unit squares
Sketch of proof
Oct
15
answered Tiling a minimal perimeter region with $n$ unit squares
Jul
19
answered Solving a polynomial modulo an integer
Jun
8
awarded  Caucus
Apr
19
revised Burgess on quadratic residues and non-residues
edited body
Apr
19
comment Burgess on quadratic residues and non-residues
No that's an error I correct it
Apr
19
comment Burgess on quadratic residues and non-residues
I have edited the answer to make it more clear. I hope this helps.
Apr
19
revised Burgess on quadratic residues and non-residues
added 1406 characters in body
Apr
17
revised Burgess on quadratic residues and non-residues
correction
Apr
17
answered Burgess on quadratic residues and non-residues
Feb
21
revised Is it a bad idea to use a Sieve of Eratosthenes to find all primes up to very large N?
added 1962 characters in body
Feb
21
revised Is it a bad idea to use a Sieve of Eratosthenes to find all primes up to very large N?
added 1962 characters in body