Math Challenge - March 2019

In summary, we discussed the proof of several mathematical statements and formulas, including the use of double integrals to prove a relationship between the Beta and Gamma functions, the fact that the Fourier series of an even function cannot contain sine, and the equivalence of two different double integrals. We also discussed the graphic representation of eye color probabilities and its connection to a real, commutative, distributive, three-dimensional algebra. Additionally, we explored various properties of this algebra, including its associativity and the existence of a weight function and basis. We also discussed the concepts of genetic and baric algebras and their relationship, and looked at several problems involving limits, sequences, and perfect numbers.
  • #36
5b could be done in Python?

First calculate 1000! then use python to count the zeroes?
 
Physics news on Phys.org
  • #37
DeathByKugelBlitz said:
5b could be done in Python?

First calculate 1000! then use python to count the zeroes?
I guess a simple count is easier and faster.
 
  • Like
Likes DeathByKugelBlitz
  • #38
5b:

import math
A = str(math.factorial(1000))
A.count('0')

472
 
  • #39
DeathByKugelBlitz said:
5b:

import math
A = str(math.factorial(1000))
A.count('0')

472
This is not correct. You cannot count those in between!
 
  • Like
Likes DeathByKugelBlitz
  • #40
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)
 
  • #41
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)
It can be done in one line without coding, two, if an explanation line is added!
 
  • #42
fresh_42 said:
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 learned in lecture :frown:
 
  • #43
DeathByKugelBlitz said:
I'm new to this, only know what we learned in lecture :frown:
You know that every integer can be written as a product of primes? That's all you need, and some 3rd grader divisions.
 
  • #44
