15,856 reputation
22877
bio website
location
age
visits member for 4 years, 3 months
seen 2 hours ago

2d
comment Choosing primes uniformly at random
@KSmarts: I'm happy to let you pick from a list, but I'm not allowing precomputation (and need arbitrary $n$), so the cost of generating the list would need to be included in the algorithm's time. This makes it less efficient (by a factor of ~$2^{n/2}$) than my 'extreme' algorithm. Practically speaking I'd like algorithms to take 'reasonable' space but I'm willing to consider unreasonable algorithms just to get a different perspective.
2d
comment Do we still need probabilistic primality testing methods for practical applications?
@DanaJ: Actually, that inspires me to ask a new question: math.stackexchange.com/q/1069693/1778 Maybe you have some ideas?
2d
asked Choosing primes uniformly at random
2d
awarded  Caucus
2d
comment Do we still need probabilistic primality testing methods for practical applications?
@DanaJ: Indeed, you're right -- I must have misread the code, because I see now that they're doing as you say (taking nextprime(random), essentially).
Dec
13
comment Do we still need probabilistic primality testing methods for practical applications?
@SalvadorDali: 95 tests because, on average, you'll have 94 composites and 1 prime. If you pretest to remove (almost) all of the composites you only need (slightly more than) one AKS test.
Dec
12
answered Do we still need probabilistic primality testing methods for practical applications?
Dec
12
revised Is $n(n+1)$ ever a factorial?
more checking
Dec
10
comment How to find smallest integer which is greater than N positive primes
@dotNET: You're welcome. Let me know if you need anything else -- bounds, error estimates, etc.
Dec
10
comment How to find smallest integer which is greater than N positive primes
@RossMillikan: I'm familiar with Rosser's theorem, but the difference between $p_n$ and $n\log n$ should be about $n\log\log n$, not $0.46n$. (Notationally, I'm defining $f$ and $f_1$ and then claiming that these approximate the $n$-th prime; I'm certainly not saying that these give the $n$-th prime exactly!)
Dec
10
answered How to find smallest integer which is greater than N positive primes
Dec
10
revised On the problem of polynomial bijection from $\mathbb Q\times\mathbb Q$ to $\mathbb Q$
fix line breaks, spelling, etc.
Dec
10
answered Constellations in $\Bbb P^n$
Dec
9
comment Make a prime number from specified number, by concatenating some more digits on its right?
@Traklon: Thanks for the edit. I don't want you to delete either -- especially since the counterexample took more effort to find than my actual answer!
Dec
9
comment Make a prime number from specified number, by concatenating some more digits on its right?
OK, here's an explicit example: 131116183. It's already 1 mod 6, but you can keep it there by adding another 3 if you like. But no matter how many 3s you add you'll never get a prime number.
Dec
9
comment Make a prime number from specified number, by concatenating some more digits on its right?
@JuliánAguirre: Dirichlet's theorem doesn't let you find infinitely many primes of the form k, k3, k33, k333, ... [where juxtaposition represents decimal concatenation], which is what we're doing here.
Dec
8
revised Dickson's (and Bunyakovsky's) conjecture with compositeness constraints
density
Dec
8
answered Make a prime number from specified number, by concatenating some more digits on its right?
Dec
8
comment Make a prime number from specified number, by concatenating some more digits on its right?
I suspect that it does not -- that specially-chosen numbers will produce only composites. This phenomenon should mirror that of Sierpiński and Riesel numbers.
Dec
8
comment What is the probability that a Poisson random variable is prime?
@wolfies: Good catch -- thanks! I fixed it.