**7**

votes

**3**answers

686 views

### Bound the error in estimating a relative totient function

Let $n=p_1^{e_1}\cdots p_k^{e_k}$ be an integer with $k$ prime factors. We know that the number of integers less than $n$ and coprime to it is
$$\Phi(n)=n-\sum_i\frac n{p_i}+\sum_{i \lt j}\frac ...

**5**

votes

**3**answers

401 views

### Quantitative and elementary proofs of the Prime Number Theorem

I would like to know two things: one, whether the best quantative bounds in the Prime Number Theorem are still basically those given by the Vinogradov-Korobov zero-free region? and two, whether there ...

**3**

votes

**2**answers

230 views

+50

### Relative-totient function (2nd attempt)

Let $\Lambda(x,y)$ be the count of totatives of $x$ that are less than or equal to $y$.
I am asking for the following result to be verified, (particularly the final proposal), I have found no ...

**1**

vote

**0**answers

99 views

### A Question on Chinese Remainder Theorem [on hold]

Let $p_1,p_2,\ldots,p_n$ be odd primes.
Let $y$ be the unique solution of the Chinese Remainder Problem ( $0 \le y < m$, $ m = p_1\cdot p_2 \cdots p_n$)
$ y = \frac{p_1-1}{2} \text{ mod } (p_1) ...

**4**

votes

**0**answers

153 views

### Any ways to Simplify Daboussi's Argument for Prime Number Theorem?

