Dividing n consecutive integers by (1,2,3,...,n)
Max Alekseyev
maxale at gmail.com
Thu May 15 19:29:09 CEST 2008
On Thu, May 15, 2008 at 7:44 AM, Don Reble <djr at nk.ca> wrote:
>> Don, could you please shed some light on how you got all these values?
>
> I test each integer in turn, to see whether it's the value.
> Just careful coding in a machine-friendly language.
Did you follow the same approach as Robert?
>> Can your approach help to compute more values?
>
> Yeah, I could have run the program longer.
Actually, I meant to ask if your approach can be adapted to counting
the number of feasible permutations. Can it?
>> 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
That is a bit unclear to me.
In particular, for n=3, your calculations indicate that there are only
5 different starting points while there are 6 feasible permutations.
But it turns out that solutions to the corresponding systems of congruences:
m = 0 (mod r(1))
m = -1 (mod r(2))
m = -2 (mod r(3))
(where r goes over all 6 permutations of {1,2,3}) are exactly all
different residues modulo 6.
In other words, 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?
Maybe, I've misunderstood what is the "starting point"? Please clarify.
> That's a good way to find all solutions; but if you want only the
> least solution, it may be a waste of time.
I cannot agree with this statement right away, in particular, since
feasible permutations can be constructed in a fast way using
branch-and-bound approach. A straightforward implementation seems to
be able to produce the result in reasonable time for n up to 20 at
least. But, maybe, there exists even a smarter way to construct such
permutations so that it will beat Robert's and your approach(es) to
computing Leroy's sequence.
Regards,
Max
Please remove me from Number Sequences. (eemcd at mac.com)
Thank ypu,
Eugene McDonnell
More information about the SeqFan
mailing list