**4**

votes

**3**answers

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

**13**

votes

**2**answers

617 views

### Odd-bit primes ratio

Say that a number is an odd-bit number if
the count of 1-bits in its binary representation is odd.
Define an even-bit number analogously.
Thus $541 = 1000011101_2$ is an odd-bit number,
and $523 = ...

**8**

votes

**0**answers

744 views

### Would the following conjectures imply $\lim\inf_{n\to\infty}p_{n+k}-p_{n}=O(k\log k)$?

Assume Goldbach's conjecture. Then for every $n\ge 2$ there exists at least one non-negative integer $r\le n-2$ such that both $n+r$ and $n-r$ are primes. Let's write $r_{0}(n):=\inf\{r\le n-2, ...

**0**

votes

**1**answer

463 views

### A possible consequence of Dirichlet's theorem about primes in arithmetic progression

EDIT : I copy-paste the beginning of a previous question since Gerry Myerson suggested this question should be self-contained.
"let's consider a composite natural number $n$ greater or equal to $4$. ...

**4**

votes

**1**answer

481 views

### Lower bound for a prime gap occurring infinitely often

In his striking paper of may 2013, Zhang showed the existence of an even integer $g\lt 70,000,000$ such that $g$ is a prime gap occurring infinitely often. What is the best unconditional lower bound ...

**19**

votes

**7**answers

3k views

### Asymptotic density of k-almost primes

Let $\pi_k(x)=|\{n\le x:n=p_1p_2\cdots p_k\}|$ be the counting function for the k-almost primes, generalizing $\pi(x)=\pi_1(x)$. A result of Landau is
$$\pi_k(x)\sim\frac{x(\log\log ...

**34**

votes

**2**answers

2k views

### A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself

Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...

**65**

votes

**6**answers

7k views

### Does Zhang's theorem generalize to $3$ or more primes in an interval of fixed length?

Let $p_n$ be the $n$-th prime number, as usual:
$p_1 = 2$, $p_2 = 3$, $p_3 = 5$, $p_4 = 7$, etc.
For $k=1,2,3,\ldots$, define
$$
g_k = \liminf_{n \rightarrow \infty} (p_{n+k} - p_n).
$$
Thus the twin ...

**21**

votes

**4**answers

2k views

### Why so difficult to prove infinitely many restricted primes?

I wondered whether there were an infinite number of
palindromic primes written in binary (11, 101, 111, 10001, 11111, 1001001, 1101011, ...)
and quickly discovered that it is unknown
(OEIS A117697).
...

**14**

votes

**4**answers

1k views

### Arithmetic progressions without small primes

The following question came up in the discussion at How small can a group with an n-dimensional irreducible complex representation be? :
Is it known that there are infinitely many primes p for which ...

**6**

votes

**2**answers

643 views

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

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

**10**

votes

**1**answer

418 views

### Primes dividing $2^a+2^b-1$

From Fermat's little theorem we know that every odd prime $p$ divides $2^a-1$ with $a=p-1$.
Is it possible to prove that there are infinitely many primes not
dividing $2^a+2^b-1$?
(With ...

**7**

votes

**1**answer

992 views

### What would be the consequences of $\displaystyle{\lim\inf_{n\to\infty}p_{n+k}-p_{n}\sim k\log k}$?

The question is in the title: what would be the number theoretic consequences if we managed to establish the conjectured asymptotic equality $\displaystyle{\lim\inf_{n\to\infty}p_{n+k}-p_{n}\sim k\log ...

**7**

votes

**2**answers

630 views

### What is the lower bound for highly composite numbers?

if $x=d(n)$ is the number of divisors of $n$, what is the tightest lower-bound for $n$ only given $x$?
http://en.wikipedia.org/wiki/Highly_composite_number

**6**

votes

**3**answers

301 views

### Quadratic residues and nonresidues of arbitrary patterns

Let $p_1, p_2, \dotsc, p_n$ be distinct primes, and let $\epsilon_1, \epsilon_2, \dotsc, \epsilon_n$ be an arbitrary sequence of $1$ and $-1$.
There is an integer $a$ such that $\left( \frac{a}{p_1} ...

**5**

votes

**1**answer

986 views

### Number field analogue of the Goldbach Conjecture

Is there a generalization of Goldbachs conjecture for prime ideals in number fields?

**11**

votes

**1**answer

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

**6**

votes

**0**answers

634 views

### Would the following conjectures imply Cramer's conjecture?

Assume Goldbach's conjecture. Then for every $n\ge 2$ there exists at least one non-negative integer $r\le n-2$ such that both $n+r$ and $n-r$ are primes. Let's write $r_{0}(n):=\inf\{r\le n-2, ...

**3**

votes

**0**answers

325 views

### Metric on the set of subsets of the rational primes

Note: this is a revision of an earlier post. It was kindly pointed out that my initial proposed metric was in fact not a metric, so this is a revised version.
I was thinking how to say that two sets ...

**3**

votes

**2**answers

373 views

### Are all counterexamples of OEIS A226181 both Poulet numbers and Proth numbers?

OEIS A226181:
3, 5, 7, 11, 13, 17, 19, 23, 29, 37, 41, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101, 103, 107, 113, 131, 137, 139, 149, 163, ...
Primes $p$ ...

**3**

votes

**3**answers

519 views

### Estimate for products of integers that are relatively prime with $N$

Let $N$ be a positive integer. Are there known estimates for the product of all numbers that are smaller than $N$ and relatively prime with $N$? One can assume that $N$ is free of squares, if this ...

**81**

votes

**4**answers

29k views

### Philosophy behind Yitang Zhang's work on the Twin Primes Conjecture

Yitang Zhang recently published a new attack on the Twin Primes Conjecture. Quoting Andre Granville :
“The big experts in the field had
already tried to make this approach
work,” Granville ...

**93**

votes

**5**answers

5k views

### Gaussian prime spirals

Imagine a particle in the complex plane, starting at $c_0$, a Gaussian integer,
moving initially $\pm$ in the horizontal
or vertical directions. When it hits a Gaussian prime, it turns left ...

**40**

votes

**1**answer

8k views

### Is the Green-Tao theorem true for primes within a given arithmetic progression?

Ben Green and Terrence Tao proved that there are arbitrary length arithmetic progressions among the primes.
Now, consider an arithmetic progression with starting term $a$ and common difference $d$. ...

**34**

votes

**4**answers

3k views

### Why could Mertens not prove the prime number theorem?

We know that
$$
\sum_{n \le x}\frac{1}{n\ln n} = \ln\ln x + c_1 + O(1/x)
$$
where $c_1$ is a constant. Again Mertens' theorem says that the primes $p$ satisfy
$$
\sum_{p \le x}\frac{1}{p} = \ln\ln ...

**38**

votes

**4**answers

9k views

### How hard is it to compute the number of prime factors of a given integer?

I asked a related question on this mathoverflow thread. That question was promptly answered. This is a natural followup question to that one, which I decided to repost since that question is answered.
...

**48**

votes

**4**answers

4k views

### Strange (or stupid) arithmetic derivation

Let us consider the following operation on positive integers: $$n=\prod_{i=1}^{k}p_i^{\alpha_i} \qquad f(n):= \prod_{i=1}^{k}\alpha_ip_i^{\alpha_i-1}$$ (Is it true that if we apply this operation to ...

**27**

votes

**4**answers

3k views

### What is exceptional about the prime numbers 2 and 3?

Admittedly this question is vague. But I hope to convey my point. Feel free to downvote this.
Permit me to define prime number the following way:
A number $n>1$ is a prime if all integers $d$ ...

**39**

votes

**1**answer

3k views

### Are the primes normally distributed? Or is this the Riemann hypothesis?

Forgive my very naive question. I know next to nothing about number theory, but I'm curious about the state of the art on the distribution of primes.
Let $\mathrm{Li}(x)$ be the offset logarithmic ...

**31**

votes

**1**answer

3k views

### Integers not represented by $ 2 x^2 + x y + 3 y^2 + z^3 - z $

EDIT, 9 March 2014: when I asked this in 2010, I did not have the courage of my convictions, and so did not ask for an if and only if proof, as Kevin Buzzard quite properly pointed out. Such problems ...

**39**

votes

**1**answer

2k views

### Exploding primes

Suppose every prime $n$ could "explode" once.
An explosion results in $\lfloor \alpha \ln n \rfloor$ particles being
uniformly distributed over the integers in a range $n \pm \lfloor \beta \ln n ...

**14**

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

**32**

votes

**4**answers

2k views

### Are There Primes of Every Hamming Weight?

That is, for every integer $n \in \mathbb{Z}_{>0}$ does there exist a prime which is the sum of $n$ distinct powers of $2$?
In this case, the Hamming weight of a number is the number of $1$s in ...

**17**

votes

**6**answers

2k views

### Question on consecutive integers with similar prime factorizations

Suppose that $n=\prod_{i=1}^{k} p_i^{e_i}$ and $m=\prod_{i=1}^{l} q_i^{f_i}$ are prime factorizations of two positive integers $n$ and $m$, with the primes permuted so that $e_1 \le e_2 \cdots \le ...

**16**

votes

**6**answers

9k views

### Examples of prime numbers in nature [closed]

Finding primes in signals is seen as a sign of some kind of intelligence - see e.g. the role of primes in the search for extraterrestrial life (see e.g. here). This is because there are relatively few ...

**15**

votes

**1**answer

868 views

### Sums of primes that are themselves prime

I'm not a math expert so this may be a trivial question; if $p_i$ is the $i$-th prime, let:
$$S(n) = \sum_{i=1}^n p_i$$
be the sum of the first $n$ primes and
$$P(n) = | \{1 \leq i \leq n \mid ...

**9**

votes

**6**answers

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

**24**

votes

**3**answers

2k views

### Composite pairs of the form n!-1 and n!+1

It's well known that the numbers of the form $n!\pm1$ are not always prime. Indeed, Wilson's Theorem guarantees that $(p-2)!-1$ and $(p-1)!+1$ are composite for every prime number $p > 5$.
Is ...

**14**

votes

**1**answer

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

**11**

votes

**1**answer

2k views

### The Green-Tao theorem and positive binary quadratic forms

Some time ago I asked a question on consecutive numbers represented integrally by an integral positive binary quadratic form. It has occurred to me that, instead, the Green-Tao theorem may include a ...

**6**

votes

**6**answers

952 views

### Sequences equidistributed modulo 1

Let $\alpha$ be any positive irrational and $\beta$ be any positive real. We have the following results.
H. Weyl (1909): The fractional part of the sequence $\alpha n$ is equidistributed modulo 1.
...

**18**

votes

**2**answers

1k views

### The prime numbers modulo $k$, are not periodic

Consider the sequence of prime numbers: $2,3,5,7, \cdots$. Now reduce this sequence modulo $k$ for some integer $k > 2$. Show the resulting sequence is not periodic. :
EDIT: As noted in the ...

**12**

votes

**1**answer

575 views

### Analytic lower bounds on the first sign change of pi(x) - li(x)?

There have been many results on the first sign change of $\pi(x)-{\mathrm{li}}(x)$: among others, Lehman, te Riele, Bays & Hudson, Demichael, Chao & Plymen, and most recently Saouter & ...

**7**

votes

**2**answers

436 views

### A non-standard ergodic limit

Suppose $T$ is an ergodic measure-preserving transformation on a measure space $(X,\Sigma,\mu)$, and $f\in L^1(\mu)$. Does the limit
$\lim_{X\to\infty} \pi(X)^{-1}\sum_{p\leq X} f(T^{p}x)$
exist ...

**9**

votes

**2**answers

681 views

### Random pseudoprimes vs. primes

(Edit. What I called "pseudoprimes" are known as "Cramér random primes" in the literature,
of which I was unaware.)
Say that a set $S$ of natural numbers is a set of pseudoprimes if they
are (a) ...

**6**

votes

**3**answers

816 views

### a question for the prime counting function

A famous inequality that has been proved by J.B. Rosser and L. Schoenfeld says that
$\frac{n}{\ln n-1/2}$ < $\pi(n)$<$\frac{n}{\ln n-3/2} , n\ge 67$.
Using this inequality we can prove ...

**22**

votes

**1**answer

1k views

### Permutations of $(Z/pZ)^*$

Let $p$ be a prime integer, and let $(\mathbb Z/p\mathbb Z)^*$ be the set of non-zero elements of $\mathbb Z/p \mathbb Z$.
Denote by $S((\mathbb Z/p \mathbb Z)^*)$ the group of permutations of ...

**9**

votes

**2**answers

1k views

### Abel summation of the alternating series of primes?

Consider the ordinary generating function of the sequence of primes ($2+3x+5x^2+7x^3 + ...$); by the ratio test and the prime number theorem, its radius of convergence is $1$. Thus, we might well ask ...

**6**

votes

**3**answers

959 views

### Values where infinite products of primes and composites are equal

Highly grateful for your help/steers on the following question (at the end):
Take the infinite product:
$$\displaystyle T(s) = \prod _{n=2}^{\infty } \left( \dfrac{{n}^{s}} {{n}^{s}-1}\right)$$
for ...

**6**

votes

**2**answers

1k views

### Can a number be factored quickly, given the sum of its prime factors?

This is perhaps most naturally phrased as a promise problem. Given numbers $n$ and $s$, where $s$ is the sum of the prime factors of $n$ (distinct or with multiplicity; I imagine both variants will ...