One strategy to prove the Prime number theorem involves removing some factors:
$$ \limsup_{x \to \infty} \underbrace{\frac{1}{x}\sum_{n \leq x} \mu(x)}_{\color{red}{A}}\leq
\prod_{p \leq y} \left( 1 ...

**2**

votes

**1**answer

430 views

### Green-Tao theorem for 1-central numbers

This question came to my mind this afternoon while trying to figure out a possible way to tackle de Polignac's conjecture, which states that every even positive integer can be written as the ...

**11**

votes

**7**answers

2k views

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

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 ...

**15**

votes

**2**answers

3k views

### Does the equation $241+2^{2s+1}=m^2$ have a solution?

Let $p$ be a prime congruent to $1$ mod. 8.
If $p= 17$ one has : $p+ 8 = 5 ^2$.
If $p= 41$ one has : $p+ 8 = 7 ^2$.
If $p= 73$ one has : $p+ 8 = 9 ^2$.
If $p= 89$ one has : $p+ 32 = 11 ^2$.
If ...

**6**

votes

**1**answer

320 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 ...

**8**

votes

**1**answer

562 views

### Estimate on radical of $2^n \pm 1$

Not sure if this belongs to MO or not.
Are there any lower bound on radical of $2^n \pm 1$ (Recall that radical of integer $rad(k)$ is a product of primes which divide integer $k$)?
As an example If ...

**-1**

votes

**1**answer

579 views

### What is wrong with this counterexample to primality test assuming GRH? [closed]

From SMOOTH NUMBERS: COMPUTATIONAL NUMBER THEORY AND BEYOND Andrew Granville pp.13-14:
2j. Lenstra’s polynomial time test as to whether an integer that is conjecturally prime, is rigorously ...

**2**

votes

**1**answer

371 views

### A general question about strictly non-palindromic numbers

For a definition, see the wikipedia page: http://en.wikipedia.org/wiki/Strictly_non-palindromic_number
So according to the wikipedia page, under properties, all strictly non-palindromic numbers with ...

**-3**

votes

**2**answers

286 views

### The number of totatives to the nth primorial, in an interval shorter than the nth primorial

(The notation of this question will be improved over the next few days, sorry for the lack of clarity at the moment.)
Can, and if so when can, we determine the amount of natural numbers which are ...

**5**

votes

**1**answer

399 views

### An elementary lower bound on the number of primes

Recall the second Chebyshev function: $$\psi(x) = \sum_{p \leq x} \lfloor \log_p x \rfloor \log p$$ where $x$ is a positive integer, and $p$ runs over all primes $\leq x$.
In a hunt for an ...

**1**

vote

**0**answers

89 views

### A deterministic and explicitly described walk which is like random ones

Consider a sequence $(X_i)_{i = 1}^{\infty}$ which every $X_i$ is $-1$, $0$ or $+1$ and lets define $Y_n = X_1+ \cdots + X_n$. We say the sequence $(X_i)_{i = 1}^{\infty}$ a Good Sequence if $Y_n \neq ...

**22**

votes

**3**answers

2k views

### Constructing prime numbers

The classical proof of the infiniteness of prime numbers is to take the $k$ first prime numbers $p_1,\ldots,p_k$, then to form
$$n_k:=1+p_1\cdots p_k.$$
Then $n_k$ has a prime factor, which is none of ...

**17**

votes

**3**answers

1k views

### Prime factorization “demoted” leads to function whose fixed points are primes?

Let $n$ be a natural number whose prime factorization is
$$n=\prod_{i=1}^{k}p_i^{\alpha_i} \; .$$
Define a function $g(n)$ as follows
$$g(n)=\sum_{i=1}^{k}p_i {\alpha_i} \,$$
i.e., exponentiation is ...

**5**

votes

**1**answer

196 views

### Bounds re Asymptotic Formula for the Sum of Largest Prime Factors

I have a reference request related to the result :
$\sum_{n=2}^{x} P(n)$ ~ $\frac{\pi^2}{12}\frac{x^{2}}{log(x)}$ as $x \rightarrow \infty$
where $P(n)$ is the largest prime factor of the positive ...

**22**

votes

**2**answers

1k views

### Proof for new deterministic primality test

Claim:
Let $p$ be a positive prime. Let $n \in \left\{1, 2, 3, ...\right\}$. Then $N =
p\cdot 2^n+1$ is prime, if and only if it holds the congruence $3^{(N-1)/2} \equiv \pm1\ ($mod $N)$.
If the ...

**-1**

votes

**1**answer

161 views

### Number of different factors of given size in primorial

Let $b_n$ be number of bits in product of all primes from $1$ to $n$ which is approximtely $b_n\approx n$.
What is the approximate number of distinct factors with number of bits ...

**0**

votes

**0**answers

60 views

### Is this sufficient condition for primality of numbers of special form of practical interest?

The best variant of deterministic primality is of complexity $ \tilde{O}(\log^{6}(n))$.
For large $n$, this is significantly worse than $O(\log{n})$.
Appears to me paper p. 16
gives sufficient ...

**6**

votes

**2**answers

422 views

### What is wrong with this deterministic algorithm efficiently generating large primes?

According to PolyMath
(Strong) conjecture. There exists deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in ...

**0**

votes

**1**answer

301 views

### Proof that $p_{n+1}-p_n\gg\frac{\log \log \log p_n}{\log \log \log \log p_n} \log {p_n}$ [closed]

I cannot find a proof of this theorem. May anyone assist?
$p_{n+1}-p_n\gg\frac{\log \log \log p_n}{\log \log \log \log p_n} \log{p_n}$

**8**

votes

**2**answers

780 views

### Update for 2015: least prime of form nq+1, with q prime?

I have received a complaint about my 2011 answer
least prime in a arithmetic progression
which, indeed, gives conflicting reports about this:
given a prime $q,$ what can we say about an upper ...

**7**

votes

**2**answers

1k views

### least prime in a arithmetic progression

Hello
Here I want to consider the simplest arithmetic progression $n\equiv 1\pmod{q}$ where $q$ is a prime. Is it true that we can find a prime $p\leq q^2$ in this arithmetic progression?
This ...

**2**

votes

**2**answers

246 views

### Asymptotics of the least common multiple of the first natural numbers

What is $$ \limsup_{n \to \infty} \frac{\log(\mathrm{lcm}(1,2, \dots, n))}{n} \ \ ?$$

**3**

votes

**1**answer

95 views

### Upper bound for OEIS A076689 “Smallest k such that k*p#+1 is prime”?

OEIS A076689
Is defined as smallest integer $a(n)=k$ such that $k n\#+1$ is prime,
where $n\#$ is primorial, the product of the first $n$ primes.
Lower bound appears $1$, the primorial primes.
...

**0**

votes

**1**answer

129 views

### Primes in simultaneous arithmetic progressions

Suppose we're given four positive integers $a$, $b$, $c$, $d$ such that $a$ and $b$ are coprime, and $c$ and $d$ are coprime. Is there a non-negative integer $k$ such that both $ak+b$ and $ck+d$ are ...

**2**

votes

**2**answers

179 views

### Finiteness of number of consecutive primes with gap $4$

Assuming Riemann Hypothesis Hardy showed primes $3\bmod 4$ are more common than primes $1\bmod 4$ https://en.wikipedia.org/wiki/Riemann_hypothesis#Consequences_of_the_generalized_Riemann_hypothesis.
...

**6**

votes

**0**answers

366 views

### Prime gap counts in short intervals

Since it is conjectured that the twin prime count at $n\sim2 C_2\ \frac{n}{\log^2n},$ where $C_2 = \prod_{p\ge 3} \frac{p(p-2)}{(p-1)^2} = 0.66016 18158 \dots,$ it follows that the twin prime count ...

**6**

votes

**1**answer

293 views

### Negative coefficient in an almost cyclotomic polynomial

Let $a,b,c,d$ be four prime numbers. We set the polynomial :
...

**7**

votes

**0**answers

163 views

### Are there an infinite number of twin semiprimes?

A semiprime is a number that is the
product of two (possibly equal) primes.
Define twin semiprimes (my terminology) as two consecutive numbers both semiprimes.
For example, $(57,58)$ are twin ...

**4**

votes

**0**answers

248 views

### Conjectured new primality test for Mersenne numbers

How to prove that this conjecture about a new primality test for Mersenne numbers is true ?
Definition: Let $M_{q}=2^{q}-1 , S_{0} = 3^{2} + 1/3^{2} , \ and: \ S_{i+1} = S_{i}^{2}-2 \pmod{M_{q}}$
...

**10**

votes

**2**answers

707 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
...

**13**

votes

**2**answers

377 views

### Are there open problems for primes which are known for probable primes?

Define "probable prime" (PP) to be natural $n>1$ satisfying $2^{n-1} \equiv 1 \pmod{n}$ or $n=2$.
Probable primes are the union of the primes and base two pseudoprimes.
This definition is much ...

**2**

votes

**2**answers

280 views

### Primality criteria for specific class of Wagstaff numbers ?

I asked this question on mathstackexchange but didn't get any answer .
Definition :
Let $W_p$ be a Wagstaff number of the form :
$W_p=\frac{2^p+1}{3}$ , with $p\equiv 1 \pmod 4$
Next , ...

**11**

votes

**1**answer

870 views

### Order of magnitude of $\sum \frac{1}{\log{p}}$

Question: What is the order of magnitude of the following sum?
$$ \sum_{\substack{p<n\\\text{$p$ prime}}} \frac{1}{\log{p}} $$
Additional information: Since
$$ ...

**0**

votes

**0**answers

132 views

### The maximum lengthed sequence of prime numbers with certain conditions (denizens)

Definition - Denizen
A sequence $\lbrace a_k \rbrace$ is a denizen if all of it's members are prime numbers, i.e $a_0, a_1, ... a_n \in \mathbb{P} $; and it satisfies the following condition;
...

**7**

votes

**1**answer

317 views

### Bounded gaps between primes in arithmetic progressions

Has Zhang's work on bounded gaps between primes been extended to the following theorem?
For any arithmetic progression $an+b,\gcd(a,b)=1$, there is a constant $H$ (depending only on $a$) such that ...

**24**

votes

**6**answers

4k views

### Explicit formula for Riemann zeros counting function

I've often seen it stated (in vague terms) that there's a Fourier duality between the set of prime numbers and the set of nontrivial Riemann zeta zeros.
Because there are various explicit formulae ...

**1**

vote

**1**answer

34 views

### Prime constant graphicial representation [closed]

I have something to check. It is about prime constant (I don't know if it is officially so called), but it is created on following way. We start with binary point number represenation. Zero followed ...

**7**

votes

**0**answers

248 views

### Intersection between the sums of the first positive integers, primes and non primes

Is the following conjecture true ?
$$\left\{\sum\limits_{\begin{array}{c}k=1\\k\in\mathbb{Z}\end{array}}^nk \ |\ n\in\Bbb Z\right\} \cap
\left\lbrace ...

**-4**

votes

**1**answer

201 views

### Gauss-Wantzel theorem, Fermat primes and solvability of S_n [closed]

Gauss-Wantzel theorem asserts that a polygon with $n$ sides is constructible if and only if $n$ is a product of a power of $2$ and distinct prime Fermat numbers, where the Fermat number of index $k$ ...

**2**

votes

**4**answers

286 views

### Prime divisors of values of a polynomial on an infinite set

This may be a well known problem:
Let $f$ be a polynomial with integer coefficients. Is it possible for the set of prime divisors of values of $f$ on an infinite set of integers, to be finite?
I ...

**10**

votes

**0**answers

345 views

### Between Fermat's primes and the twin primes

Let me start with a curiosity. The integers $11,13,17,19$ are prime numbers, and $101,103,107,109$ are prime as well. One might wonder whether there is another occurrence where $10^m+1,10^m+3,10^m+7$ ...

**4**

votes

**1**answer

379 views

### Unexpectedly prime rich cubic polynomial

We got a cubic polynomial which is unexpectedly prime rich.
Let $f(x)=29160 x^3 + 30132 x^2 + 8046 x + 643$ and
$\pi_f(n)$ the number of primes values of $f(x)$ for $x \in [1,n]$.
Let ...

**0**

votes

**0**answers

79 views

### Polynomial identities for congruent numbers and Bunyakovsky's conjecture

Bunyakovsky's conjecture states that polynomial with integer coefficients
takes infinitely many prime values unless there are obvious reasons not
to.
It appears to imply something about polynomial ...

**14**

votes

**1**answer

552 views

### A Collatz-like function that bifurcates on primes

This is likely piling one mystery on another, but ...
I was exploring a function $f(n): \mathbb{N} \mapsto \mathbb{N}$ defined as follows:
$$
f(n) =
\begin{cases}
n^2 & \text{if} \;n \;\text{is ...

**44**

votes

**3**answers

7k views

### Is a “non-analytic” proof of Dirichlet's theorem on primes known or possible?

It is well-known that one can prove certain special cases of Dirichlet's theorem by exhibiting an integer polynomial $p(x)$ with the properties that the prime divisors of $\{ p(n) | n \in \mathbb{Z} ...

**1**

vote

**0**answers

95 views

### Can someone explain some of the steps in this paper clearly?

I'm having trouble understanding the steps this paper makes to come to the conclusion $p_{f}(d) \sim e^d\sqrt{d}$
Marek Wolf, First occurrence of a given gap between consecutive primes, preprint, ...