Has work been done on looking at what happens to the exponents of the prime factorization of a number $n$ as compared to $n+1$? I am looking for published material or otherwise. For example, let $n=9=2^0\cdot{}3^2$, then,

$$ 9 \;\xrightarrow{+1}\; 10 $$

$$ 2^0\cdot{}3^2 \;\xrightarrow{+1}\; 2^1\cdot{}3^0\cdot{}5^1 $$

or looking just at the exponents,

$$ [0,2,0,0,...] \;\xrightarrow{+1}\; [1,0,1,0,...] $$

I realize the canonical way of reaching the latter is generating the prime factorization of $n$ and of $n+1$ separately, but has there been any research into manipulating the exponents directly instead (short-cutting around the factorization)?

For anyone who can't answer but still wants to see something interesting, check out FRACTRAN.

  • 2
    $\begingroup$ Any prime appearing in the factorization of $n$ doesn't appear in $n+1$, and vice versa. $\endgroup$ – Yuval Filmus Jun 7 '11 at 14:20
  • 2
    $\begingroup$ I would guess the behavior to be too erratic for anything intelligible to be said. As @Yuval points out, for every integer $n$, we have $\gcd(n,n+1) = 1$. Even worse, if you start with (or end with) a prime $p$, then you can go from a prime $p$ to a number with $\approx \log(n)$ prime factors. $\endgroup$ – JavaMan Jun 7 '11 at 14:26
  • $\begingroup$ Apart from the disjointness of prime bases in factoring $n$ and $n+1$ pointed out by Yuval, the only general observation I can think of is that the map is cycle-free (because of the monotonicity of adding 1). As a special case note that Catalan's conjecture (now Mihăilescu's theorem) tells us that the only case of mapping from a single prime exponent greater than 1 to another is $2^3 + 1 = 3^2$. Fermat and Mersenne primes are also special cases where argument and image both have single entry support (but one exponent is 1). $\endgroup$ – hardmath Jun 7 '11 at 15:10
  • 3
    $\begingroup$ As far as I know, the smart money is that there is essentially no relationship between the prime factorization of $n$ and the prime factorization of $n+1$ (other than the fact that the primes must be distinct). This can probably be made precise in various ways. $\endgroup$ – Qiaochu Yuan Jun 7 '11 at 15:24
  • $\begingroup$ @DJC: is even that much known? It's obviously plausible and widely believed that there are infinitely many Mersenne primes, or primes of the form $k^n\pm 1$, but AFAIK there aren't any specific instances where infinitely many primes are known... $\endgroup$ – Steven Stadnicki Jun 7 '11 at 18:25

If we could deduce the prime factorization of a number $n+1$ from the prime factorization of the number $n$, then by induction we could in particular arrive at the prime factorization of all numbers. By the way, this would allow us to find new prime numbers. Since prime numbers seem to appear at random in the set of integers, I doubt this method would work.

  • $\begingroup$ It has wide implications, that is why I am interested in any work that has been done in this area. $\endgroup$ – Alex Hirzel Jun 7 '11 at 15:37
  • $\begingroup$ This would carry more force without the second and third sentences! Finding new prime numbers is easy compared to factorising. $\endgroup$ – TonyK Jun 7 '11 at 17:16
  • $\begingroup$ this would be a $O(n)$ factorization algorithm, worse even than trial division. There are good reasons why you can't expect to learn much about the factorization of $n+1$ from that of $n$, but I don't think the domino theory is one of them - too many dominoes! $\endgroup$ – Gerry Myerson Jun 8 '11 at 0:10

I found this on MO which is relevant to the question:



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.