ok u mean to say 1806 *1807=3263442, now it will going to be very large. now am I right sir?plz tell

The Gateway to Computer Science Excellence

+3 votes

Consider numbers greater than one that satisfy the following properties:

- They have no repeated prime factors;
- For all primes $p \geq 2$, $p$ divides the number if and only if $p − 1$ divides the number.

The number of such numbers is

- $0$.
- $5$.
- $100$.
- Infinite.
- None of the above.

+5 votes

Best answer

The prime factors of $30$ are $2,3,5$, so it satisfies the 1st constraint.

However, $\matrix{

(2-1) & \rm divides & 30 & \color{green}\checkmark\\

(3-1) & \rm divides & 30 & \color{green}\checkmark\\

(5-1) & \rm divides & 30 & \color{red}\times\\

}$ and thus it doesn't satisfy the 2nd constraint.

One can prove that for $n$ to satisfy these properties, $n=p(p−1)$ for some prime $p$ and that $(p−1)$ satisfies the properties too.

Some examples of the numbers that satisfy both constraints are:

$$\begin{align}

&2\\

2 \times 3 = &6\\

6 \times 7 = &42\\

42 \times 43 = &1806

\end{align}$$Now $1807$ is not a prime and hence breaks the sequence. So, number of such numbers is $4.$

Correct Answer: E.

However, $\matrix{

(2-1) & \rm divides & 30 & \color{green}\checkmark\\

(3-1) & \rm divides & 30 & \color{green}\checkmark\\

(5-1) & \rm divides & 30 & \color{red}\times\\

}$ and thus it doesn't satisfy the 2nd constraint.

One can prove that for $n$ to satisfy these properties, $n=p(p−1)$ for some prime $p$ and that $(p−1)$ satisfies the properties too.

Some examples of the numbers that satisfy both constraints are:

$$\begin{align}

&2\\

2 \times 3 = &6\\

6 \times 7 = &42\\

42 \times 43 = &1806

\end{align}$$Now $1807$ is not a prime and hence breaks the sequence. So, number of such numbers is $4.$

Correct Answer: E.

0

ok u mean to say 1806 *1807=3263442, now it will going to be very large. now am I right sir?plz tell

+1

1807 is not a prime number- but how is condition b violated for 1806 * 1807? Because 13 is a prime number which divides this but 13-1=12 does not.

So, we only got 4 numbers. Any more possible? Really hard one during exam :)

So, we only got 4 numbers. Any more possible? Really hard one during exam :)

+2

Yes, kinda lengthy. One can prove that for $n$ to satisfy these properties, $n = p (p-1)$ for some prime $p$ and that $(p-1)$ satisfies the properties too.

Once that is achieved, it is a simple matter of noticing that $1807$ is not a prime and hence breaks the sequence.

Once that is achieved, it is a simple matter of noticing that $1807$ is not a prime and hence breaks the sequence.

0

okay, It is going to check longest chain ,right?

But upto how many times should I check , as there is no upper limit ? because there will be always a chance of error in result. Am I right sir?

But upto how many times should I check , as there is no upper limit ? because there will be always a chance of error in result. Am I right sir?

+4

Well, answer is 4. And the reason is told by Pragy. This is the only chain possible and it goes from 2, 6, 42. 1806. After this 3263442 comes and it doesn't satisfy the second constraint and hence we got the answer. But to try this for first time in exam is tricky. I guess for these questions smart people should get 0 and not negative :)

52,375 questions

60,615 answers

202,053 comments

95,434 users