0
$\begingroup$

Yes, this is an attempt to understand why my solution for Project Euler problem 160 isn't working. I hesitate to post my code lest I offer a solution to someone else.

The problem is to find the last n non-zero digits of a factorial. In this case, 5 digits.

I factorize all numbers from 2 to 100,000

For example, for n=9: 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9

would be:

2^7 3^4 5^1 7^1

cancelling all the powers of 5 with corresponding 2s:

2^6 3^4 7^1

I tested on 9! 10! 11! 12! 13! 20! and got the last 5 digits. I tried 100,000! and got the same number that I had achieved by a different method: 62496 This made me realize that even though the pattern repeats, I must multiply them together.

Since 10^12 = 10^5 * 10^7

the answer should require computing the answer I get for 100,000! to the power 10^7.

powermod(62496, 1e7, m)

where m is the modulo 10^5 to take out the low m digits.

I think I'm on the right track here, but since Project Euler tells me I'm wrong, my question is am I missing some bookkeeping thing, or is my approach flawed?

My new approach is to consider each terminating digit:

1 2 3 4 5 6 7 8 9

All numbers ending in 1 just multiply:

prod = 1
for i = 1 to 1 trillion stepping by 10
  prod = (prod * (i mod m) ) mod m
  powers2 += 4; // account for 2, 4, 6, 8 (can pull this out of the loop)
  d2 = (i+1)/2
  prod = (prod * (i mod m) ) mod m

  same for d3, d4, d6, d7, d8.  Evens get divided by 2

  d5 = (i+4) / 5
  while (d5 mod 5 == 0)
    powers5++
    d5 /= 5
  end while

  d10 = (i+9)/10
  while (d10 mod 5 == 0)
    powers5++
    d10 /= 5
  end while
end

powers2 = powers2 - powers5
prod = (prod * powermod(2, power2, m)) mod m

I evidently didn't get the right answer, is this concept flawed too?

Could I have combined these two concepts? I still don't see why I care about any high digits. They don't affect low digits. I do, however, need to account for extra powers of 5 resulting in more zeros. Could I just do brute force for numbers ending in 5 and 10, find out how many there are and cancel with just enough from numbers ending in 2, but do the remaining ones by multiplying all the digits from 1 to 100000? The bookkeeping of that seems complicated, and I still have to multiply 3/10 of the trillion numbers so it's not ideal.

Alternatively, can I consider all multiples of 5^2, 5^3 .. 5^17, and 2^2 2^3 ... 2^k? All I need is to pull those out, right?

How about counting all multiples of powers of 5 greater than 100,000? I can eliminate all powers of 2 in the multiplication of 1 to 100,000. Then

5^8 = 390625

There are 10^12 / 5^8 of these in the set. That should cover 5^9 and beyond as well, since anything that is a multiple of 5^8 is also a multiple of 5^9, 5^10, etc.

I get 2560000 multiples of 5^8. But 5^9 is one more 5, so:

total number of 5s: 10^12 / 5^8 = 2560000 10^12 / 5^9 = 512000 10^12 / 5^10 = 102400 10^12 / 5^11 = 20480 10^12 / 5^12 = 4096 10^12 / 5^13 = 819 10^12 / 5^14 = 163 32 6 1

Total multiples of 5: 2560000+512000+102400+20480+4096+819+163+32+6+1

So if I multiply 1 to 100,000 mod 100,000 removing all multiples of 5, and remove enough powers of 2 so that when I take it to the power:

powers5 = 2560000+512000+102400+20480+4096+819+163+32+6+1
prod = multmod(1 to 100,000, modulo 100,000)  // factoring out 5s and 2s
prod = powermod(prod, 10^7, mod 100,000)

powers2 = powers2 * 10^7
powers2 = powers2 - powers5

prod = prod * powermod(2, powers2, mod 100000)
|cite|improve this question
$\endgroup$
1
$\begingroup$

Your last step is not valid, because things do not repeat in this way (think about what happens when you reach a new power of 5, for instance).

Since this is Project Euler I won't give a solution. However I will point out the (hopefully obvious) fact that you won't be able to solve this by considering all primes less than $10^{12}$, so you will need a different approach.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I don't get it at all. In order to know the bottom 5 digits of a big multiplication, I need to know the numbers I am multiplying together. Take the case of just the last digit. If I want to know the last digit of 20!, the leading 2 is irrelevant. I simply multiply 1*2*3*4*5*6*7*8*9, the 10 doesn't matter, then I do it again *1*2*3*4*5*6*7*8*9. The last digit is a 4. 20! ends in a 4. How is that wrong? $\endgroup$ – Dov Dec 6 '13 at 3:13
  • $\begingroup$ What happens when you try this for 30! ? (The difference being that $20 < 5^2 < 30$.) $\endgroup$ – universalset Dec 6 '13 at 3:17
  • $\begingroup$ I am trying to learn here, and I feel Project Euler's rights do not trump mine in this matter. I see about the powers of 5. All I came up with is brute force multiplication mod m for 1 to 1 trillion. It's not hugely slow, about 18 minutes. I divide out powers of 5 and powers of 2 for numbers ending in 2,4,6,8. That way I have more than enough 2s to match up with the 5s. I still don't have the answer right though $\endgroup$ – Dov Dec 13 '13 at 14:01
  • $\begingroup$ Let's make a few observations: (a) If I didn't have to worry about multiples of 2 and 5 (let's pretend I wasn't even including them in the product) then I could just count the numbers of factors with each remainder (mod $10^5$) in the product, and then exponentiate for each such remainder (mod $10^5$) and then take the product of the results (mod $10^5$). (b) I do care about numbers which are multiples of 2 and 5. Perhaps I can somehow "strip off" the prime factors of 2 and 5 from these numbers and let the results contribute to the counts above. (c) Now I have to deal with the 2s and 5s. $\endgroup$ – universalset Dec 14 '13 at 1:45
  • $\begingroup$ I will add that to do the counting / stripping out factors of 2 and 5 thing, you will want to do this globally (and recursively) rather than considering each term in the factorial separately. $\endgroup$ – universalset Dec 14 '13 at 1:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.