Prime numbers are natural numbers not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

learn more… | top users | synonyms

0
votes
0answers
37 views

Why does $\frac{x^n}{n^x}$ stop growing at the approximate value of $\pi (n)$?

I noticed while playing around with these functions that $n^x$ will start slow and then speed up really fast in its growth rate. While $x^n$ grows more slowly, but faster than $n^x$ at the start. ...
5
votes
2answers
74 views

Proving the irrationality of the concatenation of the $n$th powers of primes

Note: The apostrophes are meant to separate different groups of digits. Like, $0.{1^2}'{2^2}'{3^2}'{4^2}'\cdots=0.14916\cdots$. I wasn't able to come up with something better. It is easy to show ...
5
votes
1answer
75 views

Is (73, 37) the only pair of reversible primes (p, q), s.t. p=2q-1?

In addition to being probably the only Sheldon Cooper prime, $73$ is a reversible prime $p$ (or emirp), such that its reverse is $q=(p+1)/2$. It is not hard to see that all other reversible primes ...
0
votes
2answers
62 views

Proof that every positive integer has at most one prime factor greater than it's square root?

I read the statement in the title somewhere but I can't find any proof. For a positive integer $n$, why can't there be 4 numbers $a, b, c, d$ ($b$ and $d$ are prime) for which $a < \sqrt{n} < ...
1
vote
1answer
35 views

Why hash table size is prime? [closed]

In computer science, the size of the hash table is recommended to be prime. What is the property of prime number that makes it recommended to be the size of hashtable?
-3
votes
0answers
44 views

If $p$, $q$, and $r$ are all odd primes, which of $p^2-q^2+1$, $pqr+3$, and $(p+2)(r+2)+1$ can be prime? [closed]

If $p$, $q$, and $r$ are all odd primes, which of the following might also be a prime? a) $p^2-q^2+1$ b) $pqr+3$ c) $(p+2)(r+2)+1$
-1
votes
1answer
59 views

Prove that $n^m+x$ is not prime generally if $n+x$ is (in $\Bbb N$)

If $n + x$ with $n, x \in \Bbb N$ is prime, is it possible to prove generally, that $n^m + x$ with $n, x, m \in \Bbb N$ is not prime for at least one $m$? If yes, how can this be done? EDIT: There ...
2
votes
0answers
36 views

Legendre symbol identity

I try to solve the following problems ($p$ is an odd prime) Find the sum $$\sum_{a=1}^{p-1}a \cdot \left (\frac{a}{p} \right)$$ Find the sum $$\sum_{a=1}^{p-1} 2^a \cdot \left (\frac{a}{p} \right)$$ ...
1
vote
3answers
39 views

Product of first $n$-th prime power integers $+ 1$

I was just playing with prime numbers and then I accidentally found this pattern. Let $p_1\cdot p_2\cdot p_3\cdots p_n$ is the product of first $n$-th prime power integers. Prove that: $p_1\cdot ...
2
votes
1answer
55 views

Besides 1 and 11, is $\sum_{i=0}^n 10^i$ composite for every $n\in \mathbb{N}$?

Given a number consisting of digits all equal to 1 in base 10 and not equal to 1 or 11, is it necessarily composite? I know that 11 is the smallest non-trivial counter-example, but I would like to ...
37
votes
5answers
848 views

Is ${F_{n}}^2 - 28$ always a composite number?

The problem is as follows: Prove or disprove that if ${F_{n}}$ is $n$-th Fibonacci number, and $n>5$, than $${F_{n}}^2 - 28$$ cannot be a prime. I came across this problem accidentally ...
2
votes
1answer
63 views

Primes that are approximately twice other primes

Are there infinitely many pairs of primes of the form $p,2p-1$? What about $p,2p+1$?
10
votes
2answers
224 views

Proof of infinitude of prime elements?

All proofs of infinitude of primes which I know of essentially prove that there are infinitely many irreducible elements of $\Bbb Z$, and with this goal in mind we can very easily extend this proof to ...
1
vote
3answers
49 views

Fermat primality test $\gcd$ condition and carmichael numbers

