PROJECT EULER #29

Question

Well, after solving this problem by naive STL set,I was reading the forum entries,there I find this entry :

 #include <iostream>   
 #include <cmath> 
 #define MAX 100
 using namespace std;

 int main(){
    int res=(MAX-1)*(MAX-1);
    for(int i=2;i<MAX;i++)
        for(int j=i*i;j<=MAX;j=j*i)
            res = res-int(MAX*(log(i)/log(j)))+1;
     cout<<res<<endl;
     return 0;
  }

The author's explanation : Maximum will be 99*99. I subtracted occurrences of those numbers which are powers of some lower numbers (2-100): - For example: - 4^2,4^3,4^4 (i.e. 3 should be subtracted) as they will be duplicates from lower number powers as in 2^4,2^6,2^8

This program is giving correct answer check here but I am unable to get the implemented logic,to be precise I am not getting how the duplicates are determined. Could somebody help ?

Answer 1

There are (at least) two ways to approach this problem. One is to start your count of distinct values at 0, and add one for each calculated value that hasn't been seen before. The other way is to calculate the maximum number of values, and then subtract one for each duplicate.

The poster is attempting the second methed. a can range from 2 to 100 for 99 values, as can b, so there are 99 * 99 produced values. The poster then attempts to subtract the duplicate values to get the correct answer.

Edit: However, the poster has written an incorrect algorithm. For instance, setting MAX = 8 or 9. For 8 it should give 44 but it gives 45. For 9 it should give 54 but gives 56. Either they lucked out and happened across an algorithm that gives the correct answer for some inputs, or they reverse-engineered an algorithm that worked when MAX = 100 but not for all other values.

Answer 2

first, it sets res to 99*99 at line 6, because MAX was defined as 100. Then it enters a loop, with the condition that i is smaller than MAX. then it enters this pseudocode loop

int i;
int j;
int x=2;

for( j = i²; j <= MAX , j = i^x)
{
res = res- (MAX* ( ^jlog(i) )+1;
x++;
}

sorry 'bout the not using <pre><code> above; but if I did I could not use <sup>

Please note log(a)/log(x) is the same as ^xlog(a)

---

comments on question because <sup> does not work there:

²log(2) = 1 because 2¹ = 2
²log(4) = 2 because 2² = 2
log(x) == ¹⁰log(x)
log(10) = 1

^glog(x) = y => g^y = x

Answer 3

Well, the question involves ways to combine two numbers chosen from a range. There are 99 possible numbers, so the number of combinations is 99 * 99, with possible duplicates. His basic algorithm here is to figure out how many duplicates are present, and subtract that value from the maximum.

As for counting duplicates, it might help intuitively to think of the numbers in terms of their prime factors. Raising a number to an integer power means multiplying it by itself; so, represented as a list of primes, this is equivalent to simply concatenating the lists. For instance, 6 is {2, 3}, so 6^3 would be {2, 2, 2, 3, 3, 3}. Note that if you count how many times each prime appears in the list, x^n will always have the same proportions as x, for instance 6^n will have an equal quantity of 2's and 3's. So, any two numbers in the range with the same proportion between primes must both be powers of some number.

So, in the full list, each distinct proportion of prime factors will appear repeatedly as x^2, x^3, x^4..., (x^3)^2, (x^3)^4..., (x^4)^2..., etc., where x is the smallest number with that proportion; more precisely, (x^m)^n where (x^m) <= 100 and 2 <= n <= 100. Since (x^m)^n is equal to x^(m*n), counting duplicates amounts to counting the ways that x^(m*n) can also be <= 100.