Ken Jennings

Message Boards

Number Lists

The place to talk. "On topic"? "Off topic"? We make no such petty distinctions here.

Number Lists

Postby Bill » Mon Jul 11, 2016 8:38 pm

Let's say I wanted to make a list of numbers so that, given only the sum of a selected subset of that list, I could identify the exact items that were selected for that subset. The most efficient way to do this (lower numbers being "cheaper") would be to use powers of 2. Thus, given a sum of 11, I would know for certain that the list items that made it up were [1, 2, 8]. There's no other way to get that sum, and any sum of items from that list would similarly have a unique subset that returns it.

Now, let's say that when I make the list, I know that exactly two list items will make up each of the sums I'm given. Now, I can be more efficient than my first list of powers of 2 by instead choosing the Fibonacci sequence starting with 1, 2. Now, if I'm given a sum like 23, I know for certain the list items that made it up were [2, 21].

Here's my situation. I want to make up two lists such that, given the sum of exactly two items, one from each list, I can identify for certain the two list items that generated the sum.

For example, if List A were [1, 2, 9, 10] and List B were [2, 4, 6, 8], each of the 16 possible sums would yield a different result. So if I saw the sum was 8, I would know that the ordered pair was [2, 6].

My question is this: Is there a systematic way to generate such a pair of lists so that they can be extended reliably and efficiently? For example, if I wanted twenty items on each list, is there a sequence (like the Fibonacci or powers of 2 examples above) that I could use?

This is a real question. I don't know the answer. As I grapple with it, I thought it might be a fun exercise for some of the math folks in the group.
Bill
 
Posts: 1930
Joined: Sat Jun 16, 2007 2:32 am
Location: New York City

Re: Number Lists

Postby skullturfq » Tue Jul 12, 2016 10:49 am

I'm a mathematician by profession, and this sounds like an interesting problem to me. I will look at it in more detail when I have a little more time.

Feel free to remind me later if necessary.
skullturfq
 
Posts: 3969
Joined: Tue Aug 07, 2007 5:05 pm
Location: Miami

Re: Number Lists

Postby Bill » Tue Jul 12, 2016 12:37 pm

So far, the best I've been able to do is this:

List A = [1, 2, 3, ..., 20]

List B = [20, 40, 60, ... 400]

This puts the maximum sum at 420, for 400 combinations, which is pretty good. (All numbers need to be positive integers, otherwise List B could have started at 0. List A also could have started at 0, but not both.)

The thing is that this assumes I want twenty numbers on each list. But I'm wondering if there is an efficient way to create a two-list pattern that can be extended to arbitrarily large lengths and remain efficient.

Such a pattern would also be efficient at smaller lengths. Mine isn't. If A = [1, 2, 3, 4] and B = [20, 40, 60, 80], the maximum sum is 84 for 16 combinations, which is a terrible ratio.

This "Base 20" solution will serve my original purpose though, so now it's just an interesting thought experiment.
Bill
 
Posts: 1930
Joined: Sat Jun 16, 2007 2:32 am
Location: New York City

Re: Number Lists

Postby Bill » Wed Jul 13, 2016 6:24 pm

The more I play with this, the more I think that there is no good pattern, that the optimal solution is very dependent on list length.

I was trying to find good lists of length 6, and I found A = [1, 2, 7, 8, 23, 24] and B = [1, 3, 5, 13, 15, 33], which gives me a maximum sum of 57. I also found A = [1, 2, 5, 6, 26, 30] and B = [1, 3, 9, 11, 18, 20], which cuts the maximum sum down to 50.

But if I know that my lists are going to be exactly length 6 and I don't need them to be efficient at other lengths, I can just make A = [1, 2, 3, 4, 5, 6] and B = [1, 7, 13, 19, 25, 31], for a maximum sum of 37, which is considerably better. Actually, it's perfectly optimal, given the positive integer constraint.

If anyone has additional thoughts, I'd love to hear them, but I think I have my answer.
Bill
 
Posts: 1930
Joined: Sat Jun 16, 2007 2:32 am
Location: New York City

Re: Number Lists

Postby skullturfq » Thu Jul 14, 2016 10:06 am

As you point out, if all you want is a pair of lists that work for a particular length, such as length 6, and you don't care about extending your list to other lengths, then you've found the best possible example, so in a way, there's not much more to be said.

But as you also mentioned, it's interesting to ponder whether there's one specific infinite sequence, such as the powers of 2, or the Fibonacci numbers, that would allow you to generate reasonably efficient lists of various lengths.

There is a sequence called the "Mian-Chowla" sequence, which grows more slowly than the powers of 2 or the Fibonacci numbers, that may be relevant here. (Actually, the first few members of the Mian-Chowla sequence happen to be powers of 2, but that stops after the first few.) Here are the first 15 elements of each of those sequences:

Powers of 2:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, ...

Fibonacci numbers:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

Mian-Chowla sequence:
1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, ...

The Mian-Chowla sequence has the property that all sums of pairs of elements are distinct. So an addition table like this will have no repeats, even if you extend it forever:

Code: Select all
    1  2  4  8 13 21 31 45
   -----------------------
 1| 2  3  5  9 14 22 32 46
 2|    4  6 10 15 23 33 47
 4|       8 12 17 25 35 49
 8|         16 21 29 39 53
13|            26 34 44 58
21|               42 52 66
31|                  62 76
45|                     90


This means that if you split the list [1,2,4,8,13,21,31,45] into two lists in any manner, all sums will be distinct. For example, your two lists could be [1,2,4,8] and [13,21,31,45]:

Code: Select all
    1  2  4  8
   -----------
13|14 15 17 21
21|22 23 25 29
31|32 33 35 39
45|46 47 49 53


or your two lists could be [1,4,13,31] and [2,8,21,45]:

Code: Select all
    1  4 13 31
   -----------
 2| 3  6 15 33
 8| 9 12 21 39
21|22 25 34 52
45|46 49 58 76


However, even though the Mian-Chowla sequence doesn't increase as quickly as the powers of 2 or the Fibonacci numbers, it nevertheless might not be as easy to compute its values as quickly.

Also, the Mian-Chowla sequence gives you more than you need for your problem. In the above examples, it's also true that 1+4 has a different value from all other sums of pairs, but that's not relevant or needed in your problem because 1 and 4 are in the same list.
skullturfq
 
Posts: 3969
Joined: Tue Aug 07, 2007 5:05 pm
Location: Miami

Re: Number Lists

Postby Bill » Fri Jul 15, 2016 5:20 pm

Oh, that's cool. I'd never heard of the Mian-Chowla sequence.

skullturfq wrote:Also, the Mian-Chowla sequence gives you more than you need for your problem. In the above examples, it's also true that 1+4 has a different value from all other sums of pairs, but that's not relevant or needed in your problem because 1 and 4 are in the same list.


This leads me to believe that simply dividing up the Mian-Chowla sequence would not be the most effective technique. It's the right idea, though. What we need is a new sequence, or pair of sequences actually, along the same lines. We can call it the Beavispants-Teacher duality.

List A = [1, 2, 7, 8, 23, 24, 56...]

List B = [1, 3, 5, 13, 15, 32, 44...]

It's not pretty, but it does increase more slowly than a divided Mian-Chowla. Also, there's no straightforward formula to generate it. But it does satisfy our conditions.

Somebody call the OEIS, immediately!
Bill
 
Posts: 1930
Joined: Sat Jun 16, 2007 2:32 am
Location: New York City


Return to Main Forum

Who is online

Users browsing this forum: No registered users and 3 guests

cron