OFFSET
1,1
COMMENTS
The first example where A219787(n) differs from A219786(n) is 12: A219787(12) = 28, with the set of 12 integers (13, 26, 15, 28, 25, 18, 14, 16, 27, 20, 22, 24); while it is not possible to build such a solution with the 11 integers (14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27), plus any prime within, that are found with A219786(11) = 27.
The problem can be efficiently solved using bipartite graph matching (see link). - Bert Dobbelaere, Jul 25 2019
LINKS
Bert Dobbelaere, Table of n, a(n) for n = 1..500
Bert Dobbelaere, Python program
P. Erdős and C. Pomerance, Matching the natural numbers up to n with distinct multiples in another interval, Nederl. Akad. Wetensch. Proc. Ser. A 83 (1980), 147-161.
Michel Marcus, Multiples for n=2 to 20
EXAMPLE
For n=4, a(4) = 9, since by using 5 (prime) and 6, 8, 9 (cf. A219786), the 4 integers 5, 6, 9, 8 are respectively divisible by 1, 2, 3 and 4.
PROG
(PARI)
minv(n) = {/* minimum vector of n-1 composite > n */ nbc = 0; nn = n+1; vec = vector(n-1); while (nbc != n-1, if (! isprime(nn), nbc++; vec[nbc] = nn; ); if (nbc != n-1, nn++); ); return (vec); }
mynumtoperm (num, n, vec) = {/* lexicographic numtoperm */ if (num == 0, return (vec)); nvec = vector(n); wvec = vec; forstep (i=n-1, 0, -1, ovec = wvec; cid = floor(num/i!)+1; nvec[n-i] = ovec[cid]; nnb = length(ovec); if (nnb > 1, wvec = vector(nnb-1); nj = 1; for (oj=1, nnb, if (oj != cid, wvec[nj] = ovec[oj]; nj++; ); ); ); num = num % i!; ); return (nvec); }
findv(vec, n) = {/* find a good set of n items *//* the first time vec has n elements *//* the next times vec has more than n elements */ local(nvec); n1 = length(vec); n2 = n-1; ntotal = n1!; /* print("n=", n, " n1=", n1, " n2=", n2, " ntotal ", ntotal); */ nvec = vector(n1); ok = 1; num = 0; while (ok , nvec = mynumtoperm(num, n1, vec); /*print("nvec ", nvec); */ okp = 1; j =1; while (okp && (j<= n2), if (nvec[j] % (j+1) != 0, okp = 0; ); if (okp, j++); ); if (okp, return (nvec)); /* jump over a set of bad positions */ num += (n1-j)!; if (num >= ntotal, ok = 0); ); return ([]); }
fnn(n) = { vec = minv(n); print("n=", n, " vec=", vec); /* find solution with minimal vector */ nvec = findv(vec, n); print("fnn1:", nvec); while (nvec == [], /* extend vector by adding one composite */ last = vec[length(vec)]+1; while (isprime(last), last++); vec = concat (vec, last); /* find solution with extended vector*/ nvec = findv(vec, n); print("fnn2:", nvec); ); return (nvec); }
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
Michel Marcus, Nov 28 2012
EXTENSIONS
More terms from Bert Dobbelaere, Jul 25 2019
STATUS
approved