A Math's puzzle that sounds easy

[Leonardo]

where does n get modified?

m = n*c

write m

x = y/c

write x

m will be all your 'n's

x will be all your 'y's

[Tiggs]

Does n get set to m afterwards? otherwise, n looks like it's 1, all the way through

[Leonardo]

Does n get set to m afterwards? otherwise, n looks like it's 1, all the way through

I see what you're saying. I don't need n in there at all!!!!

Told you I wasn't a programmer!!!!

I'll modify it in my post.

Okay, please check again! Hope it's better this time!

Just to let you know I'm signing off. I sure others can build on the start and finish off this puzzle for you, otherwise I'll be back online tomorrow. Cheers for the brain workout!

Edited November 8, 2007 by Leonardo

[Moon Monkey]

How are you getting the sets a,b without spending as much time iterating as in the original idea because if you can build sets like that easily you don't need a loop at all.

[Tiggs]

Okay, Leo - thanks. Now it's in pseudocode, I'll take a good long look at it

Calc'ing the set of prime numbers is prolly going to be the next big issue - Will I need all of them up to the big number / 2, or will I be able to get away with all of them up to the square root of the big number?

Actually - either of them would be pretty evil

Ummmm. C's not going to be very even once you get past 2 in both sets of primes - am I reading that right?

Edited November 8, 2007 by Tiggs

[ships-cat]

In excess of 500 digits ? Ye gods Tiggs, what are you trying to accomplish ? This sounds like the sort of things geneticists deal with.

Darn it Tiggs... I KNOW this one... I've done it at school when I was a kitten. But I can't remember the method. It's something to do with...

• This is an arithmetic progression, whereby the difference between members of the progression is constant. (2, in this case).
• In such a progression, the SUM (where, in this case, you are staring from Tiggs) is the average of all the numbers, multiplied by how many numbers there are.

And this is where it breaks down... I can't remember the next bit(s). It's something to do with finding the average, and then there is an additional trick to find the "span"... e.g. how many numbers are involved, centred around the average.

I will try and Google it..... but darnit.... I'm SURE I was shown a simple solution to this. All I can remember (ish) is that it involved the idea that successive terms in the sequence had a fixed difference, and that averaging was involved.

Meow Purr.

[Tiggs]

Ah. That's not quite the same thing, ships-cat. You're probably thinking the sum of a series for consecutive numbers, which is:

To sum 1 to x:

(1+x)/2 * x (average of the first and last number * the number of terms)

if x = 10:

(1+10)/2)*10 = 55

For Odd numbers,

The sum of a series of x odd numbers starting at 1 is:

x^2

The sum of a series of odd numbers starting at x and ending at y is

(x+y) * (((y - x) + 2) /4)

i.e the sum of the series of odd numbers 3 to 13 (3+5+7+9+11+13 = 48)

3+13 * ((13 - 3) + 2) / 4) = 16 * ((10 + 2) / 4) = 16 * 3 = 48

the quick way of doing this (mentally) is to pair them off -

3 + 13 = 16

5 + 11 = 16

7 + 9 = 16

At least - I'd guess that would be the formula - I just made it up off the top of my head - the evil (((y-x)+2)/4) bit on the end is just a quickly improvised hack to work out the number of pairs. Looks pretty close to me.

As to what I'm working on - well - time to confess, I guess - that hugely large number is taken from the RSA2048 challenge - the most complex cryptographic challenge ever issued.

Suffice to say, if this problem is solvable - so is the challenge. Everything before and after this step is easy.

[ships-cat]

Tiggs - I see what you are saying, but no... this was specificly

"given a number "n", how can you derive a series of odd (or even) numbers that sum to 'n', and constrain it by the number of ..err.. numbers that sum to 'n'... or conversly.. derive a number 's' that constrains the number of terms in the sequence "

If only I'd been paying attention. Sadly, I drifted off into a fantasy whereby Kirsten took all her clothes off.

She never did (actually, she slapped me)... so that was a double-loss.

Bah.

Meow Purr.

[Tiggs]

Ehn. Same thing happened to me in my Geography class. I still have absolutely no idea what half of the world's capitals are, due to a girl called Tiffany. Completely understandable, old chap

