pelotom

197 reputation

bio	website
	location	Los Angeles, CA
	age	32
visits	member for	2 years, 7 months
	seen	Apr 1 at 8:45
stats	profile views	31

	197 reputation	bio	website		visits	member for	2 years, 7 months
5 badges		location	Los Angeles, CA		seen	Apr 1 at 8:45

summary answers questions tags badges favorites bounties reputation activity

44 Actions

suggestions reviews revisions comments badges posts accepts all

Sep 15	comment	How can I determine the cardinality of a set of polymorphic functions? You're right, System F is the right framework in which to answer this sort of question, and specifically using the idea of Parametricity. Thanks!
Sep 15	accepted	How can I determine the cardinality of a set of polymorphic functions?
Aug 18	comment	Linear functions with rounding @Olivier - Hm, I don't see how? For what initial value(s) would that be a problem?
Aug 18	revised	Linear functions with rounding added 180 characters in body
Aug 18	comment	Linear functions with rounding Nice counterexample! What if I changed the definition of rounding to say that if the fractional part is exactly .5, it yields the adjacent even number?
Aug 18	asked	Linear functions with rounding
Aug 14	revised	What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof? added 2 characters in body
Aug 14	revised	What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof? added 78 characters in body
Aug 14	comment	What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof? @Ilmari Karonen - I think the fault is mine for not making this clearer in the original post... I was trying to keep the backstory to the question as brief as possible :) I've made a small edit to the question that will hopefully help.
Aug 14	revised	What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof? added 78 characters in body
Aug 14	comment	What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof? If $j$ is prime, then the loop will only terminate because $d > \sqrt j$. This is where Dijkstra was silently making use of the fact that $\sqrt p_{n+1} < p_n$, always. We could of course modify the algorithm if we weren't sure of that fact, to include an additional termination condition of $d = p_n$, but the algorithm as stated didn't have that.
Aug 14	comment	What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof? You are pointing out why we only need to check primes numbers $d$ up to $\sqrt j$ when looking for a divisor of $j$; if we don't find one by then we can conclude that it is prime. But that's not the hidden assumption Knuth was talking about. He is referring to the assumption that you can draw $d$ from the array of primes you have been constructing in a loop, with the only termination conditions being $d\|j$ or $d > \sqrt j$, and have no fear of reading past the end of the array, which contains primes only up to $p_n$.
Aug 14	revised	What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof? edited body
Aug 14	comment	What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof? @André Nicolas - The algorithm tests a given $j$ for primality by checking whether it is divisible by any prime $\le \sqrt j$.
Aug 14	comment	What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof? @André Nicolas - I take it you're referring to a problem of efficiency? Indeed it's far from the most efficient way to find primes... Dijkstra admits as much and was only interested in demonstrating its correctness.
Aug 14	comment	What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof? @Olivier Bégassat - yes, that's Legendre's conjecture as I learned just now :)
Aug 14	accepted	What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof?
Aug 14	comment	What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof? Very cool, I'll go look at these proofs. Thanks!
Aug 14	asked	What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof?
May 23	comment	How can I determine the cardinality of a set of polymorphic functions? @robinhoode - for each element of $\emptyset$ you give me, I can give you another element of $\emptyset$... try me :)