Consider the following quote (I read similar thing in a couple of sources but this one illustrates the issue I'm having): By Fermat's Theorem if $n$ is prime, then for any $a$ we have $a^{n-1} = 1 ...
2
votes
0answers
31 views

Equivalent conjecture to Goldbach's conjecture

I'm reading a paper regrading the basis orders. In that paper, I met with the following statement: $$3(\mathbb{P}\cup\{0 \})=\mathbb{Z}_{\geq 2}$$, Which, by definition, states that primes form ...
0
votes
1answer
73 views

Is an algorithm to find all primes up to $n$ that runs in $O(n)$ time fast?

I kindly ask you if it is useful or fast for a prime number generator to run in $O(n/3)$ time? I believe I have a way to generate all $P$ primes up to $n$, quickly and neatly, in $P$ comparisons and ...
1
vote
1answer
91 views

Is the product of adjacent primes of the form $36x^2-1$?

If $p$ and $q$ are primes such that $p-q=2$, will $pq=36x^2-1$ be always true for some natural number $x$?
3
votes
1answer
1k views

Are there infinitely many Mersenne primes?

known facts : $1.$ There are infinitely many Mersenne numbers : $M_p=2^p-1$ $2.$ Every Mersenne number greater than $7$ is of the form : $6k\cdot p +1$ , where $k$ is an odd number $3.$ ...
0
votes
1answer
20 views

What's the condition for (x+kp) and pq being coprime?

Suppose $p$ and $q$ are large primes and $N=pq$. $x$ is an arbitrary integer in $\mathbb{Z}_p$ and $k$ is a random integer. Then what is the condition for $k$ (suppose $x$ is fixed) such that ...
1
vote
1answer
43 views

Lunchroom Question: primes adding up to counting numbers?

Our lunchtime group got into another math related discussion. I apologize in advance if this isn't a rigorous question, as none of us are professional mathematicians. This is the question: Is it ...
3
votes
0answers
84 views

What is the least prime $p$, such that $[p-1000,p+1000]$ does not contain a prime $\ne p$?

I am looking for the least prime number $p$, such that the interval $[p-1000,p+1000]$ contains no prime except $p$. In other words, the prime nearest to $p$ has a distance $>1000$ to $p$. I found ...
5
votes
1answer
96 views

Is $\lim_{n\to \infty} \frac{np_n}{\sum_{i=1}^n p_i} = 2$ true?

Noob here. I was playing around with primes in JavaScript and I found that if I divide the nth prime times n to the sum of primes up to n, I get closer to 2 for each n going to infinity: $$\lim_{n\to ...
4
votes
1answer
72 views

Is the relation $P(n) \sim \frac{1}{2^n}$ already known?

Apologies in advance if there is a violation of rules/laws here, as I am not a mathematician. $$ \begin{align} \lim_{n\to\infty} \left( \frac{\pi^{n}}{\zeta(n)}P(n) \right)^{\frac{1}{n}} &= ...
2
votes
1answer
50 views

Solving $x = c\times \ln(x)$

How to solve $x = c\times \ln(x)$ where c is some constant? I'm trying to figure out how to solve the prime number theorem for x, given the number of primes.
1
vote
1answer
29 views

Are the Bernoulli denominators always divisible by these corresponding primes?

I was wondering whether it has been proven/disproven yet or at least conjectured that the bernoulli denominator of $B_{2n}$ is divisible by $2n+1$ if and only if $2n+1$ is prime? If not, must the ...
1
vote
1answer
23 views

Is the value of $c$ in $\prod_{i=1}^{n}\frac{p_i}{p_i-1}<e^c \cdot (\log p_n) \cdot(1+\frac{1}{\log_2p_n})$ known?

I Recently read this paper by Rosser and Schoenfeld (http://projecteuclid.org/download/pdf_1/euclid.ijm/1255631807) In Theorem 8, corollary 1, they state: $$\prod_{i=1}^{n}\frac{p_i}{p_i-1}<e^c ...
2
votes
0answers
34 views

Finding primes using the Fibonacci sequence in modular form

I was wondering if the following is already a known result in mathematics. I have tested it and it seems to work every single time. If I write the Fibonacci sequence in $\bmod (a)$ form and it ...
1
vote
1answer
39 views

Estimates for $1/\zeta(s)$

Recently I am reading Stein's Complex Analysis, and he is going to prove the prime number theorem after estimating the value $1/\zeta(s)$. However, I don't understand the technical details of the ...
5
votes
5answers
86 views

Decomposing an integer into primes raised to different powers

The number $711000000$ can be written as $79^1 \times 2^6 \times 3^2 \times 5^6$. How are these numbers found? I guess the more general question is - given $n \in \mathbb Z $, how can you ...
1
vote
1answer
39 views

Induction Proof - Primes and Euclid's Lemma

I'm having some trouble with this proof. Here's the question: Use mathematical induction and Euclid's Lemma to prove that for all positive integers $s$, if $p$ and $q_1, q_2, \dotsc, q_s$ are prime ...
4
votes
2answers
44 views

Is there a Divisibility Metric for Numbers?

Both prime numbers and highly divisible numbers have a common characteristic: divisibility. The former are divisible by as few lower numbers as possible, and the latter by as many as possible, like ...
4
votes
1answer
59 views

number of primes of the form |$n^2 - 6n + 5$|?

How can I find the number of primes of the form $|n^2 - 6n + 5|$ where $n$ is an integer? Through trial and error, I have found $n = 6$ (this one is obvious), and $2$. Are there any more, and what is ...
5
votes
1answer
171 views

Conjectured compositeness tests for $N=k \cdot 2^n \pm c$

How to prove that these conjectures are true ? Definition : $\text{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)~ , \text{where}~ m ...
1
vote
2answers
127 views

Primality of $2^{255}-19$

I need a test for primality that I apply to $2^{255}-19$ (which is claimed to be prime) and certify to be correct with the ACL2 theorem prover. This means that I must be able to code the test in ...
-1
votes
0answers
38 views

Concatenating the first semiprimes to get a semiprime

The first semiprime numbers are $4,6,9,10,14,15,...$ once alternate them in order from the first semiprime, we see that $46, 469, 469101415$ are also semiprimes(!). After this the largest I've found ...
-3
votes
1answer
70 views

Missing prime numbers ending in 7. [closed]

Every tenth prime number $29, 71, 113,173... $Up to the 26th such number ($1657 $a Cuban number) ends in a $1, 3 or 9;$ but none end in$ 7.$ What is the probability of this? Also there are three ...
0
votes
1answer
53 views

Something related to carmichael numbers.

$a^{n - 1} = 1 \bmod n$ for any prime $n$ and any $a$ prime to $n$. Yet there exists composite $m$ such that $a^{m-1} = 1 \bmod m $ for all $a$ relatively prime to $m$; $m$ being a Carmichael number, ...
37
votes
3answers
1k views

Small primes attract large primes

$$ \begin{align} 1100 & = 2\times2\times5\times5\times11 \\ 1101 & =3\times 367 \\ 1102 & =2\times19\times29 \\ 1103 & =1103 \\ 1104 & = 2\times2\times2\times2\times ...
1
vote
1answer
52 views

On an estimation of binomial coefficient

On page 14 of the book 'Proofs from THE BOOK', there is an estimation presented as: $$\binom{2n}{n}\le \prod_{p\le \sqrt{2n}}\ 2n. \prod_{\sqrt{2n}<p\le \frac{2}{3}n}\ p. \prod_{n<p\le 2n}\ p, ...
-1
votes
0answers
33 views

Lifting quadratic residues

Let $p$ be an odd prime. Show that if $q$ is a quadratic residue modulo $p^x$ for some $x > 0$, then $q$ is a quadratic residue modulo $p^{x+1}$. We have $x^2=q \pmod {p^x}$, and $x^2-q=m ...
8
votes
3answers
73 views

Does the sum of reciprocals of primes congruent to $1 \mod{4}$ diverge?

Let $P$ be the set of primes $p$ greater than $3$ such that $p\equiv1 \pmod{4}$. Does the following sum converge or diverge? $$ \sum_{p\in P}\frac{1}{p} $$
7
votes
0answers
202 views

The effect of roots of Dirichlet's $\beta$ function condenses to $\frac12\left(1+ie^{i2\pi\frac{p}4}\right)$

With the help of Raymond Manzoni and Greg Martin I was able to derive an explicit formula for the number of primes of the form $4n+3$ in terms of (sums of) sums of Riemann's $R$ functions over roots ...
3
votes
1answer
91 views

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

Conjecture : $$\left\{\sum\limits_{\begin{array}{c}k=1\\k\in\mathbb{Z}\end{array}}^nk \ |\ n\in\Bbb Z\right\} \cap \left\lbrace ...
8
votes
1answer
190 views

Surprising behavior of Leibniz formula for Pi (as Euler product)

I wrote a program to compute successive approximations of Pi using the following Euler product: π/4 = (3/4)*(5/4)*(7/8)*(11/12)*(13/12)... in which the ...
6
votes
2answers
2k views

Finding a point on Archimedean Spiral by its path length

I've been curious about Archimedean Spirals and their relations to Sacks Spirals and prime numbers. I would like to draw some visualizations of the points with a given distance from the center, ...
2
votes
1answer
59 views

connection between odd primes and a certain q-series

I posed a conjecture about odd primes and a certain q-serieshere.I thought it would be more appropriate ,if I could ask the converse of the aforementioned problem . Is $p$ an odd prime iff ...
1
vote
0answers
33 views

What is this quantity?

I wonder whether there is a closed form for $$-\sum_{k=1}^{\infty}\frac{\Delta^{k}\pi(x)}{k!}(-x)_k$$ where $\pi(x)$ is the prime-counting function and $(x)_k$ is the falling factorial. In other ...
3
votes
3answers
113 views

Is a prime to the power of a fraction always irrational?

Let $p$ be a prime number and let $x$ be a fraction, i.e. $x \in \mathbb{Q} \setminus \mathbb{N}$. It seems to be the case that $p^x$ is always irrational. How do I prove this?
1
vote
0answers
54 views

On $p^{\log_q n}$, where $p$ and $q$ are distinct primes

Let $p,q$ be distinct primes, $n>1$ an integer with $\log_q n $ irrational. It was, and probably still is, a conjecture that $p^{\log_q n}$ is non-integer. What progress has been made towards it?
7
votes
2answers
326 views

Showing unique prime factorization in first-order logic?

Suppose I have the symbols $\{\neg, \rightarrow, =, <,\cdot, \leftrightarrow,\land, \lor \}$ and functions $Div(x,y)$ ($x$ divides $y$), $Prime(x)$ true if $x$ is a prime, and domain $\mathbb{N}$. ...