My Math Forum The set of primes as an algebraic structure

 Number Theory Number Theory Math Forum

October 27th, 2013, 09:36 PM   #21
Math Team

Joined: Mar 2012
From: India, West Bengal

Posts: 3,871
Thanks: 86

Math Focus: Number Theory
Re: The set of primes as an algebraic structure

Quote:
 Originally Posted by CRGreathouse Maschke didn't say anything about being a formula: "Of course if we could input n and output P_n we'd become famous."
Yes, I reckon that. I was just thinking a little differently.

Quote:
 Originally Posted by CRGreathouse do you have a definition in mind?
Definition of what?

October 27th, 2013, 09:47 PM   #22
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: The set of primes as an algebraic structure

Quote:
 Originally Posted by mathbalarka Definition of what?
"Formulated". What, to you, is a formula? Can I use trig functions? Floor/ceiling? Unbounded sums and products? The Kronecker delta? Quadratic reciprocity symbols (e.g., Legendre's)? Integrals?

October 27th, 2013, 09:54 PM   #23
Math Team

Joined: Mar 2012
From: India, West Bengal

Posts: 3,871
Thanks: 86

Math Focus: Number Theory
Re: The set of primes as an algebraic structure

Quote:
 Originally Posted by CRGreathouse "Formulated".
OMG... I have no idea. Perhaps a brief expression which doesn't include any logical operators, i.e., if or for?

Quote:
 Originally Posted by CRGreathouse Can I use trig functions? Floor/ceiling? Unbounded sums and products? The Kronecker delta? Quadratic reciprocity symbols (e.g., Legendre's)? Integrals?
Um, yes, I think you can use those.

 October 27th, 2013, 10:29 PM #24 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: The set of primes as an algebraic structure That should be enough to define the Lagarias-Odlyzko analytic method then, right? So we have pi(x). The inverse logarithmic integral is similarly easy to define with those operators (plus simple ones like + and *), so just use li^-1 and two iterations of pi(x) to get a (very) close estimate of the nth prime. Probably with more work you could get an exact formula (in addition to being asymptotically efficient) but I won't stick my head out trying to come up with that tonight.
October 28th, 2013, 07:46 AM   #25
Senior Member

Joined: Aug 2012

Posts: 2,356
Thanks: 738

Re: The set of primes as an algebraic structure

Quote:
Originally Posted by CRGreathouse
Quote:
Originally Posted by mathbalarka
Quote:
 Originally Posted by CRGreathouse Any of the nontrivial pi(x) algorithms + binary search + sieving.
Oh, you're talking of algorithms. Can any of those be "formulated"?
Maschke didn't say anything about being a formula: "Of course if we could input n and output P_n we'd become famous.", but if this is just for your own curiosity, do you have a definition in mind?
Tough crowd. I did use the word "formula" in the paragraph previous to the line you quoted. Obviously there's an algorithm, you can just try each successive number and test for primality by trial division. That makes finding the n-th prime computable. But according to Wikipedia, the last word in everything these days, "No such formula which is efficiently computable is presently known. ..."

http://en.wikipedia.org/wiki/Formula_for_primes

The article's only about formulas that generate primes ... doesn't say anything about specifically generating the n-th prime. There are some interesting formulas in the article. For example if RH is true then there's a number A such that floor(A^3^n) is prime for all positive integers n. The number A is called Mills' constant.

http://en.wikipedia.org/wiki/Mills%27_constant

But the sequence skips a lot of primes.

 October 28th, 2013, 10:09 AM #26 Senior Member   Joined: Feb 2012 Posts: 628 Thanks: 1 Re: The set of primes as an algebraic structure Back on topic, I came up with a binary operation that is closed under the primes but does not form a group: Define a % b to be the largest prime factor of the sum of a + b. Some examples: 3 % 5 = 2 2 % 5 = 7 11 % 7 = 3 13 % 7 = 5 2 % 13 = 5 5 % 11 = 2 There is no identity element and even if you tried to force one of the primes to be an identity element by definition there would not be unique inverses. For example, I could arbitrarily decide that 2 % x = x % 2 = 2 by definition, and then define a % b in the normal way when 2 was not involved. But then you would have 3 % 5 = 11 % 5 = 2 so 5 would not have a unique inverse. But I was thinking that it would make the most sense for 2 to be the identity element regardless of what the binary operation was. The rationale for this is that 2 is the smallest prime and also the only one which is even.
October 28th, 2013, 11:29 AM   #27
Math Team

Joined: Mar 2012
From: India, West Bengal

Posts: 3,871
Thanks: 86

Math Focus: Number Theory
Re: The set of primes as an algebraic structure

Quote:
 Originally Posted by Maschke doesn't say anything about specifically generating the n-th prime.
There are such formulas. For example, $p_n= 1 + \sum_{m = 1}^{2^n} \left \lfloor \left \lfloor \frac{n}{1 + \pi(m)} \right \rfloor ^{1/n} \right \rfloor$ is one of such.

Quote:
 Originally Posted by CRGreathouse That should be enough to define the Lagarias-Odlyzko analytic method then, right? So we have pi(x). The inverse logarithmic integral is similarly easy to define with those operators (plus simple ones like + and *), so just use li^-1 and two iterations of pi(x) to get a (very) close estimate of the nth prime. Probably with more work you could get an exact formula (in addition to being asymptotically efficient) but I won't stick my head out trying to come up with that tonight.
I am not familiar with the method, so no comment until I familiarize myself with that.

October 28th, 2013, 12:33 PM   #28
Senior Member

Joined: Aug 2012

Posts: 2,356
Thanks: 738

Re: The set of primes as an algebraic structure

Quote:
 Originally Posted by mathbalarka There are such formulas. For example, $p_n= 1 + \sum_{m = 1}^{2^n} \left \lfloor \left \lfloor \frac{n}{1 + \pi(m)} \right \rfloor ^{1/n} \right \rfloor$ is one of such.
I stand educated. Thanks. Ah ... I see you have pi(n) stuck in there. Is there an explicit formula for pi(n)? I thought all you got was approximations. If there is an exact formula for pi(n) then your formula works ... otherwise I don't see how you can count it as a formula. Can you clarify this point?

To be clear: I'm under the impression that the only way to compute pi(n) exactly is to count the primes one-by-one. You can get an approximation to pi(n) for large n with logarithms, but it's not exact.

 October 28th, 2013, 01:13 PM #29 Senior Member   Joined: Feb 2012 Posts: 628 Thanks: 1 Re: The set of primes as an algebraic structure You are correct. There is no known explicit formula for $\pi(n)$. Also, there is no known explicit formula for the nth prime. Formulas like the one mathbalarka posted are similar to $\int \sin(x^2) dx$ in that they are very simple yet still cannot be expressed explicitly.
October 28th, 2013, 01:34 PM   #30
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: The set of primes as an algebraic structure

Quote:
 Originally Posted by Maschke Is there an explicit formula for pi(n)?
It depends on your definition of explicit, I guess. Going by balarka's definition, the analytic method mentioned above works.

 Tags algebraic, primes, set, structure

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post caters Number Theory 67 March 19th, 2014 04:32 PM soulrain Applied Math 4 July 13th, 2012 05:43 PM DavidLaPierre Academic Guidance 3 January 22nd, 2012 09:51 AM bentley4 Abstract Algebra 1 May 14th, 2011 02:20 AM Wiccidu New Users 4 April 9th, 2011 08:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top