A Math's puzzle that sounds easy

[Tiggs]

I have a maths problem that's been bothering me for a while - hoping someone can help:

I have a large(500+ digit) even number that I know must be the sum of a series of consecutive odd numbers - how do I find the start of that series and the number of terms within it?

[Moon Monkey]

I have a maths problem that's been bothering me for a while - hoping someone can help:

I have a large(500+ digit) even number that I know must be the sum of a series of consecutive odd numbers - how do I find the start of that series and the number of terms within it?

Me...I would write a small program with a couple of loops,outer loop i=1, inner loop start with j=i record a vector of [j] on each iteration on the inside loop where j=j+2 at the bottom of the loop so you get [1;3;5;7...] and sum them..if it equals your target 'stop' and return j vector, if it exceeds your target break back to the outer loop, clear j and start again with i=3 then j=i. Loop j=j+2 again [3;5;7;...] etc.

There is probably some fancy formula but I think this would take 2 mins to write and another 2 mins to calculate

Edited November 8, 2007 by Moon Monkey

[Tiggs]

Not when your number's 637 digits. Trust me.

I've previously tried an optimised version of that. I stopped it after it had been running for two months

I calc'd the initial set by a normal sum of series, worked out the remainder and then looped, adding odd numbers in pairs (as it's going to be an even number of odd numbers), and changing the start position to take into account the new pair plus the remainder from previous, which gave me a new remainder. Exit the loop when the remainder is 0.

There's some additional jiggling to make sure the initial sum has an even number of terms etc, but you can see the basic concept.

When you use a small number (20 or less digits), it works fine. It's just too slow.

ps. * Designs and writes code for a living *

Edited November 8, 2007 by Tiggs
Added details of one of my many previous attempts

[Moon Monkey]

Not when your number's 637 digits. Trust me.

I've previously tried an optimised version of that. I stopped it after it had been running for two months

I calc'd the initial set by a normal sum of series, worked out the remainder and then looped, adding odd numbers in pairs (as it's going to be an even number of odd numbers), and changing the start position to take into account the new pair plus the remainder from previous, which gave me a new remainder. Exit the loop when the remainder is 0.

There's some additional jiggling to make sure the initial sum has an even number of terms etc, but you can see the basic concept.

When you use a small number (20 or less digits), it works fine. It's just too slow.

ps. * Designs and writes code for a living *

Sorry, didn't appreciate the scale of the 500+ digit thing. Apart from a fancy formula which I don't know would it be possible to run it as matrices, sum rows or columns and then sum the sums and check with your target ?

start with [1 3],

then [3,5] [1,3;5 7]

[5,7],[3,5;7,9],[1,3,5;7 9 11]

[7,9],[5 7;9;11],[3,5,7,9,11,13],[1,3,5,7; 9, 11,13, 15 ]

[9,11],[7,9;11,13],[5,7,9;11,13,15],[3,5,7,9;11;13,15,17],[1,3,5,7,9;11,13,15,17

,19]

and so on.

As it is exponential it might be quicker, still gets to a big matrix though I suppose for a 500+ digit number. Sorry if it is useless all I could think of off the top of my head.

Edited November 8, 2007 by Moon Monkey

[Leonardo]

I have a maths problem that's been bothering me for a while - hoping someone can help:

I have a large(500+ digit) even number that I know must be the sum of a series of consecutive odd numbers - how do I find the start of that series and the number of terms within it?

Tiggs,

I don't know a formula to work this out but here are my thoughts.

Any such sequence must have an even number of addends, given the product is even.

Assuming the sequence can start at any odd number as well, not necessarily starting at 1, and it can be as large or small a sequence as required. Let's call your large number x.

So, divide x by a even number (n) where (n/2) is odd, i.e. n=6. The resultant is the middle number of your sequence. It is, of course, an even number (ignore any n where the resultant is not a whole number), so the odd numbers to either side are the start and end of each 1/2 sequence.

That number n is also the number of addends in your sequence. To find the first number in the sequence subtract n from the larger of the two 'middle' odd-numbers and to find the last number in the sequence add n to the smaller of those two numbers.

