|
%I #23 Jul 25 2019 11:55:42
%S 2,4,6,9,10,14,15,18,21,24,25,28,28,32,34,40,40,44,44,48,50,52,52,56,
%T 60,63,66,70,70,75,75,81,81,81,84,90,90,92,96,99,99,102,102,105,110,
%U 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
%N 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.
%C 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.
%C The problem can be efficiently solved using bipartite graph matching (see link). - _Bert Dobbelaere_, Jul 25 2019
%H Bert Dobbelaere, <a href="/A219787/b219787.txt">Table of n, a(n) for n = 1..500</a>
%H Bert Dobbelaere, <a href="/A219787/a219787.py.txt">Python program</a>
%H P. Erdős and C. Pomerance, <a href="http://www.math.dartmouth.edu/~carlp/PDF/matching.pdf">Matching the natural numbers up to n with distinct multiples in another interval</a>, Nederl. Akad. Wetensch. Proc. Ser. A 83 (1980), 147-161.
%H Michel Marcus, <a href="/A219787/a219787.txt">Multiples for n=2 to 20</a>
%e 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.
%o (PARI)
%o 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);}
%o 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);}
%o 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 ([]);}
%o 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);}
%o (END PARI)
%Y Cf. A219786.
%K nonn
%O 1,1
%A _Michel Marcus_, Nov 28 2012
%E More terms from _Bert Dobbelaere_, Jul 25 2019
|
