Challenge Math Challenge - March 2019

  • #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.
 
Physics news on Phys.org
  • #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:
  • #71
fbs7 said:
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).
That is a good suspicion! Such numbers are called coprime.
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.
Your proof is a bit dizzy for my taste. It is better to work with the definition of primes and the fundamental theorem of arithmetics, rather than the linear order.

The fundamental theorem of arithmetic says, that any integer can be written as a product of primes (and of course any number of factors ##\pm 1## which we do not count here).

A prime ##p## is a number, such if ##p## divides a product ##a\cdot b##, then it divides necessarily one of the factors ##a## or ##b##.
(Again, we rule out the units: ##p\neq \pm 1## and of course, ##p## can still divide both, ##a## and ##b##, but it has to divide at least one of them.)

Now let us write ##d = p_1^{r_1}\cdot \ldots \cdot p_m^{r_m}##. Then ##p_1\,|\,d\,|\,(x\cdot y)## and thus e.g. ##p_1\,|\, x##. Now we can cancel ##p_1## and proceed with the next prime. At the end they are all either divisors of ##x## or of ##y##. Since ##x## and ##y## are coprime, they do not share a prime and we have partitioned all divisors of ##p##, either in the ##x-##bucket or the ##y-##bucket and most of all, did not count the same factor twice.

Hence you are allowed to apply the formula to ##z=2^{k-1}\cdot x\, , \,x \text{ odd }##. The condition ##x## odd makes the factors coprime and the formula holds.

Can you explain the last statement, that ##s(x) = 1+a+b+c+...+x = x+y ## implies ##a =b=c=\ldots =0##, i.e. that ##a>1## is not possible?
 
Last edited:
  • #72
II) How to prove that if x and y have no common divisors, then M=0 in s(x*y)=s(x)*s(y) - M

consider [##d_2,d_3,d_5,d_7,...##] as the factorization of d in primes: d=##2^{d_2}*3^{d_3}*...##; then

x=[##x_2,x_3,...##]
y=[##y_2,y_3,...##]
z=x*y=[##z_2,z_3,...##], ##z_p=x_p+y_p##
d=[##d_2,d_3,...##], ##d_p<=z_p##

each divisor u of x is a set of numbers [##u_2,u_3,...##] such that ##u_p<=x_p##; same for each divisor v of y. When x and y have common divisors, u=v for some u and v.

The multiplication of each divisor u and v is a number w with prime factors ##w_p=u_p+v_p <= x_p + y_p##; if x and y have no common divisors, then for each p ##w_p = x_p## or ##x_p = y_p##; therefore each ##d|z## is a product of a unique pair (u,v) where ##u|x## and ##v|y##.

Conversely, if x and y have common divisors, then there can be multiple pairs u,v such that d|z, d=u*v, u|x, v|y. Call

N(d,x,y) = number of pairs (u,v) such that d=u*v, u|x, v|y

s(x)*s(y) = sum every pair u*v such that u|x and v|y
s(x)*s(y) = sum( d * N(d,x,y) ) for every unique d such that d|(x*y)
s(x)*s(y) = sum(d) + sum(d)*(N(d,x,y)-1) for every d such that d|(x*y)

s(x)*s(y) = s(x*y) + sum( d*(N(d,x,y)-1 ) for every d such that d|(x*y)

if (x,y) have no common divisors, then for every d|(x*y), N(d,x,y) = 1, therefore M=0 and s(x)*s(y)=s(x*y)
 
Last edited:
  • #73
fresh_42 said:
Your proof is a bit dizzy for my taste. It is better to work with the definition of primes and the fundamental theorem of arithmetics, rather than the linear order.

I see, thank you!
 
Last edited:
  • #74
fresh_42 said:
Can you explain the last statement, that ##s(x) = 1+a+b+c+...+x = x+y ## implies ##a =b=c=\ldots =0##, i.e. that ##a>1## is not possible?

My reasoning there is 1 and x are divisors of x, therefore s(x) = 1+x+...other divisors...

We know that s(x) = x+y, that is, both x and y are divisors of x. But 1 is always a divisor of x, so

s(x) = 1+x+(y-1)

Assume y>1, then that makes y-1 also a divisor of x, therefore the divisors of x will be 1,x,y,y-1, so

s(x) = 1+x+y+y-1 = x + 2*y

but s(x) = x+y, so that's impossible with y>0, so the assumption is wrong and y<=1 and therefore y=1 and there are no other divisors a,b,c... of x.
 
Last edited:
  • #75
fbs7 said:
II) How to prove that if x and y have no common divisors, then M=0 in s(x*y)=s(x)*s(y) - M

consider [##d_2,d_3,d_5,d_7,...##] as the factorization of d in primes: d=##2^{d_2}*3^{d_3}*...##; then

x=[##x_2,x_3,...##]
y=[##y_2,y_3,...##]
z=x*y=[##z_2,z_3,...##], ##z_p=x_p+y_p##
d=[##d_2,d_3,...##], ##d_p<=z_p##

each divisor u of x is a set of numbers [##u_2,u_3,...##] such that ##u_p<=x_p##; same for each divisor v of y. When x and y have common divisors, u=v for some u and v.
...
This is very difficult to understand. What is ##d##? You only have ##s(xy)-s(x)s(y)=M## and that ##x## and ##y## are coprime. That's where you start. Everything else has to be explained or defined. And then come ##u## and ##v## out of the blue. And how come the pairing ##z_p=x_p+y_p\,?##
I'm completely confused.

fbs7 said:
My reasoning there is 1 and x are divisors of x, therefore s(x) = 1+x+...other divisors...

We know that s(x) = x+y, that is, both x and y are divisors of x. ...
Why that again? Sure, ##x## is a divisor of ##x##, but why does ##y## have to be? E.g. ##s(12)=28=12+16## and ##16## does definitely not divide ##12##.

Let me resume where we are:
The first part of your proof in post #68 was absolutely correct: If ##2^n-1## is prime, then ##2^{n-1}\cdot (2^n-1)## is perfect.

For the second part you have chosen a perfect number ##z=2^{k-1}\cdot x## with ##k>1## and ##x## odd.
What we now need is $$2z=2^k\cdot x = s(z)=s(2^{k-1}\cdot x) \stackrel{(1)}{=} s(2^{k-1}) \cdot s(x) = (2^k-1)\cdot s(x)$$ i.e. under the assumption that ##(1)## is correct, we have with ##x=(2^k-1)\cdot y## and your correct argument about integer values here
$$x+y \leq s(x)= 2^k\cdot y = (2^k-1)\cdot y + y =x+y$$
But now you have on the left the same as on the right which makes the inequality an equation, i.e. ##s(x)=x+y##.

Let me put what you wrote in my own words, just to make it clear for myself. (I can better think if I write it and I have to keep in mind, that ##s(a)=a+b## does not mean per se that ##b## divides ##a##, see my example above.)

We already know that ##y## divides ##x## per construction. So if ##y \notin \{\,1,x\,\}## then ##s(x) \geq 1+x+y > x+y = s(x)## which cannot be. ##y=x## is also impossible, since ##k>1## by assumption. Thus ##y=1## is the only remaining possibility, i.e.
fbs7 said:
... 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)\cdot 2^{k-1}##, where ##2^k-1## is prime. [edit: typo corrected]

So only ##(1)## is left to show:
Let ##a## be a power of ##2## and ##b## an odd number, then ##s(a\cdot b) = s(a)\cdot s(b)##.

I think in this special case, your counting argument from post #68 will work, which might be the easiest way to show it. Another way is to solve the hint in the previous problem #3 of the High School section.

Functions which satisfy ##s(xy)=s(x)\cdot s(y)## for coprime ##x,y## are called multiplicative functions in number theory, and here we use that the sum of all divisors is a multiplicative function.

Numbers ##2^k-1## are called Mersenne numbers and primes ##2^k-1## Mersenne primes, in which case ##k## has to be prime, too. It is unclear (but suspected), whether there are infinitely many Mersenne primes. The highest known number is currently ##2^{82,589,933}-1## with ##24,862,048## digits. It is also unclear whether there are infinitely many perfect numbers.
 
Last edited:
  • #76
fresh_42 said:
This is very difficult to understand. What is ddd? You only have s(xy)−s(x)s(y)=M and that x and y are coprime. That's where you start. Everything else has to be explained or defined. And then come uuu and vvv out of the blue. And how come the pairing zp=xp+yp?zp=xp+yp?z_p=x_p+y_p\,?
I'm completely confused.

Sorry, I let mind to wander around in that post, as I wanted to get a result also for the case when x and y are not coprimes (it was rather easy to get it for when they are coprimes, so I wanted to go a bit beyond). Let me try to organize it. That factorization in prime factors was really superfluous.

##d|(x*y)##, d is a divisor of x*y
##u|x##, ##v|y##, u is a divisor of x, v is a divisor of y

from the previous results we know that every
##d=u*v## for some ##u|x##, ##v|y##

in general multiple ##u,v## satisfy ##d=u*v##, so define
N(d,x,y) = number of ##u,v## pairs that satisfy ##d=u*v, u|x, v|y##

##s(x) = \sum u## for all ##u|x##
##s(y) = \sum v## for all ##v|y##

##s(x)*s(y) = \sum \sum u*v## for all ##u|x, v|y##
##s(x)*s(y) = \sum N(d,x,y)*d## for all distinct d such that ##d=u*v, u|x, v|y##
##s(x)*s(y) = \sum d + \sum (N(d,x,y)-1)*d## for all distinct d such that ##d=u*v, u|x, v|y##

call
##S = \sum d ## for all distinct d such that ##d=u*v, u|x, v|y##

as the sum occurs over all possible u,v pairs, that will include all possible d such that ##d|(x*y)##
##S= \sum d ## for all distinct d such that ##d|(x*y)##

by definition of s(),
##S = s(x*y)##
##s(x)*s(y) = s(x*y) - \sum (N(d,x,y)-1)*d## for all distinct d such that ##d=u*v, u|x, v|y##
##s(x)*s(y) = s(x*y) - M##
##M = \sum (N(d,x,y)-1)*d##

if x and y are co-primes then either ##d=u*1## or ##d=1*v##, therefore N(d,x,y)=1 and M=0.
 
Last edited:
  • #77
Bit of checking my equation for M... x=6, y=12...

factors of x=(1,2,3,6) => s(x) = 12
factors of y=(1,2,4,6,12) => s(y) = 25
factors of x*y=72=(1,2,3,4,6,8,12,18,24,36,72) => s(x*y) = 186

calculating the N(...); all of them are 1 except:
N(2,6,12)=2 from 1*2 and 2*1
N(4,6,12)=2 from 1*4 and 2*2
N(6,6,12)=3 from 1*6, 3*2 and 6*1
N(12,6,12)=4 from 1*12, 2*6, 3*4 and 6*1
N(24,6,12)=2 from 2*12 and 6*4
N(36,6,12)=2 from 3*12 and 6*6

so M=1*2+1*4+2*6+3*12+1*24+1*36=2+4+12+36+24+36=114
s(x)*s(y)-M = 12*25 - 114 = 300 - 114 = 186 = s(x*y)

Hoorye! I've found an equation! Rather useless, but that's good work for a Sunday afternoon!
 
  • #78
You need to quantify your variables: for any / for all or there exist. Otherwise it is not clear what you mean. E.g.
fbs7 said:
##d|(x*y)##, ##d## is a divisor of ##x*y##
##u|x##, ##v|y##, ##u## is a divisor of ##x##, ##v## is a divisor of ##y##

from the previous results we know that every
##d=u*v## for some ##u|x##, ##v|y##
Every divisor ##d## of the form ##d=uv## ... what? If ##u,v## are as given, then ##d:=uv ## divides the product? All divisors are of this form? We only know this in case ##x## and ##y## are coprime, but you just said, that you want to consider the general case.

The art of writing a proof is the following: explain it step by step to someone who doesn't know where your thoughts currently are, like you would explain it to a stranger. Both is actually the case if you write something here. If you practice this you will find another advantage: the more detailed you explain something, always asking yourself why before the other one can, then you often learn more than you would learn by reading a book. The necessity to convince someone and thereby always convince yourself just a moment earlier can give you more insights than you might think. I once had a professor who I had the following dialogue with:
Me: I've seen you announced a lecture on measure theory next semester. I didn't know you were an expert.
Him: I'm not. I want to learn it.

For the task above, it is really best - and most helpful later on - to deduce a formula for ##s(x)##. Say we have the prime factor decomposition ##x=p_1^{r_1} \cdot \ldots \cdot p_n^{r_n}##. Then
$$
s(x)= \sum_{d|x} d = \prod_{i=1}^{n} \dfrac{N_i}{D_i} = \left( \dfrac{N_1}{D_1} \right)\cdot \ldots \cdot \left( \dfrac{N_n}{D_n} \right)
$$
If you find (by counting) those numerators ##N_i## and denominators ##D_i## which only depend on those primes, then the proof that ##s(x)## is multiplicative is really easy. Moreover, you can also tackle problem #3, AND you will have a nice formula for future use!
 
  • #79
fresh_42 said:
You need to quantify your variables: for any / for all or there exist. Otherwise it is not clear what you mean. E.g.

Every divisor ##d## of the form ##d=uv## ... what? If ##u,v## are as given, then ##d:=uv ## divides the product? All divisors are of this form? We only know this in case ##x## and ##y## are coprime, but you just said, that you want to consider the general case.

Oh, I thought that was a general result! coming back to that! Thank you!
 
  • #80
Alright, trying my hand at High School 3, and trying to get all my "i" dotted and "t" crossed this time. Doing it the long way - no shortcuts, or I'll end up kicked from the forum and sent back to pre-school! First part, for the sigma of prime decomposition

I - Define ##\sigma(x)## = sum of divisors of ##x##, including 1 and ##x##, for ##x \in N##
--------------------------------------------------------------------------------------------------------
II - Proof that if ##p## is prime, ##p > 1## and ##n>=1##, then ##\sigma(p^n) = (p^{(n+1)}-1)/(p-1)##

As ##p## is prime, ##p>1## and ##n>=1##, the divisors of ##p^n## are {##1, p, p^2, ..., p^n## }; the sum of these divisors form the sum of a geometric series:

##\sigma(p^n)## = ##1+p+p^2+...+p^n##

this series has ##a=1, rate=p, num=n+1##; as ##rate>1##, the series has ##sum=a*(rate^{num}-1)/(rate-1) = 1*(p^{(n+1)}-1)/(p-1)##, therefore

##\sigma(p^n) = (p^{(n+1)}-1)/(p-1)##
--------------------------------------------------------------------------------------------------------
III - Proof that if ##p## is a prime, ##p>1##, ##a \in N##, ##a>1##, ##n>=1##, and ##p## is not a factor of ##a##, then ##\sigma(p^n*a)=\sigma(p^n)*\sigma(a)##

(a) Define

##z = p^n*a##

(b) Define

P=set of divisors of ##p^n=\{1,p,p^2,...,p^n\}##
A=set of divisors of ##a = \{a_0,a_1,a_2,...,a_m\} ##, with ##a_0=1, a_m=a##

(c) For any ##u \in N, u>1##, such that ##u|z## and ##gcd(u, p^n)=1##; then ##u|a##; that's due to Euclid's Lemma; as ##u|a##, ##u \in A##, therefore ##u = a_j## for some ##j##, and ##u=p^0*a_j## for some j

(d) For any ##u \in N, u>1##, such that ##u|z## and ##gcd(u, p^n)=p^l## for some ##l>0## ; then necessarily ##u=p^l*v## for an integer ##v##, where ##gcd(v,p^n)=1##; then for some ##k_u \in N, k_u>0##:

##z=k_u*u=p^n*a##
##u=p^l*v##
##z/u=k_u=(p^n*a)/(p^l*v)##
##k_u=(p^n/p^l)*(a/v)##

as ##n>l## and ##k_u## is an integer and ##v## is not a multiple of ##p##, then necessarily ##a## is a multiple of ##v##, or ##v## is a divisor of ##a##:

##v|a##

therefore ##v \in A##, what means ##v=a_j## for some ##j##, and

##u=p^i*a_j## for some ##i,j##

(e) From (c) and (d), all divisors of z have the form ##p^i*a_j## for some 0<=i<=n, 0<=j<=m.

(f) Therefore the sum of the divisors of z is

##\sigma(z)=\sum_i (\sum_j (p^i*a_j)) = \sum_i (p^i * (\sum_j a_j)) = \sum_i (p^i * \sigma(a)) = \sigma(a)*(\sum_i (p^i)) = \sigma(a)*\sigma(p^n)##
--------------------------------------------------------------------------------------------------------
IV - Proof that ## \sigma ( \prod_i {p_i}^{n_i} ) = \prod_i \sigma( {p_i}^{n_i} ) ## if each ##p_i## is a different prime ##p_i > 1## and ##n_i>=0, 1<=i<=m##

(a) Define

##z = z_1##
## z_1 = \prod_i {p_i}^{n_i}, i>=1, ## that is ## z_1 = {p_1}^{n_1} * z_2##
## z_2 = \prod_i {p_i}^{n_i}, i>=2, ## that is ## z_2 = {p_2}^{n_2} * z_3##
...
## z_{(m-1)} = \prod_i {p_i}^{n_i}, i>=m-1, ## that is ## z_{(m-1)} = p_{(m-1)}^{n_{(m-1)}} * z_m ##
## z_m = \prod_i {p_i}^{n_i}, i>=m, ## that is ## z_m = {p_m}^{n_m}##

then, as each ##p_i## is a different prime,

## \sigma(z_m) = \sigma({p_m}^{n_m})##
## \sigma(z_{(m-1)}) = \sigma( ({p_{(m-1)}}^{n_{(m-1)}} * z_m ) = \sigma(p_{(m-1)}^{n_{(m-1)}})*\sigma(p_m^{n_m}) ##
...
## \sigma(z_1) = \sigma(p_1^{n_1} * z_2) = \sigma({p_1}^{n_1})*\sigma(z_2) = \sigma({p_1}^{n_1})*...*\sigma({p_m}^{n_m}) = \prod_i \sigma( {p_i}^{n_i} )##

--------------------------------------------------------------------------------------------------------
V - Proof that ##\sigma( \prod_i {p_i}^{n_i} ) = \prod_i (p^{({n_{i}}+1)}-1)/(p-1)## if each ##p_i## is a different prime ##p_i > 1## and ##n_i>=0##, for ##1<=i<=m##

(a) Just substitute II in IV

VI - Result: if the prime factorization of ##z## is ## z = \prod_i {p_i}^{n_i} ##, then ## \sigma(z) = \prod_i (p^{({n_{i}}+1)}-1)/(p-1)##
 
Last edited:
  • #81
fbs7 said:
Alright, trying my hand at High School 3, and trying to get all my "i" dotted and "t" crossed this time. Doing it the long way - no shortcuts, or I'll end up kicked from the forum and sent back to pre-school! First part, for the sigma of prime decomposition

I - Define ##\sigma(x)## = sum of divisors of ##x##, including 1 and ##x##, for ##x \in N##
--------------------------------------------------------------------------------------------------------
II - Proof that if ##p## is prime, ##p > 1## and ##n>=1##, then ##\sigma(p^n) = (p^{(n+1)}-1)/(p-1)##

As ##p## is prime, ##p>1## and ##n>=1##, the divisors of ##p^n## are {##1, p, p^2, ..., p^n## }; the sum of these divisors form the sum of a geometric series:

##\sigma(p^n)## = ##1+p+p^2+...+p^n##

this series has ##a=1, rate=p, num=n+1##; as ##rate>1##, the series has ##sum=a*(rate^{num}-1)/(rate-1) = 1*(p^{(n+1)}-1)/(p-1)##, therefore

##\sigma(p^n) = (p^{(n+1)}-1)/(p-1)##
This can also be seen by a simple long division or multiplication of polynomials: ##x^{n+1}-1=(x-1)\cdot (x^n+x^{n-1}+ \ldots + x+ 1)\,.##
--------------------------------------------------------------------------------------------------------
III - Proof that if ##p## is a prime, ##p>1##, ##a \in N##, ##a>1##, ##n>=1##, and ##p## is not a factor of ##a##, then ##\sigma(p^n*a)=\sigma(p^n)*\sigma(a)##

(a) Define

##z = p^n*a##

(b) Define

P=set of divisors of ##p^n=\{1,p,p^2,...,p^n\}##
A=set of divisors of ##a = \{a_0,a_1,a_2,...,a_m\} ##, with ##a_0=1, a_m=a##

(c) For any ##u \in N, u>1##, such that ##u|z## and ##gcd(u, p^n)=1##; then ##u|a##; that's due to Euclid's Lemma; as ##u|a##, ##u \in A##, therefore ##u = a_j## for some ##j##, and ##u=p^0*a_j## for some j

(d) For any ##u \in N, u>1##, such that ##u|z## and ##gcd(u, p^n)=p^l## for some ##l>0## ; then necessarily ##u=p^l*v## for an integer ##v##, where ##gcd(v,p^n)=1##; then for some ##k_u \in N, k_u>0##:

##z=k_u*u=p^n*a##
##u=p^l*v##
##z/u=k_u=(p^n*a)/(p^l*v)##
##k_u=(p^n/p^l)*(a/v)##

as ##n>l## and ##k_u## is an integer and ##v## is not a multiple of ##p##, then necessarily ##a## is a multiple of ##v##, or ##v## is a divisor of ##a##:

##v|a##

therefore ##v \in A##, what means ##v=a_j## for some ##j##, and

##u=p^i*a_j## for some ##i,j##

(e) From (c) and (d), all divisors of z have the form ##p^i*a_j## for some 0<=i<=n, 0<=j<=m.

(f) Therefore the sum of the divisors of z is

##\sigma(z)=\sum_i (\sum_j (p^i*a_j)) = \sum_i (p^i * (\sum_j a_j)) = \sum_i (p^i * \sigma(a)) = \sigma(a)*(\sum_i (p^i)) = \sigma(a)*\sigma(p^n)##
--------------------------------------------------------------------------------------------------------
IV - Proof that ## \sigma ( \prod_i {p_i}^{n_i} ) = \prod_i \sigma( {p_i}^{n_i} ) ## if each ##p_i## is a different prime ##p_i > 1## and ##n_i>=0, 1<=i<=m##

(a) Define

##z = z_1##
## z_1 = \prod_i {p_i}^{n_i}, i>=1, ## that is ## z_1 = {p_1}^{n_1} * z_2##
## z_2 = \prod_i {p_i}^{n_i}, i>=2, ## that is ## z_2 = {p_2}^{n_2} * z_3##
...
## z_{(m-1)} = \prod_i {p_i}^{n_i}, i>=m-1, ## that is ## z_{(m-1)} = p_{(m-1)}^{n_{(m-1)}} * z_m ##
## z_m = \prod_i {p_i}^{n_i}, i>=m, ## that is ## z_m = {p_m}^{n_m}##

then, as each ##p_i## is a different prime,

## \sigma(z_m) = \sigma({p_m}^{n_m})##
## \sigma(z_{(m-1)}) = \sigma( ({p_{(m-1)}}^{n_{(m-1)}} * z_m ) = \sigma(p_{(m-1)}^{n_{(m-1)}})*\sigma(p_m^{n_m}) ##
...
## \sigma(z_1) = \sigma(p_1^{n_1} * z_2) = \sigma({p_1}^{n_1})*\sigma(z_2) = \sigma({p_1}^{n_1})*...*\sigma({p_m}^{n_m}) = \prod_i \sigma( {p_i}^{n_i} )##

--------------------------------------------------------------------------------------------------------
V - Proof that ##\sigma( \prod_i {p_i}^{n_i} ) = \prod_i (p^{({n_{i}}+1)}-1)/(p-1)## if each ##p_i## is a different prime ##p_i > 1## and ##n_i>=0##, for ##1<=i<=m##

(a) Just substitute II in IV

VI - Result: if the prime factorization of ##z## is ## z = \prod_i {p_i}^{n_i} ##, then ## \sigma(z) = \prod_i (p^{({n_{i}}+1)}-1)/(p-1)##
You could have saved all these deviations with divisors of ##z## by the use of the fundamental theorem of arithmetic: We always have ## z = \prod_i {p_i}^{r_i} ## for integers ##z## and so all the cases are only cases of different prime factors, resp. powers. The usual way - and I only add this for completion, not because your proof was wrong - is by induction.

The induction principle is as follows: prove that a statement ##A(n)## is true for some specific ##n=n_0##. Then we assume we would have proven it for all numbers up to ##n##. If we now can show, that ##A(n)## implies ##A(n+1)## then we are done, since we have shown a way how to start from ##n=n_0## and get all the way up to any ##n##.

In our case ##A(n) = \left[ \sigma\left( \prod_{i=1}^n p_i^{r_i}\right)= \prod_{i=1}^n \frac{p_i^{r_i +1}-1}{p_i-1}\right]## and ##n_0=1##.
The verification, that ##A(1)## is true, is your step II.
Now we assume, that ##A(n-1)## is true.
By your step III, the induction hypothesis ##A(n-1)##, and again step II we know, that
\begin{align*}
\sigma\left( \prod_{i=1}^n p_i^{r_i}\right) &= \sigma\left( \prod_{i=1}^{n-1} p_i^{r_i}\right) \cdot \sigma\left( p_n^{r_n} \right)\\
&=\prod_{i=1}^{n-1} \dfrac{p_i^{r_i +1}-1}{p_i-1} \cdot \dfrac{p^{r_n+1}-1}{p_n-1}\\
&= \prod_{i=1}^{n} \dfrac{p_i^{r_i +1}-1}{p_i-1}
\end{align*}
and the formula is proven.

Another way is simply count the divisors. This would have shortened your step III as well:

Every prime power ##p_i^{r_i}## contributes divisors ##1,p_i,\ldots ,p_i^{r_i}## and every divisor can be combined with all the other divisors to get another one. So we have as many divisors as there are combinations of ##(\,1,p_1,\ldots ,p_i^{r_1}\,) \times \ldots \times (\,1,p_n,\ldots ,p_i^{r_n}\,)##, which sum up to ##\prod_{i=1}^n\ \frac{p_i^{r_i +1}-1}{p_i-1}##.

This was the main task. Now you can calculate ##\sigma(a)-a## and ##\sigma(b)-b## if ##a,b## have the given form.
 
  • #82
I see! Short and elegant! Nicely done! I didn't think of using induction!

I didn't want to assume as fact that ## \sigma(a*b) = \sigma(a) * \sigma(b)## if ## gcd(a,b)=1## given the troubles with my previous proofs of that; that's a bit why I took the pain of explicitly avoiding using that.

As I say, if one works wrong once he has to work twice to fix it!
 
  • #83
fbs7 said:
I see! Short and elegant! Nicely done! I didn't think of using induction!

I didn't want to assume as fact that ## \sigma(a*b) = \sigma(a) * \sigma(b)## if ## gcd(a,b)=1## given the troubles with my previous proofs of that; that's a bit why I took the pain of explicitly avoiding using that.

As I say, if one works wrong once he has to work twice to fix it!
This was your part III which is needed to do the induction step, so no senseless work. I only think it's easier to show it for prime powers rather than arbitrary factors.
 
  • #84
Hoorye! Let's do it! It's like being a Padawan for Master Yoda! Let's see... uhh.. what... x, y, z??... hmm... this is difficult!... I guess I'm at Amoeba-level Padawan atm

Attempt at 2nd part for High School 3:

I - definitions

(a) simplify notation

##n \in N##
define ##c=2^n##

(b) as we know already

##s(c) = s(2^n) = 2^{(n+1)} -1= 2c-1##

(c) assume

##x=3*2^n-1 = 3c-1 ## is an odd prime
##y=3*2^{(n-1)}-1 = 3c/2 - 1 ## is an odd prime
##z=9*2^{(2n-1)}-1 = 9*c^2/2 - 1 ## is an odd prime

II - notice

##xy = (3c-1)*(3c/2-1) = (9c^2/2-3c-3c/2+1) = (9c^2/2 - 9c/2 + 1)##
##xy = z - 9c/2 +2##
##x+y = (3c-1)+(3c/2-1) = 9c-2##

so, ##xy+(x+y)=z##

III - if ##x## is prime, then ##\sigma(x)=1+x##; this is rather obvious by now and only Pre-Padawans need to prove that!

IV - define

##a = cxy##
##b = cz##

(a) as ##c, x## and ##y## are co-primes, and ##x## and ##y## are primes, then

##s(a) = s(c*x*y) = s(c)*(1+x)*(1+y) = (2c-1)*(1+x)*(1+y)##
##s(a)-a = (2c-1)*(1+x+y+xy)-c*(xy) =##
##s(a)-a = (2c-1)*(1+z)-c*(xy)=(2c-1)*(1+z)-c*(z-9c/2+2)##
##= 2c+2cz-1-z-cz+9c^2/2-2c##
##= cz-1-z+(z+1) = cz = b##

(b) as ##c## and ##z## are co-primes, then

##s(b) = s(c*z) = s(c)*(1+z) = (2c-1)*(1+z)##
##s(b)-b = 2c+2cz-1-z-cz##
##= 2c+cz-z-1##
##= 2c+c(9c^2/2-1)-(9c^/2-1)-1##
##= c+9c^3/2-9c^2/2##
##= c*(9c^2-9c/2+1)##, from II, we have
##= cxy = a##

Therefore ##s(a)=a+b=s(b)## and a and b are amicable!

I should get a promotion to Ant-Padawan by now! :biggrin: ... you know, another step in evolution, just before Fly-Padawn, Centipede-Padawan, ... 60 steps... Monkey-Padawan, Padawan 1st Level, 2nd Level... 99th Level, then Auxiliary Assistant to Secretary of Jedi Initiate
 
Last edited:
  • #85
fbs7 said:
Hoorye! Let's do it! It's like being a Padawan for Master Yoda! Let's see... uhh.. what... x, y, z??... hmm... this is difficult!... I guess I'm at Amoeba-level Padawan atm

Attempt at 2nd part for High School 3:

I - definitions

(a) simplify notation

##n \in N##
define ##c=2^n##

(b) as we know already

##s(c) = s(2^n) = 2^{(n+1)} -1= 2c-1##

(c) assume

##x=3*2^n-1 = 3c-1 ## is an odd prime
##y=3*2^{(n-1)}-1 = 3c/2 - 1 ## is an odd prime
##z=9*2^{(2n-1)}-1 = 9*c^2/2 - 1 ## is an odd prime

II - notice

##xy = (3c-1)*(3c/2-1) = (9c^2/2-3c-3c/2+1) = (9c^2/2 - 9c/2 + 1)##
##xy = z - 9c/2 +2##
##x+y = (3c-1)+(3c/2-1) = 9c-2##

so, ##xy+(x+y)=z##

III - if ##x## is prime, then ##\sigma(x)=1+x##; this is rather obvious by now and only Pre-Padawans need to prove that!

IV - define

##a = cxy##
##b = cz##

(a) as ##c, x## and ##y## are co-primes, and ##x## and ##y## are primes, then

##s(a) = s(c*x*y) = s(c)*(1+x)*(1+y) = (2c-1)*(1+x)*(1+y)##
##s(a)-a = (2c-1)*(1+x+y+xy)-c*(xy) =##
##s(a)-a = (2c-1)*(1+z)-c*(xy)=(2c-1)*(1+z)-c*(z-9c/2+2)##
##= 2c+2cz-1-z-cz+9c^2/2-2c##
##= cz-1-z+(z+1) = cz = b##

(b) as ##c## and ##z## are co-primes, then

##s(b) = s(c*z) = s(c)*(1+z) = (2c-1)*(1+z)##
##s(b)-b = 2c+2cz-1-z-cz##
##= 2c+cz-z-1##
##= 2c+c(9c^2/2-1)-(9c^/2-1)-1##
##= c+9c^3/2-9c^2/2##
##= c*(9c^2-9c/2+1)##, from II, we have
##= cxy = a##

Therefore ##s(a)=a+b=s(b)## and a and b are amicable!

I should get a promotion to Ant-Padawan by now! :biggrin: ... you know, another step in evolution, just before Fly-Padawn, Centipede-Padawan, ... 60 steps... Monkey-Padawan, Padawan 1st Level, 2nd Level... 99th Level, then Auxiliary Assistant to Secretary of Jedi Initiate

Except for a few typos this is correct, although a bit hard to read.
I insert the calculation without the many abbreviations you used:

For ##n=p_1^{k_1}\cdots p_r^{k_r}## the sum of all divisors is $$\sigma(n)=\prod_{i=1}^r \dfrac{p_i^{k_{i}+1}-1}{p_i-1}$$
\begin{align*}
\sigma(a)-a&= \sigma(2^n\cdot x\cdot y)-2^n\cdot x\cdot y\\
&=\left( 2^{n+1}-1 \right)(x+1)(y+1)- 2^nxy\\
&=\left( 2^{n+1}-1 \right)(3\cdot 2^n)(3\cdot 2^{n-1}) - 2^n(3\cdot 2^n-1)(3\cdot 2^{n-1}-1)\\
&=\left( 2^{n+1}-1 \right)\cdot 9\cdot 2^{2n-1}-2^n\left(9\cdot 2^{2n-1}-9\cdot 2^{n-1}+1 \right)\\
&=2^n\cdot\left(9\cdot 2^{2n}-9\cdot 2^{n-1}-9\cdot 2^{2n-1}+9\cdot 2^{n-1}-1\right)\\
&=2^n\cdot \left(9\cdot 2^{2n-1}-1 \right)\\
&=2^n \cdot z\\
&=b
\end{align*}
and by an analogue calculation ##\sigma(b)-b=a\,.##

The statement above is called: Theorem of Thabit Ibn Qurra. (9th century, Mesopotamia)
 
  • #86
fresh_42 said:
Except for a few typos this is correct, although a bit hard to read.

What can I do to make it easier to read? I try to keep it in high-school scope and do very small steps (also because I tend to make mistakes if I try too long a step), but I fear I already go over the top as far as high-school level as I fear 99% of the high-school students have no idea what ## \prod x_n ## means (at least in my country, haha!)

At the same time the only person I ever met in life that graduated in college in math (other than my old school teachers) ended up hating math for some reason and wouldn't talk to me about it (very frustrating!). So out of reading books and internet stuff (which very very swiftly go way over my head) it's hard for me to distinguish between what's a necessary statement in a proof and what a decently-knowledged will find boring and unnecessary. For example, only now I know that n ∈ N is an important statement!

I'm kinda in-between those two levels, I guess; that's the trouble with ant-padawans!
 
  • #87
fbs7 said:
What can I do to make it easier to read? I try to keep it in high-school scope and do very small steps (also because I tend to make mistakes if I try too long a step), but I fear I already go over the top as far as high-school level as I fear 99% of the high-school students have no idea what ## \prod x_n ## means (at least in my country, haha!)
It is in general easier to follow a linear argumentation. The many support variables you used (##x,y,z,c##) led to a constant need to go back and check what you already have resp. how it is defined. After you have made a proof, you can gather all parts and rewrite it. See my example, which only uses the variables defined in the question. The typos (e.g. a forgotten square) didn't make it easier.
At the same time the only person I ever met in life that graduated in college in math (other than my old school teachers) ended up hating math for some reason and wouldn't talk to me about it (very frustrating!). So out of reading books and internet stuff (which very very swiftly go way over my head) it's hard for me to distinguish between what's a necessary statement in a proof and what a decently-knowledged will find boring and unnecessary. For example, only now I know that n ∈ N is an important statement!

I'm kinda in-between those two levels, I guess; that's the trouble with ant-padawans!
The only way is practice and reads. The more proofs you have read, the more you understand their general structure. PF is a nice way to do both, although many proofs don't qualify as a good template. But you can read a book and come over and ask whenever you got stuck. I'm sometimes surprised that not more students use this unique opportunity. On other platforms you get solutions as answers. This is a vicious advantage: it helps in the moment but worsens the overall performance. Helping to understand what's going on is far more important and advantageous than a solution could ever be. It is also helpful to be forced to explain a situation. The crucial ideas often come during the attempt of an explanation!
 
  • #88
That's true! I always find I understand something better when I have to explain something to someone else from that person's point of view!

I appreciate your help and insights. As far as not many students use the opportunity, I say: they haven't read Pauli's book "The Theory of Relativity". I got it from a used book stand when I was 16, and although I didn't understand almost nothing from it I thought: "This dude started to write it when he was 19... just 3 years older than me... he summarized all knowledge (back then) on Relativity!". That was the best evidence ever for me what someone can do, even if they are young!

So my advice to ambitious young people - read Pauli's book! It's flabbergasting!
 
  • #89
Hoorye! Trying my hand at High School 1! Full speed ahead to Ant-Padawan Level 2!

(a) note: I think the sequence starts with sqrt(2), not 2

(b) simplifying notation

define ##m=n-1##
define ##k=2/3##

(c) rewrite product

##P = \prod_{n=1}^{n=\infty} 2^{( (2^{(n-1)})/(3^{(n-1)}) )}##
##P = \prod_{m=0}^{m=\infty} 2^{((2^m)/(3^m))}##
##P = \prod_{m=0}^{m=\infty} 2^{((2/3)^m)}##
##P = \prod_{m=0}^{m=\infty} 2^{( k^m )}##
##(ln P)/(ln 2) = \sum_{m=0}^{m=\infty} k^m ##

(d) calculating infinite series

##S = 1+k+k^2+k^3+... ##
##S-S*k = S*(1-k) = 1+k+k^2...-(k+k^2+k^3+...) = 1 ##
##S = 1/(1-k)##

as ##k=2/3##

##S = 1/(1-2/3) = 3##
##(ln P)/(ln 2) = S##
##P = 2^S = 2^3 = 8##
 
  • Like
Likes QuantumQuest and fresh_42
  • #90
fbs7 said:
(a) note: I think the sequence starts with sqrt(2), not 2

No. I was given this question many years before and the wording is exactly what I've given i.e. this is how it is intended to be.

fbs7 said:
(b) simplifying notation ...

Your solution is correct. You can also do it in a more straightforward manner. Here's what I did back in my high school days

##a_n = 2\cdot \sqrt[3]{2^2}\cdot \sqrt[9]{2^4}\cdot \sqrt[27]{2^8} \,\cdots \, \sqrt[3^{n-1}]{2^{2^{n-1}}} = 2 \cdot 2^{\frac{2}{3}} \cdot 2^{\frac{4}{9}} \cdot 2^{\frac{8}{27}} \cdots 2^{\frac{2^{n-1}}{3^{n-1}}} = 2^{1 + \frac{2}{3} + \frac{4}{9} + \frac{8}{27} + \cdots + \frac{2^{n-1}}{3^{n-1}}}##.

Now, ##1 + \frac{2}{3} + \frac{4}{9} + \frac{8}{27} + \cdots + \frac{2^{n-1}}{3^{n-1}} = 1 + (\frac{2}{3}) + {(\frac{2}{3})}^2 + {(\frac{2}{3})}^3 + \cdots + {(\frac{2}{3})}^{n-1} = \frac{1[{(\frac{2}{3})}^n - 1]}{\frac{2}{3} - 1} = -3[{(\frac{2}{3})}^n - 1] \rightarrow -3(0 - 1) = 3##

So, ##\lim a_n = 2^3##
 
Last edited:
  • #91
wow! holy-choochoo! I didn't think of adding the exponents!

well done! thank you!

so the first term is really 2, not sqrt(2)... huh... I guess I'm not graduating to Ant-Padawan level 2 at all! oh no!
 
  • Like
Likes QuantumQuest
  • #92
fbs7 said:
wow! holy-choochoo! I didn't think of adding the exponents!
This is not really true. You took the logarithm of an assumed limit and did exactly this: added the exponents - now a floor below, which made a better typeset.
 
  • #93
a-ha! thank you! so I'm calling myself Ant-Padawn Level 1 1/2.. no... 1 1/3

And I used what you advised about Polynomial Division... errr... Thingie.. that was very smart!
 
  • #94
On Yoda-level Question 4:

The question is beyond my level, but I'm trying to at least understand the item (a); I'm probably not reading the notation correctly, though:

##x*(y*z) = x*(1/2y+1/2z) = 1/2(x*y)+1/2(x*z) =##
##1/2(1/2x+3/8y+1/8z) + 1/2(1/2x+1/2z) =##
##1/2x + 3/16y+5/16z##

##(x*y)*z = (1/2x+3/8y+1/8z)*z =1/2(x*z)+3/8(y*z)+1/8(z*z) =##
##1/2(1/2x+1/2z) + 3/8(1/2y+1/2z) + 1/8(z) =##
##1/4x+3/16y+9/16z##

It doesn't seem to be associative, so I'm making some mistake. Tried as I could, still can't see my mistake.
 
  • #95
fbs7 said:
On Yoda-level Question 4:

The question is beyond my level, but I'm trying to at least understand the item (a); I'm probably not reading the notation correctly, though:

##x*(y*z) = x*(1/2y+1/2z) = 1/2(x*y)+1/2(x*z) =##
##1/2(1/2x+3/8y+1/8z) + 1/2(1/2x+1/2z) =##
##1/2x + 3/16y+5/16z##

##(x*y)*z = (1/2x+3/8y+1/8z)*z =1/2(x*z)+3/8(y*z)+1/8(z*z) =##
##1/2(1/2x+1/2z) + 3/8(1/2y+1/2z) + 1/8(z) =##
##1/4x+3/16y+9/16z##

It doesn't seem to be associative, ...
Correct.
... so ...
Wrong.
... I'm making some mistake. Tried as I could, still can't see my mistake.
Me neither. Why do you expect associativity? It is an example for a non associative multiplication, i.e. a non associative algebra. Lie algebras or the Octonians are other prominent examples of non associative algebras. Both play important roles in physics, the former a bit more than the latter.
 
  • #96
Oh, good Lord! I was trying to find a way to prove that was associative, instead of answering if that was associative or not! I'm such an idiot.

By the way, I came with a property of an algebra A on vectors over a basis ##x_i## such that

##x_i*x_j = l_{ijk}*x_k##

that would make it associative; without taking much space, for three vectors u, v, w in Einstein's notation:

##u = u_i*x_i; v = v_i*x_i; w = w_i*x_i; ##

then ##u*(v*w) = (u*v)*w## makes ##u_a*x_a*(v_b*x_b*w_c*x_c) = (u_d*x_d*v_e*x_e*w_e)*w_f*x_f##

as ##u_?, v_?, w_?## are all free variables, then ##d=a, e=b, f=c##, and ## x_a*(x_b*x_c)=(x_a*x_b)*x_c##, that is the algebra is associative if the multiplication of the basis is associative; then, replacing with the expression for multiplication of the basis:

##x_a*(x_b*x_c) = x_a*(l_{bcg}*x_g) = l_{bcg}*x_a*x_g = l_{bcg}*l_{agh}*x_h##
##(x_a*x_b)*x_c = (l_{abi}*x_i)*x_c = l_{abi}*x_i*x_c = l_{abi}*l_{icj}*x_j##

as ##x_h## and ##x_j## are independent (that is, I assume they are independent), then ##h=j##; then, eliminating ##x_h## and renaming ##i=g## and ##d=h## to make it more readable,

##l_{abi}*l_{icd} = l_{bci} * l_{aid}## for any ##a, b, c, d##

And that's where my skill ends; now, question on that... this seems like a tensor operation of some kind, is that true? That is, is ##l_{ijk}## a 3-tensor, and the expression above is a tensor operation of some kind?
 
Last edited:
  • #97
Every bilinear multiplication can be written as a tensor. See the example of Strassen's algorithm here:
https://www.physicsforums.com/insights/what-is-a-tensor/
which is an example how matrix multiplication is written as a tensor.

As long as you do not put any additional restraints on ##l_{ijk}## as in the case of genetic algebras (or any other class of algebras), as long do you have an arbitrary algebra.
 
  • #98
Thank you!
 

Similar threads

2
Replies
61
Views
9K
2
Replies
56
Views
10K
Replies
42
Views
10K
3
Replies
114
Views
10K
2
Replies
86
Views
13K
2
Replies
93
Views
14K
3
Replies
100
Views
11K
2
Replies
67
Views
11K
2
Replies
61
Views
11K
2
Replies
60
Views
11K
Back
Top