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

I may be missing something, but it seems to me this program gives the wrong answer. It's off by one. If I set MAX to 10, it's off by two.

I have read that some players like to produce approximate answers and then dictionary-attack the Project Euler servers to brute-force the problem. Other players consider that rather against the spirit of the thing.

Anyway—an algorithm like this (starting with N*M and eliminating duplicates) is the right way to tackle the problem, but as written this code doesn't make much sense to me. Note that in any case int(MAX*(log(i)/log(j))) is very sensitive to rounding error; but even if you eliminate that source of error by using integer arithmetic, the program still gives the wrong answer.

EDIT: How can we (correctly) count the duplicates?

First you must understand that two numbers are only the same if they have the same prime factorization. So there are only going to be duplicates a₁^b₁ = a₂^b₂ when a₁ and a₂ are distinct integer powers of the same integer, which I'll call x. For example,

• 9⁷ = 3¹⁴; this is possible because 9 and 3 are both powers of 3.
• 8⁶ = 4⁹; this is possible because 8 and 4 are both powers of 2.

So we have established that for all duplicates, a₁ = x^e₁ and a₂ = x^e₂ for some integers x, e₁, and e₁.

Then with a little algebra,

a₁^b₁ = a₂^b₂

x^e₁b₁ = x^e₂b₂

e₁b₁ = e₂b₂

Going back to the earlier examples,

• 9⁷ = 3¹⁴ because 2×7 = 1×14.
• 8⁶ = 4⁹ because 3×6 = 2×9.

So to find all duplicates for any given x, you only need to find duplicates for the simpler expression eb where 2 ≤ x^e ≤ 100 and 2 ≤ b ≤ 100.

Here is a picture of that simpler problem, for x=3 and b ranging only from 2 to 10. I've marked two places where there are duplicates.

e=1  a=3    *********
e=2  a=9      * * * * * * * * *
e=3  a=27       *  *  *  *  *  *  *  *  *
e=4  a=81         *   *   *   *   *   *   *   *   *
                  |               |
        1*8 = 2*4 =  4*2         3*8 = 4*6
        3^8 = 9^4 = 81^2        27^8 = 81^6

And here are the duplicates:

e=1  a=3    *********
e=2  a=9      x x x x * * * * *
e=3  a=27       x  x  x  *  x  *  *  *  *
e=4  a=81         x   x   x   x   x   *   *   *   *

The C++ program you found is trying to count them by visiting each pair of overlapping rows i and j, and calculating how much of row i overlaps row j. But again, unless I'm missing something, the program seems hopelessly imprecise. And it misses some pairs of rows entirely (you never have i=9 and j=27, or i=27 and j=81).