I tested this on numbers x = 168; n = (6,14) and x = 3036; n = (6,22). It seems to work even when the sequence rolls past 1 into negative odd numbers (as was the case with x = 168; n = 14)

You should be able to do this with any even number divisor as stipulated. Please let me know if it works or not!

*edited for clarity. I had some of my thoughts a bit garbled!!!!

Edited November 8, 2007 by Leonardo

[Tiggs]

Thanks, Moon Monkey, but it's still going to be too slow. Plus, I'd have to have petabytes to store the matrixes in.

I wouldn't feel so bad - It's been driving me slowly crazy for the last year or so, now. *Sighs*

ps There is a solution, halving the number and subtracting 1, and then adding 2 to it, giving two odd numbers which will sum to the answer - that's not the one I'm looking for - there's another solution, with lots more terms in

[Moon Monkey]

Yeh sorry again. Did you try leonardos method ?

Edited November 8, 2007 by Moon Monkey

[Tiggs]

Interesting Leo - I have a sneaking suspicion that my problem will be finding a value of n where the resultant is a whole number.

I'll run it for the first million values of n this evening and get back to you. If anyone wants to have a try, the number I'm playing with is:

1007836339026315739761087329601935942857

1712850481612811110855134417464808283038

2225056074103523137627673162564998060328

7571942365967047380112339564802913799707

4957122915110694388567338908104758550005

9887298764660310453519436382800389321838

9952337136071897164025698347672687804749

8448606069061852912886747995019672968973

4549036340567461848174307193693548739097

7916829597369463392952971247926552600426

9924180664150922422480647870502453537657

4415335617659810537728760458630177816713

6960836984660628934031148309992685030898

7185170554542549315964861932575267159954

0161781456094109527805514546257564848041

588491288482881428

Edited November 9, 2007 by Tiggs
Finally got round to multiplying it by 4

[Leonardo]

LMAO!!!!!!!!

Sorry, Tiggs.

I think there must be a relationship between x and n other than n being a simple divisor. A relationship that should let you know what values of n are valid, but I'm still working on that!

[Leonardo]

Okay, some of the resultants can be odd whole numbers and, according to my calculations, these can be ignored as the n that results in these cannot be the number of such a sequence, only use n's resulting in an even resultant of division.

More updates to follow...

[Moon Monkey]

Okay, some of the resultants can be odd whole numbers and, according to my calculations, these can be ignored as the n that results in these cannot be the number of such a sequence, only use n's resulting in an even resultant of division.

More updates to follow...

So what we are looking for is even factors of the number (x) that when divided by 2 result in an odd number ? Apart from 2 which Tiggs has already decided is too easy.

Edited November 8, 2007 by Moon Monkey

[Leonardo]

So what we are looking for is even factors of the number (x) that when divided by 2 result in an odd number ? Apart from 2 which Tiggs has already decided is too easy.

Sorry, no. The product of the division, y, must be an even number for the sequence of size n to add up to the total x.

So x / n = y ; y = even integer.

Also n_z = (2 + (z*4)); z = {1,2,3,4,...}

That's a general formula for putting in code though. Not all y's derived from that will be valid. Still check if they are even integers.

Edited November 8, 2007 by Leonardo

[Moon Monkey]

Sorry, no. The product of the division, y, must be an even number for the sequence of size n to add up to the total x.

So x / n = y ; y = even integer.

I am getting confused,what I said was "So what we are looking for is even factors of the number (x) that when divided by 2 result in an odd number ? " Maybe I should have said, "where one of them divided by 2 is odd"

I thought n is an even integer and y is an even integer....... so x = n*y where both n and y are even integers and are factors of x, where 1 of them when divided by 2 is odd (this one we will call n in your first post). So we are looking for 2 even factors of x where one of them when divided by 2 is odd ? If I am wrong I am giving up and steering clear of this.

[Leonardo]

I am getting confused,what I said was "So what we are looking for is even factors of the number (x) that when divided by 2 result in an odd number ? " Maybe I should have said, "where one of them divided by 2 is odd"

I thought n is an even integer and y is an even integer....... so x = n*y where both n and y are even integers and are factors of x, where 1 of them when divided by 2 is odd (this one we will call n in your first post). So we are looking for 2 even factors of x where one of them when divided by 2 is odd ? If I am wrong I am giving up and steering clear of this.

