Finding the smallest sets

Consider three sets A, B and C each containing n integers. From this we can make the set

S_n = {a * b + c | a in A, b in B, c in C}.


Given an n, there are one or more minimal sized S_n which depend on which sets A,B and C have been chosen.

The sets can contain any n distinct integers (positive, zero or negative). There is no need for them to be consecutive integers or for the sets to be equal to each other for example. A = {-1, 0, 5, 10, 27}, B = {2, 5, 6, 10, 14} and C = {-23, 2, 100, 1000,10000} is acceptable (although not a good idea) for example.

The task is to write code to find the smallest set S_n it can for each n from 1 to 20.

For each n from 1 to 20 your code should output the chosen A, B and C along with the resulting size of S_n

Score

Your score will be the sum of the sizes of the S_n you create. That is it will be a sum of twenty numbers.

The lower the score the better.

Examples

If A = B = C = {1, 2, 3, 4} then S_4 = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} which is of size 19.

This is however in no way optimal. For example, A = B = C = {-1, 0, 1, 2} gives S_4 = {0, 1, 2, 3, 4, 5, 6, -1, -3, -2} which is of size 10.

Timings

As I will need to run your code to verify the output, please make sure it takes no more than 30 minutes and 4GB of RAM to run on a normal desktop.

Notes

Your code must actually compute the output. You are not allowed to hardcode precomputed answers into your code.

• Could someone find the sets using more time and computing power, then write code to output them hardcoded?
– xnor
Jun 20, 2017 at 6:38
• @xnor That looks like cheating to me. Please don't do that. Having said that, I am not sure what a computationally expensive approach would be that would still terminate. There are a lot of integers!
– user7467
Jun 20, 2017 at 6:38

Rust, score 1412 1411

src/main.rs

extern crate gmp;

use std::collections::BinaryHeap;
use std::collections::hash_map::{HashMap, Entry};
use gmp::mpz::Mpz;

fn visit(
queue: &mut BinaryHeap<(i32, i32, i32, Mpz, Mpz)>,
visited: &mut HashMap<(i32, Mpz), i32>,
score: i32,
h: i32,
k: i32,
d: Mpz,
c: Mpz,
) {
match visited.entry((k, d.clone())) {
Entry::Occupied(mut e) => {
if *e.get() < score {
e.insert(score);
queue.push((score, h, k, d, c));
}
}
Entry::Vacant(e) => {
e.insert(score);
queue.push((score, h, k, d, c));
}
}
}

fn main() {
let mut total = 0;
for n in 1..21 {
let a_range = n / 2 - n + 1..n / 2 + 1;
let min_ab = a_range.start * (a_range.end - 1);
let mut ab = Mpz::zero();
for a in a_range.clone() {
for b in a_range.clone() {
ab.setbit((a * b - min_ab) as usize);
}
}

let heuristic = |k: i32, d: &Mpz| if k == n {
0
} else {
k + 1 - n -
(0..d.bit_length())
.map(|i| (&ab & !(d >> i)).popcount())
.min()
.unwrap() as i32
};

let mut queue = BinaryHeap::new();
let mut visited = HashMap::new();

let (k1, d1) = (0, Mpz::zero());
let h1 = heuristic(k1, &d1);
visit(&mut queue, &mut visited, h1, h1, k1, d1, Mpz::zero());
while let Some((score, h, k, d, c)) = queue.pop() {
if k == n {
println!("n={} |S|={}", n, -score);
println!("  A={:?}", a_range.clone().collect::<Vec<_>>());
println!("  B={:?}", a_range.clone().collect::<Vec<_>>());
println!(
"  C={:?}",
(0..c.bit_length())
.filter(|&i| c.tstbit(c.bit_length() - 1 - i))
.collect::<Vec<_>>()
);
total += -score;
break;
}

let kd = (k, d);
if score < visited[&kd] {
continue;
}
let (k, d) = kd;

let (k1, d1) = (k, &d >> 1);
let h1 = heuristic(k1, &d1);
visit(
&mut queue,
&mut visited,
score - h + h1,
h1,
k1,
d1,
&c << 1,
);

let (k1, d1) = (k + 1, (&d | &ab) >> 1);
let h1 = heuristic(k1, &d1);
visit(
&mut queue,
&mut visited,
score - h - (&ab & !&d).popcount() as i32 + h1,
h1,
k1,
d1,
&c << 1 | Mpz::one(),
);
}
}

println!("total={}", total);
}


