Remove ads

Introducing the LemonFools Personal Finance Calculators

Six

cinelli
2 Lemon pips
Posts: 169
Joined: November 9th, 2016, 11:33 am
Has thanked: 42 times
Been thanked: 23 times

Six

#153622

Postby cinelli » July 20th, 2018, 10:35 am

This puzzle is to find two positive rational numbers (fractions) whose cubes total precisely 6.

Cinelli

jfgw
Lemon Slice
Posts: 684
Joined: November 4th, 2016, 3:36 pm
Has thanked: 95 times
Been thanked: 148 times

Re: Six

#154169

Postby jfgw » July 22nd, 2018, 5:18 pm

Spoiler:

(17/21)^3 + (37/21)^3
= (17^3+37^3)/21^3
=(4913+50653)/9261
=6

If two fractions in their simplest form add up to an integer, their denominators must be the same.

The sum of the cubes of the numerators must be a multiple of six. Obviously, if the roots of both cubes are multiples of six, then the cubes are both multiples and so is the sum. For example, 6^3+12^3 must be a multiple of six.

Looking at the remainders when other numbers were cubed and divided by six, I discovered that the remainder increased by 1 when the root was increased by 1. For example, 7^3 /6 gives a remainder of 1, 8^3 /6 gives a remainder of 2, and so on. In order for there to be no remainder, the sum of the two roots must be a multiple of 6, e.g., 2^3+10^3 must be a multiple of 6.

I used Excel for the next step:

I generated two columns with numbers that added up to a value in another cell which I could change. I increased this value in this cell in steps of 6 and observed the results.
I calculated the sum of the cubes of these numbers and divided it by 6.
I took the cube root of the result and tested it to see if it was an integer.


Julian F. G. W.

Gengulphus
Lemon Quarter
Posts: 2532
Joined: November 4th, 2016, 1:17 am
Been thanked: 1175 times

Re: Six

#154268

Postby Gengulphus » July 23rd, 2018, 7:48 am

I won't try to improve much on jfgw's solution, though I will observe that the identity:

a^3 + b^3 = (a+b) * (a^2 - ab + b^2)

is helpful for establishing one of its intermediate results. His method does involve a 'brute force' search (which fortuitously finds a solution quite quickly), but I don't know of any method that doesn't!

Interestingly, if one has a solution and drops the "positive" requirement, there are methods to generate other solutions - and it seems very likely to me that those other solutions include others that meet the "positive" requirement. The "if one has a solution" condition is important, though: it's finding the first solution that is hard.

But don't try "brute force" searching for other solutions using jfgw's "incrementing the sum of the numerators by 6 by hand" spreadsheet method. The solution involving the next smallest numbers (by magnitude) is (-1805723/960540)^3 + (2237723/960540)^3 = 6, with numerator sum 432000, so you would be in for a lot of incrementing by 6! Furthermore, the search involved for each particular numerator sum changes from a finite one to an infinite one once one drops the "positive" requirement, and solutions beyond that one involve much bigger numbers still, so the next positive solution (which I don't know) is way beyond being findable by a by-hand 'brute force' searches in practice, and probably beyond completely automated ones as well.

All of the above follows from the mathematical theory of elliptic curves (*). The Wikipedia article about them contains a lot of information about them, though it's dense enough to require a lot of study and chasing up links to fully understand it. The way that solutions are created from each other is explained under "The group law", for example. A fairly easy explanation of the connection between this problem and elliptic curves can be found in http://mathforum.org/kb/message.jspa?messageID=42986, and https://math.stackexchange.com/question ... -rationals is another useful link about the problem.

(*) Which are decidedly confusingly named, as ellipses are not elliptic curves! I believe they're named the way they are because they arose from the problem of determining the length of an arc of an ellipse.

Gengulphus

jfgw
Lemon Slice
Posts: 684
Joined: November 4th, 2016, 3:36 pm
Has thanked: 95 times
Been thanked: 148 times

Re: Six

#154476

Postby jfgw » July 23rd, 2018, 5:36 pm

Gengulphus wrote:I won't try to improve much on jfgw's solution, though I will observe that the identity:

a^3 + b^3 = (a+b) * (a^2 - ab + b^2)

is helpful for establishing one of its intermediate results.


Not entirely conclusive unless I have misunderstood (quite likely).

The remainders from dividing the sequence of cubes by 6 give a rather neat sequence of 1, 2, 3, 4. 5, 0... which enabled me to reduce the amount of brute force needed. The (a^2 - ab + b^2) part of the above identity turned out to be irrelevant. The same is not always true for other divisors, however. If the sum of the cubes had been seven, the sequence of remainders would have been 1, 1, 6, 1, 6, 6, 0... which would have made the puzzle more difficult to solve.

I was surprised to find a solution so quickly and thought that I would need to write a macro to increment the sum of the roots. (I was still not sure that a solution existed within the limits of my spreadsheet.)

I was thinking of writing a macro anyway to try to find another solution but, after Gengulphus's reply, It is clear that such an exercise would be futile.

Julian F. G. W.

Gengulphus
Lemon Quarter
Posts: 2532
Joined: November 4th, 2016, 1:17 am
Been thanked: 1175 times

Re: Six

#154661

Postby Gengulphus » July 24th, 2018, 12:15 pm

jfgw wrote:
Gengulphus wrote:I won't try to improve much on jfgw's solution, though I will observe that the identity:

a^3 + b^3 = (a+b) * (a^2 - ab + b^2)

is helpful for establishing one of its intermediate results.


Not entirely conclusive unless I have misunderstood (quite likely).

The remainders from dividing the sequence of cubes by 6 give a rather neat sequence of 1, 2, 3, 4. 5, 0... which enabled me to reduce the amount of brute force needed. The (a^2 - ab + b^2) part of the above identity turned out to be irrelevant. ...

The identity does give a quick proof that if a+b is divisible by 6, so is a^3 + b^3, with the a^2 - ab + b^2 part being irrelevant beyond the very obvious fact that it is an integer. But I did overlook the fact that it's not so helpful on establishing the opposite implication (i.e. that if a^3 + b^3 is divisible by 6, so is a+b), so yes, not entirely conclusive.

jfgw wrote:I was surprised to find a solution so quickly and thought that I would need to write a macro to increment the sum of the roots. (I was still not sure that a solution existed within the limits of my spreadsheet.)

I was thinking of writing a macro anyway to try to find another solution but, after Gengulphus's reply, It is clear that such an exercise would be futile.

Before I resorted to a web search to find out whether other solutions were known, I actually did a spreadsheet along your lines but with some refinements to make it go a lot further. It didn't use macros, but did use carefully-designed formulae to make it run through the possibilities that I wanted, which were combinations of a and b such that a+b is a multiple of 6, a < b and a and b are not multiples of either 2 or 3 (and so are 1 or 5 mod 6).

That last requirement was on the basis that if a+b is a multiple of 6 and either a or b is a multiple of a prime p that divides 6 (i.e. p is 2 or 3), then the formula above establishes that (a^3 + b^3)/6 is a multiple of a^2 - ab + b^2, which is a multiple of p (and indeed of p^2). So if c = CubeRoot((a^3 + b^3)/6) is an integer, it too is a multiple of p. But c is the denominator of the two rational numbers a/c and b/c whose cubes add up to 6, so that implies that those rational numbers are not in lowest terms - so if a solution does come out of it, it's just a repeat of a solution I've already seen for a smaller sum a+b.

So the spreadsheet's first four columns were (arrived at after a few rounds of refining them - I didn't manage to leap straight to them!):

