Least amount of terms for sum.

  • Thread starter martix
  • Start date
  • Tags
    Sum Terms
In summary, the conversation revolved around finding the optimal values for three buttons that would allow any number up to 100 to be made with the least amount of clicks. There was discussion about different approaches and solutions, including the possibility of using the Fibonacci numbers. Ultimately, it was concluded that a human interface may not necessarily follow the mathematically most efficient solution.
  • #1
martix
160
0
I was trying to design some GUI for a tool I'm making and I noticed there's a hidden math problem somewhere in there. Not being one to let the opportunity slide, I decided it's worth exploring.

Basically there's 3 buttons that add to a variable.
What are the best values to put on those buttons so any number up to 100 can be made with the least amount of clicks.

Only I don't know how to approach this systematically. Best I got is intuition at this point. Or the brute-force approach.
 
Mathematics news on Phys.org
  • #2
I don't think there is an answer to the question as posed.

You want every number to be possible, up to 100, with the least number of clicks, but no solution will have the fewest clicks for every number.

So can it be clarified? Where do you want the fewest clicks to occur? For a random number maybe? (I think that can be solved)

If we go with the random number idea, I think it can be looked at as follows:

#1.) One button must be 1
#2.) If the two other buttons are dubbed X and Y, the optimal value for X and Y are the values such that the set {s | s is expressible as nX + k or lY + m} is equal to [1,100] for the minimum values of n and l (k and m are in the interval [0,9]…

But I am just thinking out loud, this may be wrong but it is what my intuition says. Kudos for the cool question!
 
Last edited:
  • #3
That much is obvious, it will vary. The question was, what's the set of numbers which will produce the least average clicks over 1-100.
 
  • #4
1MileCrash said:
... the set {s | s is expressible as nX + k or lY + m} ...
Shouldn't that be k + nX + mY?
That is, k clicks of '1' plus n clicks of X plus m clicks of Y, where the sum k+n+m is minimized.

On an unrelated note, I always find it interesting that people so quickly gravitate toward clicking the mouse when pushing a key seems easier.
 
  • #5
http://math.stackexchange.com/questions/645317/3-incrementing-buttons-optimal-value

I hope the OP doesn't mind, but I posted this question on Math.SE because I was so interested in seeing a nice solution.

Someone wrote a program and included a chart, and explained the results.

For our specific case [1,100], his finding was (1,12,19), which gives about an average of 5 clicks.

There was also a remark about a connection to the Fibonacci numbers (woah!) in that the two remaining numbers were likely to be adjacent Fibonacci numbers, and that he would "not be surprised" if the ratio of the two remaining buttons approached phi as we considered bigger and bigger [1,*] intervals. That text has been removed, I'm not sure if it was retracted for being wrong, or just removed for some other reason, but if that's true, this is an even cooler problem!


KenJackson said:
Shouldn't that be k + nX + mY?
That is, k clicks of '1' plus n clicks of X plus m clicks of Y, where the sum k+n+m is minimized.

On an unrelated note, I always find it interesting that people so quickly gravitate toward clicking the mouse when pushing a key seems easier.

Yes, you are right, both of the other numbers can be pressed for a value, not sure what I was thinking.
 
  • #7
1MileCrash said:
http://math.stackexchange.com/questions/645317/3-incrementing-buttons-optimal-value

I hope the OP doesn't mind, but I posted this question on Math.SE because I was so interested in seeing a nice solution.

Someone wrote a program and included a chart, and explained the results.

For our specific case [1,100], his finding was (1,12,19), which gives about an average of 5 clicks.
I don't agree with that finding. Assuming we're limited to non negatives*, my first hunch on this was [itex](1,\, 100^{1/3},\, 100^{2/3})[/itex], which rounds to (1,5,22). Testing this solution it gives an average of 5.26 clicks and a worst case of 10 clicks. The (1,12,19) solution fared worse on both counts.

Testing with a program to run all combinations it turns out that (1,5,22) is indeed optimal. The solution is not however unique, there were several combination which gave an equal average value and many that gave an equal worst case count. There were however only two non negative solutions which were optimal for both the average and the worst case counts. These are (1,5,22) as already stated, and also (1,5,23) which was equivalent.

*BTW. Including "1" as one of the increments is only necessary if you disallow negatives. If you allow negative numbers then including "1" is no longer mandatory, for example (-2,3,10) could clearly construct all possible numbers 1..100.

EDIT: And I could be wrong. :blushing:
I just noticed that my program exhausts the multiples of the larger increments before moving on to the smaller ones. This may well be suboptimal for cases like (1,12,19), so I have probably unfairly dismissed that solution.
 
Last edited:
  • #8
That's actually rather interesting. :)
I guess an exhaustive search is the go-to approach.

I knew this reminded me of something!

The whole discussion spurred my memory:
I believe we are looking at a variation of the coin-counting problem.

uart, there's two approaches. One is the greedy algorithm which you have used, but for certain cases where the terms are not proper multiples of each other, the algorithm is insufficient.
The SE solution with the weird terms needs to be covered by the dynamic programming algorithm.

HOWEVER!

On further consideration - given that the original problem of this going into a UI - something a human would use, the go-to approach of a person will probably be the greedy one. I mean I can't imagine a person trying to enter stuff like that is going to consider the mathematical ramifications of how to most efficiently go about doing so.
Therefore a solution that is mathematically the most efficient might not turn out to be as good an idea for a human interface. :)
 
Last edited:
  • #9
Well, if we're accounting for how humans will decide to use the buttons, it's kind of hard to answer the question.
 
  • #10
No, we aren't, I don't mind the discussion, it was just a very sudden realization. :P
 
  • #11
martix said:
HOWEVER!

On further consideration - given that the original problem of this going into a UI - something a human would use, the go-to approach of a person will probably be the greedy one. I mean I can't imagine a person trying to enter stuff like that is going to consider the mathematical ramifications of how to most efficiently go about doing so.
Therefore a solution that is mathematically the most efficient might not turn out to be as good an idea for a human interface. :)

Exactly. This is something I was going to suggest. As far as human interaction is concerned, either one of (1,5,20) or (1,5,25) are close enough to optimal to make one of these the best choice in my opinion. And yes you are correct, this is precisely the coin problem.
 

1. What does "least amount of terms for sum" mean?

The phrase "least amount of terms for sum" refers to finding the minimum number of terms needed to add together to reach a given sum.

2. How is the least amount of terms for sum calculated?

The least amount of terms for sum is calculated by using mathematical methods such as factoring, prime factorization, or theorems such as the Goldbach Conjecture.

3. Can the least amount of terms for sum be negative?

No, the least amount of terms for sum cannot be negative as it represents the smallest number of terms needed to reach a positive sum.

4. Is there a formula for finding the least amount of terms for sum?

There is no universal formula for finding the least amount of terms for sum, as it depends on the specific sum and the methods used to calculate it.

5. What are some applications of finding the least amount of terms for sum?

Finding the least amount of terms for sum can be useful in various areas such as cryptography, optimizing algorithms, and solving mathematical puzzles.

Similar threads

  • Topology and Analysis
Replies
3
Views
1K
Replies
6
Views
942
  • Precalculus Mathematics Homework Help
Replies
1
Views
735
Replies
5
Views
1K
  • High Energy, Nuclear, Particle Physics
Replies
2
Views
1K
  • Beyond the Standard Models
Replies
1
Views
2K
  • Sci-Fi Writing and World Building
3
Replies
96
Views
5K
  • Art, Music, History, and Linguistics
Replies
1
Views
1K
Replies
1
Views
525
Replies
7
Views
1K
Back
Top