Cargo.toml

[package]
name = "small"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]

[dependencies]
rust-gmp = "0.5.0"


Compile and run with cargo run --release.

Output

n=1 |S|=1
A=[0]
B=[0]
C=[0]
n=2 |S|=3
A=[0, 1]
B=[0, 1]
C=[0, 1]
n=3 |S|=5
A=[-1, 0, 1]
B=[-1, 0, 1]
C=[0, 1, 2]
n=4 |S|=10
A=[-1, 0, 1, 2]
B=[-1, 0, 1, 2]
C=[0, 1, 2, 3]
n=5 |S|=13
A=[-2, -1, 0, 1, 2]
B=[-2, -1, 0, 1, 2]
C=[0, 1, 2, 3, 4]
n=6 |S|=21
A=[-2, -1, 0, 1, 2, 3]
B=[-2, -1, 0, 1, 2, 3]
C=[0, 2, 3, 4, 5, 6]
n=7 |S|=25
A=[-3, -2, -1, 0, 1, 2, 3]
B=[-3, -2, -1, 0, 1, 2, 3]
C=[0, 2, 3, 5, 6, 7, 8]
n=8 |S|=35
A=[-3, -2, -1, 0, 1, 2, 3, 4]
B=[-3, -2, -1, 0, 1, 2, 3, 4]
C=[0, 3, 4, 6, 7, 8, 10, 11]
n=9 |S|=39
A=[-4, -3, -2, -1, 0, 1, 2, 3, 4]
B=[-4, -3, -2, -1, 0, 1, 2, 3, 4]
C=[0, 3, 4, 6, 7, 8, 10, 11, 14]
n=10 |S|=53
A=[-4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
B=[-4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
C=[0, 1, 4, 5, 6, 9, 10, 11, 14, 15]
n=11 |S|=58
A=[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
B=[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
C=[0, 1, 4, 5, 6, 9, 10, 11, 14, 15, 19]
n=12 |S|=74
A=[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6]
B=[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6]
C=[0, 4, 5, 6, 9, 10, 11, 12, 15, 16, 17, 21]
n=13 |S|=80
A=[-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6]
B=[-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6]
C=[0, 4, 5, 6, 9, 10, 11, 12, 15, 16, 17, 21, 22]
n=14 |S|=100
A=[-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
B=[-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
C=[0, 1, 6, 7, 8, 12, 13, 14, 15, 19, 20, 21, 26, 27]
n=15 |S|=106
A=[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
B=[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
C=[0, 5, 6, 7, 11, 12, 13, 14, 18, 19, 20, 21, 25, 26, 27]
n=16 |S|=128
A=[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
B=[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
C=[0, 6, 7, 8, 13, 14, 15, 16, 20, 21, 22, 23, 28, 29, 30, 36]
n=17 |S|=135
A=[-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
B=[-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
C=[0, 6, 7, 8, 13, 14, 15, 16, 20, 21, 22, 23, 28, 29, 30, 36, 44]
n=18 |S|=161
A=[-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
B=[-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
C=[0, 7, 8, 9, 15, 16, 17, 18, 23, 24, 25, 26, 27, 32, 33, 34, 35, 41]
n=19 |S|=167
A=[-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
B=[-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
C=[0, 7, 8, 9, 15, 16, 17, 18, 23, 24, 25, 26, 27, 32, 33, 34, 35, 41, 42]
n=20 |S|=197
A=[-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
B=[-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
C=[0, 1, 8, 9, 10, 11, 17, 18, 19, 20, 21, 26, 27, 28, 29, 30, 36, 37, 38, 46]
total=1411


On my laptop, this used about 8 minutes and about 1.5 GiB of memory.

How it works

We assume (without any particular justification) that A and B are the obvious range of consecutive integers centered at 0 or ½, then do an A* search for an optimal C given A and B.

• If you fix B and C can you do the same A* search on A? I am thinking of a sort of coordinate descent approach. Fix all but one sets, optimize on the last one and repeat.
– user7467
Jun 20, 2017 at 11:39
• @Arthur I doubt a search on A can run as efficiently as a search on C because the space of partial results doesn’t collapse as nicely, and it was already nontrivial to get the search on C to run within the time limit. Jun 20, 2017 at 11:52
• Interesting. Maybe I set 10 minutes too low. I am just intrigued if A = B and both consecutive integers is really always optimal. Just one counter example would be exciting.
– user7467
Jun 20, 2017 at 11:57

Axiom, score 1466

)time on

g(a:List INT,b:List INT,c:List INT):List INT==
s:List INT:=[]
for i in 1..#a repeat
for j in 1..#b repeat
for h in 1..#c repeat
s:=cons(a.i*b.j+c.h, s)
removeDuplicates(s)

inc(a:List INT, b:INT):List INT==
#a=0=>a
i:=1; len:=#a
repeat
if i>len then
for j in 1..len repeat a.j:=0
return a
if i<len then
if a.i<a.(i+1) then
if a.i<b then
a.i:=a.i+1
for j in 1..(i-1) repeat a.j:=0
break
for j in 1..i repeat a.j:=0
else
if a.i<b then
a.i:=a.i+1
for j in 1..(len-1) repeat a.j:=0
break
i:=i+1
a

f(n:PI):List List INT==
a:List INT:=[0];  b:List INT:=[0];   c :List INT:=[0]
aix:List INT:=[]; cmin:List INT:=[]; cp:List INT:=[ ]
s:List INT :=[ ];   c1:List INT:=[0]; smin:INT
-- costruisce gli insiemi a,b
i:=1
for j in 1..n-1 repeat
if member?(i,a) then (a:=cons(-i,a);b:=cons(-i,b);i:=i+1)
else                 (a:=cons( i,a);b:=cons( i,b))
if n=1 then return [a,b,c,[0],[1]]
a:=sort(a)
c :=copy(a); cmin:=copy(a); cp:=copy(a)
for i in 1..n repeat c.i:=i-3
for i in 1..n repeat aix:=cons(0, aix)
-- ottimizzati per i vari casi... si parte da particolari insiemi c
-- da cui fare le variazioni
if n>=8         then c.n:=c.n+2
if n=10 or n=13 then c.(n-1):=c.(n-1)+2
if n=9  or n=16 or n=19 then (c.(n-2):=c.(n-2)+1; c.(n-1):=c.(n-1)+1; c.n:=c.n+1)
smin:=n*n+10
repeat
for i in 1..n repeat cp.i:=c.i+aix.i
k:=# g(a,b,cp)
if k<smin then
smin:=k;
for i in 1..n repeat cmin.i:=cp.i
--output ["assign",c,aix,cmin, k]
inc(aix, 3)
--output aix
i:=0;repeat(i:=i+1;if i>n or aix.i~=0 then break)
if i>n then break
[sort(a),sort(b),sort(cmin),g(a,b,cmin),[smin]]

h(n:PI):NNI==
k:=0
r:List List INT:=[]
for i in 1..n repeat
r:=f(i)
output [i,r.5.1,r.1,r.3]
k:=k+r.5.1
k


The sets would be A=B=[-n/2..n/2] if n%2==0 else A=B=[-n/2..((n/2)+1)]

The set C is the sum of the array as [-2,-1,..(n-2)] to one array arr[] of this kind [0,0,0,0,0] or [0,1,1,1,2] or [0,0,0,0,3] so that array it has property

 arr[i] <= arr[i+1] for i in 1..n-1


If you want to be more precise or you PC is more fast you can try to increase '3' in 'inc(aix, 3)' that increase the number of arrays for the C set variation and so it would increase the result precision.

In the results the string printed is

 [n, |{a*b+c for a in A for b in B for c in C}|,A,C]


where B=A and |S| is the number of element of S

(6) -> h 20
[1,1,[0],[0]]
[2,3,[0,1],[- 2,- 1]]
[3,5,[- 1,0,1],[- 2,- 1,0]]
[4,10,[- 1,0,1,2],[- 2,- 1,0,1]]
[5,13,[- 2,- 1,0,1,2],[- 2,- 1,0,1,2]]
[6,21,[- 2,- 1,0,1,2,3],[- 2,- 1,0,1,2,3]]
[7,25,[- 3,- 2,- 1,0,1,2,3],[- 2,- 1,0,1,2,3,4]]
[8,35,[- 3,- 2,- 1,0,1,2,3,4],[- 2,- 1,1,2,3,5,6,9]]
[9,39,[- 4,- 3,- 2,- 1,0,1,2,3,4],[- 2,1,2,4,5,6,8,9,12]]
[10,53,[- 4,- 3,- 2,- 1,0,1,2,3,4,5],[- 2,- 1,2,3,4,6,7,8,11,12]]
[11,59,[- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5],[- 2,- 1,0,2,3,4,5,7,8,9,12]]
[12,76,[- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6],[- 2,- 1,0,3,4,5,6,8,9,10,11,14]]
[13, 82, [- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6],[- 2,- 1,0,3,4,5,6,8,9,10,11,14,15]]
[14, 103, [- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7],[- 2,- 1,0,3,4,5,6,7,9,10,11,12,13,16]]
[15, 110, [- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7],[- 2,- 1,0,1,4,5,6,7,8,10,11,12,13,14,17]]
[16, 134, [- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8],[- 2,- 1,0,1,4,5,6,7,8,9,11,12,13,15,16,19]]
[17, 142, [- 8,- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8],[- 2,- 1,0,1,4,5,6,7,8,9,11,12,13,14,15,16,19]]
[18, 169, [- 8,- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8,9],[- 2,- 1,0,1,2,3,4,6,7,8,9,10,11,12,15,16,17,20]]
[19, 178, [- 9,- 8,- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8,9],[- 2,- 1,0,1,2,5,6,7,8,9,10,11,13,14,15,16,18,19,22]]
[20, 208, [- 9,- 8,- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8,9,10],[- 2,- 1,0,1,2,3,4,5,7,8,9,10,11,12,13,14,17,18,19,22]]

(6)  1466
Type: PositiveInteger
Time: 0.03 (IN) + 910.75 (EV) + 0.02 (OT) + 24.00 (GC) = 934.80 sec


SQL Server, 1495

declare @N int=20;
--set @N=40;
with
n as(select 1 n union all select n+1 from n where n<@N),
s as(select n,n/2-n+1 m from n union all select n,m+1 from s where m<n/2),
t as(select n,m,row_number()over(partition by n order by m) p from s),
a as(select n,m a,p from t),
b as(select n,m b,p from t),
c as(select n,m c,p from t),
u as(
select a.n,count(distinct a*b+c) q
from a,b,c
where b.n=a.n and c.n=a.n
group by a.n
)
select u.n,a,b,c,q,sum(distinct q) N
from u,a,b,c
where a.n=u.n and b.n=u.n and c.n=u.n and b.p=a.p and c.p=a.p
group by grouping sets((u.n,a,b,c,q),());


The solution can be verified here.

Excuse me for the output is in the tabular form.

C, score 1448 1431

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define P printf
#define R return
#define F for

int cmp(const void*a,const void*b)
{int aa, bb;
aa=*(int*)a; bb=*(int*)b;
R aa>bb?1:(aa<bb?-1:0);
}

void show(int* a,unsigned n){unsigned i;P("[ ");F(i=0;i<n;++i) P("%d ", a[i]);P("]");}

// l'insieme "a" deve essere del tipo {0,1} {-1,0,1} {-1,0,1,2} {-2,-1,0,1,2} ecc di numero elementi n
// l'insieme "c" e' un insieme di numero elementi n
// l'insieme a cui "r" punta sarà *r={x*y+z : x in a, y in a, z in c }
// ritorna -1 per errore altrimenti il numero di elementi
// di {x*y+z : x in a, y in a, z in c }

int g(int**r,int*a,int*c,unsigned n)
{static int *arrs,*res;
static unsigned  alen;
unsigned i,j,k,m,v,vv,len;

if(a==0||c==0||n<=0||n>128) R -1;
len=n*n*n;
if(alen<n)
{if(arrs) free(arrs);  // leaks: arrs and res remain until the program end
if(res ) free(res);
arrs=0; res=0; alen=0;
arrs=malloc(sizeof(int)*len);
if(arrs==0)             R -1;
res =malloc(sizeof(int)*len);
if(res==0)
{free(arrs); arrs=0;R -1;}
alen=n;
}
v=0;
F(k=0;k<n;++k) arrs[v++]=c[k]; // il caso 0

F(m=0;m<n&&a[m]<0;++m);// da una parte i positivi dall'altra i negativi; m punta a 0
// il caso 0 non e' trattato
F(i=0;i<m;++i)    // positivi per negativi
F(j=m+1;j<n;++j)
F(k=0;k<n;++k)
if(-a[i]<=a[j]) arrs[v++]=a[i]*a[j]+c[k];
F(i=m+1;i<n;++i)  // positivi per positivi
F(j=i;j<n;++j)
F(k=0;k<n;++k)
arrs[v++]=a[i]*a[j]+c[k];
qsort(arrs,v,sizeof(int),cmp);
res[0]=arrs[0];  // elimina i doppioni
F(vv=1,i=1; i<v; ++i)
if(arrs[i-1]!=arrs[i]) res[vv++]=arrs[i];
*r=res;
R vv;
}

int inc(int* a,int len,int b)
{int i,j;
if(len<1||b<1)R 1;
F(i=0;;)
{if(i>=len)
{F(j=0;j<len;++j)a[j]=0;
R 1;
}
if(i==len-1||a[i]<a[i+1])
{if(a[i]<b)
{a[i]+=1;
F(j=0;j<i;++j)a[j]=0;
break;
}
}
i+=1;
}
R 0;
}

// a,b,c,cmin sono array e devono avere size n
// s          e' un array deve avere size n*n*n
//            come risultato la sua lunghezza e' *slen
//
int f(int* a,int* b,int* cmin,int* s,int* slen, int n)
{int i,j,k, *c, *aix, *cp, smin, *rs;

if(slen)*slen=0;
if(n<1||a==0||b==0||cmin==0||s==0||slen==0)R -1;

// costruisce a e b
j=-n/2;
if(n%2==0)++j;
F(i=0;i<n;++i,++j) s[i]=cmin[i]=a[i]=b[i]=j;
// {-x..x}  oppure {-x..(x+1)}

*slen=n;
if(n==1)R 1; // caso di un solo elemento
c  =malloc(sizeof(int)*(n+1)); // **
if(c==0)R -1;
aix=malloc(sizeof(int)*(n+1)); // **
if(aix==0){free(c);R -1;}
cp =malloc(sizeof(int)*(n+1)); // **
if(cp==0){free(aix);free(c);R -1;}

F(i=0;i<n;++i){cp[i]=aix[i]=0;c[i]=i;}
if(n>=16)//16
{c[n-1]=c[n-1]+3;c[n-2]=c[n-2]+3;c[n-3]=c[n-3]+3;}
F(smin=n*n+10;;)
{cp[0]=c[0];
F(i=1;i<n;++i) cp[i]=c[i]+aix[i-1];
k=g(&rs,a,cp,n);
if(k<smin){F(smin=k,i=0;i<n;++i) cmin[i]=cp[i];
//P("Assign: %d,  ", k);
//show(aix,n);P(",");
//P("Cmin=");show(cmin,n);P("\n");
}
//show(aix,n);P("\n");
if(inc(aix,n-1,7))break;
}
free(cp);free(aix);free(c);
k=g(&rs,a,cmin,n);
if(k==-1)R -1;
F(i=0;i<k;++i)s[i]=rs[i];
*slen=k;
R k;
}

unsigned h(unsigned nmax)
{time_t                             ti, tf;
double  dft;
int i,j, *a, *b, *cmin, *s, slen, rlen, r;
unsigned                            n,len;
if(nmax>128||nmax<1)R -1;
len =nmax*nmax*nmax+1;
s   =malloc(sizeof(int)*len);      // **
a   =malloc(sizeof(int)*(nmax+1)); // **
b   =malloc(sizeof(int)*(nmax+1)); // **
cmin=malloc(sizeof(int)*(nmax+1)); // **
if(s==0||a==0||b==0||cmin==0){free(s);free(a);free(b);free(cmin);R -1;}
ti=time(0);
F(n=1,r=0;n<=nmax;++n)
{rlen=f(a,b,cmin,s,&slen,n);
if(rlen!=-1)
{P("%d %d", n, rlen); show(cmin,n);P("\n");}
else break;
r+=rlen;
}
tf=time(0);
dft=difftime(tf, ti);
P("Result=%d  secondi=%.0f  minuti=%.0f\n", r, dft, dft/60.0);
free(s);free(a);free(b);free(cmin);
R r;
}

int main(){h(20); R 0;}


It would be the same +/- algo of Axiom implementation

results

1 1[ 0 ]
2 3[ 0 1 ]
3 5[ 0 1 2 ]
4 10[ 0 1 2 3 ]
5 13[ 0 1 2 3 4 ]
6 21[ 0 1 2 3 4 5 ]
7 25[ 0 1 2 3 4 5 6 ]
8 35[ 0 1 3 4 5 7 8 11 ]
9 39[ 0 3 4 6 7 8 10 11 14 ]
10 53[ 0 1 4 5 6 8 9 10 13 14 ]
11 59[ 0 1 2 4 5 6 7 9 10 11 14 ]
12 75[ 0 1 2 5 6 7 8 11 12 13 17 18 ]
13 81[ 0 1 2 5 6 7 8 11 12 13 14 17 18 ]
14 101[ 0 1 2 3 6 7 8 9 10 13 14 15 16 20 ]
15 107[ 0 1 2 3 6 7 8 9 10 13 14 15 16 20 21 ]
16 130[ 0 1 2 6 7 8 9 10 13 14 15 16 17 21 22 23 ]
17 137[ 0 1 2 3 7 8 9 10 11 15 16 17 18 19 23 24 25 ]
18 163[ 0 1 2 3 7 8 9 10 11 12 16 17 18 19 20 25 26 27 ]
19 171[ 0 1 2 3 4 8 9 10 11 12 13 17 18 19 20 21 26 27 28 ]
20 202[ 0 1 2 3 7 8 9 10 11 12 13 17 18 19 20 21 22 27 28 29 ]
Result=1431  secondi=618  minuti=10


Python 2, score 1495

f=lambda n:range(-n/2+1,n/2+1)
f_A=f_B=f_C=f

def comb_set(A, B, C):
return sorted({a*b+c for a in A for b in B for c in C})

def S(n):
return comb_set(f_A(n), f_B(n), f_C(n))


Try it online!

A simple baseline of having each set be a length-n interval centered around 0, slightly unbalanced for even n. The TIO has Python code to compute your score.

1   1
2   3
3   5
4   10
5   13
6   21
7   25
8   36
9   41
10  55
11  61
12  78
13  85
14  105
15  113
16  136
17  145
18  171
19  181
20  210

Total: 1495


The size is (n*n+1)/2 for odd n and (n*n+n)/2 for even n.

• @Arthur Added. I'd like to say this is just a start, but I have no idea yet how to do better :) Something like the sum-product phenomenon gets in the way.
– xnor
Jun 20, 2017 at 7:33
• I plugged the sequence of results into OEIS. It's there, and with an entirely different definition.
– user62131
Jun 20, 2017 at 8:14
• Looks like it was just a start after all.
– user7467
Jun 20, 2017 at 14:10

Mathematica, score 1495

z = 0;
For[n = 1, n <= 20, n++,
r = Range[n] - Ceiling[n/2];
Print["S_n size=", x = (s = Length@#;
Length@
Union@Flatten@
Table[#[[i]]*#[[j]] + #[[k]], {i, s}, {j, s}, {k, s}]) &[r],
"  ", "A=B=C=", r]; z = z + x]
Print["SCORE=", z]


S_n size=1 A=B=C={0}
S_n size=3 A=B=C={0,1}
S_n size=5 A=B=C={-1,0,1}
S_n size=10 A=B=C={-1,0,1,2}
S_n size=13 A=B=C={-2,-1,0,1,2}
S_n size=21 A=B=C={-2,-1,0,1,2,3}
S_n size=25 A=B=C={-3,-2,-1,0,1,2,3}
S_n size=36 A=B=C={-3,-2,-1,0,1,2,3,4}
S_n size=41 A=B=C={-4,-3,-2,-1,0,1,2,3,4}
S_n size=55 A=B=C={-4,-3,-2,-1,0,1,2,3,4,5}
S_n size=61 A=B=C={-5,-4,-3,-2,-1,0,1,2,3,4,5}
S_n size=78 A=B=C={-5,-4,-3,-2,-1,0,1,2,3,4,5,6}
S_n size=85 A=B=C={-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6}
S_n size=105 A=B=C={-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7}
S_n size=113 A=B=C={-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7}
S_n size=136 A=B=C={-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8}
S_n size=145 A=B=C={-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8}
S_n size=171 A=B=C={-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9}
S_n size=181 A=B=C={-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9}
S_n size=210 A=B=C={-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10}
SCORE=1495

C++, score 1411

Conjecturing A and B are consecutive integers centered near 0, simply use simulated annealing to find C.

Source:

#include <algorithm>
#include <iostream>
#include <random>
#include <bitset>
#include <cmath>

using namespace std;

using bools = bitset<270>;
using irand = uniform_int_distribution<int>;
ranlux48 gen;
uniform_real_distribution<double> frand(0, 1);

int evaluate(const bools& a, const vector<int>& v)
{
bools t = a;
for (int i : v) t |= a << i;
return t.count();
}

vector<int> best;
int best_score, prev_score;

void transition(double Temp, int Q, const bools& a, vector<int>& now)
{
int rep, pos, tmp;
do rep = irand(1, Q)(gen); while (find(now.begin(), now.end(), rep) != now.end());
pos = irand(0, now.size() - 1)(gen);
tmp = now[pos];
now[pos] = rep;
int now_score = evaluate(a, now);
if (now_score <= prev_score || frand(gen) < exp((double)(prev_score - now_score))) {
prev_score = now_score;
if (now_score < best_score) best_score = now_score, best = now;
}
else now[pos] = tmp;
}

int main()
{
int score = 0;
for (int N = 1; N <= 20; N++) {
gen.seed(0);
int first = -N / 2, last = first + N, Q = N * 3;
bools st;

for (int i = first; i < last; i++)
for (int j = first; j < last; j++)
st[i * j + last * last] = true;

vector<int> lst;
for (int i = 1; i < N; i++) lst.push_back(i);

best = lst;
prev_score = best_score = evaluate(st, lst);

if (N != 1)
for (double Temp = 70.; Temp > 0; Temp -= 3e-5) transition(Temp, Q, st, lst);
sort(best.begin(), best.end());
cout << "N = " << N << "; |S| = " << best_score << endl;
cout << " A = B = {";
for (int i = first; i < last; i++) cout << i << (i != last - 1 ? ", " : "}\n");
cout << " S = {0";
for (int i : best) cout << ", " << i;
cout << "}\n";

score += best_score;
}
cout << "Score: " << score << endl;
}


Results:

N = 1; |S| = 1
A = B = {0}
S = {0}
N = 2; |S| = 3
A = B = {-1, 0}
S = {0, 1}
N = 3; |S| = 5
A = B = {-1, 0, 1}
S = {0, 1, 2}
N = 4; |S| = 10
A = B = {-2, -1, 0, 1}
S = {0, 1, 2, 3}
N = 5; |S| = 13
A = B = {-2, -1, 0, 1, 2}
S = {0, 1, 2, 3, 4}
N = 6; |S| = 21
A = B = {-3, -2, -1, 0, 1, 2}
S = {0, 1, 2, 3, 4, 5}
N = 7; |S| = 25
A = B = {-3, -2, -1, 0, 1, 2, 3}
S = {0, 1, 2, 3, 4, 5, 6}
N = 8; |S| = 35
A = B = {-4, -3, -2, -1, 0, 1, 2, 3}
S = {0, 3, 4, 6, 7, 10, 11, 14}
N = 9; |S| = 39
A = B = {-4, -3, -2, -1, 0, 1, 2, 3, 4}
S = {0, 3, 4, 6, 7, 8, 10, 11, 14}
N = 10; |S| = 53
A = B = {-5, -4, -3, -2, -1, 0, 1, 2, 3, 4}
S = {0, 1, 4, 5, 6, 9, 10, 11, 14, 15}
N = 11; |S| = 58
A = B = {-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5}
S = {0, 1, 4, 5, 6, 9, 10, 11, 14, 15, 19}
N = 12; |S| = 74
A = B = {-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5}
S = {0, 4, 5, 6, 9, 10, 11, 12, 15, 16, 17, 21}
N = 13; |S| = 80
A = B = {-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6}
S = {0, 6, 10, 11, 12, 15, 16, 17, 18, 21, 22, 23, 27}
N = 14; |S| = 100
A = B = {-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6}
S = {0, 5, 6, 7, 11, 12, 13, 14, 18, 19, 20, 21, 25, 26}
N = 15; |S| = 106
A = B = {-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7}
S = {0, 5, 6, 7, 11, 12, 13, 14, 18, 19, 20, 21, 25, 26, 32}
N = 16; |S| = 128
A = B = {-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7}
S = {0, 6, 7, 8, 13, 14, 15, 16, 21, 22, 23, 24, 29, 30, 31, 37}
N = 17; |S| = 135
A = B = {-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8}
S = {0, 6, 7, 8, 13, 14, 15, 16, 21, 22, 23, 24, 29, 30, 31, 37, 45}
N = 18; |S| = 161
A = B = {-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8}
S = {0, 7, 8, 9, 14, 15, 16, 17, 18, 22, 23, 24, 25, 26, 31, 32, 33, 40}
N = 19; |S| = 167
A = B = {-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
S = {0, 7, 8, 9, 15, 16, 17, 18, 23, 24, 25, 26, 27, 32, 33, 34, 35, 41, 42}
N = 20; |S| = 197
A = B = {-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
S = {0, 8, 9, 10, 16, 17, 18, 19, 20, 25, 26, 27, 28, 29, 35, 36, 37, 38, 45, 46}
Score: 1411


With -O2 on my computer, it takes 50 secs to compute all the results.