2
$\begingroup$

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)$

$\endgroup$
6
  • $\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, 2015 at 13:31
  • $\begingroup$ @quid : Not seeing a pattern does not prove that there is no pattern. $\endgroup$
    – jimjim
    Jan 6, 2015 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, 2015 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, 2015 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, 2015 at 14:42

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • 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, 2017 at 2:21
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ $p_4^2\times p_5+1 = p_1^2p_2^3p_3$ $\endgroup$
    – jimjim
    Jan 6, 2015 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, 2015 at 0:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .