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

[Max Alekseyev]

On Thu, May 15, 2008 at 7:44 AM, Don Reble <djr at nk.ca> wrote:

>> 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
>
>    Furthermore, sometimes two permutations map onto the same starting
>    point, modulo lcm(1..n). The number of starting points is
> 1, 2, 5, 8, 32, 11, 72, 64, 66, 17, 213, 37, 417, 120, 67, 60, 694, 217

This is the corrected sequence of starting points (just submitted):

%I A140275
%S A140275 1, 2, 5, 8, 32, 20, 120, 112, 172, 80, 1164, 312, 5160,
1852, 812, 432, 10168,
%N A140275 The total number of distinct solutions (modulo
lcm(1,2,...,n)) of the system of congruences x == i (mod p(i)),
i=1,2,...,n, where p is a permutation of order n.
%C A140275 The system of congruences x == i (mod p(i)) has the same
solution as the system of congruences x == n-1-i (mod p'(i)) where
p'=(p(n),p(n-1),...,p(1)). Therefore, this sequence also gives the
number of distinct solutions to the system of congruences x == -i (mod
p(i)), i=1,2,...,n.
%Y A140275 A003418, A140257
%O A140275 1
%K A140275 ,nonn,
%A A140275 Max Alekseyev (maxal at cs.ucsd.edu), May 16 2008

and here is the updated and extended entry A140257:

%I A140257
%S A140257 1, 2, 6, 8, 48, 24, 216, 120, 240, 128, 2544, 336, 11520,
3168, 1536, 480, 23616, 2592,
%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).
%C A140257 Note that if the system is solvable for a permutation
p=(p(1),p(2),...,p(n)), then it is solvable for reversed permutation
(p(n),p(n-1),...,p(1)). Also, any two primes q1, q2 > n/2 in p can be
exchanged without affecting the system solvability. Therefore, for
n>1, a(n) is divisible by 2*(A000720(n)-A000720(n/2))!.
%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

Regards,
Max



Stefan,

I wanted to follow up with the results of a computation I left running as a 
background task this week. Below is a complete of solutions to


with integers 0<=a<b<=n for n up to 18951 (this number just happens to be 
how far it got before I needed to reboot the machine for other reasons). 
There are 18 solutions, all of which have b-a<=2 (but the program checked 
all possible values of a and b, not just those differing by 1 or 2).

bin(19,3)+bin(19,5) divides bin(19,8)
bin(34,6)+bin(34,7) divides bin(34,13)
bin(41,5)+bin(41,7) divides bin(41,12)
bin(89,7)+bin(89,8) divides bin(89,15)
bin(104,3)+bin(104,4) divides bin(104,7)
bin(359,5)+bin(359,6) divides bin(359,11)
bin(398,20)+bin(398,21) divides bin(398,41)
bin(495,12)+bin(495,14) divides bin(495,26)
bin(527,7)+bin(527,9) divides bin(527,16)
bin(1845,15)+bin(1845,17) divides bin(1845,32)
bin(2309,5)+bin(2309,6) divides bin(2309,11)
bin(2729,19)+bin(2729,20) divides bin(2729,39)
bin(3539,35)+bin(3539,36) divides bin(3539,71)
bin(4619,11)+bin(4619,12) divides bin(4619,23)
bin(8644,18)+bin(8644,19) divides bin(8644,37)
bin(12923,34)+bin(12923,36) divides bin(12923,70)
bin(14135,30)+bin(14135,31) divides bin(14135,61)
bin(15774,24)+bin(15774,26) divides bin(15774,50)

Cheers,

Drew

p.s. I notice the sequence of n for which such a solution exists is not in 
the OEIS. Have you, or do you plan to submit such a sequence?

On May 5 2008, Stefan Steinerberger wrote:

>First, thanks for all your interest and thoughts.
>The computed numbers lead me to conjecture that
>both problems
>
>C(n,a)+C(n,a+1) | C(n,2a+1)
>C(n,a)+C(n,a+2) | C(n,2a+2)
>
>have infinitely many solutions and that Drew's observation
>about the fact that the two variables never differ by more than
>2 is correct. Sadly, no idea for a proof (I don't suppose one
>could prove the "differ by 2" statement by using Legendre's
>theorem to count the multiplicity of prime factors of both terms?)
>
>In any case, thanks for all your interest/time/computing power,
>Stefan
>