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

[Max Alekseyev]

On Thu, May 15, 2008 at 3:27 AM, Max Alekseyev <maxale at gmail.com> wrote:

> btw, I thought about limiting my original approach of iterating over
> all permutations to only feasible ones.
> I call a permutation (r(1),...,r(n)) feasible only if for every pair
> of indices i and j, gcd(r(i),r(j)) divides (i-j). Only for such
> permutations, the system of congruences
>
> m = 0 (mod r(1))
> m = -1 (mod r(2))
> ...
> m = -(n-1) (mod r(n))
>
> is solvable.
> It turns out that there are no so many feasible permutations, their
> number for n=1,...,16 is:
>
> 1, 2, 6, 8, 48, 24, 216, 120, 240, 128, 2544, 336, 11520, 3168, 1536, 480

I've just submitted this sequence as A140257 (see below).
Unfortunately, I don't know Leroy's sequence number, so I didn't give
any cross references.

Regards,
Max

%I A140257
%S A140257 1, 2, 6, 8, 48, 24, 216, 120, 240, 128, 2544, 336, 11520,
3168, 1536, 480
%N A140257 Number of permutations p of order n such that the system of
congruences x == i (mod p(i)), i=1..n, is solvable.
%C A140257 The system of congruences x == i (mod p(i)), i=1..n, is
solvable if and only if for every pair of indices i,j=1..n
gcd(p(i),p(j)) divides (i-j).
%o A140257 (PARI) { allper(n,i) = local(b); if(i>n,r++;return);
p[i]=0; while(p[i]<n, p[i]++; if(P[p[i]],next); b=0; for(j=1,i-1,
if((i-j)%gcd(p[i],p[j]),b=1;break)); if(b,next); P[p[i]]=1;
allper(n,i+1); P[p[i]]=0) }

{ a(n) = P=p=vector(n); r=0; allper(n,1); r }
%O A140257 1
%K A140257 ,nonn,
%A A140257 Max Alekseyev (maxal at cs.ucsd.edu), May 16 2008


X-NetKnow-OutGoing-4-69-9-1-MailScanner-Watermark: 1211349799.80499 at cEf8dbVnM1rzEBMOTqnLdw