Bharat Rakshak

Moral of the story is not always believe in wiki ...when you can rely on BRF

(Yes, my friend there are infinite solutions to this and this can be proved ... and no we do not have to include zero..)



Again, are you sure?
How about 3^3+6^3 = 3^5 ( There is no zero involved ) ?

If I may, Elements of Discrete Mathematics by C.L. Liu (ISBN 0-07--038133-X) is an introductory classic.

I only got as far as follows:

Suppose $\Sigma_{i=1}^{n} i = m^2$

The following condition has to be satisfied (m^2 mod 4 = 1) && (n mod 4 = 1 || n+1 mod 4 = 1)

Edit: I rush in where angels fear to tread - The m^2 mod 4 = 1 is too strong due to the counter example of m^2 is 36. The second half would generate some but not all.

Oops! There was a major error in the way I formulated the problem. It was that by imposing n = 2k, I was trying to "broove" that n = 8 was the only even value for which sigma n is a square. Of course, that was not the your question all and there was no reason to do that.. I think it came about because I started off with 8*9/2 and did it while typing and not the good 'ol pen and paper.

So let me re-work this and put pen on paper and do it.

1+2.. n = n(n+1) /2 = r^2 (for it to be a square)

Rearranging it becomes n^2 + n - 2r^2 = 0 which becomes (n + 1/2) ^2 - (2r^2+ 1/4) = 0

or n = sqrt(8r^2+1) / 2 - 1/2 .

For n to be a natural number 8r^2 + 1 must be a square and the problem reduces to this.

ie 8r^2 +1 = y^2 (say) .. For this lets see use the "broof" method if you will to find out that if there are other squares.

Now for r = 1 , yes, y is a square .. so the solution is of the form (8+k)

So let us see if 8r^2 + 1 = 64+k^2 ie k^2 = 8r^2 -63 there exists natural values of r and k so that it is satisfied.. Now lets start with r>3 does not give natural k, r = 4 & 5 do not, 6 does! . Hence there are other solutions beyond r=1 (the next are r= 12,33,69,192.. etc from spreadhseet..) . Hence infinite solutions. So yeah, the broof , does work!

