Math Challenge - March 2019

  • Challenge
  • Thread starter fresh_42
  • Start date
  • Featured
  • #76
345
37
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
345
37
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
13,468
10,524
You need to quantify your variables: for any / for all or there exist. Otherwise it is not clear what you mean. E.g.
##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
345
37
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
345
37
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
13,468
10,524
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
345
37
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
13,468
10,524
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
345
37
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: ... ya 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
13,468
10,524
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: ... ya 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
345
37
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
13,468
10,524
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
345
37
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
345
37
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
QuantumQuest
Science Advisor
Insights Author
Gold Member
926
485
(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.

(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
345
37
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
13,468
10,524
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
345
37
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
345
37
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
13,468
10,524
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
345
37
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
13,468
10,524
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
345
37
Thank you!
 

Related Threads on Math Challenge - March 2019

Replies
40
Views
6K
Replies
121
Views
12K
Replies
40
Views
10K
Replies
86
Views
13K
Replies
101
Views
9K
Replies
39
Views
6K
Replies
42
Views
6K
Replies
83
Views
13K
Replies
48
Views
6K
Replies
47
Views
6K
Top