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.

  • 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
    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