2
$\begingroup$

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
    Any prime appearing in the factorization of $n$ doesn't appear in $n+1$, and vice versa.2011-06-07
  • 2
    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.2011-06-07
  • 0
    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)](http://en.wikipedia.org/wiki/Catalan's_conjecture) 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).2011-06-07
  • 3
    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.2011-06-07
  • 0
    @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...2011-06-07
  • 0
    @Steven: My comment did not intend to speak about Mersenne primes. I was only (and not very precisely) saying that an "average" number had $\approx \log n$ factors. To say anything inteligible about what information the prime factorization of $n$ has to do with the prime factorization of $n+1$, one would have to also deal with the extreme case of going from a prime to a prime plus one.2011-06-07
  • 0
    @DJC Ahhh - in that case, I think you're missing a log; average numbers have roughly $\log \log n$ factors. I suspect that there _are_ infinitely many primes $p$ such that one of $p\pm 1$ has 'a lot' ($O(\log p)$) of factors, but that's a different and probably hard statement. :-)2011-06-08
  • 0
    @Steven: Thanks for letting me know! That is probably a difficult statement if $n$ has on average $\log_2(n)$ factors. Cheers!2011-06-08

2 Answers 2

5

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.

  • 0
    It has wide implications, that is why I am interested in any work that has been done in this area.2011-06-07
  • 0
    This would carry more force without the second and third sentences! Finding new prime numbers is easy compared to factorising.2011-06-07
  • 0
    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!2011-06-08
3

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

https://mathoverflow.net/questions/55010/prime-factorization-of-n1