For questions about factoring elements of rings into primes, or about the specific case of factoring natural numbers into primes.

learn more… | top users | synonyms (2)

0
votes
0answers
24 views

Every integer $n > 1$ can be written in one and only one way with a certain property [duplicate]

Every integer $n > 1$ can be written in one and only one way in the form $n = p_1p_2p_3 \ldots p_r$ where $p_i$ are positive primes s.t. $p_1 \le p_2 \le p_3 \le \ldots \le p_r$. $n$ is unique ...
2
votes
2answers
45 views

Existence of integer solution of $a^2 -17b^2 = $ any constant

When checking whether if $9-\sqrt{17}$ in the ring $\{a+b\sqrt17: a,b \in \mathbb{Z}\}$ is a prime. Suppose $$\alpha\cdot \beta = 9-\sqrt{17},$$ using norm argument $$N(\alpha)N(\beta) = ...
0
votes
2answers
100 views

How many prime numbers we need? [closed]

If we have some not prime number $n > 1$ we always can make prime factorization. For this operation we need $m$ prime numbers. Is there any way to prove that for given $n$ we can use no more then ...
1
vote
0answers
27 views

What is the usefulness of cycles of f(x) in Pollard's rho factorization?

I've been getting myself acquainted with the Pollard Rho factorization from this page: http://www.cs.colorado.edu/~srirams/classes/doku.php/pollard_rho_tutorial. I think I understood well almost ...
-6
votes
0answers
67 views

Lepore primality test and factorization . What is the complexity?

I have found an algorithm which tests if a number NR is primes . What is the complexity? I show only NR = X * Y, where NR = 6G + 1, X = 6a + 1, Y = 6b + 1, G, a and b natural numbers. X and Y are ...
-1
votes
1answer
63 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 ...
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 ...
0
votes
1answer
27 views

What can we say about the distribution of the prime-power factors of a big factor-rich number?

Let us say that a positive integer is factor-rich if it has more factors than any smaller integer. For example, $60$, which has twelve factors, is factor-rich; and therefore $72$, which also has ...
2
votes
1answer
51 views

Factorization of the semi-palprime $N = pq$

I define semi-palprime be a prime number that remains the prime when its digits are reversed, like $p = 13$, and its mate is $q = 31$. I know that number $N$, $ N ...
0
votes
0answers
40 views

Puzzle on multiplying by fixed values to reach a target number.

So, this one's tricky. There's a keycode combination, and there are six buttons. Each button multiplies the base number of 1 by their respective multipliers (see below). Once the result number gets ...
0
votes
0answers
19 views

Notation for separating out factors of a number

I have an integer (let's call it $n$), and I want to define it as the product of two values: one that's a pure power of two, and another that is odd. Obviously, these two values are unique for a ...
0
votes
2answers
15 views

Series of positive factors of a number divided by that number

Let $S_n$ be the sum of the positive factors of $2015^n$, with $n$ being a positive integer approaching infinity. What is $\dfrac{S_n}{2015^n}$? I might be on the wrong track, but I figure that if $x ...
0
votes
0answers
21 views

Factorisation And Ideals

I have only a basic grasp of algebraic number theory. I understand the proofs of UF for the rational integers and the analogous proofs (using norms) of UF for Gaussian and Eisenstein integers, for ...
0
votes
3answers
76 views

The square of n+1-th prime is less than the product of the first n primes.

I wanted to prove the following question in an elementary way not using Bertrand postulate or analytic estimates like $x/\log x$. The question is $$ p_{n+1}^2<p_1p_2\cdots p_n,\qquad(n\geq4) $$ I ...
0
votes
3answers
73 views

Prime number equation

The number of solutions of the equation $xy(x+y)=2010$ where $x$ and $y$ denote positive prime numbers, is ____ I tried various things but nothing seems to work out. $2010$ can be resolved into ...
1
vote
2answers
49 views

Largest Arithmetic Sum of Relatively Prime Numbers Under 30

Pick however many integers in the range $[1,30]$ (inclusive). The only constraint is that all of these numbers must be relatively prime to each other. What is the largest possible arithmetic sum ...
5
votes
3answers
455 views

Prime factorization number theory

Let $n$ be a positive integer, and let $ 1=d_1<d_2<\dots <d_6=n $ be all of its divisors. Find all $n$ that satisfy $ \frac 1{d_1} +\frac 1{d_2} + \dots + \frac 1{d_6 } = 2. $ I started by ...
0
votes
2answers
72 views

The number $2^{2^n} + 2^{2^{n - 1}} + 1$ can be expressed as the product of at least $n$ prime factors

Prove that the number $2^{2^n} + 2^{2^{n - 1}} + 1$ can be expressed as the product of at least $n$ prime factors, not necessarily distinct. Doing what the hint has suggested, I have done the ...
3
votes
2answers
51 views

GCD, LCM Relationship

Problem: Let $(a,b)$ denote the greatest common divisor of $a$ and $b$ and $[a,b]$ denote the least common multiple of $a$ and $b$. Prove that $ ...
2
votes
1answer
44 views

Factoring, Minimum/Maximums

Let $a,b,c$ be three positive integers such that $$\text{lcm}(a,b) \cdot \text{lcm}(b,c) \cdot \text{lcm}(c,a) = a \cdot b \cdot c \cdot \gcd(a,b,c). $$ Given that none of $a,b,c$ is an integer ...
2
votes
0answers
94 views

Number of unordered factorizations into $k$ distinct parts

Let $H_d(n)$ denote the number of distinct ordered factorizations of $n$ and $H_d(n,k)$ the number of ordered factorizations of $n$ into $k$ distinct parts. We have the following recurrence: ...
5
votes
0answers
54 views

a new(?) operation using products of multiplicities

Does the operation $$n \odot m := \prod_{p \text{ prime}} p^{v_p(n) \cdot v_p(m)}$$ on positive integers have a common name? Has this operation been studied somewhere? Notice that $\odot$ is ...
2
votes
1answer
48 views

Comparing $\pi(x)$ and $\pi^{(k)}(x)$

We say a k-almost prime is an integer that results as the product of k prime, counting repetition. For example, $12$ is a $3$-almost prime as $12= 3 \times 2 \times 2$. Additionally, we define ...
6
votes
0answers
136 views

Is there a quicker way to generate integers which are hard to factor than multiplying two large primes?

An easy way to generate an integer which is hard to factor is to find two large primes and multiply them. As a bonus, you know the factors. I'm interested in whether it's possible to find integers ...
3
votes
1answer
28 views

Is there a way to estimate the number of positive integers less than or equal to $n$ that have a given prime $p$ as a least prime factor

The probability that an integer $p$ divides an integer $x$ is $\dfrac{1}{p}$. From this article on almost prime numbers, the number $\pi_k(n)$ of positive integers less than or equal to $n$ with at ...
2
votes
1answer
76 views

Calculation of product of all coprimes of number less than itself

Is there any fast way or formula to calculate product of all coprimes of a number less than itself? How can we do it without finding all coprimes manually? Note : I have to find actually (product) ...
2
votes
3answers
54 views

Find all numbers that have 30 factors and have 30 as one of their factors.

Find all numbers that have 30 factors and have 30 as one of their factors. Thank you. Note: please show way if possible.
1
vote
2answers
86 views

Do prime numbers have prime factors?

(This is a somewhat trivial question). Do prime numbers have prime factors, i.e. itself? For example is 7 a prime factor of 7? The reason I ask this is because there is a statement in my lecture ...
0
votes
1answer
24 views

What is the summatory function of the number of (not necessarily distinct) prime factors?

In the Math World article on Merten's Constant, a related constant $B_2$ is mentioned which "appears in the summatory function of the number of (not necessarily distinct) prime factors." I am very ...
3
votes
1answer
56 views

Inverse of prime counting function

The prime counting function $ \pi (x) \approx \dfrac {x} {\ln(x-1)} $. This function returns the number of primes less than $x$. Note: $x-1$ gives a better estimate than $x$. How to find $x$ given $ ...
0
votes
1answer
58 views

Newton-Raphson For Integer Factorization

Per my earlier question on Naive Grouping for factorization here, below is the modified Newton-Raphson method (integers only) for the polynomial $N -x^2 - yx - x = 0$. ...
2
votes
0answers
37 views

Notation for indexing the factorizations of a number?

Background Given any $n \in \mathbb{N}$, the ordered factorization count of $n$ can be computed and is traditionally written $H(n)$. This is, essentially, the number of unique decompositions of $n$ ...
3
votes
3answers
90 views

Storing a natural number as a set of its Nth prime factors, how much data is used?

Spoiler, tap to reveal. In asking the following question, I knew that each natural number could be prime factorised. However I assumed that most natural numbers would each be equal to the ...
1
vote
0answers
50 views

Given a number $N$ and a prime $P$, how many numbers $\leq N$ are divisable by P but not by any smaller primes?

The following Math Exchange question deals with a similar problem: not divisible by 2,3 or 5 but divisible by 7 However, the answers given become infeasible quite quickly because the amount of ...
1
vote
1answer
35 views

Average smallest prime factors

I looked at the average smallest prime factor (ASPF) for the numbers up to N: $\text{ASPF}(N) = \frac{1}{N-1}\ \Sigma_{k=2}^N \text{SPF}(k)$ ASPF(100) = 13 ASPF(1,000) = 79 ASPR(10,000) = 578 ...
2
votes
0answers
57 views

Greatest prime factor of $\left(\dfrac{n(n+1)}{2}\right)^2-1$.

Consider $$ \left(\dfrac{n(n+1)}{2}\right)^2-1. $$ Is is possible to say something about the lower bound on the greatest prime divisor of the above expression depending only on $n$? I surfed through ...
2
votes
1answer
46 views

Is there anything I could read that talks about dimensionality of prime/composite numbers?

Is there anything out there that talks about how primes are one dimensional numbers and composites can only be in dimensions greater than 1? What I mean is, 4 would be a two dimensional number (2x2) ...
4
votes
1answer
51 views

Probability, that a random number has no “small” prime factors

What is the probability, that a random number $N$ with $k$ digits has no prime factor with at most $l$ digits ? I came across the formula $\frac{e^{-\gamma}}{log(p)}$ , giving the approximate ...
0
votes
1answer
20 views

find the prime factorization of $x^3-5x^2+6x+7$ in $Z/11Z$

I need to find the prime factorization of $f = x^3-5x^2+6x+7$ in $Z/11Z$ I tried the following but not sure if it is correct and if there is a better and faster way to do it. first i tried one by ...
0
votes
0answers
87 views

Naive Grouping for Factorization

I have a naive grouping method for factorization. I am curious as to its novelty and aspects of the code below that will increase its efficiency. The method is best described with an example: For n ...
1
vote
1answer
209 views

Number of Divisors of N factorial

Say d(N) = Number of factors of N! Briefly: I wish to know if there is a Recurrence relation for this problem Now I wish to Know if there is a way to calculate d(N) in terms of previously calculated ...
2
votes
1answer
32 views

Adding a power of two to a composite odd number

If I have a composite odd number $p_1$, then adding $2$ to $p_1$ will make it a number that is either a prime or that shares none of its factors: $p_2$. If I have the equation $p_1+2=p_2$ and I can ...
1
vote
2answers
35 views

Finding the upper bound for a number's factors length

Okay, so the title is a bit misleading but I had to keep it short.. Anyhow, if I have a number X what will the length of it's longest two factors be? For example: $X = 10000$ I want $3$ and $3$ ...
10
votes
0answers
268 views

Distributing groups of objects into boxes

How can I enumerate the number of ways of distributing distinct groups of identical objects (but various cardinality) into $k$ boxes such that at most one box is empty $(1)$ and no combination of ...
4
votes
1answer
46 views

Solving a Diophantine equation with LTE

Show that only positive integer value of $a$ for which $$4(a^n+1)$$ is a perfect cube for all positive integers $n$, is $1$. Rewriting the equation we obtain: $$4(a^n+1)=k^3$$ It is obvious that $k$ ...
0
votes
1answer
57 views

Primes in quadratic number fields

If $p$ is a prime number such that $p≡3\;mod\;4$, prove that $\sqrt{-p}$ is prime in $\mathbb{Z}[\sqrt[ ]{-p}]$ and in $\mathbb{Z}[\displaystyle\frac{1+\sqrt[ ]{-p}}{2}]$ too. Notes We have seen in ...
2
votes
1answer
57 views

Total possible ways of representing n! as a sum of two or more consecutive positive integers.

I need to calculate total possible ways of representing $n!$ as a sum of two or more consecutive positive integers. Example : $3!=1*2*3=6$ and $6=1+2+3$ the only one possible way. Answer : $1$ The ...
2
votes
2answers
237 views

Total number of divisors of factorial of a number

I came across a problem of how to calculate total number of divisors of factorial of a number. I know that total number of divisor of a number $n= p_1^a p_2^b p_3^c $ is $(a+1)*(b+1)*(c+1)$ where ...
25
votes
3answers
409 views

Can a number be equal to the sum of the squares of its prime divisors?

If $$n=p_1^{a_1}\cdots p_k^{a_k},$$ then define $$f(n):=p_1^2+\cdots+p_k^2$$ So, $f(n)$ is the sum of the squares of the prime divisors of $n$. For which natural numbers $n\ge 2$ do we have ...
3
votes
0answers
21 views

Special $\omega(n)$-sequence

Let $k$ be a natural number, $\omega(n)$ the number of distinct prime factors of $n$. The object is to find a number $n$ with $\omega(n+j)=j+1$ for each $j$ with $0\le j\le k-1$. In other words, a ...