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

1
vote
0answers
19 views

Strategies to find the commonality of a set of prime numbers

I have a set $E$ of prime numbers that are the error results of a test. I would like to isolate them at least partially, so I am trying to find a non basic commonality between them. UPDATE: As ...
0
votes
1answer
35 views

Find the lowest value of $x$ so that $x \in (A \setminus B)$

Let $A$ and $B$ be two sets for which the following applies: $A = \{x: \text{GCD(}x,12) = 1\}$ $B = \{x: x\ \text{is a prime}\}$ Find the lowest value of $x$ so that $x \in (A \setminus B)$. $x \in ...
2
votes
1answer
27 views

for which values of the pair of integers $(n,k)$ is $p(n,k) =1+\frac{2^{k}-1}n$ is prime?

let $p(n,k)= 1+\frac{2^{k}-1}{n}$ for a positive integer $n,k$ -for which values of the pair of integers $(n,k)$ : $p(n,k)$ is prime ? Any help is very welcom .Thank you
4
votes
1answer
41 views

Sum of reciprocals of primes diverges

I can show that $$\log(\zeta (s)) = \sum _{p\in\Bbb P} \frac{1}{p} + R(s)$$where $$R(s) = \sum _{m\geq 2} \sum_{p\in\Bbb P} \frac{1}{m} \frac{1}{p^{ms}}$$ where $\Bbb P$ is the set of all primes, ...
2
votes
1answer
62 views

Can the expression $6^{2n} - 25$ be a prime for all $n \geq 2$?

Can the expression $6^{2n} - 25$ be a prime for any $n \geq 2$? My attempt to solve the problem: No, it cannot. $6^{2n} - 25 = (6^{n})^{2} - 25 = (6^{n})^{2} - 5^{2} = (6^{n} + 5)(6^{n} - 5)$ And ...
1
vote
0answers
89 views

Conjecture: for even n without primitive roots modulo n, the set of $m \in Max(ord_n(k))$ contains one pair of primes $p_1+p_2=n$ (Goldbach)

Conjecture: for those n even numbers that do not have primitive roots modulo n ,$Pr(n)$, the set $M(n)$ of those $k$ having a maximum multiplicative order $ord_n(k)$ contains at least a pair of primes ...
0
votes
2answers
83 views

How to find the greatest prime number that is smaller than $x$? [duplicate]

I want to find the greatest prime number that is smaller than $x$, where $ x \in N$. I wonder that is there any formula or algorithm to find a prime ?
0
votes
0answers
16 views

Is there a match between this modified prime pi function and the Log integral function?

Table T is defined as through the properties that accumulated row sums give prime numbers, while accumulated column sums give composite numbers. ...
0
votes
1answer
23 views

Set theory, intersection of two sets

We have the set $D$ which consists of $x$, where $x$ is a prime number. We also have the set F, which consists of $x$, belongs to the natural numbers (positive numbers $1, 2, 3, 4, 5,\dots$) that is ...
1
vote
0answers
42 views

Is the Ulam Spiral just a coincidence?

I was messing around with the Ulam spiral because I was a little skeptical on it having any actual relevance. I noticed that if you lay out the spiral and then circle all the even numbers, it displays ...
2
votes
2answers
90 views

Prove an inequality of Prime Numbers

The problem on which I am currently stuck is, Is it true that, $$x+y< \dfrac{p_{\pi(x)}+p_{\pi(y)}+p_{\pi(x)+1}+p_{\pi(y)+1}-2}{2}$$ for all sufficiently large $x$ and $y$, $x+y$ is a prime ...
2
votes
1answer
24 views

Cyclic consecutive zeros of binary sequence with prime length

I found a feature that if $N>5$ is a prime, and $M \triangleq \frac{N-1}{2}$ is also a prime, then we will always have a binary sequence $x_1,\ldots, x_N$ with $L=\frac{N-1}{2}$(or ...
16
votes
2answers
270 views

Geometric mean of prime gaps?

The arithmetic mean of prime gaps around $x$ is $\ln(x)$. What is the geometric mean of prime gaps around $x$ ? Does that strongly depend on the conjectures about the smallest and largest gap such as ...
1
vote
1answer
33 views

A Problem on the Prime Counting Function $\pi(x)$

Let $\pi(x)$ denotes the number of primes less than or equal to $x$. Also suppose that for some fixed $N$ we have $\pi(x+y)\ge\pi(x)+\pi(y)$. The problem is, Show that the equality in the above ...
0
votes
0answers
36 views

Least pair of numbers having at least $k$ distinct prime factors

Consecutive numbers with less than $k$ prime factors? shows that for every $k$, there is a pair $(n/n+1)$, such that $n$ and $n+1$ both have at least $k$ distinct prime factors. The object is to ...
1
vote
1answer
39 views

A question on Primes in Arithmetic Progression

We know that an arithmetic progression has to have a composite number since there are arbitrarily large gaps between primes. But I was wondering whether the following construction is possible: Can ...
4
votes
2answers
42 views

A Mertens-like product over primes

MathWorld's page Prime Products gives the 'related result' (7) to Mertens' theorem: $$ \lim_{n\to\infty}\log p_n\prod_{k=1}^n\frac{1}{1+1/p_k}=\frac{\pi^2}{6e^\gamma}. $$ Does this identity have a ...
3
votes
2answers
61 views

Set and subsets link by prime numbers

I have a bit idea to solve this problem for small $n$ by programation but I think for $n>100$ I will need maths to help me. My problem is : Let S be the set of prime numbers less than n. Find ...
3
votes
1answer
61 views

Has this approximation $0.41468250985111166$ a name?

William Hughes calculated on WolframAlpha the expression $$ \sum_{n=1}^{\infty} \frac{1}{2^{\operatorname{prime}(n)}} $$ and got the approximate value $0.41468250985111166$. If one enters this value ...
2
votes
1answer
18 views

Sequences formed by integer evaluations of polynomials modulo $ p^{k} $, where $ p $ is a prime number and $ k \in \Bbb{N} $.

I have the following question. Let $ p $ be a prime number and $ k $ a positive integer. Let $ (a_{n})_{n \in \Bbb{Z}} $ be a two-way sequence in $ \Bbb{Z} / p^{k} \Bbb{Z} $. Then is it true that ...
1
vote
0answers
41 views

Primes with the first $k$ digits of the solution of the equation $e^{-x^2}=x$

Let $s$ be the solution of the equation $e^{-x^2}=x$ The first $1000$ digits are : ...
36
votes
5answers
781 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 ...
0
votes
0answers
20 views

Primality radius and quadratic reciprocity law

Given an integer $n>1$, I say that $r$ is a primality radius of $n$ if both $n-r$ and $n+r$ are primes. Goldbach's conjecture asserts that every integer greater than $1$ admits a primality radius. ...
2
votes
1answer
44 views

How to compute Dirichlet densities?

I need to calculate the Dirichlet density of the set of primes $p$ of the form $p = n^2 +1$ (in fact show it is zero), but I have no idea how to go about it. My definition of Dirichlet density of a ...
1
vote
1answer
34 views

Mathematical terminology for primes $(q+1)/2$ such that $q$ is also prime

So I know that if both $p$ and $2p + 1$ are primes, then $p$ is a Sophie Germain prime from the Prime Glossary. My question is this: How do we call a prime $r=(q+1)/2$ such that $q=2r-1$ is also ...
4
votes
0answers
37 views

Number of squarefree numbers and the Basel problem

Who discovered/proved that there are about $$ \frac{x}{\zeta(2)} $$ squarefree numbers up to $x$, or (roughly) when was this first known? Today I think this is considered 'obvious', but I don't know ...
1
vote
1answer
27 views

Is there a probabilistic prime test with time complexity $log^p (p\lt 1)$?

My question is: Is there a (possibly probabilistic) prime test with sub-logarithmic runtime complexity? Is it possible to construct one? I have found the following complexities for the most common ...
3
votes
2answers
42 views

$\forall n\ /\ \not\exists$ {primitive roots modulo n}: if $\ Max(ord_n(k))+1 \mid n\ $ then $\ Max(ord_n(k))+1\ $ is prime?

When a number $n$ does not have primitive roots modulo n, $Pr(n)$, it is possible to generate the set $M$ of those numbers $m$ whose order $ord_n(m)$ is the maximum multiplicative order of $k$ in ...
23
votes
3answers
2k views

How to force prime numbers into a line?

Inspired by an article on Prime Spiral and Hough transform I tried to analyze patterns created by plotting numbers on spiral (Archimedean?). $$x = \cos( angle ) * radius$$ $$y = \sin( angle ) * ...
0
votes
1answer
110 views

Gaps between primes: bounds - a question of possibilty

Let $n$ be any given natural number. Let $p$ be the very next prime greater than $n$. Let $b$ be the bound for the prime gap above $n$. Here, the bound is strictly the limit from $n$ to $p$, meaning ...
0
votes
0answers
16 views

system of congruency prime solutions

If you have a system of congruency and you have the solution space. Is there criteria to determine if there is a prime in the solution space and if yes is there a better way to find them instead of ...
0
votes
1answer
30 views

If $N\equiv 1\pmod 4$ does then follow that $p\equiv q\equiv 1\pmod 4$

$N = pq$ is the product of two primes. If $N\equiv 1\pmod 4$, does then follow that $p\equiv q\equiv 1\pmod 4$ ?
2
votes
1answer
90 views

Special representation of a number

How can I check, if a number $n$ can be representated by $$pq+rs$$ where $p,q,r,s$ are pairwise different prime numbers with the same number of digits. For example, $$105153899965560312960 = ...
3
votes
1answer
29 views

Matrix with prime entries and largest possible determinant

Let $n\ge 1$ be a natural number. Arrange the first $n^2$ primes in a $n\times n$-matrix, such that the determinant becomes as large as possible. What is the largest possible determinant and which ...
13
votes
2answers
342 views

Euler's Totient function $\forall n\ge3$, if $(\frac{\varphi(n)}{2}+1)\ \mid\ n\ $ then $\frac{\varphi(n)}{2}+1$ is prime

While I was studying Euler's Totient function, $\varphi(n)$, I stumbled upon the marvelous book "Index to Mathematical Problems, 1980-1984" By Stanley Rabinowitz. In this page of the book (link to ...
4
votes
0answers
138 views

About the total number of twin primes in the vicinity of twin primes

Just for curiosity's sake, I did a test regarding twin primes, and I have doubts about the meaning of the results. Test: calculation of ${\pi_2}$(n) and the twin primes density in the vicinity of ...
4
votes
1answer
48 views

Is there a counterexample? $\forall p \in \Bbb P\ ,\ p\gt 61\ ,\ \exists\ r1,r2\ \in \{\ Primitive\ Roots\ Modulo\ p\ \}\ /\ r1+r2 = NextPrime(p)$

This is the weirdest thing I have observed so far! Take the set of Primitive Roots Modulo p (link to definition here) of a prime number $p$, $Pr(p)$. For those primes $p \gt 61$ there is always a pair ...
0
votes
0answers
21 views

Counting the number of elements $x$ between $p$ and $p^2$ where lpf$(x(x+2))=7$

Let $p > 7$ be any prime. Let $f_7(p)$ be a function that counts the number of elements $x$ where $p < x < p^2$ and lpf$(x(x+2))=7$ where lpf is the least prime factor. It has been ...
3
votes
2answers
245 views

Fastest way to find if a given number is prime

Given a random number, what would be the quickest possible way of finding out whether it was prime? Obviously, one could just iterate through the number in order to see if it was divisible by ...
22
votes
6answers
5k views

Efficiently finding two squares which sum to a prime

The web is littered with any number of pages (example) giving an existence and uniqueness proof that a pair of squares can be found summing to primes congruent to 1 mod 4 (and also that there are no ...
3
votes
0answers
107 views

Conjecture concerning sums of reciprocals of largest prime factors

Let $x$ be an integer, $r(x)$ the reciprocal of the largest prime factor of $x$. Let $f(n) = \sum_{k=1}^{n-1} r(k) r(n-k)$ for which $k$ and $(n-k)$ are coprime. For $n = 3 \dots 10$, $f(n) = ...
2
votes
3answers
84 views

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

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

Prove or disprove $\frac{\left(2^{p}-2\right)}{p}\ \in \Bbb N, \forall\, p,\, prime$

Apologies in advance for poor formatting, not completely accustomed to typeset. What I ask is any non-particular value p, with one condition that it is prime, for which to disprove the following ...
-6
votes
3answers
116 views

Is this the real reason why 1 is not prime? [duplicate]

Divisibility by 1 is misleading as it does not divide a number into smaller parts. If divisibility by 1 is disallowed, then: The Unit: A whole number that is indivisible. Prime: A whole number that ...
3
votes
1answer
48 views

Is this reasoning correct for average prime gap?

Since \begin{align} &\operatorname{li}(n)\sim\Pi (n)\equiv\sum _{k=1}^{\lfloor \log (n)\rfloor } \frac{\pi \left(n^{1/k}\right)}{k}\\ \end{align} then the average gap for \begin{align} ...
0
votes
0answers
48 views

Looking for a function which can serve as an upper bound to a count of the the pairs (x)(x+2) that have a given least prime factor?

Let $p \ge 7$ be a prime. Let $z > p$ also be a prime. Let $f_p(z)$ be the number of elements $x$ such that $z \le x < z^2$ and the least prime factor of $x(x+2) = p$ I am trying to find ...
0
votes
0answers
46 views

Solve an equation of the prime counting function

The problem is, Find all the positive integral values of $x$ for which we have, $$\pi(p_n-x)=\pi(p_{n+1}-x-1)$$where $\pi(x)$ denotes the number of primes not exceeding $x$. I don't know where ...
0
votes
1answer
30 views

Notation about factors

What is the name (if there is one) of the "full factorization representation" of a number, in which also the powers of the factors are (recursively) decomposed until all the numbers used in the ...
0
votes
4answers
2k views

Co Prime Numbers less than N

I need to find all the numbers that are coprime to a given $N$ and less than $N$. Note that $N$ can be as large as $10^9.$ For example, numbers coprime to $5$ are $1,2,3,4$. I want an efficient ...
2
votes
2answers
51 views

prime number problem:

How can I show that; For any prime $p,$ there exist $u, v\in\mathbb{N}\setminus{\{p\}}$ ( and depend on $p$) such that $\color{Purple}{p\mid uv}$ and both ...