You are correct in that you have to find an n where x/n = y | n, y = {2,4,6,8,...}

The y you find is the centre of the sequence, but the sequence is only odd numbers, so the two actual 'middle numbers' are (y-1) and (y+1). The first number in the sequence is ((y+1)-n), the last is ((y-1)+n).

So far it works for all the x's I've checked and found valid n and y for. I'm trying to work out a formula (see above) so it can be more quickly run in code.

Edited November 8, 2007 by Leonardo

[Moon Monkey]

You are correct in that you have to find an n where x = n*y ; y = {2,4,6,8,...}

The y you find is the centre of the sequence, but the sequence is only odd numbers, so the two actual 'middle numbers' are (y-1) and (y+1). The first number in the sequence is ((y+1)-n), the last is ((y-1)+n).

So far it works for all the x's I've checked and found valid n and y for. I'm trying to work out a formula (see above post) so it can be more quickly run in code.

Yeh, phew I was understanding it correct. It reduces the size of the solution set by quite a lot. If you are using matlab I am sure there is a function out there in the file exchange forums that will give all the factors and then you can limit it to those that meet the constraints you give, still the size of the number Tiggs is dealing with that might be a problem for any code.

Maybe just write the code to provide the even numbers that when divided by two give a odd integer and check if its a factor with an even co-factor, still iterating but got to be a lot quicker.

Edited November 8, 2007 by Moon Monkey

[Leonardo]

Yeh, phew I was understanding it correct. It reduces the size of the solution set by quite a lot. If you are using matlab I am sure there is a function out there in the file exchange forums that will give all the factors and then you can limit it to those that meet the constraints you give, still the size of the number Tiggs is dealing with that might be a problem for any code.

Maybe just write the code to provide the even numbers that when divided by two give a odd integer and check if its a factor with an even co-factor, still iterating but got to be a lot quicker.

I understand. But take, for example, if x = 168, n = {4,6,14,42}.

so...

x= 168

n = 4 ; y = 42 ; sequence = {39, 41, 43, 45} = 168

n = 6 ; y = 28 ; sequence = {23, 25, 27, 29, 31, 33} = 168

n = 14 ; y = 12 ; sequence = {-1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25} = 168

n = 42 ; y = 4 ; sequence = {-37, -35, -33,..., 39, 41, 43, 45} = 168

You would have to check if either the n/2 or the y/2 value was odd (not both).

Edited November 8, 2007 by Leonardo

[Belial]

Sorry leonardo, you typed - (x= 168) IT SHOULD READ AS X= WTF are you all on about?????? my eyes/head and back ache from reading this thread and even trying to understand it all. lol.

[Moon Monkey]

I understand. But take, for example, if x = 168, n = {4,6,14,42}.

so...

x= 168

n = 4 ; y = 42 ; sequence = {39, 41, 43, 45} = 168

n = 6 ; y = 28 ; sequence = {23, 25, 27, 29, 31, 33} = 168

n = 14 ; y = 12 ; sequence = {-1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25} = 168

n = 42 ; y = 4 ; sequence = {-37, -35, -33,..., 39, 41, 43, 45} = 168

You would have to check if either the n/2 or the y/2 value was odd (not both).

Yes thats the easy bit (e.g. IF loops, OR gates) its getting all the factors and co-factors for such a large number thats the difficult bit.