[Moon Monkey]

Tiggs, if I had to code this (and I don't know what language you use, mine is matlab-ish) I would make use of the square root to limit the set, otherwise you will just be duplicating and use something like this;

x = your number;

% for the example of 168

a = x^0.5; .....................you will have to drop decimals and go to the nearsest even number below a, a =12.96

b = rem(a,2);.....................rem is a matlab function that gives the leftover when dividing the first term by the second, b = 0.96

c = a-b;............................. c = 12

d = [4:2:c];.......................don't need 2 so step from 4 in twos to the end d = [ 4 6 8 10 12]

e = x./d;...........................element wise division e = [42 28 21 16.8 14]

f = [d' e'];.........................I transpose because I prefer columns, just pair them up f = [ 4 42; 6 28; 8 21; 10 16.8; 12 14]

g = f/2;............................ g = [2 21;3 14;4 10.5;5 8.4;6 7];

h= rem(g,2);.....................find remainders by dividing by 2, h = [0 1; 1 0;0 0.5; 1 0.4; 0 1]

i =h(:,1) +h(:,2);.............. add up the remainders in each row, i =[1; 1; 0.5; 1.4; 1]

j = find( i ==1) ;................find the rows where there is exactly one number that is odd when divided by 2, j = [1;2;5]

k = f( j , : ); ..................return the factor pairs that satisfy the constraints of being even factors of x where one, when divided by 2, is odd k = [4 42; 6 28; 12 14]

Then you have the factor pairs [4,42], [6,28] and [12,14] and you can use the method Leonardo first came up with and decide if you want to use sequences that go into minus numbers, Could preallocate a matrix and do this in one line really, just wanted to be clear.

I have tried it on a few other small numbers like 96, [6 16], sequence [11,13,15,17,19,21] and 344, [4,86] sequence [83,85,87,89] and 1000, [4,250],[10,100],[20,50] (not going to write the sequences out) and it seems ok. At the moment I read your big number as inf so have to change the settings and might run it over the weekend if you haven't found a better way.

I am a bit worried because when I did Leonardos second example given as x = 3036; n = (6,22). it came up no sequence, which seems right as [6,506] and [22,138] are both odd when divided by 2 which goes against the constraints given.

Edited November 8, 2007 by Moon Monkey

[Tiggs]

Thanks, Moon Monkey

I definitely won't need sequences that go into negative numbers. I see the principle - my concern is that the amount of memory needed to store d (and everything derived from d) would be extremely large, even using the square root to trim the amount necessary, roughly

1587321910503912041744825086610630075793584634448097157957

2662775357997008074994840427864325956810113267140205619002

1464753419480472816840646168575222628934671405739213477439

5338704897910389731668340687362340203616648202669877269194

5335682413800738198579649362123303511284937304748414833909

5287142097834807843 entries

[camlax]

Thanks, Moon Monkey

I definitely won't need sequences that go into negative numbers. I see the principle - my concern is that the amount of memory needed to store d (and everything derived from d) would be extremely large, even using the square root to trim the amount necessary, roughly

Sorry I dont have time to read through it all so forgive me if this was posted, as I believe it was leo who was headed down this path. But here is some hints.

For a series of consecutive odd integers whose sum is some constant, c. We can say these things.

[n₁, n₂, n₃....n_x]

Call the total number of integers in the series, N

Call the sum of the series, C (your given)

C/N= median, m

(m+1)-N= n₁

(m-1)+N= n_x

Also note, for the first and last integers of the series,

n₁ + n_x = some number Z

C/Z = N/2

This all works under your conditions, assuming the integers that compose the series are positive and consecutive.

Maybe I'll put in a spoiler when I get more time!

~Cam

Edit: Someone needs to convince Saurman to add some maths notation so we can have like a monthly math challenge problem or something!

Edited November 9, 2007 by camlax

[InHuman]

Please stop, this thread makes me feel stupid.

I havn't taken a math class or done any math related work in 5 months.

[Leonardo]

Tiggs, if I had to code this (and I don't know what language you use, mine is matlab-ish) I would make use of the square root to limit the set, otherwise you will just be duplicating and use something like this;

x = your number;

% for the example of 168

a = x^0.5; .....................you will have to drop decimals and go to the nearsest even number below a, a =12.96

b = rem(a,2);.....................rem is a matlab function that gives the leftover when dividing the first term by the second, b = 0.96

c = a-b;............................. c = 12

d = [4:2:c];.......................don't need 2 so step from 4 in twos to the end d = [ 4 6 8 10 12]

e = x./d;...........................element wise division e = [42 28 21 16.8 14]

f = [d' e'];.........................I transpose because I prefer columns, just pair them up f = [ 4 42; 6 28; 8 21; 10 16.8; 12 14]

g = f/2;............................ g = [2 21;3 14;4 10.5;5 8.4;6 7];

h= rem(g,2);.....................find remainders by dividing by 2, h = [0 1; 1 0;0 0.5; 1 0.4; 0 1]

i =h(:,1) +h(:,2);.............. add up the remainders in each row, i =[1; 1; 0.5; 1.4; 1]

j = find( i ==1) ;................find the rows where there is exactly one number that is odd when divided by 2, j = [1;2;5]

k = f( j , : ); ..................return the factor pairs that satisfy the constraints of being even factors of x where one, when divided by 2, is odd k = [4 42; 6 28; 12 14]

Then you have the factor pairs [4,42], [6,28] and [12,14] and you can use the method Leonardo first came up with and decide if you want to use sequences that go into minus numbers, Could preallocate a matrix and do this in one line really, just wanted to be clear.

I have tried it on a few other small numbers like 96, [6 16], sequence [11,13,15,17,19,21] and 344, [4,86] sequence [83,85,87,89] and 1000, [4,250],[10,100],[20,50] (not going to write the sequences out) and it seems ok. At the moment I read your big number as inf so have to change the settings and might run it over the weekend if you haven't found a better way.

I am a bit worried because when I did Leonardos second example given as x = 3036; n = (6,22). it came up no sequence, which seems right as [6,506] and [22,138] are both odd when divided by 2 which goes against the constraints given.

MM,

I like the sound of your idea. I was concerned over the iterations/duplications and about how to get the set of primes into my second attempt.

I'm concerned over your result with x = 3036 though.

Assuming n = 6, (y = 506), {501, 503, 505, 507, 509, 511} = 3036

Assuming n = 22, (y = 138), {117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157, 159} = 3036

So my assumption about only one of the factors being odd was incorrect. I was basing this on only a few of the valid pairs I'd discovered. My apologies!!!

So there are situations where n/2 AND y/2 can be odd. I have not found a solution for any x (so far) where n/2 AND y/2 are even though, however I'm loath to rule that out.

*reminds self to always drink more coffee BEFORE posting*

So, basically, until n >= x^1/2, iterate for all even n's ; n >= 4 ; y = even integer

Edited November 9, 2007 by Leonardo

[Moon Monkey]

Tiggs, if I had to code this (and I don't know what language you use, mine is matlab-ish) I would make use of the square root to limit the set, otherwise you will just be duplicating and use something like this;

x = your number;

% for the example of 168

a = x^0.5; .....................you will have to drop decimals and go to the nearsest even number below a, a =12.96

b = rem(a,2);.....................rem is a matlab function that gives the leftover when dividing the first term by the second, b = 0.96

c = a-b;............................. c = 12

d = [4:2:c];.......................don't need 2 so step from 4 in twos to the end d = [ 4 6 8 10 12]

e = x./d;...........................element wise division e = [42 28 21 16.8 14]

f = [d' e'];.........................I transpose because I prefer columns, just pair them up f = [ 4 42; 6 28; 8 21; 10 16.8; 12 14]

g = f/2;............................ g = [2 21;3 14;4 10.5;5 8.4;6 7];

h= rem(g,2);.....................find remainders by dividing by 2, h = [0 1; 1 0;0 0.5; 1 0.4; 0 1]

i =h(:,1) +h(:,2);.............. add up the remainders in each row, i =[1; 1; 0.5; 1.4; 1]

j = find( i ==1) ;................find the rows where there is exactly one number that is odd when divided by 2, j = [1;2;5]

k =find(i==2);...................find the rows where both numbers are odd integers when divided by two, example for 168 this is empty, example for 3036 [2; 10; 22]

l = f( j , : ); ..................return the factor pairs that satisfy the constraints of being even factors of x where one, when divided by 2, is odd l = [4 42; 6 28; 12 14]

m=f(k,;.......................return the factor pairs that satisfy the constraints of being even factors of x where both are odd integers, when divided by 2,for 3036 m =[6 506;22 138; 46 66];

MM,

I like the sound of your idea. I was concerned over the iterations/duplications and about how to get the set of primes into my second attempt.

I'm concerned over your result with x = 3036 though.

Assuming n = 6, (y = 506), {501, 503, 505, 507, 509, 511} = 3036

Assuming n = 22, (y = 138), {117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157, 159} = 3036

So my assumption about only one of the factors being odd was incorrect. I was basing this on only a few of the valid pairs I'd discovered. My apologies!!!

So there are situations where n/2 AND y/2 can be odd. I have not found a solution for any x (so far) where n/2 AND y/2 are even though, however I'm loath to rule that out.

*reminds self to always drink more coffee BEFORE posting*

So, basically, until n >= x^1/2, iterate for all even n's ; n >= 4 ; y = even integer

Hi Leonardo, without proof it seems that when the even factors are divided by two they can both be odd as long as they are integers and BOTH odd integers(x=100,n=10,y=10 seems the best example), I have changed the code by adding a extra line checking the remainders for 2 odd integers. This was confirmed by running it with 3036 where it picked up n =6,y=506 [501....511], n=22, y=138 [117...159] and also n= 46,y =66 [21.....111]. I haven't checked for where this method falls down as I don't know any sensible test numbers that definately do or don't have an odd sequence somewhere off the top of my head. Tiggs do you have any test numbers ?

Just messed around with a few numbers, as we need an even mean to the series we need an even number of terms in the series to make Tiggs original even number. (simple multiplication) therefore it makes sense that it doesn't really matter if when halved they are both odd, both even or one is odd and one is even as long as they are whole numbers. I will check this in a bit.

I used x= 19837444 giving

n .............. y

22....... 901702

38...... 522038

122.... 162602

418.... 47458

778.... 25498

1342.. 14782

2318.. 8558

When halved they are all odd

Using the last sequnce we have n=2318, y=8558, sequence [6241.....10875]

When halved they can both be even as I thought, example is 208, n=4, y=52 sequence [49,51,53,55]

Tiggs, with such a big number and you wanting a sequence I am afraid you are always going to run into memory problems. If it was me I would get the basic code running and then start to trim it down where possible, preallocating, dropping things you don't need etc (but I don't need to tell you how to code). Ithink you can drop the tests for odd even etc just ensure that when halved they are whole numbers just drop ones that leave a remainder because 1/2 the terms in the sequence are on one side of the mean (y) and the other half are on the other side so fractions would ruin it.

For example 168

actual even factors are:

2 84

4 42

6 28

8 21

10 16.8

12 14

[2 84] Tiggs doesn't want

[4 42] when halved is [2 21], one odd one even and works

[6 28] when halved is [3 14], same

[8 21]........................[4 10.5], fraction screws the sequence

Edited November 9, 2007 by Moon Monkey

[Leonardo]

Hi Leonardo, without proof it seems that when the even factors are divided by two they can both be odd as long as they are integers and BOTH odd integers(x=100,n=10,y=10 seems the best example), I have changed the code by adding a extra line checking the remainders for 2 odd integers. This was confirmed by running it with 3036 where it picked up n =6,y=506 [501....511], n=22, y=138 [117...159] and also n= 46,y =66 [21.....111]. I haven't checked for where this method falls down as I don't know any sensible test numbers that definately do or don't have an odd sequence somewhere off the top of my head. Tiggs do you have any test numbers ?

Just messed around with a few numbers, as we need an even mean to the series we need an even number of terms in the series to make Tiggs original even number. (simple multiplication) therefore it makes sense that it doesn't really matter if when halved they are both odd as long as they are whole numbers, (they should both be able to be even when halved as well really but I haven't checked this out yet just means an extra find(i==0) I will check this in a bit).

I used x= 19837444 giving

n .............. y

22....... 901702

38...... 522038

122.... 162602

418.... 47458

778.... 25498

1342.. 14782

2318.. 8558

When halved they are all odd

Using the last sequnce we have n=2318, y=8558, sequence [6241.....10875]

When halved they can both be even as I thought, example is 208, n=4, y=52 sequence [49,51,53,55]

Sounds good!

I've been doing a little playing around and I found that when x = 199202 there are no factor pairs where both factors are even (the only factor pairs I could find were {2,99601} and {206,967}), thus there should be no solution for this number. You might want to check that, but it could be a test for your program.

[Moon Monkey]

Sounds good!

I've been doing a little playing around and I found that when x = 199202 there are no factor pairs where both factors are even (the only factor pairs I could find were {2,99601} and {206,967}), thus there should be no solution for this number. You might want to check that, but it could be a test for your program.

No it doesn't guve a sequence for 199202....we need some test numbers of Tiggs, he must have a few after a year

[Tiggs]

I'm at work at the mo, but I'll dig some out when I get home tonight.

If we can work out some method that doesn't involve massive recurssion or storage, then I'll put it into code this weekend.

Thanks for helping, btw - it's much appreciated

[Moon Monkey]

I'm at work at the mo, but I'll dig some out when I get home tonight.

If we can work out some method that doesn't involve massive recurssion or storage, then I'll put it into code this weekend.

Thanks for helping, btw - it's much appreciated

Tiggs can you provide the square root of your number, I am away at the mo on a laptop and can only represent numbers up to 1.7977e+308, I hope the square root of your number is less than this, and I wil trim my program and run it as well...see if it gets anywhere

Edited November 9, 2007 by Moon Monkey

[Tiggs]

Still at work, so I can't do any massive calcs, either, but it's (the number of entries I said earlier + 1) * 2

i.e:

15873219105039120417448250866106300757935846344480

97157957266277535799700807499484042786432595681011

32671402056190021464753419480472816840646168575222

62893467140573921347743953387048979103897316683406

87362340203616648202669877269194533568241380073819

85796493621233035112849373047484148339095287142097

834807844 * 2

If I've counted right, that's 308 digits. Gah.

Edited November 9, 2007 by Tiggs
I can't count. *shakes head *

[Moon Monkey]

Sorry Tiggs the number is too big for me, can you give me the sqaure root of the last number you gave me as I think the factors of the square root of the square root will be factors of the original (oviously will miss some but its better than nothing).

Edited November 9, 2007 by Moon Monkey

[Roj47]

Sorry guys, but I am unable to help on this....

Tiggs> Are we allowed to know the reasoning for doing this or how long you have been with it?

All the best

regards

[Tiggs]

In brief, it's the RSA2048 challenge. It's never been solved, and was retired from active duty this year, so, sadly, there are no cash prizes involved.

I've been working on it on and off for a couple of years. I realised a while ago, that it was as simple as solving this particular problem - I just couldn't solve it. If there's a solution to this - the rest is trivial math.

I'm attracted to solving impossible things, I guess

[questionmark]

In brief, it's the RSA2048 challenge. It's never been solved, and was retired from active duty this year, so, sadly, there are no cash prizes involved.

I've been working on it on and off for a couple of years. I realised a while ago, that it was as simple as solving this particular problem - I just couldn't solve it. If there's a solution to this - the rest is trivial math.

I'm attracted to solving impossible things, I guess

How 'bout trying some of those that get you a cash award.... maybe you could buy yourself a slightly used cray to put in your hobby room!

[Tiggs]

Ehn. Cray's are cheating.

Given enough firepower, you can brute force the answer. RSA 200 was broken using the equivalent of 55 years processing time for a single PC. The general estimate for RSA2048 is that we're still a couple of decades (real time) away from anyone having enough processing power to be able to brute force the answer.

If you only have (very) basic tools, then you have to think a lot smarter and come up with a completely new way of solving the problem, rather than just reverting to GNFS, for example. Necessity is the mother of invention, after all...