Dividing n consecutive integers by (1,2,3,...,n)

[Robert Israel]

The trouble is that there are n! permutations of {1...n},
so this is not going to be practical if n is large.
Checking whether there is a permutation r such that
r(j)|a+j for j=0..n-1 can be thought of as an Assignment
Problem, and this has efficient polynomial-time algorithms.
Here's a Maple procedure:

Quet:= proc(n)
    local a,i,j,G, R;
    global Match;
    uses GraphTheory;
    for a from n+1 do
      G:= Graph(select(t -> (t[2] mod t[1] = 0),
        {seq(seq({i,j},i=1..n),j=a..a+n-1)}));
      R:= BipartiteMatching(G);
      if R[1] = n then Match:= R[2]; return a end if
    end do;
  end proc;

> seq(Quet(n), n=1..15);

    2, 3, 4, 6, 6, 20, 24, 48, 48, 110, 110, 110, 243, 403, 402

It's interesting that the sequence is not monotone: a(15) < a(14)

Cheers,
Robert Israel

On Wed, 14 May 2008, Max Alekseyev wrote:

> On Tue, May 13, 2008 at 10:01 AM, Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:
>
>> %I A000001
>> %S A000001 2,3,4,6,6,20,24
>> %N A000001 a(n) = the least integer > n such that
>> r(1)|a(n), r(2)|(a(n)+1), r(3)|(a(n)+2),..., and
>> r(n)|(a(n)+n-1), where (r(1),r(2),r(3),...,r(n))
>> is some permutation of (1,2,3,...,n).
>> %C A000001 It is easy to see that every term of
>> this sequence exists, because the stretch of n
>> terms, n!-n to n!-1, is such that n|(n!-n),
>> (n-1)|(n!-n+1),...,2|(n!-2), 1|(n!-1).
>
> More terms:
> 2,3,4,6,6,20,24,48,48,110,110
>
>> It seems likely to me that there is a more direct
>> and simpler way, simpler and more direct than
>> just checking stretches of integers, to calculate
>> the terms of this sequence. Is there an easy way
>> to calculate the sequence's terms without not
>> just checking all stretches of n consecutive
>> integers for their divisibility?
>
> For every permutation r(1),r(2),r(3),...,r(n)) of numbers
> {1,2,3,...,n}, computing the corresponding number m such that r(1)|m,
> r(2)|(m+1), ..., r(n)|(m+n-1) can be done via solving the following
> system of congruences:
> m = 0 (mod r(1))
> m = -1 (mod r(2))
> ...
> m = -(n-1) (mod r(n))
> Therefore, to compute a(n) it is possible to go over all permutations
> of {1,2,3,...,n}, for each of them solve the system above, and select
> the minimum solution (but >n as required) overall. This is my PARI/GP
> implementation of this approach:
>
> { a(n) = local(L,m,p,c); L=lcm(vector(n,i,i)); m=2*L; for(i=1,n!,
> p=numtoperm(n,i); trap(,next,c=lift(
> chinese(vector(n,i,Mod(1-i,p[i])))) ); while(c<=n,c+=L); m=min(m,c);
> ); m }
>
> It has produced the numbers listed above.
>
> Regards,
> Max
>