Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2012-04-30 10:57:43

mpatt
Member
Registered: 2012-04-30
Posts: 5

working out which addends from a list will add up to a given value.

I have a real world problem, and I'm hoping there will be an elegant mathematical solution to this.

I have an unordered  list of ~100 values, some of which may appear more than once in the list e.g 10,15,15,12,13,10,15,29,30,.....
and I want to find the smallest number of those values, in the order given, which will add up to a particular sum, e.g. 666

Can it be done?

Thanks in advance for any help.
M:

Offline

#2 2012-04-30 11:00:10

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 83,138

Re: working out which addends from a list will add up to a given value.

Hi;

May I see the list or is this any list?


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#3 2012-04-30 15:02:28

mathgogocart
Member
Registered: 2012-04-29
Posts: 1,426

Re: working out which addends from a list will add up to a given value.

i do need too see the list      to total things


Hey.

Offline

#4 2012-04-30 21:51:44

mpatt
Member
Registered: 2012-04-30
Posts: 5

Re: working out which addends from a list will add up to a given value.

The list will change depending on when I run it, so I was hoping for an 'any case' method.

Last edited by mpatt (2012-04-30 21:52:08)

Offline

#5 2012-04-30 21:54:46

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 83,138

Re: working out which addends from a list will add up to a given value.

You must keep the ordering given too?


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#6 2012-05-01 07:03:20

mpatt
Member
Registered: 2012-04-30
Posts: 5

Re: working out which addends from a list will add up to a given value.

bobbym wrote:

You must keep the ordering given too?

yes.

For the record here's a sample list, the numbers will either be whole numbers or halves there will be no other fractions, oh and there may be occasions where it's not possible to find a set of values that will add up to the given sum:

30
20
22.5
15.0
25.0
17.5
17.5
20.0
15.0
22.5
20
20.0
37.5
32.5
12.5
22.5
20.0
20
30
25
12
15.0
22.5
17.5
15.0
17.5
20
22.5
22.5
20
21.5
25
27.5
15.0
22.5
12.5
15.0
30.0
15
30.0
27.0
20
15
12.5
17.5
33.0
22.5
17.5
15.0
20
20
17.5
15.0
22.5
17.5
17.5
17.5
10
27.0
15.0
15.0
22.5
15.0
15.0
12.5
17.5
15.0
15
15.0
25.0
24.0
25.0
15.0
22.5
20
24.0
27.0
22.5
15.0
15.0
15.0
35
17.5
27.0
20.0
15.0
15.0
30
25.0
12.5
21.0
30
20
18.0
27.5
15.0
24.0
10
17.5
11.5

Offline

#7 2012-05-01 07:07:47

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 83,138

Re: working out which addends from a list will add up to a given value.

Hi mpatt;

Since the order must remain as given, I think that there is no mathematical way to solve the problem. There is a computer way that can do it.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#8 2012-05-01 07:10:05

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 14,885

Re: working out which addends from a list will add up to a given value.

Hi mpatt

First,you are contradicting yourself. You said in your first post you have  unordered list. Please,be clear when you ask a question.

Second,I think there isn't a mathematical formula for this. The next best thing you can do is solve it by a computer.

Last edited by anonimnystefy (2012-05-01 08:40:07)


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#9 2012-05-01 08:38:10

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 83,138

Re: working out which addends from a list will add up to a given value.

Hi mpatt;

Do you program?


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#10 2012-05-01 11:03:24

mpatt
Member
Registered: 2012-04-30
Posts: 5

Re: working out which addends from a list will add up to a given value.

bobbym wrote:

Do you program?

A little, if there's an algorithm which will do it I'll have a go, thanks.

Offline

#11 2012-05-01 11:06:03

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 83,138

Re: working out which addends from a list will add up to a given value.

The simplest approach is to try all singles and then all doubles and then all triples etc. What do you program in?


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#12 2012-05-01 11:11:47

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 14,885

Re: working out which addends from a list will add up to a given value.

Hi bobbym

That would take a lot because they needn't be consecutive.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#13 2012-05-01 11:16:30

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 83,138

Re: working out which addends from a list will add up to a given value.

and I want to find the smallest number of those values, in the order given,

I assume they are consecutive. He does not say they are not.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#14 2012-05-01 11:20:55

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 14,885

Re: working out which addends from a list will add up to a given value.

Not stating it doesn't give you the right to assume that.

The OP should've been clearer on the problem.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#15 2012-05-01 19:10:40

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 83,138

Re: working out which addends from a list will add up to a given value.

The algorithm can be adjusted to handle that using recursion. I could write it in M as soon as he stipulates the rules. Trouble is he will need to a better than beginner to program it.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#16 2012-05-02 07:51:40

mpatt
Member
Registered: 2012-04-30
Posts: 5

Re: working out which addends from a list will add up to a given value.

Hi Chaps,
  When I said 'unordered' originally I meant unordered in the sense of unordered - not arranged in order hierarchically. Perhaps I should have said "unsorted"?
I'm not sure what you mean by consecutive? If by that you mean that the numbers to add up to 666 must be consecutive in the list then that is not the case, it could be that the solution is the 1st, 2nd, 5th, 8th.... nth value.

I can program in perl and have considered how I could write this using recursive loops in perl but it seems to me that for a set of 100 values I could end up with a huge number of iterations which would take ages, which is why I was hoping there might be a mathematical solution.

Offline

#17 2012-05-02 07:54:03

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 83,138

Re: working out which addends from a list will add up to a given value.

Recursion is the way to go.  You said they are not all integers too?


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#18 2012-05-02 09:39:03

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 83,138

Re: working out which addends from a list will add up to a given value.

Let's take the list you have in post #6. Let's do some mathematics on it. Whamo! Done!

You can make the hideous 666 from those numbers in 490208257 ways. Using generating functions will tell you how many there are. To get one answer you will need to do a PSLQ.

Both methods are computer dependent.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#19 2012-05-02 09:41:01

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 14,885

Re: working out which addends from a list will add up to a given value.

Hi bobbym

Do you think the GF method would work?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#20 2012-05-02 09:42:11

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 83,138

Re: working out which addends from a list will add up to a given value.

That is what I used!


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#21 2012-05-02 09:45:44

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 14,885

Re: working out which addends from a list will add up to a given value.

Cool! So there is a mathematical way to do it without the use of procesural programming!


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#22 2012-05-02 09:47:37

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 83,138

Re: working out which addends from a list will add up to a given value.

Yes. But it will require a computer to set it up and to solve it. But it will be fast.

I came full circle, the story is complete.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#23 2012-05-02 09:50:50

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 14,885

Re: working out which addends from a list will add up to a given value.

So we will need more than just computer maths? We will have to use loops?!?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#24 2012-05-02 09:52:52

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 83,138

Re: working out which addends from a list will add up to a given value.

It could be done with loops and procedural code but it will be clumsy and slow. C++ provides a better solution. But the functional paradigm is the real answer.


In mathematics, you don't understand things. You just get used to them.
I have the result, but I do not yet know how to get it.
All physicists, and a good many quite respectable mathematicians are contemptuous about proof.

Offline

#25 2012-05-02 09:53:40

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 14,885

Re: working out which addends from a list will add up to a given value.

Functional paradigm?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

Board footer

Powered by FluxBB