User larry freeman - MathOverflow

A question about the second Chebyshev function $\psi(x) = \sum_{m=1}^{\infty}\vartheta(\sqrt[m]{x})$

2013-05-05T18:52:33Z

Using a simple java application, I have noticed that for $x > 25$:

$$\psi\left(\frac{x}{5}\right) \ge \psi\left(\frac{x}{3}\right) - \psi\left(\frac{x}{4}\right)$$

where:

$$\psi\left(x\right) = \sum_{m=1}^{\infty}\vartheta\left(\sqrt[m]{x}\right)$$

and

$$\vartheta\left(x\right) = \sum_{p \le x} \log p$$

As I understand it, based on the Prime Number Theorem, this inequality should be true.

Is this inequality elementary and straight forward to prove? Or is this more difficult to prove than it appears?

Thanks very much,

-Larry

Are there any interesting or lesser known proofs related to Bertrand's Postulate

2012-08-01T22:54:28Z

There are 3 standard proofs of Bertrand's Postulate:

(1) Chebyshev's original proof

(2) Ramanujan's simplification of Chebyshev's proof

(3) Erdos's proof

I recently learned about the very simple proof that if the Goldbach conjecture is true, then Bertrand's postulate follows (see here).

Does anyone know of any other proofs? There are recent proofs that extend Bertrand's postulate to show that there is always a prime in $2n$/$3n$ and $3n$/$4n$.

I am wondering if there aren't other lesser known proofs that take a different approach to establish the existence of a prime between $n$ and $2n$.

Thanks,

-Larry

What are the best known lower and upper bounds for the second Chebyshev function $\psi(x)$

2013-04-23T12:38:19Z

I was reading through Jitsuro Nagura's proof that there is always a prime between $x$ and $\frac{6x}{5}$ when $x \ge 25$.

In the paper, he uses the following bounds for the second Chebyshev function $\psi(x)$:

$$1.086x > \psi(x) > 0.916x - 6.954$$

If I apply the better upper bound from Rosser & Schoenfeld, 1962 of:

$$1.03883x > \psi(x)$$

Then Nagura's proof shows that there is always a prime between $x$ and $\frac{8x}{7}$ when $x \ge 34$.

Is this the best upper and lower bound for $\psi(x)$:

$$1.03883x > \psi(x) > 0.916x - 6.954$$

Does anyone know of any results that improve on these bounds?

Thanks,

-Larry

At what point would an elementary generalization of Bertrand's Postulate be interesting?

2013-04-11T13:58:27Z

I know that in 1952 Jitsuro Nagura was able to show that there is always a prime between $k$ and $\frac{6k}{5}$ for $k > 24$.

At what point would an improvement on Nagura's result be interesting? If an approach could show for example that for any $k$, there is a specific value $X$ which could be calculated such that for all $x \ge X$, there is a prime between $kx$ and $(k+1)x$, would this be interesting?

Or, does the Prime Number Theorem provide us enough insight that short of a proof of Legendre's Conjecture, elementary results are not very interesting at this time?

Greatest Prime Factors: For any prime p, is there an integer C such that for any x >= C, all but 1 integer in the sequence x+1, x+2, ..., x+p has a greatest prime factor > p.

2012-09-09T16:32:02Z

I apologize if this is a naive question about greatest prime factors (gpf). I was thinking about the sequence of integers where $gpf(x) \le p$ where $p$ is any prime.

Clearly, as $x$ increases, the distance $d$ between an integer where $gpf(x) \le p$ and $gpf(x+d) \le p$ increases at a seemingly every increasing rate.

For all primes $p$, does there exist an integer $C$ where if $x ≥ C$, then there is at most $1$ integer in the sequence $x+1, x+2, \dots, x+p$ has $gpf(x) \le p$

For example, if $p=2$, $C = 2$ since for any $x \ge 2$, either $x$ or $x+1, gpf(x) > 2$

Are there any theorems about a prime $p > k$ in a sequence stronger than Sylvester-Schur?

2012-11-08T15:43:45Z

Sylvester-Schur says: "if $n \ge 2k$, then there is a number in the list $n − k + 1, n − k + 2,$ ... $, n$ divisible by a prime $p > k$."

