# Challenge Math Challenge - March 2019

• Featured

#### fresh_42

Mentor
2018 Award
I got this but i made mistake somewhere
import math
A = (str(math.factorial(1000)))
B = (str(int(math.factorial(1000)))[::-1])
C = len(A) - len(B)
print(C)
It can be done in one line without coding, two, if an explanation line is added!

#### DeathByKugelBlitz

Gold Member
It can be done in one line without coding, two, if an explanation line is added!
I'm new to this, only know what we learnt in lecture

#### fresh_42

Mentor
2018 Award
I'm new to this, only know what we learnt in lecture
You know that every integer can be written as a product of primes? That's all you need, and some 3rd grader divisions.

#### Ibix

I'm new to this, only know what we learnt in lecture
Your approach should work in principle. Expand your calculation of B over several steps and make sure each one is doing what you think it is - I can think of a couple of likely failure points.

As fresh says, there are more elegant solutions.

#### DeathByKugelBlitz

Gold Member
import math
def reverse_int(n):
return int(str(n)[::-1])
A = (math.factorial(1000))
B = (reverse_int(A))
C = int(B)
D = A.count(0)
E = C.count(0)
print(D - E)

NameError: name 'D' is not defined

#### fbs7

I tried the 1000! problem with logic, by counting the x10 and x100 numbers, then counting the x2 . x5 combinations that produce 1, 2, 3 and 4 zeroes... but I got the wrong total of zeroes compared to the real number from Wolfram-Alpha's ...

