RE: [math-fun] Prime "number system" ? (Goldbach, etc.)
The Prime Number Theorem, pi(X) ~ X/logX, implies that the ratio of consecutive primes approaches 1 as a limit. In fact, a bit more is proven - roughly, for large enough numbers, there's always a prime between any two cubes. So by taking the representation of N to be (largest prime <= N) + (recurse to represent the balance), each prime will reduce the size of the leftover from N down to O(N^(2/3)), and the total number of terms is around O(loglogN). Of course, if you allow Goldbach, then 3 primes is likely always enough. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com [mailto:math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com] On Behalf Of Henry Baker Sent: Monday, July 10, 2006 2:19 PM To: Michael Reid Cc: math-fun@mailman.xmission.com Subject: Re: [math-fun] Prime "number system" ? (Goldbach, etc.) Interesting. Is it then true that there is a prime of every length when expressed in the binary system? Then I suppose we could always choose the smallest such for each length, and we would never need more than ~log_2(n) such numbers in the representation. So this representation is as compact as the usual binary system? At 01:08 PM 7/10/2006, Michael Reid wrote:
In an analogy with Zeckendorf (Fibonacci) number systems, can every positive integer be expressed as a _sum_ of _distinct_ (positive) primes ?
If not, what is the smallest integer not so expressible?
For this purpose, I'll allow "1" as a "prime", although I suspect it's only needed a constant number of times.
yes, with your convention of considering 1 to be prime. you've already shown how to do the first few cases. for a larger value of N , let p be the largest prime <= N . then p > N/2 , by the theorem usually called "Bertrand's postulate". express N - p as a sum of distinct "primes", and add p to the result. since p > N - p , the primes in this sum are distinct.
it is probably easy to modify this argument to show that 1 is only needed a few times (twice?)
mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Really? I thought it was still an open conjecture that there is always a prime between consecutive squares. On the other hand, it has long been known that there is always a prime between n and 2n. Franklin T. Adams-Watters -----Original Message----- From: Schroeppel, Richard <rschroe@sandia.gov> The Prime Number Theorem, pi(X) ~ X/logX, implies that the ratio of consecutive primes approaches 1 as a limit. In fact, a bit more is proven - roughly, for large enough numbers, there's always a prime between any two cubes. So by taking the representation of N to be (largest prime <= N) + (recurse to represent the balance), each prime will reduce the size of the leftover from N down to O(N^(2/3)), and the total number of terms is around O(loglogN). Of course, if you allow Goldbach, then 3 primes is likely always enough. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com Interesting. Is it then true that there is a prime of every length when expressed in the binary system? Then I suppose we could always choose the smallest such for each length, and we would never need more than ~log_2(n) such numbers in the representation. So this representation is as compact as the usual binary system? At 01:08 PM 7/10/2006, Michael Reid wrote:
In an analogy with Zeckendorf (Fibonacci) number systems, can every positive integer be expressed as a _sum_ of _distinct_ (positive) primes ?
If not, what is the smallest integer not so expressible?
For this purpose, I'll allow "1" as a "prime", although I suspect it's only needed a constant number of times.
yes, with your convention of considering 1 to be prime. you've already shown how to do the first few cases. for a larger value of N , let p be the largest prime <= N . then p > N/2 , by the theorem usually called "Bertrand's postulate". express N - p as a sum of distinct "primes", and add p to the result. since p > N - p , the primes in this sum are distinct.
it is probably easy to modify this argument to show that 1 is only needed a few times (twice?)
mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
franktaw＠netscape.net -
Schroeppel, Richard