Shouldn't it also be true that if $n \ge k$, then there is a number in the list $n + 1, n + 2, $ ... $, n+k$ divisible by a prime $p > k$.

Does anyone know of a theorem that comes close to establish this or why the stronger claim is not true?

Thanks very much,

-Larry

smallest k such that highest prime factor of m(m+1)...(m+k-1) is > n if m > n.

2012-09-24T20:51:23Z

I am fascinated by this entry OEIS A213253 which lists the smallest $k$ such that highest prime factor of $m(m+1)\dots(m+k-1)$ is $> n$ if $m > n$.

The article has references to the algorithm for generating this list.

Does anyone know of any recent work analyzing the upper or lower bounds for this sequence?

Answer by Larry Freeman for Greatest Prime Factors: For any prime p, is there an integer C such that for any x >= C, all but 1 integer in the sequence x+1, x+2, ..., x+p has a greatest prime factor > p.

2012-09-10T02:54:21Z

I heard a great answer to this question based on the Thue equation.

I investigated the Thue equation and there was one point that was not clear to me. It seems to me that there are an infinite number of values that $a$ and $b$ can take. If there are an infinite number of combinations of finite solutions, then there is an infinite number of solutions. Right?

So, if I understand it, the Thue equation alone doesn't seem to work. I apologize if I am misunderstanding the classical result there.

Here's an argument that seems to work as far as I understand:

(1) For any prime $p$, there is a finite number of combinations of primes that are less than $p$.

(2) For any of these combinations there exists an integer $x$ such that if a combination is greater than $x$, then at least one of the primes that make up the combination are of a degree greater than $2$.

(3) Let $c$ be either the highest of the values $x$ from step (2) or $4p^{4}(3\prod_{p} p^{\frac{1}{2}})^3$ depending on which is higher.

(4) There is a finite number of ways that we can pair these different combinations so that we have an equation of the form $ax^3 - by^3 = c$ where $c < p$.

(5) If $a \ne b$ and $gcd(x,y)=1$, then using a result from Siegel, there is at most $1$ solution (see Theorem A in the link below).

http://matwbn.icm.edu.pl/ksiazki/aa/aa75/aa7538.pdf

(6) if $a = b$ and $a = c$, then using a result from Michael Bennett, there is at most $1$ solution. Here's the reference:

M. A. Bennett, Rational approximation to algebraic numbers of small height : the Diophantine equation $|ax^n-by^n|=1$}, J. Reine Angew. Math. 535 (2001), 1-49

http://www.math.ubc.ca/~bennett/B-Crelle2.pdf

(7) if $a = b$ and $a < c$, then the equation has a form such as:

$x^3 - y^3 = \frac{c}{a}$

This is a Thue Equation and we can conclude that there is a finite number of solutions.

(8) if $a \ne b$ and $gcd(x,y) > 1$, then it means that both combinations consist of the same prime so we have an equation of the form:

$x^m - x^n = c$

Then, as I understand it, we have a Thue equation so we can again assume that there is a finite number solutions.

I believe that covers all the possible cases.

Since, there are only a finite number of solutions, it follows that there exists an integer $c$ which is greater than all of these solutions and for all $x \ge c$, we have at most $1$ integer in the sequence where $gpc(x+i) \le p$.

Apologies for the length of this argument. I'm sure a professional mathematician such as user 631 would be able to state the argument more elegantly. :-)

Answer by Larry Freeman for Are there any interesting or lesser known proofs related to Bertrand's Postulate

2012-09-06T01:05:33Z

I found an interesting proof today that demonstrates a stronger form of Bertrand's Postulate. I hadn't seen it before:

Abstract. In this paper we give a stronger form of Bertrand's postulate and use it to prove that every positive integer, except 1, 2, 4, 6, and 9, can be written as the sum of distinct odd primes.

http://www.ams.org/journals/proc/1972-033-02/S0002-9939-1972-0292746-6/S0002-9939-1972-0292746-6.pdf

A question about the Mobius Function

2012-07-11T13:42:26Z

I have been playing around with the Möbius Function and primorials and I am finding results that I am not yet able to understand which I suspect are very elementary.

Here's the current result which is I am working through. Any help is greatly appreciated!

Let $p_k$ be any prime. Let $x$ be any integer.

It seems based on my calculations that $\sum_{i | p_{k}\#} \lfloor{\frac{(x \% i) + (p_k \% i)}{i}}\rfloor\mu(i) \ge -1$

where % is the remainder so that $5 \% 3 = 2$ and $7 \% 3 = 1$

But if we let $x,y$ be any integer, we can find that there exists $x,y$ such that:

$\sum_{i | p_{k}\#} \lfloor{\frac{(x \% i) + (y \% i)}{i}}\rfloor\mu(i) < -1$

For example:

If $x=13$, $y=23$, $p_k = 5$ , then the sum is $-2$

Is there a well known explanation for this? Thanks.

Is it true that the sum of a specific floor function of a prime = 1?

2012-06-20T22:52:58Z

I noticed that for primes $p \le 109$, the following seems to be true:

$\sum_{i | p\#}^{p\#} \lfloor{\frac{p}{i}\mu(i)}\rfloor = 1$

where $\mu(i)$ is the Mobius function.

For example:

$\frac{2}{1} + \frac{2}{2}(-1) = 1$

$\frac{3}{1} + \lfloor\frac{3}{2}(-1)\rfloor + \frac{3}{3}(-1) + \lfloor\frac{3}{6}\rfloor = 1$

and so on...

I verified this up to $p=109$ using a simple java application.

I might be making a mistake in my code or my thinking. This seems like a very surprising result to me.

Is it correct? If it is, does it stop being true for some prime? Could anyone help me to understand this result.

Thanks very much,

-Larry

Least Prime Factors: found a counting formula for a given range -- what is the standard approach?

2012-01-17T18:24:13Z

Hi Everyone,

I am a math amateur who for the past year has been working on better understanding Bertrand's Postulate, the Ramanujan Primes, and the recent expansion of Bertrand's Postulate (always a prime between 2x and 3x and always a prime between 3x and 4x) using elementary methods.

I've been working with least prime factors and primorials and I came up with a counting formula that I have not seen elsewhere. It is quite similar to the standard prime counting formula using floor functions and it is using elementary methods so it is most likely uninteresting. I hope you don't mind me posting a sketch of it here.

I am presenting it here in hopes that experts can steer me to more modern analytic methods that accomplish the same thing in a better way. I would also be interested in understanding why the new methods are superior to the elementary methods.

The counting formula accomplishes the following:

Let $p_k$ be any prime. The formula provides an exact count of the number of least prime factors greater than $p_k$ in the range $r_{start}$ (exclusive) and $r_{end}$ (inclusive).

The formula consists of $2^{k-2}$ subformulas where each subformula looks something like this:

Least Prime Factor (5 or greater) between $x_{start}$ and $x_{end}$ =

$2\lfloor\frac{x_{end}}{6}\rfloor + \lfloor\frac{(x_{end} \% 6) + 3}{4}\rfloor - 2\lfloor\frac{x_{start}}{6}\rfloor - \lfloor\frac{(x_{start} \% 6) + 3}{4}\rfloor$

where $x_{end} \% 6$ is the value congruent to $x$ modulo $6$.

Note: The above formula, for example, is the expression for finding the number of least prime factors greater than $3$ in the range $r_{start}$ to $r_{end}$.

To give another example, if I wanted to count the number of least prime factors greater than $p_{6} = 13$, then the formula consists of $2^{6-2} = 16$ subformulas where each subformula is roughly similar to the example above.

Thanks very much.

Paul Erdős and Ramanujan Primes

2011-08-22T04:24:30Z

It's easy to find Ramanujan's proof of Ramanujan primes:

Ramanujan's Proof

Wikipedia mentions that Paul Erdős also had a proof:

Wikipedia article on Bertrand's Postulate

Does anyone know the full citation for Erdős's proof that for any number $n$, there exists a prime $p$ such that for all $x \ge p$, there are $n$ primes between $x$ and $2x$?

Thanks very much,

-Larry

Least Prime Factor in a sequence of 2n consecutive integers

2011-06-21T08:10:47Z

I was thinking about consecutive integers and I wondered if anyone had done work exploring whether a sequence of $2n$ consecutive integers (i.e. 101,102,103,...,100+2n) always contains at least one integer with a least prime factor $p > n$.

I had been thinking about it for some time when I noticed this post: http://mathoverflow.net/questions/49400/question-in-prime-numbers

Using complete residue systems for $p$# and the Chinese Remainder Theorem, I noticed that it is possible to find a sequence of $38$ (2*19) consecutive integers that has only one least prime factor greater than $19$. It is also true of a sequence of $62$ (2*31) that you can find a sequence with only one least prime factor greater than $31$.

For any sequence where $n \le 23$ with the exception of $19$, there are at least two integers where the least prime factor is greater than $2$.

The fact that any sequence of $46$ (2*23) integers always has at least $2$ such integers while a sequence of $38$ (2*19) integers might just have $1$ suggested to me that there might be an elementary argument there.

I did a Google search and could find very little on least prime factors. As you can probably tell from this write up, I am an amateur very interested in learning more about number theory.

I would greatly appreciate any help that can be provided in showing me a proof or an example that there exists integers $x,n$ such that $x+1, x+2,$ ... $, x+2n$ are all divisible by some prime $p \le n$

Thanks very much

-Larry

Comment by Larry Freeman

2013-04-12T10:38:35Z

Thanks very much for the reference! I look forward to checking it out.

Comment by Larry Freeman

2013-04-11T15:33:51Z

Thanks very much. That helps. I am reviewing Ramanujan's proof of Bertrand's Postulate and I'm wondering if his approach can be applied to an arbitrary value of $k$. I'm still getting up to speed so my thoughts are very preliminary.

Comment by Larry Freeman

2013-01-11T21:28:58Z

Hi Dr. Memory, My interest in primarily in understanding the context behind the Sylvester-Schur Theorem: mathoverflow.net/questions/111823/… For example, I am especially interested in patterns like this: oeis.org/A213253 Cheers, -Larry

Comment by Larry Freeman

2012-11-08T16:32:53Z

Thanks for noticing! I just fixed it. :-).

Comment by Larry Freeman

2012-09-25T01:10:02Z

Hi Gerry, I've edited the question so that the full information is in the body. I've read through Najman's paper and also M. Bauer and M. A. Bennett, Prime factors of consecutive integers, Math. Comp., 77 (2008), 2455-2459.

Comment by Larry Freeman

2012-09-10T13:34:43Z

Thanks very much, Pauline! That really provides the additional details to help me understand Gerhard's explanation! :-)

Comment by Larry Freeman

2012-09-10T04:58:54Z

Here is the OEIS entry: oeis.org/A002072

Comment by Larry Freeman

2012-09-10T04:52:39Z

Thanks, Gerhard! I really appreciate the explanation! :-)

Comment by Larry Freeman

2012-09-10T04:42:40Z

Harpo, I hope that's better. I really appreciate your answer and your logic! I am a math amateur and I greatly value the information that I receive from experts such as yourself on this wonderful web site!

Comment by Larry Freeman

2012-09-10T04:40:42Z

I will do as you ask. I will remove your name. I meant no insult. Apologies. I really appreciated your comment about the Thue Equation! That was exactly the guidance I was looking for. :-)

Comment by Larry Freeman

2012-09-10T04:28:20Z

Hi Harpo, I meant no insult. You changed your name two times today. I thought your answer was brilliant. I willl change the user 61 to Harpo Marx immediately. Apologies. -Larry

Comment by Larry Freeman

2012-09-10T04:27:04Z

Thanks! I just read the link. It looks great: en.wikipedia.org/wiki/Stormer%27s_theorem I'll start reading up on Stormer's Theorem to better understand it!

Comment by Larry Freeman

2012-09-09T22:39:57Z

@Gerhard, Thanks very much for your comments! If I find an OEIS entry, I'll post it here.

Comment by Larry Freeman

2012-09-09T18:19:14Z

Linking to a question on a good introduction to Thue's equation: mathoverflow.net/questions/66910/…

Comment by Larry Freeman

2012-09-09T17:47:58Z

For those, like me, who were not familiar with Thue's equation, I found this paper which details how to find the finite solutions of a Thue equation: doc.utwente.nl/70433/1/Tzanakis89on.pdf