< Edited Later: The misunderstood part removed for clarity) >
(Sorry if I am misunderstanding .. (The above post was edited after I posted.. so adding more here)

What values of n do they give?
TIA

There obviously was an error in what I posted yesterday, I didnt go back to look at it. The most obvious one was the one constraining n to even, so I just junked it. That apart, do look up what I posted just now. In fact this doing on paper and transferring to kampooter is even more error prone. I think the list of further answers I put up calculated using the "broof" seems okay. That does have r as 12,33,69,192 among others.. so that is 2*12^2, and 2*192^2 among the even ones.

2*12^2 may work (as 289 is a perfect square) but How does 2*192^2 work?...

I was going to post this, but got busy reading and responding to Vinaji...
Here it goes - wrt to sigma(n) being a perfect square..

There are indeed infinite solutions..

And and it is quite easy..
(For method see chapter 2 of (See the link below):
ब्रह्मस्फुटसिद्धान्त
Start with 1
Then 2
Next one is 2*2+1 = 5
Next one is 2*5+2 = 12
Next one is 2*12+5 = 29
(Each step 2* previous line + line previous to previous..). You get
n = { 1, 2 , 5 , 12, 29, 70, 169, 408 }
You will see that 2n^2 is either 1 more or 1 less than a perfect square..
So the sigma (2n^2) (or 1 less than that) will be a perfect square.
(All explained by Brhamgupta about 1500 years ago

(So these numbers are, {1, 8 , 49 , 288, 1681, 9800, 57121 ..}


Hope this is interesting ...

Sorry. I must have posted some other column /row or typed something else . . However, he is the 5 or 6 values from the spread sheet. and I will just cut and paste it.

Sweet . But can you explain it in English? I am challenged when reading Devanagiri and really beyond very basic Sanskrit. I mean, I can see that there is a spiffy algo that spits out the answer much much faster than I can set it up on a calculator to crunch numbers and do it , but how did he arrive a that?

Amber ji and others

Hilbert's 10th problem which asks for an "algorithm" (he did not use that particular word as that concept came much later due to Turing, Church and Emile Post among others) to solve any Diophantine equation has been proven in the negative Matiyasevich who provided final and crucial step basing his work on that of Martin Davis, Putnam, and Julia Robinson. The book "Hllbert's 10th Problem" by Yuri Matiyasevich (MIT Press) is quite accessible. So, solving a system of Diophatine Equations is hard in the sense that every equation, if it can be solved, has to be solved by it's own unique method.

^^^ Thanks for the reference for the book. Seems very interesting.
Yes, Diophantine equations, and some of number theory problems in general, can be lot of fun, since some of them (logic behind the solutions) are easy to understand even for high school students, yet could be challenging to all.

The problem I posted here (2^n+12^n+...) was, IIRC, from this years (Junior) USAMO (10th grade and lower). (For those who don't know the contest is open to all us students.. about half a million take part, top 1-2% get invited for next level.. and about 1-2% from these are invited to take USAMO, from which the IMO team is selected)

Vinaji and others - Using computers may be fun, but in my opinion it will not be too helpful for problems like this. For example, for sigma (n) problem, unless you know Brhamgupta's method (or something essentially similar 'algorithm') brute-force method will not give you more than 10 or 20 terms.. because ..

1. Due to rounding off errors (this I suspect will happen very quickly in Excel) you will get many false results. One has to use large-precision type language. (Numbers become very large pretty soon)

2. Even if the computers become millions (or trillions) of times faster, (with parallel procession, or improved algorithm etc).. it may still require more than the life of the universe to get first 20-30 numbers by brute force - 10th number is already is >> (thousand times greater than) a trillion) ..

This is what makes math fun

Will do that in the next post.
But meanwhile, taking Ramanaji suggestion, let me comment on one topic of math, continued fraction, which does not get too much attention these days. I learned this in my high school (or earlier) like all others in those days, but the subject is not taught here in US and I don't think people do that in India now a days either.

This is why when I heard a very similar problem (to sigma(n)) I knew the answer almost right away .. (I'll come back to that at the end of the post).
The theory was, according to wiki and other sources, developed by Bhaskara II. People in India learned it, others did not (or not that much)
According to wiki:http://en.wikipedia.org/wiki/Srinivasa_Ramanujan


Wiki (or Wolfram or such sources) has good article on continued fraction.
And using this the sigma problem becomes very easy..
sqrt(2) = 1 + 1/( 2+ 1/( 2+ 1/(2+1/(......)))).....
(see: http://en.wikipedia.org/wiki/Square_root_of_2#Continued_fraction_representation
With first convergents: 1/1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408 ...
(Denominators are same as the series posted before {1,2,5,12,29,70..}
Each fraction is pretty close to sqrt(2), .. so if the fraction is (a/b)
a^2/b^2 is close to 2, in fact, difference between 2b^2 and a^2 is 1..

QED.
(PS - the logic of the relationship given by Brahamgupta (a_n = 2*a_(n-1)+a_(n-2)) becomes quite clear here)

..
Okay, here is not exact translation but using the modern language... from my notes...will give the essential ideas .. I will just use this particular case but techniques can be used for similar problems.
Let a = (1+sqrt(2)) and b= (1-sqrt(2))

(Note that ab = -1)

Now a^n would be something like :
(integer + (another integer)(sqrt(2)))
Or IOW X + Y* sqrt(2)
(Then b^n would be X - Y* sqrt(2))

So we have: X = (1/2) (a^n + b^n) is obviously an integer.
Also Y = (1/(2*sqrt(2)) (a^n - b^n) ... is also an integer...

Try X^2 - 2 Y^2 = (1/4) ((a^n+b^n)^2-(a^n-b^n)^2) (note that ab=-1)
which is (+-1) (+1 for even n, -1 for odd n)

So (X,Y) give the solution we need.
(and since n can take any value, there are infinite solution)
(One can also prove that there are no other solutions except given by different values of n) ... (proof is a little harder but still not very hard)

****
One should notice, that the key is expression of a^n which can be written as
a^n = X + Y sqrt(2)

So if you know the value of (X,Y) for n, you can get a recursive relation for (n+1) ... this is essentially the same which was given before..

****
The same method can be used not only for sqrt(2) but for any other number which is not a perfect square.

Hope people find it interesting ...
(This method is little different than continued fraction method of Bhaskara)

an observation -

brahmagpta's series, if i may coin the term, is similar to fibonocci's series. defining both recursively, we get

fibonocci: $f_1 = 1; f_2 = 1; f_i = f_{i-1} + f_{i-2}$
brahmagupta: $f_1 = 1; f_2 = 2; f_i = 2 f_{i-1} + f_{i-2}$

both are second order linear recurrence relation with constant coefficients. A general method for solving these kinds of methods is in aforementioned book by C.L. Liu

By the way, another problem related to Summations is

$\Sigma_{i=1}^n i^k = (n+1)^k$

The above is true for n = 2 and k =1, i.e. 1+2 = 3

Are there other solutions?

Last chapter of the on-line book by Leo Moser at http://www.trillia.com/moser-number.html has an interesting theorem.

As Amber ji says, the numbers become very large.

Edited after Amber ji pointed out the mistake in my original problem statement

Few comments..

Historically Fibonacci numbers, were not "discovered" by Fibonacci, he himself notes that work came from Indian mathematicians. Virahanka's work (written nicely Gopala) was quite nicely written and may be that's what was available to Fibonacci..

Just did a wiki and found that right in the beginning it has " the sequence had been described earlier in Indian mathematics"...and

Also:http://www.sciencedirect.com/science/article/pii/0315086085900217

But it's form and continued function (It is just (1+1(1+1/(1+1/(1+...) )
was certainly worked by Brhamgupta.. if not before.

Yes, both linear and second order diophantine equations have standard methods (both known to Brahmgupta/ bhaskara) of solving. If one does not know these methods, they become hard to solve.



What exactly is sigma here? ( Assuming n is a positive integer).. if it is sum (that is 1+2+...n = n(n+1)/2 ) then obviously n=2 is the only solution)

Can you post the "interesting theorem from Leo Moser's book?
P.S... In number theory, sigma (small sigma) is generally used to represent sum of all the factors of a number. Eg (sigma(6)=1+2+3+6=12) , in that case for any prime number (and prime numbers only) sigma(n)=n+1.

^^^ Yep, not only that, but a solution like:
1^3+2^3 = 3^2

too can generate infinite solutions like 100^3+200^3 = 3000^2
(n^2)^3+(2n^2)^3 = (3n^3)^2 (For any n)

Also many others... where, x,y are prime --or all are prime to each other, also exist ... (again infinite such numbers):


11^3 + 37^3 = 228^2
or
8663^3 + 2137^3 = 812340^2

(general formula is left as an exercise )
(BTW, one can prove that there are no solutions for x^3+y^3=z^5 when x,y,z have no common factors)

Ah. But your question was n^5 on the RHS! If it was 6 , I was going to do exactly this , but I wasn't sure of 5/3! .

But how does (n^2)^3 + (2n^2)^3 = (3n^2)^3 (which is the same as what is in the quote) square with a^n + b^n = c^n for any n >=2 . That is what confuses me. If so, what was the hoo-ha about the Fermat's theorem all about?

.. Two separate questions..(Actually look at your own posts where you make that clear .. ) one with power of 2 another with power of 5 on RHS)


But the equation is NOT true when all powers are 3. (you cannot find a solution in natural number ..)... What you have is 1^3+2^3=3^2 (RHS power is not 3 but 2)
Could it be that you are confusing between (3n^3)^2 and (3n^2)^3 which are NOT equal

Ah. Yes. Thanks.

Information about Fibonocci is interesting.

I have corrected my OP to reflect correct statement of the problem and pasting it below for reference.

What solutions are there for the following Diophantine equation?

$\Sigma_{i=1}^n i^k = (n+1)^k$

I am paraphrasing Moser's book below.

Erdos conjectured that the only solution is the trivial one, i.e. n=2 and k=1. Moser proves a theorem that says that if a solution k>1 exists then n > 10^1000000. In this case, a brute force method is clearly infeasible due to two difficulties -

1. Since the lower bound on n is so large, even checking for a few modest values of k is computationally very intensive.
2. This is more technical - if there is no solution the program does not halt.

I will post a problem later whose solution can be captured in a program easier than derive a closed form solution.

Thank you.
Yes, if one finds one solution, one can generate infinite solutions from that.
For example Najunamar's solution to x^3+y^3=z^2 's basic (primitive)
is 2^3+2^3=4^2
(and it can generate (2n^2)^3+(2n^2)^3 = (4n^3)^2 etc..)
Another primitive solution is 1^3+2^3=3^2
And there are infinite more primitive solutions like 11^3+37^3 = 208^2

(There are - not too difficult - ways to get all these types too,.. in may require a little more math ( math techniques) ..)

****

BTW I think it is easy to show that k is of the order of (.6n) (say it is more than .5n and less than n) ... but that does not help much..

Any way, as you know this is known as Erdos-Moser conjuncture..
http://mathworld.wolfram.com/Erdos-MoserEquation.html

The limit for lower value of n has been raised to about 10^1000000000 now.(see below) ... BTW there is a talk in December in Amsterdam which you may find interesting...
http://event.cwi.nl/wcnt2011/invitedspeakers.html
Check out the talk by Pieter Moree

Here's another nice Diophantine problem:

Say x^2 + y^2 +z^2 = 59^n, show that natural number solutions are always possible for (x, y, z) for any natural number n.

Nice problem
^^^ A number can be written as x^2+y^2+z^2 if (and only if) the number is of the form 4^k(8t+7) where (k, t) are integers.. (hard to prove)
IOW all numbers 7 mod 8 can never be written ... (obviously. - easy to prove...)
And all other numbers (except those of the form given above) can always be written as sum of (at most) three squares...
(one could have had any odd number which is not 7 mod 8 instead of 59 and the relationship would be true... of course, for even n, this will be true for even these numbers..: ) ... only exception may be 5 where you need only 2 squares.. iow the z has to be zero)

Stop here.. if you want to try your own method ..
Read further only if you want to get one solution...
Hint 1: if you can write p as a^2+b^2+c^2 .. you are done...
(Cause then you can always get it for p^2..
(and then for every k^2 p (or k^2 p^2))

59=1+3^2+7^2, 59^2 = 14^2+42^2+39^2 ..

^^^ Was just thinking .... Above can be modified, where y=z, that is, prove that
59^n can always be written as x^2+2y^2
(which is a special case of x^2+y^2+y^2).

Yes, of course for n =1 itself there are 2 (at least) distinct triads satisfying the equation, one of which has the repeated integer. It is interesting, that excepting for the 7mod8 cases every one of such numbers can be written as the sum of 3 squares, the general result is 4 squares I believe; Fermat(? - help) showed that every positive integer can be written as sum of at most 4 squares, 19 cubes and so on...

Yes that is correct.. though one may have to be a little careful..


Yes, every 7mod8 can not be expressed as sum of 3 squares, but there are other numbers like 28 which can not be expressed as sum of 3 squares ..

(It is fairly easy to prove that 7mod8 can not be expressed as sum of 3 squares but the reverse part is pretty hard - that is to prove that all numbers which are not of the form 4^k(8t+7) can be expressed as sum of 3 squares..

2, and any prime of the form 4k+1 can be expressed as sum of 2 squares...
And yes, all numbers can be expressed as sum of 4 squares...(Theorem, I think was proved by Lagrange )

One thing people may find a lot of fun, if they are not familiar with it, is use of algebraic integers which makes the last few problems fairly easy to solve..

Algebraic integers in many ways have the same kind of arithmetic as ordinary integers..(and once you get a hang of it..it is a very powerful tool)

In any case, to see the beauty of this method, let us see the above problem ...
We define our "integer" as any thing like (a+b*sqrt(-2)) (where a and b are ordinary integer), In this case, any multiplication (or addition) of such "integers" will give another one of the of the same form.

In particular, say (a+b* sqrt(-2))^n will be of the form (A+ B* sqrt(-2))


59 = 9+50 = 3^2 + 2*5^2 = (3+5*sqrt(-2)) (3- 5*sqrt(-2))
so 59^n = ((3+5*sqrt(-2))^n) ((3-5*sqrt(-2))^n )
Now in RHS, first term is of the form A+B*sqrt(-2) (A and B are integers)
the second term has to be (A-B*sqrt(-2))
So 59^n = A^2 + 2* B^2
QED!
(With almost same kind of logic, one can find, say, (all) solutions of the previous problem ( of (x^3+y^3 = a^2)) fairly easy.. or prove that there is only one solution for
x^2+2=y^3 (soln (5,3) or x^2+1 = y^3 etc....))

Amber ji

Thanks for the pointers. The raising of the lower bound is very interesting. I wonder if there is a procedure which can successively increase the lower bound. If so, that would consist a proof of the conjecture.

Two papers previous to the linked paper seem interesting - especially the block Lanczos iterative method.

By the way, using the notation of small sigma (did not know about this notation), one can define perfect numbers and amicable numbers in a compact way. I was doing it awkwardly with words

n is a Perfect number if $\sigma(n) = n$ and m and are amicable if $\sigma(m)=n ^ \sigma(n)=m$

^^^ A minor comment. For sigma function, from standard definition in math books, it is normally defined as sum of all the factors (including the number it self).. So for example, a perfect number is defined as (conventionally) (sigma(n)=2n).

Defined this way, it has nice distributive property, that provided (a, b) are relatively prime,
sigma(a*b) = sigma(a)*sigma(b)

(It is a very useful property, for example if you want to find the sum of all the factors of, say, 120 ...instead of summing all these (1+2+3+4+5+6+8+10+....) numbers.. you can write it as 15*8 (or 3*5*8) and this is sigma(3)sigma(5)sigma(8) = (1+3)(1+5)(1+2+4+8) = 4*6*15 etc...

Najunamar: There was a math-Olympiad try-out problem.. prove that there are infinte values of k, such that one can find solutions (in natural numbers)
k^k = a^3+b^3
(Problem may look hard, but one proof is quite simple... if one can think of it - Hint: it can almost follow your solution given before)

Meanwhile: The following problem from Ramanujan's note book (where he just simply writes an answer without any method ...)

what is the value of (this infinite sequence..

sqrt(1+sqrt(1+2*sqrt(1+3*sqrt(1+4*sqrt( .................................

The answer is 2.
(Will not put a solution here, as it is fairly hard and may appears as problem in some contests.. .. can be looked up in a book ..etc .. but it just gives an idea of Ramanujan's genius...)

No higher mathematics needed for this one:

You start a new job. This job pays Rs. 10,000 per annum, with paychecks coming in on the 1st and 15th of every month. Your boss also offers you two options:
1. You get an annual raise of Rs. 1,000
2. You get a raise of Rs. 300 every 6 months.

Which option should you choose to make more money .

Wish that the problem was defined clearly ...

What exactly does that mean?
Does this mean your salary after 6 months for the next pay (24 pay checks per year) check is (10,000+300)/24 or
10,000/24+ 300/12 IOW the raise of 300 is calculated as in "yearly salary" or per 6 months .. (or per pay check ? as in you get 10000/24+300?..

Also how long are you going to work.. (Because if you plan to quit before 1 year before your annual increase kicks in...

Do one assume interest (investment) rate to be 0?

^^^^
It means your salary goes up Rs. 300 every 6 months. So if you got Rs. 1000 in the first six months, you get Rs. 1300 in the next six. Sorry for any confusion caused.

Assumption here is that you work for a few years at least (years > 1) and no interest or investment rates are involved.

Even lesser maths required for this one!

Received by email.

Money bags

This year, July has 5 Fridays, 5 Saturdays and 5 Sundays. This happens
once every 823 years. This is called money bags. Based on Chinese
Feng Shui.

Kinda interesting - read on!!!

This year we're going to experience four unusual dates.

1/1/11, 1/11/11, 11/1/11, 11/11/11 and that's not all...

Take the last two digits of the year in which you were born - now add
the age you will be this year,

The results will be 111 for everyone in whole world.

This is the year of the Money!!!

Chetak, please read this.

In that case, unless I am missing something in translation, Obviously 300 every 6 month is so much better.. you will be about 100n(n+2) dollars ahead at the end of n years...obviously (1/2) square is 1/4 so over the long run anything better than 1000/4 will end in net plus...

IOW, the pay rate increase per 6months = ( equivalent to 600/year).. which gives acceleration as (1200/year) per year or (1200/year^2)....

(Added later: Actually a "raise" of $10 per month is much better than "raise" of $1000/yr .. or even $1400 /yr.. and $1 per week increase is better than $2500/yr...)

As Jaspreet pointed out, don't believe in any silly thing passed as "math".. or having " mythical significance" .
EVERY month which has 31 days will always have 3 days of the week 5 times. (Hint 31 = 4*7 +3) and approximately (1/7) of these of will have FRI/SAT/SUN...

So it is not 823 years.. more like about 7 years.. (due to leap years... not every seventh year but approximately 7 in long run....)


First, if a person was born in 2001, the sum will be 11 and not 111 ...
But if a person was born in 19xx .. big deal? x+(111-x) is always 111.
(Next year this will be 112 .. and so on..)

Amber G,
Got it, again using k = 2^m and a = b= 2^p, we get m*2^m = 3p+1, which has solutions for m=2n for all natural n.

Thanks for the hint.

^^Yes!
It will also work when a=(27n^3+1)^(9n^3), b=3n(27n^3+1)^(9n^3)
and k=(27n^3+1) etc...