Dividing n consecutive integers by (1,2,3,...,n)
Max Alekseyev
maxale at gmail.com
Wed May 14 21:20:17 CEST 2008
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
More information about the SeqFan
mailing list