Questions where prime numbers play a key-role, such as: questions on the distribution of prime numbers (twin primes, gaps between primes, Hardy–Littlewood conjectures, etc); questions on prime numbers with special properties (Wieferich prime, Wolstenholme prime, etc.). This tag is often used as a ...

learn more… | top users | synonyms

2
votes
2answers
297 views

Primes as uncorrelated random variables [on hold]

The heuristic justification section of the Wikipedia article about Goldbach's conjecture says that the argument that suggests that the number of twin primes below $x$ should be roughly ...
14
votes
3answers
2k views

A variant of Goldbach Conjecture

I'm asking if this variant of weak Goldbach's Conjecture is already known. Let $N$ be an odd number. Does there exists prime numbers $p_1$, $p_2$ and $p_3$ such that $p_1+p_2-p_3=N$? Ideally, can we ...
8
votes
0answers
160 views
+50

Small quotients of smooth numbers

Assume that $N=2^k$, and let $\{n_1, \dots, n_N\}$ denote the set of square-free positive integers which are generated by the first $k$ primes, sorted in increasing order. Question: what is a good ...
8
votes
2answers
833 views

divisible by all standard prime numbers

This question is about prime numbers in nonstandard models of Peano Arithmetic. Every such model looks like N+AxZ, where A is a dense linear order without end points. There are many nonstandard ...
6
votes
0answers
220 views

Can integers be distorted to make primes more regular?

Given a set $P$ of real numbers $\ge 1$, define the gap among different products in $P$ as $$g(P) = \inf \big\{\prod_{i=1}^n p_i^{a_i} - \prod_{i=1}^n p_i^{b_i} \mid p_i\in P;\,\, p_i\ne p_j \,\text{ ...
1
vote
0answers
128 views

Generalization of Little Fermat Theorem for a particular $a$ and perfect shuffles

I'm looking for the smallest $n\in \mathbb{N}$ that solves the following equation: $$2^n=1 \mod m$$ For an odd $m$. I know that Little Fermat Theorem and Euler Totient give me a solution but they ...
-4
votes
2answers
293 views

Brocard's problem [closed]

According to Brocard's problem $$x^{2}-1=n!=4!*(5+1)(5+2)...(5+s)$$ here,$(5+1)(5+2)...(5+s)=\mathcal{O}(5^{r}),4!=k$. So, $$x^{2}-1=k *\mathcal{O}(5^{r})$$ Here, $\mathcal{O}$ is Big O ...
-1
votes
0answers
75 views

Semiprime number theorem with small prime factor

Hardy & Wright, Theorem 437 gives a nice asymptotic for $k$-almost primes less than $x$. Can we say anything if we restrict one of the prime factors of our almost prime to having a small prime ...
3
votes
1answer
83 views

What is the Complexity Class of the “Function Variant” of the Integer Factorization Problem?

I've been reading up a lot Prime Factorization and it's complexity, including a fair number of questions on this very site. However, I still feel there is a question still left unanswered. So, ...
2
votes
0answers
104 views

Infinite sums with Mobius Inversion : can we have uniform convergence of inversion formula?

My question is on Mobius inversion formula convergence/properties when used with infinite sums of function. Lets consider (on $\mathbb{R}^{+}$): $$S(x)= \sum\limits_{n=1}^{\infty} f(nx)$$ We call ...
2
votes
1answer
321 views

Can you find squares in this class?

For a problem I am working over, I would like to prove that numbers of the following type are not squares $p(l^4+6l^2m^2-3m^4)$ where $p,l,m$ are integers an $p$ prime. I have already found various ...
7
votes
1answer
370 views

Which kind of subsets of primes one needs to generate a positive ratio of the natural numbers?

Not knowing elementary number theory well, I ask this one, which is not very clear to answer, rather I am looking for some results around this question or known theorems. The problem is the following: ...
0
votes
0answers
79 views

Polynomial congruences with respect to a large prime (power)

Suppose that $f(x) \in \mathbb{Z}[x]$ is a polynomial of degree $d$ such that for all primes $p$, there exists $x_0 \in \mathbb{N}$ such that $p^2 \nmid f(x_0)$. Further, suppose that $f$ is ...
5
votes
1answer
286 views

A set of integers whose factorial can be written as a product of two factorials

I am trying to collect informations concerning the set $$\mathcal{A}=\left\{n\in\mathbb{N} \mid (\exists k,l\in\{2,3,\dots,n-2\})(n!=k!l!)\right\}.$$ It seems not much is known about the set ...
-3
votes
1answer
273 views

Asymptotic formula for $\prod_{p\leq x} (1-p^{-1})$ [closed]

Does there exists a good asymptotic formula for $$A(x) := \prod_{p\leq x}(1-\frac 1p).$$ By using a heuristic argument one can guess: $$A(x) \sim \frac{1}{2\,\mathrm{ln}(x)}.$$ Here is the ...
1
vote
0answers
143 views

Density of numbers whose prime factors all come from a fixed congruence class

Let $q$ be a positive integer greater than one, and let $a$ be an integer such that $\gcd(a,q) = 1$. Define $$D(a,q) = \{n \in \mathbb{N} : p | n \Rightarrow p \equiv a \pmod{q} \}.$$ Do we know the ...
2
votes
1answer
300 views

Is anything like $\phi(n)>\dfrac n{e^\gamma\log\log n},\ \sigma(n)<e^\gamma n\log\log n$ known/conjectured for the generalizations of these functions?

Is anything like $\dfrac n{\phi(n)}<\dfrac{\sigma(n)}n<e^\gamma\log\log n$ known/conjectured for the generalizations of these functions? Let $n=p_1^{a_1}\cdots p_t^{a_t}$ be the canonical prime ...
7
votes
2answers
551 views

Most dense subset of numbers that avoids arbitrarily long arithmetic progressions

The famous Green-Tao theorem says that there exist arbitrarily long sequences of primes in arithmetic progression. I am wondering: How dense can a subset $S \subset \mathbb{N}$ be and still avoid ...
2
votes
0answers
89 views

Best constant for Maier's theorem?

Maier proved that, for fixed $\lambda>1,$ $$ \limsup_{x\to\infty}\frac{\pi(x+\log^\lambda x)-\pi(x)}{\log^{\lambda-1}x}>1 $$ and in particular $$ \limsup_{x\to\infty}\frac{\pi(x+\log^\lambda ...
8
votes
2answers
702 views

What is known about primes of the form x^2-2y^2?

David Cox's book Primes of The Form: $x^2+ny^2$ does a great job proving and motivating a lot of results for $n>0$. I was unable to find anything for negative numbers, let alone the case I am ...
2
votes
1answer
268 views

$n^3 | \sum_{i=1}^{n-1}\binom{n}{i}^2$ => $n | \sum_{i=1}^{n-1}\binom{n}{i}$?

For $n\in \mathbf{N}$ is $$n^3 \text{ divides } \sum_{i=1}^{n-1}\binom{n}{i}^2=\binom{n}{1}^2+\cdots +\binom{n}{n-1}^2$$ impling $$n \text{ divides } ...
0
votes
0answers
87 views

logarithmic integral question

Define: $\operatorname{li}(x)=\int_{0}^{x}\dfrac{1}{\log(t)}\operatorname{d}t$. When does the following statement fail? With $\theta = 1 + \frac{1}{\operatorname{li}(x)}$, for $x \ge x_0$, ...
0
votes
0answers
148 views

Does the Euler product converge at $s=1$ for the Dirichlet $L$ function?

For the Riemann Zeta function, the Euler product converges on $\{Re(s)=1\}$ except at $s=1$.The zeta series diverges everywhere on $\{Re(s)=1\}$. But the $L$ series converges on $\{Re(s)>0\}$. What ...
16
votes
1answer
753 views

Primes that are sums of two squares with constraints on the squares

It is well known that there are infinitely many primes of the form $a^2+b^2$ (namely all primes congruent to $1$ modulo $4$). On the other hand, Euler raised the problem as to whether there are ...
5
votes
1answer
347 views

Generating primes with floor of a polynomial $[p(n)]$

Is there a polynomial $p(x)$ with real coefitients and degree at least one that $[p(n)]$ for everey natural number like $n$ be a prime? If yes, what is such a polynomial $p(x)$ and if no, how to ...
11
votes
0answers
296 views

Word complexity of primes mod 4

For an infinite binary word $w$, the word complexity $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the ...
4
votes
2answers
628 views

How to calculate the sum of remainders of N?

I'm trying to sum the remainders when dividing N by numbers from 1 up to N $$\sum_{i = 1}^{N} N \bmod i$$ It's easy to write a program to evaluate the sum if N is small in O(N) but what if N is large ...
4
votes
0answers
268 views

Is there a hidden symmetry in the prime numbers distribution?

Under Goldbach's conjecture, let's consider once again the map $r_0\colon n\mapsto r_{0}(n)$ such that $r_{0}(n)$ is the smallest non negative integer $r$ such that both $n-r$ and $n+r$ are prime. ...
1
vote
2answers
585 views

Has this formula about prime gaps already been conjectured and/or proven?

While playing around with prime gaps, I found out that the following formula seems to be a rather good approximation of the ratio $\dfrac{p_{b}-p_{a}}{b-a}$ where $a<b$ are positive integers: ...
1
vote
0answers
434 views

Is $ a^2b^2-ab-ap$ a perfect square for suitable $a,b\in \mathbb{Z}^+$?

Consider the expression $$ a^2b^2-ab-ap\qquad (a,b\in \mathbb{Z}^+), $$ where $p\equiv1\pmod{4}$. Question. For every prime $p\equiv1\pmod{4}$ do there exist $a,b\in\mathbb{Z}^+$ such that ...
2
votes
1answer
244 views

Prime Number Theorem on APs under various conjectures

I'm trying to find the best asymptotic expansions for $\pi(x; a, q)$ in various states: Unconditionally we have \begin{equation} \pi(x; a, q) = \frac{\operatorname{li(x)}}{\phi(q)} + O\left(x ...
2
votes
0answers
371 views

A “Take a Square Root When You Can” conjecture related to the prime factorization

I would tend to think that the following has already been investigated. But as implied from the title, I have no idea how to even start looking for it. Let $P_n$ denote the sum of the squares of ...
1
vote
0answers
47 views

closed form for a series with binomials and primes

does the series $\sum_{n=0}^\infty p^n \binom{x}{p^n}$ have a closed form ? ($p$ prime) this is a special case of $\sum_{n=0}^\infty p^n \left(\sum_{k=p^n}^{p^{n+1}-1}a_k\binom{x}{k}\right)$ with the ...
2
votes
1answer
522 views

Conjecture on the square root of the sum of the squares of the prime factors of a number

Let $A_{n}$ denote the square root of the sum of the squares of the prime factors of $n$. For example, $A_{60}=\sqrt{2^2+2^2+3^2+5^2}\approx6.48$. I have recently made the following observations: ...
10
votes
1answer
618 views

Divergence of a series similar to $\sum\frac{1}{p}$

Suppose we start with $k$ primes $p_1,p_2,\ldots ,p_k$ (not necessarily consecutive) and a residue class for each prime $r_1,r_2,\ldots ,r_k$. We denote the least integer not covered by the arithmetic ...
8
votes
3answers
551 views

Is $n = p-q$ equivalent to Goldbach's Conjecture?

One open conjecture is that every even integer greater than two is the difference of two primes. (Some superficial discussion here.) Goldbach's conjecture states that every even integer greater than ...
5
votes
1answer
553 views

Any way to prove Prime Number Theorem using Hyperbolic Geometry? [closed]

The prime number theorem says that the density of prime numbers is inverse as the number of digits of $n$: $$\displaystyle \frac{\{1 \leq k \leq n : \text{ prime } \}}{n} \approx \frac{1}{\log n}$$ ...
2
votes
2answers
408 views

Prime divisors of $p^n+1$

Let $p$ be a rational prime and $n$ be a positive integer. It can be easily deduced from Zsigmondy's theorem that $p^n+1$ has a prime divisor greater than $2n$ except when $(p,n)=(2,3)$ or ...
5
votes
1answer
366 views

Ruth-Aaron triples, etc

A Ruth-Aaron pair is two numbers $(n,n+1)$ such that their sum of prime factors is equal, counting repeated prime factors. (The name refers to Hank Aaron's 715 homeruns surpassing Babe Ruth's 714!) So ...
3
votes
0answers
426 views

Two (strictly related) proofs by induction of inequalities

This is a question I originally asked on MSE, receiving no answer, even with a bounty (which expired) on it. Therefore I am crosslinking in order to prevent duplication of effort: see here for the ...
3
votes
1answer
269 views
4
votes
1answer
200 views

Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$ such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...
1
vote
1answer
133 views

Cardinality of the prime divisor set of a k-power sum

Let $a_{1},\dots,a_{n}$ be positive natural numbers ($n>2$) such that $a_{i}\neq a_{j}$ if $i\neq j$. I want to prove that $$ \left\lvert \left\{ p \text{ prime} \; : \; p \mid \sum_{i=1}^n ...
12
votes
1answer
531 views

Is there a known primitive recursive upper bound on the nth “Zhang prime”

(This question is pure curiosity. Feel free to close it if you feel it is not appropriate for mathoverflow.) In 2013 Zhang showed that there are infinitely many pairs of primes which are less that ...
2
votes
1answer
387 views

Have there been any new developments in the Firoozbakht conjecture? [duplicate]

Let $(p_{n})_{n∈ℕ}$ be the sequence of consecutive primes. In P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag, 1995, page 185, the author says: A new conjecture by F. ...
4
votes
0answers
133 views

The divisors of $p-1$ and high-degree residues modulo $p$

Here is a somewhat more explicit version of a question that I asked a while ago. Suppose that $p$ is a prime of the form $p=2n(n+1)+1$, with a positive integer $n$. Can every odd prime divisor of ...
0
votes
0answers
73 views

Lucasian Primality Criterion for Specific Class of $k \cdot 2^n-1$

Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers . Conjecture Let $N=k\cdot 2^n-1$ such ...
2
votes
0answers
96 views

counting irreducible factors

In How hard is it to compute the number of prime factors of a given integer? a question was asked on computing number of prime factors of an integer. Suppose we have a polynomial $f(X)\in \Bbb Z[X]$ ...
4
votes
1answer
185 views

References to proofs of upper and lower bounds on the number of coprimes in an interval?

On the first page of the article "When the sieve works", the authors present upper and lower bounds for $S(T,T+x;\mathcal{E})$; the number of integers in the interval $(T,T+x]$ that are coprime to all ...
2
votes
0answers
118 views

Siegel Walfisz Theorem for algebraic number fields

Is there a generalization of the Siegel Walfisz to algebraic number fields? This has been done for the prime number theorem in the prime ideal theorem.