Decimation Sequences

[davar55]

Consider the first N positive integers arranged in a circular manner
so that 2 follows 1, 3 follows 2, ... , and 1 follows N.

Let M be any positive integer. Start counting at 1, and when you
reach M, note the number and remove it. Count M numbers again
(wrapping around when needed), note the number and remove it.
Continue in this way until all N numbers are removed.
The sequence of removed numbers is called a "decimation sequence"
on N generated by M.

(a) Show that every permutation on (1 thru N) is a decimation sequence
on N generated by some M in the range 1 <= M <= N! .

(b) Find the last number in the decimation sequence on N=10^12
generated by M=3.

[davar55]

I must withdraw the claim of part (a).
It's easy to construct counterexamples.
The so-called argument I had to support it is flawed.
My apologies.

Perhaps the question can be rescued by asking instead
how many decimation sequences there are for any given N?

[petrw1]

706915036709

Brute force would never have finished.

I computed this in .001 seconds on my computer.

[petrw1]

Originally Posted by petrw1

I computed this in .001 seconds on my computer.

Algorithm available if I am correct ... otherwise the algorithm is obviously useless.

[petrw1]

BUMP

[fivemack]

I think this is called the Josephus Problem, and is discussed in an early chapter of Knuth's Concrete Mathematics; there's a bit of discussion at http://mathworld.wolfram.com/JosephusProblem.html without a useful algorithm, http://www.cut-the-knot.org/recurrence/j_solution.shtml is a bit closer to a useful algorithm.

[petrw1]

Not sure if I should have called it an algorithm as much as a formula or sequence for m=3.
Starting with the trivial cases:
Length (N) ... Ending Number (E)
1 ... 1
2 ... 2
3 ... 3
4 ... 1
Then...progressively add 1 to N and 3 to E. If E>N then E=E-N
While this work it still takes much too long for 10^12.

So I looked only at the points that E=1 or 2 and found a way to calculate it as:
IF E=2 AND N IS EVEN THEN N=N+CEILING(N/2)-1
ELSE N=N+CEILING(N/2)
IF N IS EVEN THEN E=3-E (This flips E from 2 to 1 OR 1 to 2)

Now the sequence displayed is:
Length (N) ... Ending Number (E)
4 ... 1
6 ... 1
9 ... 1
14 ... 2
21 ... 2
etc.

When I get to the point where the next N would be larger then 10^12 I compute the last E knowing that for each N+1 there is an E+3.

Then entire source in BASIC is (it runs in well under a second):

defqud N,E
defdbl z
print 4;1
N=4
E=1
do while N*1.5<1000000000000
z=N/2
N=N+ceil(z)
if E=2 and z<>int(z) then N=N-1
if z<>int(z) then E=3-E
print N;E
loop

E=E+3*(1000000000000-N)
N=N+(1000000000000-N)
print N;E