If $p_n$ is the nth prime number. then what is the next composite number after say $p_4^2\times p_5$ without actual calculation? ($p_4^2\times p_5+1$ is $p_1^2p_2^3p_3$) the first few composite numbers seem to follow no immediate pattern i.e. $p_1^2,p_1p_2,p_1^3,p_2^2,p_1^2p_2,\cdots $

For example given the consecutive composite numbers $p_{j_1}^{k_1}p_{j_2}^{k_2}\cdots p_{j_n}^{k_n}$ and $p_{m_1}^{n_1}p_{m_2}^{n_2}\cdots p_{m_r}^{n_r}$ what is the mapping from $\big( ({j_1},{k_1}),({j_2},{k_2}) \cdots ({j_n},{k_n})\big) \to \big( ({m_1},{n_1}),({m_2},{n_2}) \cdots ({m_r},{n_r}) \big)$

  • $\begingroup$ I do not understand what specifically you want to ask. "the first few composite numbers seem to follow no immediate pattern" yes, and neither will subsequent ones. $\endgroup$ – quid Jan 6 '15 at 13:31
  • $\begingroup$ @quid : Not seeing a pattern does not prove that there is no pattern. $\endgroup$ – Arjang Jan 6 '15 at 13:38
  • $\begingroup$ No it does not. Could you still please try to make precise what type of answer you are looking for. $\endgroup$ – quid Jan 6 '15 at 13:42
  • $\begingroup$ I do not know much about number theory, but from the fact that the decomposition into prime factors can be hard (and some encryption algorithms rely on that fact) I assume that no "simple" mapping exists. $\endgroup$ – Martin R Jan 6 '15 at 14:33
  • 1
    $\begingroup$ I know. But such a mapping would allow to compute the factorization of (x+1) from the factorization of x. $\endgroup$ – Martin R Jan 6 '15 at 14:42

While it is true that there is not any known way to find the next composite number after an arbitrarily given composite number,

there is this algebraic identity:

$s1 (s1 s2 s3 + s2 + s3) + 1 = (s1 s2 + 1) (s1 s3 + 1)$

That is, there are special composite numbers for which the very next integer is also composite, and if you know the factors of one of them, you know the factors of the other.

  • 1
    $\begingroup$ Please be sure to use MathJaX formatting in the future, though in this case it isn't really a big deal and the answer is still readable. $\endgroup$ – The Count Feb 10 '17 at 2:21

The next composite number after $p_4^2\times p_5$ is clearly $p_4^2\times p_5+1$, which is even.

  • $\begingroup$ $p_4^2\times p_5+1 = p_1^2p_2^3p_3$ $\endgroup$ – Arjang Jan 6 '15 at 14:33
  • $\begingroup$ @Arjang, ah, now I see what you mean. I don't think there is any satisfactory answer, as Martin R said. $\endgroup$ – lhf Jan 7 '15 at 0:20

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.