Column A, labelled "a+b" in cell A1, initialised with 6 in cell A2, with formula "=IF(B2+C2=D2,A2+6,A2)" in cell A3

Column B, labelled "inc" in cell B1, initialised with 4 in cell B2, with formula "=IF(B2+C2=D2,4,6-B2)" in cell B3

Column C, labelled "a" in cell C1, initialised with 1 in cell C2, with formula "=IF(B2+C2=D2,1,B2+C2)" in cell C3

Column D, labelled "b" in cell D1, with formulae "=A2-C2" and "=A3-C3" in cells D2 and D3 respectively

The "inc" value is the amount I would normally increment a by: it starts as 4 when a=1 and then normally alternates between 2 and 4, so that the sequence of a values is 1, 5, 7, 11, 13, 17, ..., i.e. those that are 1 or 5 mod 6.

The "B2+C2=D2" conditions test whether that normal increment of "a" would generate the current value of "b" - if so, I'm about to move into (a,b) combinations with a>b, which are just reversed-order versions of combinations I've already tested, so I've finished testing the current multiple of 6 for a+b and should move on to the next one, i.e. I should increment a+b by 6 and reinitialise a to 1 and inc to 4. Otherwise, I should leave a+b unchanged, do the normal increment to a, and perform the normal 2/4 alternation on inc.

So copying row 3 to subsequent rows produces a table that runs through the (a,b) combinations I want to test, limited only by the 1048576-row Excel restriction. More columns calculated c and determined whether it was a cube and whether a/c and b/c were in lowest terms. (I've already ensured neither a nor b has a factor 2 or 3 in common with c, but not larger primes. So the tested combinations do include e.g. a=85, b=185, which produces c = 1157625 = 105^3 and the solution (85/105)^3 + (185/105)^3 = 6, which is just a duplicate of the already-known (17/21)^3 + (37/21)^3 = 6.)

A final column produced 1 if c was a cube and had greatest common divisor with a and b, 0 otherwise, and summed that column to produce the number of different solutions found.

Then I went a bit mad and did indeed copy row 3 all the way down to row 1048576... The spreadsheet took a pretty long time to update, even on the fairly powerful desktop I was using, but did eventually get there - and the number of solutions was 1 (that's a complete check on a+b values up to 8682 and a partial check on 8688).

I could have reprogrammed the search as a C program, which would have run a lot quicker and had considerably smaller memory requirements (due to not keeping all the tested (a,b) combinations in memory at the same time). But it was clear that solutions were pretty sparse, and I already had a bit of a suspicion that elliptic curves might be involved, basically because of mathematical background knowledge that they often are for number theory problems involving cubes, plus the further snippet that if elliptic curves were involved, there would very probably be further solutions but the numbers might get very big. So at that point, I decided instead to do a web search for what was known about the problem.

Gengulphus

cinelli
2 Lemon pips
Posts: 169
Joined: November 9th, 2016, 11:33 am
Has thanked: 42 times
Been thanked: 23 times

Re: Six

#155354

Postby cinelli » July 26th, 2018, 2:31 pm

Well done, solvers. I don’t have an analytical method, only brute force. I can add that French mathematician Adrien-Marie Legendre “proved” that there was no solution only to be confounded by my favourite puzzler Henry Dudeney who found the fractions 17/21 and 37/21 decades before the invention of computers. He also found the unlikely solution where the sum is nine instead of six (apart from 1 and 2):

415280564497/348671682660 and 676702467503/348671682660.

Cinelli


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 1 guest