\(a^b \forall \; 2 \leq a,b \leq 100\)
Unique means that any term is counted only once, e.g. $2^32 = 16^8 = 4^16$ is counted only once. You could - of couse - use a brute force method using large Integeres and the c++ container set. However, there is a more elegant approach that can be used to avoid explicit calculation of \(a^b\).
If you - for once - ignore multiple occurences, it is quite straightforward to get the number of terms.
Each \(a\) produces \(100-2+1=99\) terms. As there are \(100-2+1=99\) possible values for a, that yields \(9801\) terms. From this number the number of duplicates has to be subtracted.
I tried to write an implementation in C++, but it did not come to the correct result. In the end it was much faster and easier to do the calculations and logic by hand:
First consider numbers \(k\) that can be written as \k=(a^2\) with
\(\forall \, i \in \mathbb{N}: \sqrt[i]{a} \not\in \mathbb{Q}\), i.e. \(a \in \{2,3,5,6,7,10\}\)
For \(4^n = 2^{2n}\) it is easy to be seen that every term is a duplicate of 2\(2^{\frac{2n}{2}}\) up to \(2n = 100\), resulting in 49 duplicates. This is true for any \(a\) given above. Therefore we have \(6*49 = 294\) duplicates so far.
Secondly take into account numbers \(k\) that can be written as a third power of another number, the latter of which cannot be written as a power of a smaller number:
\(k=a^3, \forall \, i \in \mathbb{N}: \sqrt[i]{a} \not\in \mathbb{Q}\), i.e. \(a \in \{2,3\}\)
For \(k^n = a^{3n}\) every term is a duplicate \(\forall n \in [2, 33]\), resulting in 32 duplicates for each \(a\). Furthermore, there are duplicates for which \(a^{3n} = a^{2\tilde n}\). Obviously, all values \(\in \leq 50\) have already been accounted for. The upper bound of the interval is given by \(n_{max} = \frac{2}{3}\tilde n_{max}\) with \(\tilde n_{max} = 100\). The lower bound is \(34\). Only even numbers are to be taken into account. This results in another \(17\) duplicates for each \(a\). Altogether that is \(98\) duplicates.
In the next step take into account the numbers that can be written as fourth powers of other numbers. In this case these are \(k = 16 = 2^4\) and \(k = 81 = 3^4\). In the same fashion as above we get 49 duplicates for the cases where \(a^{4n} = a^{2\tilde n}\). In addition we have to consider the cases for which \(a^{4n} = a^{3\tilde n}\). \(n\) has to be a multiple of \(3\) and also \(51 \leq n \leq 75\), thus adding \(9\) more duplicates for each \(k\).
From now on only powers of \(2\) are to be considered, as \(3^5 = 243 > 100\). We now need to find \(n\), s.t.
\(2^{5n} = 2^{i\tilde n} \forall i \in [1,4]\)
For \(i = 1\) n goes from \(2\) to \(20\), giving \(19\) duplicates. If \(i = 2\) there are duplicates for all even \(n \in [22, 40]\), that is \(10\) duplicates. For \(i = 3\) all multiples of 3, \(n = 3k \in [21, 60]\) are duplicate. The duplicates already accounted for for \(i = 2\), i.e. \(\{24, 30, 36\}\) have to be ignored, i.e. \(11\) duplicates. Finally, for \(i = 4\) all multiples of 4 in the range \([44, 80]\) have to be counted, except for \(60\), which gives \(8\) duplicates. That makes for 48 duplicates.
The last case is \(64 = 2^6 = 8^2\). Using the same considerations as before, the number of duplicates can easily be determined to be 62:
\(64^n = 8^{\tilde n} \Rightarrow 49 \)
\(2^{6n} = 2^{4\tilde n} \Rightarrow 8 \)
\(2^{6n} = 2^{5\tilde n} \Rightarrow 5 \)
Adding up all duplicates we get:
\(294+98+116+48+64 = 618\)
So in the end there are \(9801 - 618 = 9183\) unique terms.
No comments:
Post a Comment