|
| |
|
|
A219787
|
|
Least number such that in the interval [n+1, a(n)] there are n integers b(i) with i | b(i) for i = 1 to n.
|
|
2
|
|
|
|
2, 4, 6, 9, 10, 14, 15, 18, 21, 24, 25, 28, 28, 32, 34, 40, 40, 44, 44, 48, 50, 52, 52, 56, 60, 63, 66, 70, 70, 75, 75, 81, 81, 81, 84, 90, 90, 92, 96, 99, 99, 102, 102, 105, 110, 112, 112, 120, 120, 126, 126, 130, 130, 135, 136, 144, 144, 144, 144, 150, 150, 150, 160, 168, 168, 168, 168, 170, 171, 176
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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); }
(END PARI)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
