All Questions
Tagged with prime-factorization prime-numbers
831
questions
2
votes
2
answers
63
views
Is there a more efficient way to find the least prime factor?
Assuming $Q_{k} \equiv p_{k}\text{#} + 1$, my goal is to find the least prime factor of $Q_{k}$ for each integer $k = 1 \ldots 100$ . The Python program shown below tries using SymPy to do so, but ...
- 223
3
votes
1
answer
199
views
Smallest "diamond-number" above some power of ten?
Let us call a positive integer $N$ a "diamond-number" if it has the form $p^2q$ with distinct primes $p,q$ with the same number of decimal digits. An example is $N=10^{19}+93815391$. Its ...
- 85.1k
1
vote
2
answers
73
views
Expected number of factors of $LCM(1,…,n)$ (particularly, potentially, when $n=8t$)
I’m trying to prove something regarding $8t$-powersmooth numbers (a $k$-powersmooth number $n$ is one for which all prime powers $p^m$ such that $p^m|n$ are such that $p^m\le k$). Essentially, I have ...
- 1,789
1
vote
1
answer
64
views
Find the next "consecutive-prime composite number" from a given one.
Good day all. I am not a mathematician by a long shot. Please bear with me...
I am playing with "descending-consecutive-prime composite numbers" (I don't think that's the term). These are ...
- 153
3
votes
2
answers
191
views
Convergence of a product involving primes
Let $p_1, ... , p_n, ...$ be the prime numbers in order. Let $n \in \mathbb{N}$ and $q_1, ..., q_n \in \mathbb{N}$. Define
$$
P_n = \prod_{k=1}^n p_k^{q_k} \hspace{1cm} Q_n = \prod_{k=1}^n \left( p_k^{...
- 1,291
1
vote
1
answer
58
views
Distribution of perfect numbers for a semiprime
Given a semiprime with a length of 120 digits (397bit):
is it possible to meet any assumptions about perfect numbers (prime factors with same length, 199+199bit) for this number?
I have made an ...
- 121
1
vote
1
answer
146
views
Minimum $k$ for which every positive integer of the interval $(kn,(k+1)n)$ is composite
I am looking for references containing results on the minimum $k$ for which every positive integer of the interval $(kn,(k+1)n)$ is composite.
If we denote as $k(n)$ this minimum $k$ for some $n$, $k$ ...
- 1,190
0
votes
0
answers
39
views
Denjoy's Probabilistic Interpretation
Does Denjoy's Probabilistic Interpretation actually "prove" that the Mertens function ratio between numbers with odd number of distinct prime factors and even number of prime factors is 1? ...
- 39
1
vote
1
answer
94
views
Will there be infinity prime numbers of the sort $a^2 -2$ (where $a$ is odd)?
Will there be infinity prime numbers of the sort $a^2 -2$ (where $a$ is odd)?
To begin with, every odd composite number can be written as $a^2$ or as $a_{x}^2 -a_{y}^2$ as long as either $x$ or $y$ ...
- 1,405
0
votes
0
answers
67
views
Prime number $p$ such that $p+1$ has all given prime numbers as prime factor.
For given finite prime numbers set $P$,
does there exist some prime number $p$ such that
for any $\ell\in P$, $\ell\mid (p+1)$?
For example, if $P=\{2,3,7\}$, then we can take $p=41$.
In this case, $(\...
- 1,934
3
votes
3
answers
221
views
For what integers $n$ does $\varphi(n)=n-5$?
What I have tried so far: $n$ certainly can't be prime. It also can't be a power of prime as $\varphi(p^k)=p^k-p^{k-1})$ unless it is $25=5^2$. From here on, I am pretty stuck. I tried considering the ...
- 637
2
votes
0
answers
57
views
What did I get wrong in this Mobius function question? [closed]
$f(n):=\sum\limits_{d\mid n}\mu(d)\cdot d^2,$ where $\mu(n)$ is the Möbius function. Compute $f(192).$
First, I found all of the divisors of 192 by trial division by primes in ascending order:
$D=\{...
- 637
4
votes
0
answers
144
views
What are the next primes/semiprimes of the form $\frac{(n-1)^n+1}{n^2}$?
This question is inspired by this question
For an odd positive integer $n$ , define $$f(n):=\frac{(n-1)^n+1}{n^2}$$ as in the linkes question.
For which $n$ is this expression prime , for which $n$ ...
- 85.1k
1
vote
0
answers
112
views
Plot of the ratios of Goldbach pairs
Preface
I was playing around with matplotlib to generate some number sequences. I wound up looking at Goldbach pairs and manipulating them in different ways. End result was the following plots. I can'...
- 11
2
votes
1
answer
61
views
Asymptotic Approximation towards Sum of the Composite Number's Smallest Prime Factor
I wonder if there is any asymptotic approximation towards the sum of the smallest prime factor of the composite numbers which are less than $n$. This is also the sum of terms whose index is not prime ...
- 21
1
vote
1
answer
84
views
How many different squares are there which are the product of six different integers from 1 to 10 inclusive?
How many different squares are there which are the product of six different integers from 1 to 10 inclusive?
A similar problem, asking how many different squares are there which are the product of six ...
- 45
2
votes
1
answer
97
views
Show that $n$ has $2^{\omega(n) - 1}$ coprime factor pairs
I am trying to show that $n$ has $2^{\omega(n) - 1}$ coprime factor pairs. I'm pretty sure this is true but I don't see how to prove it. There is no obvious way to use induction.
Here is an example:
$...
- 3,187
2
votes
0
answers
62
views
Is my proof of the divergence of prime reciprocals valid
I tried to prove the divergence of the prime reciprocals as a challenge and I think I came up with quite an intuitive argument using Borell Cantelli, but maybe not rigorous.
For two primes $p_n>...
- 702
2
votes
0
answers
64
views
What percentage of numbers can be written as $n=p*m$ with p prime and $p>m$
What is the chance* that a random positive integer $n$ is the product of a prime $p$ and an integer $m>0$, with $p>m$
Or in other words: when $n$ has a prime factor greater than it's square root
...
- 702
3
votes
1
answer
217
views
A question about prime factorization of composite Mersenne numbers and $(2^p-2)/(2 \cdot p)$
Mersenne numbers are numbers of the form $2^p-1$ where $p$ is a prime number. Some of them are prime for exemple $2^5-1$ or $2^7-1$ and some of them are composite like $2^{11}-1$ or $2^{23}-1$.
I'm ...
- 141
2
votes
2
answers
262
views
Prime factors of $5^n+6^n+7^n+8^n+9^n+10^n$
I currently run an integer factoring project of the numbers of the form $$5^n+6^n+7^n+8^n+9^n+10^n$$ where $n$ is a non-negative integer.
Do the prime factors have a particular form as it is the case ...
- 85.1k
0
votes
0
answers
52
views
Found a relation regarding the primes, is this interesting?
Define $S_{odd}$ as all $n\in N $ where $n$ is the product of an odd number of distinct primes. Define $S_{even}$ similarly. Thus:
$$S_{odd} = \{2,3,5,...,30,42,....\}$$
$$S_{even} = \{6,10,14, ....,...
- 702
1
vote
2
answers
92
views
SemiPrime Test to determine distance between P and Q
I have two composite primes (semiprimes) where $17*641 = 10897$ and $101*107 = 10807$.
Notice that $10897$ and $10807$ are almost equal. Their square roots are $104.38$ and $103.95$ respectively. But ...
- 137
0
votes
0
answers
31
views
Form of the divisors of a number (Prime Factorization). Is this algorithm-based proof correct? [duplicate]
I am trying to proof the following result:
For a number $n$ whose prime number decomposition is $p_1^{\alpha _1} ... p_m^{\alpha _m}$. Every divisor of $n$ has the form $p_1^{\beta _1} ... p_m^{\beta ...
- 1,231
1
vote
1
answer
110
views
Open Question: For natural $n$ with prime decomposition $\prod p_i^{r_i}$, define $f(n)=\sum p_i r_i$. Find all $n$ such that $f(n)-f(n+1)=1$.
A question I created myself:
For any $n\in \Bbb{N}$, we can get $n = p_1^{r_1}\cdots p_m^{r_m}$, where $p_i$ are primes. Take $$f(n)=p_1r_1+\cdots+p_mr_m$$
Find all $n$ such that $f(n)-f(n+1)=1$
It ...
- 27
4
votes
2
answers
166
views
Asymptotics of $p_k$-adic valuation of the sum of the divisors of the $n$-th primorial
Given this product:
$$a(n) = \prod_{k=1}^{n} (1+p_k)$$
where $p_k$ is the $k$-th prime number and which can be interpreted also as the sum of the divisors of the $n$-th primorial (OEIS A054640), is ...
- 2,103
1
vote
0
answers
65
views
Distribution of the number of prime factors a large number $n$ has?
I know that a large number $n$ has probability $\frac{1}{\ln (n)}$ of having exactly 1 prime factor (i.e. it's prime). But is there any statement on the exact distribution for the number of prime ...
- 2,230
1
vote
0
answers
46
views
Can the order of a possible further Wieferich prime with respect to base $2$ be prime or a power of two?
A Wieferich prime has the property $$2^{p-1}\equiv 1\mod p^2$$ We only know two Wieferich primes $1093$ and $3511$ , a further Wieferich prime must exceed $2^{64}$.
It is conjectured that there are ...
- 85.1k
2
votes
0
answers
50
views
The number of integers less than x that have at least two distinct prime factors of bit size greater than one-third the bit size of x
Sander came out with a paper describing how to generate what he calls an RSA-UFO. Anoncoin then utilizes this and mentions that the paper proves that the probability that a randomly generated integer, ...
- 123
1
vote
1
answer
157
views
Is it correct to say that prime numbers don't exist on $\mathbb{R}$ and $\mathbb{Q}$?
A prime number is defined as: "A non invertible and non zero numer $p$ of a ring $A$ is called a prime number if any time it divides a product of two numbers, it also divides one of the factors&...
- 121
0
votes
1
answer
140
views
How to factor numbers like 8,023 manually
I was given a random 4-digit number to factor over the prime numbers. My number was 8,023. I tried applying all the divisibility rules up to 36 before giving up on them. I tried using algebra as ...
- 2,370
1
vote
1
answer
61
views
How would one show that any given prime p_i must be a factor of some (p_j - 1)? Is that a true property of primes even? [closed]
In short, what I'm asking is, if you were to go through the whole set of positive primes term by term and find for each prime p the prime factorization of (p - 1), whether all prime numbers would ...
- 19
1
vote
1
answer
104
views
Finding the (smallest) next number with the same distinct prime factors as a previous number
(Since there is no answer yet, I removed most "EDIT"'s to make the text more readable)
Today, I was trying to find a natural number $n_{2}$ such that this number has the same distinct prime ...
user1114342
1
vote
1
answer
77
views
Legendre's Conjecture and estimating the minimum count of least prime factors in a range of consecutive integers
I recently asked a question on MathOverflow that got me thinking about Legendre's Conjecture.
Consider a range of consecutive integers defined by $R(x+1,x+n) = x+1, x+2, x+3, \dots, x+n$ with $C(x+1,x+...
- 10.5k
2
votes
2
answers
127
views
The equation $175a + 11ab + bc = abc$ [closed]
Consider all the triples $(a, b, c)$ of prime numbers that satisfy the equation
$$175a + 11ab + bc = abc\ .$$
Compute the sum of all possible values of $c$ in such triples.
I could only get to the ...
- 33
0
votes
2
answers
614
views
Method to finding the number of factors [duplicate]
I've seen that the number of factors of $x$ can be found:
Prime factorising $x$
Taking each power in the factorisation and adding $1$
Multiplying these numbers together.
This results in the number ...
- 855
1
vote
1
answer
118
views
Prove that $\sqrt{-5}$ is a prime in the ring $R=ℤ[\sqrt{-5}]$.
If $R=ℤ[\sqrt{-5}]$ is a ring but not a UFD, prove that the irreducible element $\sqrt{-5}$ is a prime.
This is what I have so far.
Proof: Let $R=ℤ[\sqrt{-5}]$ be a ring but not a UFD. Since $\sqrt{-5}...
0
votes
1
answer
51
views
Difference in two products of prime factorizations
Let $\Phi(n)=\{p_1, p_2, ..., p_k\}$ be the set of prime factors of a number $n$. How does
$$
p_1(n) = \prod_{p_i\in\Phi(n) \\ 1 \le i \le k}{p_i}
$$
compare to
$$
p_2(n) = \prod_{p_i\in\Phi(n) \\ 1 \...
- 128
5
votes
2
answers
663
views
Number of maximal antichains in the set $\{1,2,3,4,5,6,...,120\}$ where the order is by divisibility relation.
Find the number of maximal antichains in the set $\{1,2,3,4,5,6,7,...,120\}$ where the order is divisibility relation. For example, $\{6,7,15\}$ is an antichain but not a maximal antichain, and $\{1\}$...
- 3,800
8
votes
2
answers
223
views
Showing that prime factors of a number is congruent to $1 \pmod 5$
I have come across numbers of the form
$$b=1+10a+50a^2+125a^3+125a^4$$
where $a$ is a positive integer.
Looking at the prime factors of $b$, I am conjecturing that all prime factors of $b$ are $\equiv ...
- 1,106
1
vote
1
answer
61
views
Set of natural numbers related to least common multiple
I have come across the following set in my research, and I am curious whether this has been studied before/if there is a reference for a related construction.
Given a natural number $n$, let $S(n)$ be ...
- 1,261
0
votes
0
answers
51
views
Find upper and/or lower bounds for the least prime $p$ such that $p^n + k$ is the product of $n$ distinct primes
Well, first of all, happy new year to everyone.
I am trying to solve the following problem: "Let $k$ be a fixed natural number. Find the least prime $p$ such that there exists a natural number $...
- 28.7k
5
votes
0
answers
305
views
Valid Elementary Proof of the Bertrand-Chebyshev Theorem/Bertrand's Postulate? [closed]
$\textbf{Theorem}$ (Bertrand-Chebyshev theorem/Bertrand's postulate): For all integers $n\geq 2$, there exists an odd prime number $p\geq 3$ satisfying $n<p<2n$.
$\textit{Proof }$: For $n=2$, we ...
- 445
1
vote
1
answer
56
views
Lets that $p_1,p_2, ...,p_\lambda>2$ be a set of prime numbers. Is there estimation for the summation of $ A=\sum_{i=1}^{\lambda}\varphi(p_i-1)$?
Lets that $p_1,p_2, ...,p_\lambda>2$ be a set of primes number greater than $2$. Is there any exact formula or estimation for the summation
$$
A=\sum_{i=1}^{\lambda}\varphi(p_i-1)
$$
- 775
-1
votes
1
answer
70
views
Suppose a, b are integers and LCM(a, b) = GCD(a, b)^2. What can be said about the prime decompositions of a and b? [duplicate]
Unsure how to approach the problem besides using the fact that the LCM(a,b) * GCD(a,b) = a*b. I see the implication that the GCD(a,b)^3 = a * b. Perhaps it means a and b are different powers of the ...
- 1
3
votes
1
answer
130
views
Numbers between powers of consecutive primes
So if we try to categorize numbers based on the number of their prime factors we would have something as following where $L_n$ is the list of numbers with $n$ prime factors.
$$
L_1 : 2, 3, 5, 7, 11, .....
- 367
0
votes
0
answers
72
views
Are there any pairs of integers that are divisible by the same primes such that adding $1$ or $2$ also keeps them divisible by the same primes?
The answer to this question shows that there are infinitely many pairs of integers $(m, n)$ such that $m$ and $n$ have the same prime factors, and $m+1$ and $n+1$ also have the same prime factors. Are ...
- 4,057
1
vote
1
answer
189
views
Are there finitely many pairs of integers that are divisible by the same primes such that adding $1$ also keeps them divisible by the same primes? [duplicate]
Integers m and n have the same prime divisors but m is not equal to n, i.e. the same primes are just raised by different powers, resulting in integers m and n. But we also know that m+1 and n+1 have ...
3
votes
1
answer
119
views
Length of this representation increases really slowly?
$$\def\'{\text{'}}\def\len{\operatorname{len}}$$
A recent Code Golf challenge introduced a "base neutral numbering system". Here I present a slightly modified version, but the idea is the ...
- 562
-1
votes
2
answers
85
views
Why does Euclid theorem fail in some cases? [duplicate]
The euclidean theorem says that if we have a limited prime numbers and we added 1 it cant be divided by any prime numbers
I notice that it work in some cases with lower number but when I added a ...
- 103