Question

A set M of numbers is defined recursively by

1. 2 and 3 belong to M
2. If x and y belong to M, so does x * y

Which of the following numbers belong to M?
6, 9, 16, 21, 26, 54, 72, 218

Answer 1

One approach to solve this problem can be as below:

First prepare a set of numbers upto 218 and then check which numbers are in the set.

Second approach can be while computing the numbers in the set also check whether the given numbers are in the set or no, as they are already arranged in the ascending order.

So let us start building set M

Given: {1,2,3,....}

Add 1X2, 1X3, 2X3 to this set and we get

set M = {1,2,3,6,...}

The new number added must be multipled by every other number excluding the 1st as multiplying by 1 gives the same no.

Add 2X6,3X6

set M = {1,2,3,6,12,18,....}

New numbers 12 and 18 are added to the set

Add 2X12,3X12,6X12,2X18,3X18,6X18,12X18

the new numbers are 24,36,72,36,54,216

So that makes set M look as below, once these numbers are arranged in the ascending order:

set M = {1,2,3,6,12,18,24,36,54,72,216....}

The new numbers are to be multipled by every previous number, only upto max value of 218

2X24,3X24,6X24,12X24,2X36,2X54,6X54,18X54,24X54,2X72,3X72,6X72,12X72,...

New numbers 48,72,144,72,108,216,...(excluding numbers like 6X54=326, that are higher than 218)

set M = {1,2,3,6,12,18,24,36,48,54,72,108,144,216....}

Now let us check the numbers that belong to the set and these are

6, 54, 72

Here we have made the assumption that x*x does not belong to the set. Every number can be used only once.

Numbers that have been excluded are 9,16,21,26,218

If x*x is also in the set then 9 and16 will also be in the set as 3X3, 2X2 =4 and 4X4=16

However 21 has a prime factor 7, 26 has a prime factor 13 and 218 has a prime factor 109 which are not in the given initial set. So these numbers are not part of M.

Third approach to solve this problem:

If there is such huge set to be checked, then another algorithm can be used to check the prime factors of the numbers and clearly exclude those numbers for which prime factor is not a part of the given set.