My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
October 27th, 2013, 10:36 PM   #21
Math Team
 
mathbalarka's Avatar
 
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?
mathbalarka is offline  
 
October 27th, 2013, 10:47 PM   #22
Global Moderator
 
CRGreathouse's Avatar
 
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?
CRGreathouse is offline  
October 27th, 2013, 10:54 PM   #23
Math Team
 
mathbalarka's Avatar
 
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.
mathbalarka is offline  
October 27th, 2013, 11:29 PM   #24
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
October 28th, 2013, 08:46 AM   #25
Senior Member
 
Joined: Aug 2012

Posts: 2,075
Thanks: 593

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.
Maschke is online now  
October 28th, 2013, 11: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.
icemanfan is offline  
October 28th, 2013, 12:29 PM   #27
Math Team
 
mathbalarka's Avatar
 
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, 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.
mathbalarka is offline  
October 28th, 2013, 01:33 PM   #28
Senior Member
 
Joined: Aug 2012

Posts: 2,075
Thanks: 593

Re: The set of primes as an algebraic structure

Quote:
Originally Posted by mathbalarka
There are such formulas. For example, 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.
Maschke is online now  
October 28th, 2013, 02: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 . Also, there is no known explicit formula for the nth prime. Formulas like the one mathbalarka posted are similar to in that they are very simple yet still cannot be expressed explicitly.
icemanfan is offline  
October 28th, 2013, 02:34 PM   #30
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
algebraic, primes, set, structure



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
primes and twin primes: Number between powers of 10 caters Number Theory 67 March 19th, 2014 05:32 PM
Proof Structure soulrain Applied Math 4 July 13th, 2012 06:43 PM
The natural structure of mathematics DavidLaPierre Academic Guidance 3 January 22nd, 2012 10:51 AM
Is an algebraic structure a set? bentley4 Abstract Algebra 1 May 14th, 2011 03:20 AM
Questions regarding structure Wiccidu New Users 4 April 9th, 2011 09:00 PM





Copyright © 2018 My Math Forum. All rights reserved.