DeathByKugelBlitz said:
I'm new to this, only know what we learned in lecture :frown:
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.
 
  • #45
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
 
  • #46
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.. :(
 
  • #47
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.. :(
Why did you count the twos? Were you afraid there might not be enough of them?
 
Last edited:
  • #48
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! :H
 
Last edited:
  • #49
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! :H
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.
 
  • #50
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
 
  • #51
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
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.
 
  • #52
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.

This is annoying lol

I'm just going to import math and math.factorial(1000) then count the zeroes myself lol
 
  • #53
DeathByKugelBlitz said:
This is annoying lol

I'm just going to import math and math.factorial(1000) then count the zeroes myself lol
Count the fives, that'll do.
 
  • #54
fresh_42 said:
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.
 
  • #55
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.

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.
 
  • #56
Hmm.. product of primes... what this means... hmm...
 
  • #57
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:
  • Like
Likes fresh_42 and Ibix
  • #58
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!
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
fbs7 said:
##\lfloor(1000/5) \rfloor + \lfloor(1000/25)\rfloor + \lfloor(1000/125)\rfloor + \lfloor(1000/625)\rfloor=200+40+8+1=249##
 
  • #59
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:
  • #60
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.
 
  • Like
Likes QuantumQuest
  • #61
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

This is what I was aiming for
 
  • #62
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.
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.

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.
 
Last edited:
  • #63
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.
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.
Instead you have e.g. ##c(a+b)=ca \Longrightarrow cb = 0## which cannot be the case, as all numbers are positive.
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.
Very nice.

For the sake of completion:
The recursive arguments can be shortened by the following "trick":

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.
 
  • #64
fresh_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.
Nice idea . Thanks

For me is very interesting that all pairs a/b in the tree are mutually prime ("co-prime" GDC(a,b)=1 )
And of course all mutually prime positive pairs (a, b) are somewhere in the tree as a/b.
We can make the algorithm that generate two random a, b and we know that they are mutually prime without checking.
Code:
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
Maybe this can be used in the RSA or in the other type of the encryption , or for a something else ...
 
  • #65
My attempt at High School 4; notice I had to spy on Euler's proof for directions, so I'm not sure if this an acceptable answer or not:

=====================================================================
I) if (2^n-1) is prime, then z=2^(n-1)*(2^n-1) is perfect:

x1 = 2^0*(2^1-1) = 2
x2 = 2^1*(2^2-1) = 2*3 = 12
x3 = 2^2*(2^3-1) = 4*7 = 28
...
xk = 2^(n-1)*(2^n-1)

factors 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 a1*(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,x1,x2,...} = {xi}
divisors of y = {1,y1,y2,...} = {yj}

define s(x) as the sum of all divisors of x (including x), ie
s(x) = sum( xi )
s(y) = sum( yj )

if z = x.y
then every divisor of z has the form xi*yj, therefore

s(z) = (1*1+1*y1+1*y2+...+x1*1+x1*y1+x1*y2+...+x2*1+x2*y1+x2*y2+...
= 1*(1+y1+y2+...)+x1*(1+y1+y2+...)+x2*(1+y1+y2+...)+...
= 1*s(y)+x1*s(y)+x2*s(y)+...
= (1+x1+x2+...)*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(3) = 1+2+4
...
for k=k, we have s(2^(k-1)) = 1+2^1+...+2^(k-1)

that's 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

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
 
  • #66
Hmm... there must be another way of doing 4, without cheating with Euler... hmm...
 
  • #67
fbs7 said:
Hmm... there must be another way of doing 4, without cheating with Euler... hmm...
You should use the hint of the question before, they are closely related.

Could you please transform your text into LaTeX format? It is hard to read and one never knows for sure whether you meant ##2^{n-1}## or ##2^n-1##.
Indices are written x_1 and not x1, formulas with a double sharp ##2^{n-1} \text{ or } 2^n-1## and not 2^n-1.

See https://www.physicsforums.com/help/latexhelp/, it's really not difficult - at least much easier than to decode your linear text.
 
  • #68
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

##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##

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!
 
Last edited:
  • #69
Looks o.k. in general. Just a few remarks. I think there are some further steps needed.
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
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?
##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##
Why is it impossible? What happens if ##a>1\,##?
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!
The proof would have been a bit shorter with a closed formula for ##s(z)##.
 
Last edited:
  • #70
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?

Hmmm... s(2)=1+2=3, s(3)=1+3=4, s(2*3)=s(6)=1+2+3+6=12=s(2)*s(3)... in the same way s(2)=1+2=3, s(4)=1+2+4=7, s(2*4)=s(8)=1+2+4+8=15... holy choo-choo, that's different than s(2)*s(4)! I forgot something! Thanks Lord that they don't let high-schoolers design homes, otherwise they would forget something like the doors and everybody would have to enter through the roof!

I suspect s(a*b)=s(a)*s(b) only if a and b have no common divisors other than 1 (no common factors). How to prove... for s(2) and s(4), the factors are {1,2} and {1,2,4}, therefore the ##x_i*y_j## forms would be {1*1, 1*2, 1*4, 2*1, 2*2, 2*4} = {1,2,4,2,4,8}... so the 2 and 4 are counted twice... that's because ##x_i1*y_j1## = ##x_i2*y_i2## for some i1 <> i2. If we separate these double-counted forms, then s(2)*(4)-(2+4)=(1+2+4+8)=15=s(8), so s(2*4) = s(2)*s(4) - M. So I suspect in general s(a*b) = s(a)*s(b) - M.

So, two troubles: how to prove M=0 if a and b have no common factors, and how to prove that if d|(x*y) then ##d=x_i*y_j##. Hmm... let's try this without cheating (I cheated too much already by spying on Euler's!).

Defining ##d|z## is true if d is a divisor of z.

I) if d|(x*y) then d is a product of a factor of x and a factor of y; this can be proved by logical arguments (not sure how to prove it an algebraically correct way), as:

expressing z=x*y,d,x,y as the product of primes (notice these are different than ##x_i, y_i## and ##z_i## from the previous post!: ##z=2^{z_2}*3^{z_3}*5^{z_5}*..., d=2^{d_2}*3^{d_3}*5^{d_5}*..., x=2^{x_2}*3^{x_3}*5^{x_5}, y=2^{y_2}*3^{y_3}*5^{y_5}##, then for every prime factor p, ##z_p=x_p+y_p##

as ##d|z##, ##d_p<=z_p##, ie ##d_p<=x_p+y_p##; define:

##dx_p = min( x_p, d_p )##, what makes ##p^{dx_p}|x##
##dy_p = d_p - dx_p##, what makes ##p^{dy_p}|y## [Note]

[Note: ##d_p <= x_p+y_p##, if ##dx_p=d_p## then ##dy_p=0## ie ##p^{dy_p}|y##; otherwise if ##dx_p=x_p## that means ##d_p - dx_p <= x_p+y_p - x_p = y_p##, or ##dy_p - dx_p <= y_p## therefore ##p^{dy_p}|y##]

then name

## u=2^{dx_2}*3^{dx_3}*...##, that makes ##u|d## and ##u|x##
## v=2^{dy_2}*3^{dy_3}*...##, that means ##v|d## and ##v|y##

we get d=u*v for the reason that ##dx_p+dy_p=d_p##

so, if ##d|(x*y)##, then there exists two numbers u and v, such that ##d=u*v## and ##u|x## and ##v|z##. This holds true even if they have common factors.
 
Last edited:

Similar threads

  • Math Proof Training and Practice
2
Replies
61
Views
6K
  • Math Proof Training and Practice
2
Replies
56
Views
7K
  • Math Proof Training and Practice
2
Replies
42
Views
6K
  • Math Proof Training and Practice
4
Replies
114
Views
6K
  • Math Proof Training and Practice
3
Replies
93
Views
10K
  • Math Proof Training and Practice
3
Replies
86
Views
9K
  • Math Proof Training and Practice
3
Replies
100
Views
7K
  • Math Proof Training and Practice
3
Replies
80
Views
4K
  • Math Proof Training and Practice
2
Replies
61
Views
7K
  • Math Proof Training and Practice
2
Replies
67
Views
7K
Back
Top