1
$\begingroup$

I need to obtain prime factorizations of numbers of the type: $\sum_{i=0}^n p^i$, for any prime number $p$ (not the same one each time).

Do you know if there is a quicker algorithm to calculate these factorizations than those used for other natural numbers?

I don't know if there is a known solution. My only lead is that all Mersenne primes are of the form $\sum_{i=0}^n 2^i$.

Edit: by prime factorization I mean, for example, if $p$ is 3 and $n$ is 6, the number is 364, and the prime factorization I'm looking for is 2^2, 7 and 13.

$\endgroup$
1
$\begingroup$

You have a geometric series, so $\sum_{i=0}^n p^i=\frac {p^{n+1}-1}{p-1}$. When the prime is $2$ this does not give a factorization because the denominator is $1$. For all other primes it does.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer. I didn't think of the formula of a geometric series, that could prove to be useful. However, I don't see how the sum obtained by this formula leads to the prime factorization of itself, which is what I am looking for. For example, when p equals 3 and n equals 3, the sum is $1+3+9+27=40$. This is obtainabled by your given formula, but my task is to find the prime factorization of that sum, i.e 5^1 and 2^3 $\endgroup$ – Ifn47 Aug 2 at 15:11
  • $\begingroup$ To extend on that, when p is 3 and n is 6, the sum is 364, and its prime factorization is 2^2, 7, and 13. My question is if there is a method to find those factors that is quicker than other prime factorization algorithms $\endgroup$ – Ifn47 Aug 2 at 15:20
  • $\begingroup$ @Ifn47, you can factor the numerator $p^{n - 1} - 1$ by the same idea as $(p - 1) (1 + p + p`2 + \dotsb + p^{n - 2})$. $\endgroup$ – vonbrand Aug 2 at 15:56
  • $\begingroup$ @Ifn47, even better, use the known factorization $x^{r s} - 1 = (x^r - 1) (x^{(r - 1) s} + x^{(r - 2) s} + \dotsb + 1)$. Pick any factorization of your $n - 1$, and you are in bussiness. $\endgroup$ – vonbrand Aug 2 at 16:03
  • $\begingroup$ Awesome thanks! $\endgroup$ – Ifn47 Aug 2 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.