1 168...00....False (we don't want 1's and 2's)

2 84....00....False

4 42....01... True

6 28....10... True

8 21....00... False

12 14...01...True

and we already know that if 12,14 works then 14,12 works, its up to Tiggs if he wants to go into minuses, if he sees them and doesn't like them then simply switch. If its done through iteration simply chose n to be the smaller of the two factors, it is easy to order them in this way.

It rests and falls on getting all the factors, then seperating out all factors which are both even, then splitting and then testing the pairs for ones where one (like you say not both) are even. Not the easy job in the world for such a big number but I'll bet there is a program out there somewhere for free download.

[Tiggs]

Trust me - that number doesn't have many factors. Nothing smaller than 250 digits, anyway.

To be honest, I don't think it's solvable - which is a shame, as it sounds like it should be an easy thing to do.

[Leonardo]

Yes thats the easy bit (e.g. IF loops, OR gates) its getting all the factors and co-factors for such a large number thats the difficult bit.

1 168...00....False (we don't want 1's and 2's)

2 84....00....False

4 42....01... True

6 28....10... True

8 21....00... False

12 14...01...True

and we already know that if 12,14 works then 14,12 works, its up to Tiggs if he wants to go into minuses, if he sees them and doesn't like them then simply switch. If its done through iteration simply chose n to be the smaller of the two factors, it is easy to order them in this way.

It rests and falls on getting all the factors, then seperating out all factors which are both even, then splitting and then testing the pairs for ones where one (like you say not both) are even. Not the easy job in the world for such a big number but I'll bet there is a program out there somewhere for free download.

Getting the factors shouldn't be too difficult, just time consuming. Start with n = 1, y = (x) - I know we don't want this sequence, but this is just to initialise n and y to a value. Introduce an operand (a?) and make it initially 2, initialise this to another operand (. For each iteration make n*b and y/b. After finish b = b + a. Repeat until you cannot divide y any further. Then restart the iterations (n = 1, y = x) with a = a + 1, and so on. You'll eventually get to a point where the first iteration of n*b is as equal to y/b as possible given the original x. This is your full set of factors. You can dump the (2, x/2) sequence after that.

Scrub the a = a + 1 bit. You need to use the set of primes for the multiplication/division a = {2, 3, 5, 7, 11,...} up to IF n*a > y/a then stop. That should be a quicker way of working out your factors and with no duplication.

Edited November 8, 2007 by Leonardo

[questionmark]

Trust me - that number doesn't have many factors. Nothing smaller than 250 digits, anyway.

To be honest, I don't think it's solvable - which is a shame, as it sounds like it should be an easy thing to do.

It is solvable and will probably end up with several possible solutions... the way I see it Leo is on the right path. Sorry, too busy right now to chalk up my blackboard.

[Tiggs]

Getting the factors shouldn't be too difficult, just time consuming. Start with n = 1, y = (x) - I know we don't want this sequence, but this is just to initialise n and y to a value. Introduce an operand (a?) and make it initially 2, initialise this to another operand (. For each iteration make n*b and y/b. After finish b = b + a. Repeat until you cannot divide y any further. Then restart the iterations (n = 1, y = x) with a = a + 1, and so on. You'll eventually get to a point where the first iteration of n*b is as equal to y/b as possible given the original x. This is your full set of factors. You can dump the (2, x/2) sequence after that.

My brain's spinning a little - how many iterations do you roughly think that would be?

[Moon Monkey]

It is definately solvable its just a size problem, there may be multiple solutions but we should be able to get them all. The problem is if you are going to use the prime number method you need all the prime numbers up to **that big number**/2-ish, not a quick task in itself and then iterate through them all, again time.

You might as well calculate all the possible even numbers that when divided by 2 give an odd number seperately, stack these in a vector and divide them against **that big number** and check for real, even numbers in the answer vector this will give you pairs of real even numbers and even numbers that give an odd number when divided by 2 in one, long waiting time,shot.

[Leonardo]

My brain's spinning a little - how many iterations do you roughly think that would be?

Sorry Tiggs, had to rethink that as I realised there'd be lots of duplication. If you initialise n = 1 and y = x, let a = {2,3,5,7,11,13,17...} (set of primes) and have a STOP condition if n*a > y/a that should do the trick.

So (I'm not a programmer so forgive the language)

#

y = <your number>

a = {2,3,5,7,11,13,17...}

b = {1,2,3,5,7,11,13,17...}

loop:

c = a*b

x = y/c

IF c > x

THEN

end loop

IF c even AND x even

THEN

IF c/2 odd AND x/2 odd

THEN

next b

goto loop

IF c/2 = even AND x/2 = even

THEN

next b

goto loop

write c

write x

next a

reset b

goto loop

:end program

I think this logic is correct, please check it of course! You'll still get some duplication, but not nearly as much.

Edited November 8, 2007 by Leonardo

[Tiggs]

where does n get modified?