24 for c=6 (should be optimal per wpolly's link)
[CODE]0
63
455
729
876
946
1258
1393
1436
1622
1701
1803
2292
2394
2473
2659
2702
2837
3149
3219
3366
3640
4032
4095
[/CODE]

[QUOTE=axn;201940]for c=5, greedy algorithm yielded 25
[CODE]0
31
227
374
440
461
620
693
730
1145
1198
1236
1795
1820
2016
2047
2341
2378
2451
2603
2641
2694
3122
3143
3209[/CODE]

EDIT:- 26
[code]0
31
231
377
698
803
846
981
1138
1244
1427
1453
1589
1739
1816
2016
2156
2225
2358
2498
2643
2953
3115
3397
3718
4095
[/code][/QUOTE]An exhaustive search via a backtracking algorithm has turned up many examples with 26 members. As noted by akruppa, one would expect there to be many such sets if at least one exists. No examples with 27 have yet been found in a few minutes of computation.

My program has been written in a hurry and can doubtless be improved. However, the size of the search space is so large that it can probably not be searched exhaustively. I may continue to optimize my search on the algorithmic level. There is no great point in fiddling with compiler options, and the like as that will give at most a constant speed-up.

It's gratifying to see that so much interest has been shown in this problem.


Paul

[QUOTE=xilman;201950]An exhaustive search via a backtracking algorithm has turned up many examples with 26 members. As noted by akruppa, one would expect there to be many such sets if at least one exists. No examples with 27 have yet been found in a few minutes of computation.[/QUOTE]

Unless I misunderstood the link -- and I may have -- optimal should be 32 for c = 5 (and 144 and 24 for 4 and 6, respectively). That's significantly larger.

[QUOTE=CRGreathouse;201951]Unless I misunderstood the link -- and I may have -- optimal should be 32 for c = 5 (and 144 and 24 for 4 and 6, respectively). That's significantly larger.[/QUOTE]

Yes, that's correct. Seeing the references I think some of the results found by nonlinear programming. Here is my guess for this: if u and v are bits then
[code]
u xor v=u+v-2*u*v
[/code]
This would give an NLP problem for 24*12=288 binary variables for c=6 (12 bits for each number) to find the optimal solution. Writing down the system is trivial, maybe solvable. (Obviously you can reduce the number of variables by the above tricks.)

See also [url]http://www.research.att.com/~njas/codes/And/[/url]

Paul, are you still interested in better results? I've found 1 set of size 27 and 4 of size 28 for c=5. Are you interested in results for c=4 (or 3)? Also, I think I wrote my program correctly, but could someone verify my results so I can be sure.

Size=27, c=5
[CODE]
0x000,0x01f,0x0e7,0x1b1,0x1cc,
0x26a,0x2d9,0x336,0x474,0x52b,
0x5d2,0x683,0x6ac,0x718,0x745,
0x7ff,0x8ba,0x943,0x97d,0xa25,
0xad6,0xb8f,0xbe0,0xc4e,0xc95,
0xce9,0xda6
[/CODE]

Size=28, c=5
[CODE]
0x000,0x01f,0x0e7,0x1b1,0x1cc,
0x26a,0x2d9,0x336,0x474,0x52b,
0x5d2,0x683,0x6ac,0x718,0x745,
0x7ff,0x8ba,0x943,0x97d,0xa25,
0xad6,0xb8f,0xbe0,0xc4e,0xc95,
0xce9,0xda6,0xe73

0x000,0x01f,0x0e7,0x1b1,0x1cc,
0x26a,0x2d9,0x336,0x474,0x52b,
0x5d2,0x683,0x6ac,0x718,0x745,
0x7ff,0x978,0xa94,0xb2d,0xb53,
0xb8a,0xc49,0xcba,0xd06,0xd9d,
0xe31,0xe5e,0xfe0

0x000,0x01f,0x0e7,0x1b2,0x1cc,
0x269,0x2da,0x335,0x474,0x52b,
0x5d1,0x683,0x6ac,0x718,0x746,
0x7ff,0x8b9,0x943,0x97e,0xa26,
0xad5,0xb8f,0xbe0,0xc4d,0xc96,
0xcea,0xda5,0xe73

0x000,0x01f,0x0e7,0x1b2,0x1cc,
0x269,0x2da,0x335,0x474,0x52b,
0x5d1,0x683,0x6ac,0x718,0x746,
0x7ff,0x978,0xa94,0xb2e,0xb53,
0xb89,0xc4a,0xcb9,0xd05,0xd9e,
0xe32,0xe5d,0xfe0

[/CODE]

[quote=WraithX;208026]Paul, are you still interested in better results? I've found 1 set of size 27 and 4 of size 28 for c=5. Are you interested in results for c=4 (or 3)? Also, I think I wrote my program correctly, but could someone verify my results so I can be sure.

Size=27, c=5
[code]
0x000,0x01f,0x0e7,0x1b1,0x1cc,
0x26a,0x2d9,0x336,0x474,0x52b,
0x5d2,0x683,0x6ac,0x718,0x745,
0x7ff,0x8ba,0x943,0x97d,0xa25,
0xad6,0xb8f,0xbe0,0xc4e,0xc95,
0xce9,0xda6
[/code]Size=28, c=5
[code]
0x000,0x01f,0x0e7,0x1b1,0x1cc,
0x26a,0x2d9,0x336,0x474,0x52b,
0x5d2,0x683,0x6ac,0x718,0x745,
0x7ff,0x8ba,0x943,0x97d,0xa25,
0xad6,0xb8f,0xbe0,0xc4e,0xc95,
0xce9,0xda6,0xe73

0x000,0x01f,0x0e7,0x1b1,0x1cc,
0x26a,0x2d9,0x336,0x474,0x52b,
0x5d2,0x683,0x6ac,0x718,0x745,
0x7ff,0x978,0xa94,0xb2d,0xb53,
0xb8a,0xc49,0xcba,0xd06,0xd9d,
0xe31,0xe5e,0xfe0

0x000,0x01f,0x0e7,0x1b2,0x1cc,
0x269,0x2da,0x335,0x474,0x52b,
0x5d1,0x683,0x6ac,0x718,0x746,
0x7ff,0x8b9,0x943,0x97e,0xa26,
0xad5,0xb8f,0xbe0,0xc4d,0xc96,
0xcea,0xda5,0xe73

0x000,0x01f,0x0e7,0x1b2,0x1cc,
0x269,0x2da,0x335,0x474,0x52b,
0x5d1,0x683,0x6ac,0x718,0x746,
0x7ff,0x978,0xa94,0xb2e,0xb53,
0xb89,0xc4a,0xcb9,0xd05,0xd9e,
0xe32,0xe5d,0xfe0

[/code][/quote]Your results are impressive but, sadly, I no longer need them for my work.

Thanks all the same.


Paul

Bummer, because I found 2 sets of size 139 for c=4 over night. I'll keep running them for a little while to see if I can come up with the maximum sized sets for c=4 (144) and c=5 (32). If I find anything better, I'll post them here.

Here are the two sets of size 139 for c=4:
[CODE]
0x000,0x00f,0x03a,0x055,0x066,0x069,0x096,0x0a3,0x0bd,0x0cc,
0x0db,0x0f0,0x113,0x11c,0x125,0x14a,0x17f,0x189,0x1ae,0x1c7,
0x219,0x22c,0x237,0x243,0x25e,0x285,0x28a,0x2ef,0x306,0x32b,
0x330,0x34d,0x39f,0x3c0,0x3f3,0x3fc,0x431,0x452,0x47c,0x498,
0x4a4,0x4c1,0x4ea,0x4f7,0x522,0x544,0x559,0x595,0x5bb,0x5de,
0x5ed,0x614,0x648,0x665,0x67b,0x693,0x6a9,0x6be,0x6c6,0x6dd,
0x701,0x71a,0x73d,0x757,0x76e,0x78c,0x7a7,0x7cb,0x834,0x858,
0x873,0x891,0x8a8,0x8c2,0x8e5,0x8fe,0x939,0x941,0x956,0x96c,
0x984,0x99a,0x9b7,0x9dd,0x9eb,0xa12,0xa21,0xa44,0xa6a,0xa7d,
0xa9c,0xaa6,0xabb,0xac9,0xad7,0xb08,0xb15,0xb3e,0xb5b,0xb67,
0xb83,0xbad,0xbce,0xc03,0xc0c,0xc3f,0xc60,0xcb2,0xccf,0xcd4,
0xcf9,0xd10,0xd75,0xd7a,0xda1,0xdbc,0xdc8,0xdd3,0xde6,0xe38,
0xe51,0xe76,0xe80,0xeb5,0xeda,0xee3,0xeec,0xf0f,0xf24,0xf33,
0xf42,0xf5c,0xf69,0xf96,0xf99,0xfaa,0xfc5,0xff0,0xfff

0x000,0x00f,0x03a,0x055,0x066,0x069,0x096,0x0a3,0x0bd,0x0cc,
0x0db,0x113,0x11c,0x125,0x14a,0x170,0x17f,0x189,0x1ae,0x1c7,
0x219,0x22c,0x237,0x243,0x25e,0x285,0x28a,0x2b0,0x2ef,0x306,
0x32b,0x34d,0x39f,0x3c0,0x3f3,0x3fc,0x431,0x452,0x47c,0x498,
0x4a4,0x4c1,0x4ea,0x4f7,0x522,0x544,0x559,0x595,0x5bb,0x5de,
0x5ed,0x614,0x648,0x665,0x67b,0x693,0x6a9,0x6be,0x6c6,0x6dd,
0x701,0x71a,0x73d,0x757,0x76e,0x78c,0x7a7,0x7cb,0x834,0x858,
0x873,0x891,0x8a8,0x8c2,0x8e5,0x8fe,0x939,0x941,0x956,0x96c,
0x984,0x99a,0x9b7,0x9dd,0x9eb,0xa12,0xa21,0xa44,0xa6a,0xa7d,
0xa9c,0xaa6,0xabb,0xac9,0xad7,0xb08,0xb15,0xb3e,0xb5b,0xb67,
0xb83,0xbad,0xbce,0xc03,0xc0c,0xc3f,0xc60,0xcb2,0xccf,0xcd4,
0xcf9,0xd10,0xd75,0xd7a,0xda1,0xdbc,0xdc8,0xdd3,0xde6,0xe38,
0xe51,0xe76,0xe80,0xeb5,0xeda,0xee3,0xeec,0xf0f,0xf24,0xf33,
0xf42,0xf5c,0xf69,0xf96,0xf99,0xfaa,0xfc5,0xff0,0xfff
[/CODE]