All Questions
Tagged with prime-factorization prime-numbers
831
questions
3
votes
1
answer
61
views
Approximating a number by using only a given set of prime-factors for the approximant.
Let $n \in\mathbb{N},$ and $S$ be a (finite) set of prime numbers.
I'm looking for an efficient algorithm to find the greatest $m\leq n$ such that $m$'s prime factors are of $S$?
For $S=\{p\}$ the ...
- 3,652
0
votes
1
answer
125
views
Finding the number of factors [closed]
To find the number of factors of a number, we can prime factorise that number and add one to every power, before multiplying those powers together. By why can every factor of that number be made via ...
2
votes
1
answer
162
views
Time complexity of classical period finding
Shor's algorithm for a quantum computer uses period finding in the quantum part to factor a number. For example, finding $r$ in $1 = a^r \; (mod \; N)$ will allow you to find two factors of a number $...
- 217
6
votes
0
answers
181
views
Curiosity: $\text{antiprime} = \text{prime} + 1$
The following is just a mathematical curiosity that popped into my head that I thought was interesting. I haven't been able to find anything about it online, although maybe I just am unaware of the ...
- 555
0
votes
1
answer
97
views
Generating primes with Euclid's theorem
Euclid famously proved that the set of primes $P$ is infinite by showing that for any finite list of primes, you can multiply them together and add $1$ to get a number divisible by a prime not on the ...
- 22.9k
0
votes
1
answer
113
views
What is the most efficient way to compute sum of sum of divisors of all numbers from 1 to n?
$σ_1(i)$ be the sum of divisors of $i$,
Calculate
$S(n) = \sum_{i=1}^n σ_1(i)$
I am looking for something better than $O(\sqrt{n})$
To address @ingix's question here is my $O(\sqrt{n})$ python ...
- 491
4
votes
0
answers
84
views
Finite many primes for every positive integer $b$?
Consider the function $$f(a,b):=\sum_{j=0}^a (bj)!=1+b!+(2b)!+\cdots +(ab)!$$
Given a positive integer $b$ , are there always only a finite number of positive integers $a$ such that $f(a,b)$ is prime ...
- 85.1k
3
votes
2
answers
114
views
About the Set of $\mathbb{S}=\{ n | n = a^2+b^2, a, b \in \mathbb{Z}. \}$
About the Set of $\mathbb{S}=\{ n | n = a^2+b^2, a, b \in \mathbb{Z}. \}$
This is also known as OEIS A001481.
I just found an interesting one from this set.
From my favorite identity, Brahmagupta-...
- 2,815
0
votes
0
answers
146
views
How do we get the number of prime divisors?
We have a natural square-free number $n$ such that $2^5\cdot 3^6\cdot 5^4\equiv 0 \pmod {\tau(n)}$.
Which is the maximum number of different primes that can divide $n$ ?
$$$$
We have that $\tau(n)$ is ...
- 14k
2
votes
1
answer
141
views
Prove that the power of prime factors of $\binom{2n}{n}$ has an upper bound of $\left\lfloor \frac{\ln(2n)}{\ln p} \right\rfloor$ [duplicate]
The proof of $
\ln\binom{2n}{n}\leq\sum_{p\leq 2n}\left\lfloor\dfrac{\ln(2n)}{\ln(p)}\right\rfloor\ln(p)$ is :
Let's define $\nu_p(n)$ be the highest power of a prime factor $p$ of $n$.
Note that in ...
- 7,674
5
votes
2
answers
194
views
Periodic sequences of integers generated by $a_{n+1}=\operatorname{rad}(a_{n})+\operatorname{rad}(a_{n-1})$
Let's define the radical of the positive integer $n$ as
$$\operatorname{rad}(n)=\prod_{\substack{p\mid n\\ p\text{ prime}}}p$$
and consider the following Fibonacci-like sequence
$$a_{n+1}=\...
- 1,828
0
votes
1
answer
855
views
Find two prime factors of a number so that the multiplication of factors give the original number
I have a number say N, I need to divide this number into p and q so that when I multiply p and q I would get original number back. Also, p and q should be two prime numbers.
Google search suggest to ...
- 227
3
votes
0
answers
92
views
Are there infinite many primes $\ p\ $ that cannot divide $\ 3^n+5^n+7^n\ $?
Let $\ M\ $ be the set of the prime numbers $\ p\ $ such that $\ p\nmid 3^n+5^n+7^n\ $ for every positive integer $\ n\ $ , in short the set of the prime numbers that cannot divide $\ 3^n+5^n+7^n\ $.
...
- 85.1k
1
vote
1
answer
104
views
Adequately defining the fundamental theorem of arithmetic.
Adequately defining the fundamental theorem of arithmetic.
So after sifting through the internet, I realized that there are a few ways the fundamental theorem of arithmetic is defined. Paraphrasing, ...
3
votes
0
answers
100
views
Does the following hold as a conjecture for maximum gaps between prime numbers? and can it be proved?
Even though I used matrix related mathjax on the backend, the frontend is intended to be just a regular table.
$$\begin{matrix}
a&X&X:explanation
\\1&1
\\2&3
\\3&5
\\4&(6)&(...
- 1,405