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)

3
votes
1answer
45 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
32 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$. ...
1
vote
0answers
30 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
70 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
46 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
30 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
51 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
41 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
41 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
80 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
55 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
29 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
28 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$ ...
9
votes
0answers
199 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
35 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
56 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
48 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
87 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 ...
20
votes
0answers
189 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
20 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 ...
4
votes
2answers
68 views

How does one prove that $\mathbb{Z}\left[\frac{1 + \sqrt{-43}}{2}\right]$ is a unique factorization domain.

By extending the Euclidean algorithm one can show that $\mathbb{Z}[i]$ has unique factorization. This logic extends to show $\mathbb{Z}\left[\frac{1 + \sqrt{-3}}{2}\right]$, $\mathbb{Z}\left[\frac{1 ...
2
votes
1answer
29 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 ...
0
votes
1answer
58 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
0answers
42 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 : ...
2
votes
1answer
51 views

Consecutive numbers with less than $k$ prime factors?

Let $k$ be an integer. Consider the consecutive numbers with less than $k$ distinct prime factors. Are there arbitary large differences between those numbers ? With other words : Are there ...
2
votes
1answer
37 views

About the ways prove that a ring is a UFD.

I'm doing an exercise where I have a commutative ring with unity $R$. We had to find that the nonunits formed an ideal (maximal). After that, we found the irreducible elements, and then we saw that ...
0
votes
1answer
21 views

Counting the spokes

I’ve been playing around with wheel factorization (Wikipedia link) and wanted to know how many spokes there are in a given wheel. For a 2-7 wheel the circumference of this would be 210 and then I can ...
4
votes
2answers
65 views

Conjecture: only one even Fibonacci term divided by two gives a prime: $F(9) = 34 = 2 \times 17$

Every Fibonacci term $F(3n)$ is divisible by two $F(3) = 2$ $F(6) = 8$ $F(9) = 34$ $...$ After seeking Fibonacci tables factorization until $F(10000)$, for every term $\frac{F(3n)}{2}$, it ...
0
votes
2answers
35 views

Where does the proof of unique factorization fail for $\mathbb Z[\sqrt{-5}]$?

I know that unique factorization does not hold for all rings, such has the much-used example $\mathbb Z[\sqrt{-5}]$. It seems that Euclid's lemma does not hold for these rings, and so on. However, ...
1
vote
0answers
20 views

Trouble finding the norm of the two following ideals

Given that $\alpha$ is the root of the polynomial, $x^3 - x - 1$ is $\alpha$ and $K=\mathbb{Q}(\alpha)$, show that the norm of the ideal $\langle 5, \alpha-2\rangle$ is $5$ and the norm of the ideal ...
1
vote
1answer
70 views

The following is a necessary condition for a number to be prime, from its digit expansion. Has it been referred somewhere?

Concerning a numbers’ digits we know some necessary conditions on them for the number to be prime, besides the last digit having to be odd (except for prime 2). For example in decimal representation ...
4
votes
2answers
154 views

How many ways are there to express a number as the product of groups of three of its factors?

Specifically, I am thinking of a cuboid with a given volume ($28\,000$) that has sides of integer length. For example, $20 \cdot 20 \cdot 70 = 28\,000$, but so do $10 \cdot 40 \cdot 70$ and $1 \cdot 1 ...
1
vote
1answer
54 views

relation between set of prime divisors of two positive integers

How to tell in most efficient way that the set of prime divisors of a positive integer M is a superset of the set of prime divisors of another positive integer N where M and N are quite big numbers. ...
2
votes
1answer
73 views

How to Find the smallest integer with exactly N odd divisors.

Hi All I was trying one problem in which is it asking for the smallest number having N odd divisors. As I know the smallest number having n divisors can be find easily.First we need to find the prime ...
1
vote
1answer
56 views

Upper bound on the maximal number of prime factors

I would like to prove $$\omega(n) \le \frac{\ln{n}}{\ln\ln{n}}$$ This is a quite standard result, but I haven't been able to find a proof. Here's what I've tried doing: ...
3
votes
1answer
66 views

prime divisor propertyfor Hurwitz integers

The Hurwitz integers $\mathcal{H}_{\mathbb{Z}}$ is a particular subset of quaternions. Define: $$ \mathcal{H}_{\mathbb{Z}} = \left\{ a\frac{1+i+j+k}{2}+bi+cj+dk \ | \ a,b,c,d \in \mathbb{Z} \right\} = ...
1
vote
0answers
36 views

Non-unique factorization in $\mathbb{Z}[\sqrt{-5}]$

I want to show that the decomposition into irreducible factors in the ring $$\mathbb{Z}[\sqrt{-5}] = \{a + b\sqrt{-5}|\space a, b \in \mathbb{Z}\}$$ is not unique, except for the order of factors ...
1
vote
0answers
82 views

Can I use integer frequencies in quadratic intervals to set a lower bound for primes? [closed]

I want to find out if the following arithmetic approach could produce a backdoor proof of Legendre’s Conjecture. There are two assumptions, Questions A and B, which are posed in the text and labeled ...
0
votes
0answers
26 views

Motivation for $r$ in AKS Primality Test

I've been reading up on the AKS primality test, and I understand the big ideas and proofs as they are pretty elementary number theory. I am confused about how to value of $r$ is selected. In the ...
6
votes
2answers
123 views

Prove or disprove : $a^3\mid b^2 \Rightarrow a\mid b$

I think it's true, because I can't see counterexamples. Here's a proof that I am not sure of: Let $p_1,p_2,\ldots, p_n$ be the prime factors of $a$ or $b$ \begin{eqnarray} a&=& ...
3
votes
3answers
77 views

A doubt concerning the fundamental theorem of arithmetic

Will a prime $p^{0}$ be considered a unique prime in prime decomposition of a number? If the answer to the above question is yes then it breaks the uniqueness which the Fundamental Theorem of ...
0
votes
1answer
55 views

$a^2\equiv1 \pmod n$ iff $a\equiv\pm\,1\pmod p$ for all $p\mid n$

(Not)if $a$ is an integer and $n$ a postive integer, then $a\equiv\pm 1\pmod p$ for all primes dividing n if and only if $$a^2\equiv 1\pmod n$$ $\Longrightarrow $ is wrong,Tonyk note ...
0
votes
0answers
17 views

Tree structure by using integer markers

I'm trying to model a situation in witch a group of entities are organized hierarchically. We say that entity A has privileges over entity B if there a direct hierarchical connection between A and B ...
2
votes
3answers
50 views

Proving gcd($a,b$)lcm($a,b$) = $|ab|$

I was trying to prove that $$ dm = |ab|$$ where $d$ = gcd(a,b) and m = lcm(a,b). So I went about by saying that $a = p_1p_2...p_n$ where each $p_n$ is a prime. Same applies to $b = q_1q_2 ... q_c$. ...
1
vote
0answers
52 views

Is there a standard notation for the sequence of sorted exponents in the prime power factorization of a number?

Given some $n \in \mathbb{N}$, is there a name or notation for any/all of the following? The set of all factors $F(n)$ of $n$ (including 1 and $n$). The ascending sequence of non-unique prime ...
0
votes
2answers
26 views

Asymptotic upper bound on number of solutions to $ab \equiv n \pmod m$

Does anyone know a rough upper bound on the number of solutions to $ab \equiv n \pmod m$ when $n$ and $m$ are given and $a<m$, $b<m$, $n<m$? Specifically, I want to know how the number of ...
0
votes
0answers
22 views

Help with Dixon's factorization algorithm?

I've been trying to implement Dixon's factorization method in python, and I'm a bit confused. I know that you need to give some bound $B$ and some number $N$ and search for numbers between ...
10
votes
5answers
221 views

Which of these two factorizations of $5$ in $\mathcal{O}_{\mathbb{Q}(\sqrt{29})}$ is more valid?

$$5 = (-1) \left( \frac{3 - \sqrt{29}}{2} \right) \left( \frac{3 + \sqrt{29}}{2} \right)$$ or $$5 = \left( \frac{7 - \sqrt{29}}{2} \right) \left( \frac{7 + \sqrt{29}}{2} \right)?$$ ...
1
vote
1answer
40 views

If $a^2+3b^2$ is a cube in $\mathbb Z$ , then are $a+\sqrt{-3}b$ and $a-\sqrt{-3}b$ both cubes in $\mathbb Z[\sqrt{-3}]$ ?

If $a,b \in \mathbb Z$ are such that g.c.d.$(a,b)=1$ and if $a^2+3b^2$ is a cube in $\mathbb Z$ , then are $a+\sqrt{-3}b$ and $a-\sqrt{-3}b$ both cubes in $\mathbb Z[\sqrt{-3}]$ ? I cannot use ...