9,556 reputation
2732
bio website
location
age 38
visits member for 2 years, 7 months
seen 2 hours ago

2d
comment Differences between large numbers with many factors has little factors
@Assaultous2 To summarize: the whole point of your question is that certain small numbers have "few" prime factors, but only when the standard of comparison is two large numbers specially chosen to have many many prime factors? Why is that surprising or interesting?
2d
comment The decision tree has height at least $\log n!$
@user45195 Notice the question does not ask for the best way to sort a list :). The whole point of the OP is to show that a decision tree cannot sort faster than $O(n \log n)$. Whether or not it can be done faster by other means is irrelevant to the question at hand. (And I'm skeptical that a hash table would be of much value, since it wouldn't generically preserve sort order.)
2d
comment Why can't the definition of convergence be alterted to this one?
@flawr No, as Meelo points out below, the sequence must diverge to $\infty$ ($\infty$ here in the sense of the one-point compactification of $\mathbb R$).
2d
comment Why can't the definition of convergence be alterted to this one?
@voldemort That example doesn't satisfy $\varepsilon = 1$.
Dec
17
comment Number theory and abstract algebra question
Duplicate of math.stackexchange.com/questions/156213/… ?
Dec
15
awarded  Caucus
Dec
15
comment How to show if $\alpha$ is in the range than so is $T(\alpha)$
This seems awfully vague. $T$, $V$, and $x$ are never defined (which also means $E_k$ doesn't have a real definition).
Dec
12
comment How many co-prime pairs are there between 1 and N?
$\sum_{i\le n} \phi(i)$ is asymptotically about $3n^2/\pi^2$, so your sum is approximately $0.7n^2$, but the true value is closer to $0.6n^2$. Did you try it for $n < 8$?
Dec
12
comment Is there an easy way to remember the ring axioms?
Addition is an abelian group, multiplication is a monoid, and left- and right-distributivity. If you can't remember which group axioms a monoid has, just think of matrix multiplication as a prototype (associative, not commutative, identity, no inverse).
Dec
12
comment How quickly can we multiply hypercomplexes?
What naive algorithm needs $2^{2^n}$ multiplications? Why not $(2^{n})^2$?
Dec
5
comment Chance on pairs when picking 'Sinterklaas tickets'
@CamilStaps Actually, rather than double-counting, most likely your is_derangement is always returning true. The incidence of permutations having cycles of length 1 or 2 in the space of all permutations is $1-e^{-3/2} \approx 0.7769$ which would explain your findings.
Dec
5
comment Chance on pairs when picking 'Sinterklaas tickets'
@CamilStaps Interesting that this is about half of the experimental value. Suggests that perhaps you are double-counting somewhere in your code?
Dec
5
comment Is a homomorphisim one-to-one or onto?
@phatty I think you misunderstand one-to-one. Your phrasing suggests that you imagine it to mean something like "not onto", or "is a function", neither of which is accurate.
Dec
3
revised Prove that this recurrence relation algorithm generates all positive rational numbers, and does so without repetition and in reduced form
edited title
Dec
3
comment Prove that this recurrence relation algorithm generates all positive rational numbers, and does so without repetition and in reduced form
When will $q_k$ ever be nonpositive?
Dec
3
comment The decision tree has height at least $\log n!$
@user45195 Incorrect (linear time != constant time) and irrelevant (a hash function won't be described by a constant-height decision tree).
Dec
2
comment Isn't this the most compact binary representation of all numbers?
@YuvalFilmus The definition seems muddled, but it's hard to interpret it as prescribing a fixed $M$ when $M>N$ and $N\to \infty$ :)
Dec
2
revised Isn't this the most compact binary representation of all numbers?
Update with better lower bound.
Dec
2
answered Isn't this the most compact binary representation of all numbers?
Dec
2
comment Isn't this the most compact binary representation of all numbers?
What role does the $N$ play in this definition? How does it give a different average than taking $N=M$?