- #36
DeathByKugelBlitz
Gold Member
- 28
- 16
5b could be done in Python?
First calculate 1000! then use python to count the zeroes?
First calculate 1000! then use python to count the zeroes?
I guess a simple count is easier and faster.DeathByKugelBlitz said:5b could be done in Python?
First calculate 1000! then use python to count the zeroes?
This is not correct. You cannot count those in between!DeathByKugelBlitz said:5b:
import math
A = str(math.factorial(1000))
A.count('0')
472
It can be done in one line without coding, two, if an explanation line is added!DeathByKugelBlitz said: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)
fresh_42 said:It can be done in one line without coding, two, if an explanation line is added!
You know that every integer can be written as a product of primes? That's all you need, and some 3rd grader divisions.DeathByKugelBlitz said:I'm new to this, only know what we learned 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.DeathByKugelBlitz said:I'm new to this, only know what we learned in lecture
Why did you count the twos? Were you afraid there might not be enough of them?fbs7 said: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.. :(
I have serious trouble decoding that! I assume that "xN." doesn't mean the hexadecimal number N?fbs7 said: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!
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 said: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 said: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.
Count the fives, that'll do.DeathByKugelBlitz said:This is annoying lol
I'm just going to import math and math.factorial(1000) then count the zeroes myself lol
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.fresh_42 said:Not sure what the string means,
fresh_42 said: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.
And without code it is a two liner:fbs7 said: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!
fbs7 said:##\lfloor(1000/5) \rfloor + \lfloor(1000/25)\rfloor + \lfloor(1000/125)\rfloor + \lfloor(1000/625)\rfloor=200+40+8+1=249##
>>> len(str(math.factorial(1000)))-len(str(math.factorial(1000)).rstrip("0"))
249
mfb said:Python also has "rstrip", which makes it a one-liner:
Code:>>> len(str(math.factorial(1000)))-len(str(math.factorial(1000)).rstrip("0")) 249
fresh_42 said:5.) Prove that starting with ##\frac{1}{1}## the following binary tree
$$
\begin{array}{ccccc}
&&\frac{a}{b}&&\\
&\swarrow &&\searrow \\
\frac{a}{a+b}&&&&\frac{a+b}{b}
\end{array}
$$
defines a counting of all positive rational numbers without repetition and all quotients canceled out.
No quite correct, as you cannot conclude that the quotients have equal numerators and denominators as long as you don't know that they are canceled out, which for ##c/c## is obviously not the case.Bosko said:1) Let prove that for any ##\frac{a}{b}## in the tree , a and b are positive natural numbers. ( The mathematical induction by depth n of the tree )
for 0 , ##\frac{1}{1}## , a=1 and b=1 are positive natural numbers
for n-1 , we assume that for all numbers in form ##\frac{a_i }{b_i}## on depth n-1 , ##a_i## and ##b_i## are positive and natural . ( depth = distance from the root )
for n , and any ##\frac{a}{b}## on depth n is either ##a=a_i## and ##b=a_i + b_i## or ##a=a_i+b_i## and ##b=b_i##
In both cases a and b are positive natural numbers.
2) There is no non-root ##\frac{c}{c}## , in the tree (c is positive natural number as proven in (1.) ),
Let assume the opposite . There is non-root ##\frac{c}{c}## in the tree.
Then the "parent" ##\frac{a}{b}## of ##\frac{c}{c}## exists and either ##\frac{c}{c}=\frac{a}{a+b}## or ##\frac{c}{c}=\frac{a+b}{b}##
if ##\frac{c}{c}=\frac{a}{a+b}##
c=a , c=a+b
a=c , b=c-c
"parent" is ##\frac{c}{0}## -> 0 is not positive natural number -> contradiction
if ##\frac{c}{c}=\frac{a+b}{b}##
c=a+b , c=b
a=c-c , b=c
"parent" is ##\frac{0}{c}## -> 0 is not positive natural number -> contradiction.
Very nice.Consequence -> Only the "root" ##\frac{1}{1}## is equal 1
Notice -> Every "left child" is ##\frac{a}{a+b}<1## and every "right child" ##\frac{a+b}{b}>1## of any "parent" ##\frac{a}{b}##
3) "... all quotients canceled out"
a) if c is divisor of a and a+b ( "left child" ##\frac{a}{a+b}## ) then c is divisor of a and b=a+b-a ("parent" ##\frac{a}{b}## )
b) if c is divisor of a+b and b ( "right child" ##\frac{a+b}{b}## ) then c is divisor of a=a+b-b and b ("parent" ##\frac{a}{b}## )
If c is divisor of ##a_n## and ##b_n## for some ##\frac{a_n}{b_n}## on the "depth" n of the tree.
Then c is divisor of ##a_{n-1}## and ##b_{n-1}## for the "parent" ##\frac{a_{n-1}}{b_{n-1}}## on the depth n-1 of the tree
... on the depth n-2 of the tree
...
Then c is divisor of ##a_0=1## and ##b_0=1## for the "root" ##\frac{1}{1}## on the depth 0 of the tree
Then c=1 . ##\frac{a_n}{b_n}## are already canceled out.
4) "... all positive rational numbers..." are in the tree
Let assume that there is a positive rational number ##\frac{a_0}{b_0}## not in the tree
If ##a_0 < b_0## then its "parent" ##\frac{a_1}{b_1}=\frac{a_0}{b_0-a_0}## is not in the tree also.
Because if the "parent" ##\frac{a_1}{b_1}## is in the tree then the "left child" ##\frac{a_1}{a_1 + b_1}=\frac{a_0}{b_0-a_0+b_0}=\frac{a_0}{b_0}## is in the tree
##a_0 = a_1##
##b_0 > b_1 = b_0-a_0##
If ##a_0 > b_0## then its "parent" ##\frac{a_1}{b_1}=\frac{a_0-b_0}{b_0}## is not in the tree also.
Because if the "parent" ##\frac{a_1}{b_1}## is in the tree then the "right child" ##\frac{a_1+b_1}{b_1}=\frac{a_0-b_0+b_0}{b_0}=\frac{a_0}{b_0}## is in the tree
##a_0 > a_1=a_0-b_0##
##b_0 = b_1 ##
Similarly we will get that the "parent" of the "parent" ##\frac{a_2}{b_2}## and ##\frac{a_3}{b_3}##... are not in the tree
But in every step either ...
##a_i = a_{i+1}## and ##b_i> b_{i+1}## or ...
##a_i > a_{i+1}## and ##b_i= b_{i+1}##
Means that ##a_i + b_i > a_{i+1} + b_{i+1}##. and there is n so ##a_n=b_n=1##. and ##\frac{a_n}{b_n}=\frac{1}{1}## is not in the tree .
but ##\frac{a_n}{b_n}=\frac{1}{1}## is the "root" of the tree.
Our assumption that ##\frac{a_0}{b_0}## is not in the tree is wrong
5) "... without repetition..." (as you assume / I will assume the opposite :-) )
There are two different "node"-s in the tree with the same numbers ##\frac{a_0}{b_0}=\frac{c_0}{d_0}##
and its "parents" ##\frac{a_1}{b_1}=\frac{c_1}{d_1}## are equal and different nodes of the tree
and the "grand parents"...
...
and ##\frac{1}{1}=\frac{a_n}{b_n}=\frac{c_n}{d_n}## are equal and different nodes of the tree.
Our tree have two roots -> impossible . My assumption is wrong.
Nice idea . Thanksfresh_42 said:... We define a norm of these elements by ##N(p/q)=p+q\,.## The parent quotient of ##\frac{p}{q}\neq \frac{1}{1} ## is either ##\frac{p}{q-p}## or ##\frac{p-q}{q}##. The norm of the child has strictly increased in both cases. Now we have a linear ordering of the levels and can argue by minimality instead of running all the way up.
a=1
b=1
repeat ...
r= random () # random number from the segment[0,1]
if r<0.5 then
b=a+b
else
a=a+b
You should use the hint of the question before, they are closely related.fbs7 said:Hmm... there must be another way of doing 4, without cheating with Euler... hmm...
It is clear that all ##x_i \cdot y_j ## divide ##x \cdot y##. But why does every divisor have this form?fbs7 said:Hmm...sorry... trying with the latex thingie with my cheater's proof:
I) if ##(2^n-1)## is prime, then ##z=2^{(n-1)}*(2^n-1)## is perfect:
the factors of z (less z) are:
##1,2,2^2,...,2^{(n-1)},##
##(2^n-1),2*(2^n-1),(2^2)*(2^n-1),...,2^{(n-2)}*(2^n-1)##
sum of the factors (less z) is
##S=1+2^1+2^2+...+2^{(n-1)}+##
##(2^n-1)*(2^0+2^1+...+2^{(n-2)})##
the sum of a geometric series is ##a_1*(r^n-1)/(r-1)##; so
##S=1*(2^n-1)/(2-1) + (2^n-1)*( 1*(2^{(n-1)}-1)/(2-1) )##
##= (2^n-1) + (2^n-1)*(2^{(n-1)}-1)##
##= (2^n-1)*(2^{(n-1)}-1+1)##
##= (2^n-1)*2^{(n-1)}=z##
so the sum of factors (less z) is equal to z, so z is perfect.
============================================================================
II) If X is even and X is perfect, then ##X = (2^n-1)*2^{(n-1)}##
I had to spy on Euler's proof for this guy; this is my version of Euler's proof, assuming no previous knowledge.
divisors of ##x = ##{##1,x_1,x_2,...,x##} = {##x_i##}
divisors of ##y = ##{##1,y_1,y_2,...,y##} = {##y_j##}
define s(x) as the sum of all divisors of x (including x), ie
##s(x) = sum( x_i )##
##s(y) = sum( y_j )##
if ##z = x*y##
then every divisor of z has the form ##x_i*y_j##, therefore
Why is it impossible? What happens if ##a>1\,##?##s(z) = (1*1+1*y_1+1*y_2+...+x_1*1+x_1*y_1+x_1*y_2+...+x_2*1+x_2*y_1+x_2*y_2+...##
##= 1*(1+y_1+y_2+...)+x_1*(1+y_1+y_2+...)+x_2*(1+y_1+y_2+...)+...##
##= 1*s(y)+x_1*s(y)+x_2*s(y)+...##
##= (1+x_1+x_2+...)*s(y)##
##= s(x)*s(y)##
therefore ##s(x*y) = s(x)*s(y)##
So, if z is even and perfect, then z is a multiple of 2, ie for some k there is an odd x:
##z = 2^{(k-1)}*x##, x is odd
##s(z) = s( 2^{(k-1)} * x ) = s(2^(k-1))*s(x)##
for k=1, we have ##s(2^{(k-1)}) = s(1) = 1##
for k=2, we have ##s(2^{(k-1)}) = s(2) = 1+2##
for k=3, we have ##s(2^{(k-1)}) = s(4) = 1+2+4##
...
for k=k, we have ##s(2^{(k-1)}) = 1+2^1+...+2^{(k-1)}##
that's the sum of a geometric series with a1=1, r=2, n=k; ie
##s(2^{(k-1)}) = 1*(2^k-1)/(2-1) = 2^k-1##
##s(z) = (2^k-1)*s(x)##
as z is perfect, s(z) = 2*z, so
##s(z) = 2*z = 2*2^{(k-1)}*x = (2^k-1)*s(x)##
##(2*2^{(k-1)})*x = (2^k-1)*s(x)##
##(2^k)*x = (2^k-1)*s(x)##
##(2^k-1)*x + x = (2^k-1)*s(x)##
##s(x) = x + x/(2^k-1)##
s(x) is integer and x is integer, therefore ##x/(2^k-1)## is integer, therefore ##(2^k-1)## is a divisor of x.
It remains to prove that x has no other divisors except 1. For some y,
##x = (2^k-1)*y##
##s(x) = x + (2^k-1)*y/(2^k-1) = x + y##
now, the divisors of x will in general be {1,a,b,c,...,x }, therefore
##s(x) = 1+a+b+c+...+x = x+y##
that's impossible to satisfy for any a,b,c, therefore a, b, c do not exist, and x only has 2 divisors, so:
##s(x) = 1 + x = x + y##
The proof would have been a bit shorter with a closed formula for ##s(z)##.then ##y=1##, and ##x = (2^k-1)## and has no other divisors other than 1 and itself, therefore it is a prime. That way
##z = (2^k-1)*(2^{k-1})##, where ##2^{k-1}## is prime
I so wish there's a way to prove this by induction; this is kinda screaming induction... Induction would be so awesome!
fresh_42 said:Looks o.k. in general. Just a few remarks. I think there are some further steps needed.
It is clear that all ##x_i \cdot y_j ## divide ##x \cdot y##. But why does every divisor have this form?
Given ##d\,|\,(xy)##, show that ##d=x_iy_j## for some pair ##(i,j)\,?##
The problem is the following: If ##d|(xy)## then ##d=x_{i_1}\ldots x_{i_k}y_{j_1}\ldots y_{j_l}##, i.e. the divisors of ##d## are somehow distributed over the divisors of ##x## and ##y##. But we cannot conclude that ##x_{i_1}\ldots x_{i_k}## is again a divisor of ##x##, e.g. ##2|12## and ##4|12## but ##8\nmid 12\,.## So how does ##d## have the desired form?
In other words: ##s(2)\cdot s(6) = 3 \cdot 12 = 36 \neq 28 = s(12)##. So ##s(xy)\neq s(x)s(y)## in general. However, with an additional assumption it is true, and you only need it in the restricted version. Which is the additional assumption and can you prove it in that case?