That puts me back in kindergarten, oh no.. :(

#### fresh_42

Mentor
2018 Award
I tried the 1000! problem with logic, by counting the x10 and x100 numbers, then counting the x2 . x5 combinations that produce 1, 2, 3 and 4 zeroes... but I got the wrong total of zeroes compared to the real number from Wolfram-Alpha's ...

That puts me back in kindergarten, oh no.. :(
Why did you count the twos? Were you afraid there might not be enough of them?

Last edited:

#### fbs7

Because 2.5 = 10, so each group of 1.2.3.4.5.6.7.8.9 = 2.5.(1.3.4.6.7.8.9) = 10.(36,288)

So numbers that end in 1,3,4,6,7,8,9 don't add any zeroes to the result ( ex x3.x6 = (10x+3).(10x+6) = 100x^2 + 10.(3+6).x + 6.3... no zeroes in any x6.x3 for all x in {0..99} ).

As any number ending in 2 will be followed by a number ending in 5 in the sequence {1..1000}, then for x in 0..99 we have x2.x5 = 100x^2 + 10.(2+5)x + 10 = 100x^2+10(7x+1), therefore x2.x5 add zeroes. So we get 1x3 zeroes from 1000, 9x2=18 zeroes from 100, 200, .. , 900, 90x1 zeroes from 10, 20, ..., 90, 110, 120, ..., 190, 210, ... , 290, .. , 990, = 111 zeroes, plus the zeroes from the multiplications of x2.x5.

The zeroes for x2.x5 will be 1 for each x in 0..99... which is 100 numbers (ex 22.25 = 550); then 1 more for each (10.x^2 mod 10 + 7x+1) that is multiple of 10; then 1 more for each (x^2 mod 10 + 7x+1 ) that is multiple of 100. Inspection shows that only x=7, 17, 27, ..., 97 produces that expression as multiple of 10 (ex 372.375 = 139,500), and only 87 produces an expression that is multiple of 100 (872.875 = 736,000). So the x2.x5 terms produce 100 + 10 + 1 = 111 zeroes.

This calculation yields 222 zeroes, but Wolfram-Alpha shows 249 zeroes, so my result is wrong... I'm missing something and I have no clue what... :-(

Back to kindergarten, fbs7!

Last edited:

#### fresh_42

Mentor
2018 Award
Because 2.5 = 10, so each group of 1.2.3.4.5.6.7.8.9 = 2.5.(1.3.4.6.7.8.9) = 10.(36,288)

So numbers that end in 1,3,4,6,7,8,9 don't add any zeroes to the result ( ex x3.x6 = (10x+3).(10x+6) = 100x^2 + 10.(3+6).x + 6.3... no zeroes in any x6.x3 for all x in {0..99} ).

As any number ending in 2 will be followed by a number ending in 5 in the sequence {1..1000}, then for x in 0..99 we have x2.x5 = 100x^2 + 10.(2+5)x + 10 = 100x^2+10(7x+1), therefore x2.x5 add zeroes. So we get 1x3 zeroes from 1000, 9x2=18 zeroes from 100, 200, .. , 900, 90x1 zeroes from 10, 20, ..., 90, 110, 120, ..., 190, 210, ... , 290, .. , 990, = 111 zeroes, plus the zeroes from the multiplications of x2.x5.

The zeroes for x2.x5 will be 1 for each x in 0..99... which is 100 numbers (ex 22.25 = 550); then 1 more for each (10.x^2 mod 10 + 7x+1) that is multiple of 10; then 1 more for each (x^2 mod 10 + 7x+1 ) that is multiple of 100. Inspection shows that only x=7, 17, 27, ..., 97 produces that expression as multiple of 10 (ex 372.375 = 139,500), and only 87 produces an expression that is multiple of 100 (872.875 = 736,000). So the x2.x5 terms produce 100 + 10 + 1 = 111 zeroes.

This calculation yields 222 zeroes, but Wolfram-Alpha shows 249 zeroes, so my result is wrong... I'm missing something and I have no clue what... :-(

Back to kindergarten, fbs7!
I have serious trouble decoding that! I assume that "xN." doesn't mean the hexadecimal number N?
You shouldn't worry about the last digits, just write $1000!$ as a product of primes.

#### DeathByKugelBlitz

Gold Member
import math
def primeFactors(n):
while n % 2 == 0:
print 2,
n = n / 2
for i in range(3,int(math.sqrt(n))+1,2):
while n % i== 0:
print i,
n = n / i
if n > 2:
print n
(primeFactors(math.factorial(1000)))

2 2 13 107 36791

#### fresh_42

Mentor
2018 Award
import math
def primeFactors(n):
while n % 2 == 0:
print 2,
n = n / 2
for i in range(3,int(math.sqrt(n))+1,2):
while n % i== 0:
print i,
n = n / i
if n > 2:
print n
(primeFactors(math.factorial(1000)))

2 2 13 107 36791
Not sure what the string means, as there are plenty of primes in $1000!$. Each prime below $1000$ occurs at least once, and the smaller primes do occur quite often. Fortunately, we are only interested in two primes.

#### DeathByKugelBlitz

Gold Member
Not sure what the string means, as there are plenty of primes in $1000!$. Each prime below $1000$ occurs at least once, and the smaller primes do occur quite often. Fortunately, we are only interested in two primes.
This is annoying lol

I'm just gonna import math and math.factorial(1000) then count the zeroes myself lol

#### fresh_42

Mentor
2018 Award
This is annoying lol

I'm just gonna import math and math.factorial(1000) then count the zeroes myself lol
Count the fives, that'll do.

#### Ibix

Not sure what the string means,
Almost certainly, it means that something in the primeFactors function does not respect unlimited precision integers. Not sure which step without a python interpreter to hand.

#### fbs7

I have serious trouble decoding that! I assume that "xN." doesn't mean the hexadecimal number N?
You shouldn't worry about the last digits, just write $1000!$ as a product of primes.
Oh, sorry, that was short-hand; that meant x2 = a number ending in 2, that is x2 = (10x + 2), like, x2 = 22 or 42 or 132 and so forth; meanwhile x5 is a the same first digits, but ending in 5, like 25, 45 or 135.

#### fbs7

Hmm.. product of primes... what this means... hmm...

#### fbs7

Oh... I see!... what a smart man!!! This is my attempt at 5b:

17! has 17 numbers in it. So, between 1 and 17 there are floor(17/2)=8 numbers divisible by 2! They are 2,4,6,8,10,12,14,16. Then there are floor(17/2^2)=4 numbers divisible by 4! They are 4,8,12,16. And floor(17/2^3)=2 numbers divisible by 8, and floor(17/2^4)=1 numbers divisible by 16.

Therefore 17! must be 2^(8+4+2+1)*x = 2^15*x = 32768*x; proof is

X = 17! = 355687428096000 = 32768*10854718875

What an excellent thing!! So

X = 1000! = 2^a * 3^b * 5^c * etc...

Now, there are more numbers (<X) divisible by 2 than there are numbers divisible by 5, therefore a>b, therefore each factor 5 can be paired with a factor 2 to generate a number 10, and as no other pair of primes multiply to 10 or multiple, then no other primes matter other than 5!

So, we only need to consider the number of factors for 5 (not the number of twos!! now I get it - haha!!)

X=1000!
5^1... floor(1000/5)=200
5^2... floor(1000/25)=40
5^3... floor(1000/125)=8
5^4... floor(1000/625)=1
5^5... floor(1000/3125)=0
stop

The number of 2*5=10 factors in the factorization by primes is therefore 200+40+8+1=249! And that matches Wolfram-Alpha!! Hooray!!

This is extraordinary! If I could cook, I'd cook you some cookies, fresh_42!

Last edited:

#### fresh_42

Mentor
2018 Award
The number of 2*5=10 factors in the factorization by primes is therefore 200+40+8+1=249! And that matches Wolfram-Alpha!! Hooray!!
And without code it is a two liner:

We have enough $2$ for pairing with $5$, so we only need to count the number of prime factors $5$ in $1000!$ which is
$\lfloor(1000/5) \rfloor + \lfloor(1000/25)\rfloor + \lfloor(1000/125)\rfloor + \lfloor(1000/625)\rfloor=200+40+8+1=249$

#### fbs7

Now I see the error in my original thought process. The right solution counts:

1 zero for each multiple of 5 (all of them end in 5 or 0)
+1 zero for each multiple of 25 (all of them end in 25, 50, 75 or 00)
+1 zero for each multiple of 125 (all of them end in 125,250,375,500,625,750,875 or 000)
+1 zero for each multiple of 625 (for <1000, that means end in 625)
----------------
249 zeroes

My original count that yielded 222 zeroes went from the last digits:

1 zero for each number ending in 0
+1 zero for each number ending in 00
+1 zero for each number ending in 000
+1 zero for each number ending in 5
+1 zero for each number ending in 75
+1 zero for each number ending in 875
---------------
222 zeroes

Problem with the 2nd count is that misses zeroes on numbers that end in 25,50,125,250,375,625,750. The right count on the 2nd method should have been:

1 zero for each number ending in 0
+1 zero for each number ending in 00
+1 zero for each number ending in 000
+1 zero for each number ending in 5
+1 zero for each number ending in 25, 50 or 75
+1 zero for each number ending in 125, 250, 375, 500, 625, 750 and 875
+1 zero for each number ending in 625
---------------
249 zeroes

The underlying logic fail is that I failed to consider what happens to (10x+2)*(10x+5) when x itself is a multiple of 5. Of course the 1st method is much simpler.

This kind of thing is a common problem, I suspect: one goes down instinctively in some direction, and ends in a rabbit hole that he can't get out of. Mind was decided in considering in detail the last digits of the numbers, but didn't get it right and was blind to an easier approach.

Last edited:

#### mfb

Mentor
By the way: Python can calculate the factorial correctly.
math.factorial(1000) -> long number
len("[copied zeros]") -> 249

Python also has "rstrip", which makes it a one-liner:
Code:
>>> len(str(math.factorial(1000)))-len(str(math.factorial(1000)).rstrip("0"))
249
But the insight that it is sufficient to count factors of 5 is much better.

"Math Challenge - March 2019"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving