eehaa.blogg.se - Project euler 54

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.

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. His basic algorithm here is to figure out how many duplicates are present, and subtract that value from the maximum.Īs for counting duplicates, it might help intuitively to think of the numbers in terms of their prime factors. There are 99 possible numbers, so the number of combinations is 99 * 99, with possible duplicates. Well, the question involves ways to combine two numbers chosen from a range. And it misses some pairs of rows entirely (you never have i=9 and j=27, or i=27 and j=81). But again, unless I'm missing something, the program seems hopelessly imprecise. 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.

I've marked two places where there are duplicates. Here is a picture of that simpler problem, for x=3 and b ranging only from 2 to 10. 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. So we have established that for all duplicates, a 1 = x e 1 and a 2 = x e 2 for some integers x, e 1, and e 1.

8 6 = 4 9 this is possible because 8 and 4 are both powers of 2.

9 7 = 3 14 this is possible because 9 and 3 are both powers of 3.

So there are only going to be duplicates a 1 b 1 = a 2 b 2 when a 1 and a 2 are distinct integer powers of the same integer, which I'll call x. 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.ĮDIT: How can we (correctly) count the duplicates?įirst you must understand that two numbers are only the same if they have the same prime factorization. Other players consider that rather against the spirit of the thing.Īnyway-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.

I have read that some players like to produce approximate answers and then dictionary-attack the Project Euler servers to brute-force the problem. Prime.I may be missing something, but it seems to me this program gives the wrong answer.