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

[Max Alekseyev]

On Thu, May 15, 2008 at 8:50 PM, Don Reble <djr at nk.ca> wrote:

>> Did you follow the same approach as Robert?
>
>    Sorry, I don't know Maple.

I did not mean to study Robert's maple code.
Basically, Robert summarized his approach in the following sentense:

"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."

I can elaborate a bit on this approach: it constructs a bipartite
graph where one part is the set of integers {1,2,...,n} while the
other part is { a, a+1, ..., a+n-1 }, and there is an edge (i,a+j) as
soon as i divides (a+j). A perfect matching M (if it exists) in this
graph defined a permutation r(k), k=1..n, such that r(k) is connected
to a+k-1 in M. It is clear that such a permutation is what we need,
while finding it is a particular case of Assignment Problem:
http://en.wikipedia.org/wiki/Assignment_problem

You described your approach before as "I test each integer in turn, to
see whether it's the value."
So, your approach coincides with Robert's one in at least testing each
integer a=n+1,n+2,.... as a potential term of Leroy's sequence. But
while I understand how Robert's approach works, I still have no idea
of how such testing is done in your approach. Do you also solve some
kind of Perfect Matching / Assignment Problem in your approach?

>> ... for n=3, your calculations indicate that there are only
>> 5 different starting points while there are 6 feasible permutations.
>> ...
>> ... each of the feasible permutations here results in an
>> unique solution modulo lcm(1,2,3)=6. But how then the number of
>> starting points can be equal 5?
>
>    The permutations (1,3,2) and (2,3,1) both map onto (2,3,4) mod 6.
>    The starting point is 2. No permutation maps onto (5,0,1) mod 6,
>    so 5 is not a starting point.

Yes, you're right. There was a bug in my program with respect to
starting points.
However, after correcting it, I still have disagreements with the
values that you posted before.

The first disagreement happens for n=6.
Your value for the number of starting points is 11 while I got 20.
These are the 20 starting points and corresponding permutations:

[Mod(0, 60), [6, 1, 2, 3, 4, 5]]
[Mod(1, 60), [1, 2, 3, 4, 5, 6]]
[Mod(2, 60), [2, 3, 4, 5, 6, 1]]
[Mod(3, 60), [3, 2, 5, 6, 1, 4]]
[Mod(4, 60), [2, 5, 6, 1, 4, 3]]
[Mod(5, 60), [5, 6, 1, 4, 3, 2]]
[Mod(20, 60), [4, 3, 2, 1, 6, 5]]
[Mod(23, 60), [1, 6, 5, 2, 3, 4]]
[Mod(24, 60), [6, 5, 2, 3, 4, 1]]
[Mod(25, 60), [5, 2, 3, 4, 1, 6]]
[Mod(30, 60), [6, 1, 4, 3, 2, 5]]
[Mod(31, 60), [1, 4, 3, 2, 5, 6]]
[Mod(32, 60), [4, 3, 2, 5, 6, 1]]
[Mod(35, 60), [5, 6, 1, 2, 3, 4]]
[Mod(50, 60), [2, 3, 4, 1, 6, 5]]
[Mod(51, 60), [3, 2, 1, 6, 5, 4]]
[Mod(52, 60), [2, 1, 6, 5, 4, 3]]
[Mod(53, 60), [1, 6, 5, 4, 3, 2]]
[Mod(54, 60), [6, 5, 4, 3, 2, 1]]
[Mod(55, 60), [5, 4, 3, 2, 1, 6]]

Do you see any errors in this list or was it miscalculation on your side?

Regards,
Max


X-NetKnow-OutGoing-4-69-9-1-MailScanner-Watermark: 1211388871.11489 at Na8cAN7KdPU67dhKkXBzBA