1,626 reputation
711
bio website
location Madrid, Spain
age 50
visits member for 3 years, 5 months
seen 31 mins ago

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
5
comment Proving a simple inequality
I find $$f(3) = \frac{\tfrac{2}{3}\log 2}{\log 6} = 0.2579... > f(4) = \frac{\tfrac{1}{2}\log 3}{\log 12} = 0.2210...$$ Are you sure the inequality is correctly written?
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
Feb
21
answered Is it a bad idea to use a Sieve of Eratosthenes to find all primes up to very large N?