A set of positive integers has the properties that
– Every member in the set, apart from 1, is divisible by at least one of 2,3 or 5.
– If the set contains 2n, 3n or 5n for some integer n, then it contains all three and n as well.
The set contains between 300 and 400 numbers. Exactly how many does it contain?
The question IS perfectly well-defined, you have to read it fairly carefully and think it through, I had to think overnight about it.
Call the set S. The important point to note is the actual identities of what the members of S are are irrelevant, the question is about the STRUCTURE of S. (But in fact you can discover their values anyway).
Property P> If S contains 2n, 3n or 5n for some integer n, => S contains all three and n as well.
Read that very closely, and apply it recursively.
Now since every member of S (other than 1) is divisible by 2,3 or 5, if you keep applying that backwards recursively (dividing a number by factor of 2,3 or 5), the value eventually reduces to 1. Hence 1∈S and is the smallest element of S.
Since the cardinality #S is >300, S must also contain each of {2,3,5} (proof by contradiction: if it contained none of them, #S would be only 1, not ≥ 300. Hence it must contain at least one of them. But if it contains one of them, by property P, it must contain all of them). Hence S also contains {2,3,5}
Now we have 4 elements.
Again applying property P backwards and setting n to each of {2,3,5}, S must also contain {2*2, 2*3, 2*5, 3*3, 3*5, 5*5} i.e. S contains 2^a 3^b 5^c for at least all integers a+b+c ≤ 2.
Now we have #S = 10 elements.
Again applying property P backwards and setting n to each of {2*2, 2*3, 2*5, 3*3, 3*5, 5*5}, S must also contain {2*2*2, 2*2*3, 2*2*5, 2*3*3, 2*3*5, 2*5*5, 3*3*3, 3*3*5, 3*5*5, 5*5*5} i.e. S contains 2^a 3^b 5^c for at least all integers with 0 ≤ a+b+c ≤ 3. Now we have #S = 20.
And so on… (proof by recursion).
These look to me like the triangular pyramidal (tetrahedral) numbers.
The cardinality of S is #S = k’th triangular pyramidal number,
which have the form t(k) = k(k+1)(k+2)/6
Then it is easy to find that the only tetrahedral number between 300 and 400 is 364. QED.
Fun.
(I started out from the fact that S must have a smallest element (by the well-ordering principle). I initially thought it was not necessarily 1, it might be some arbitrary 2^x 3^y 5^z, and the tetrahedral cardinality would still apply. But then I realized that P must apply to 2^x 3^y 5^z and hence necessarily eventually strips away all factors of 2,3 or 5 and maps the smallest element to 1.)
Thanks for smci.
