Problem 843

[pri_gua]

Can someone PM me or respond here with input for n = 6 that gives a period of 2. I have tried all possible permutations of (1, 2, 3, 4, 5, 6) and I keep getting a period of only 1. I have also tried all possible permutations of (a1, a2, a3, a4, a5, a6) where ai = random.randint(1, 216). (216 = 6 x 6 x 6).

Thanks.

[skoczian]

Where in the text of the problem do you find a limit for the integers forming the cycle? I can only see limits for the circle sizes.

[jaap]

Can someone PM me or respond here with input for n = 6 that gives a period of 2. I have tried all possible permutations of (1, 2, 3, 4, 5, 6) and I keep getting a period of only 1. I have also tried all possible permutations of (a1, a2, a3, a4, a5, a6) where ai = random.randint(1, 216). (216 = 6 x 6 x 6).

Thanks.

What sequence do you get with (1, 2, 3, 4, 5, 6)?

[pri_gua]

@skoczian

Here:
n = 5 can have a period of 3 (This I can reproduce)
n = 6 can have a period of 2 (This I cannot reproduce)

@jaap
Here is the sequence I get:

>>> import task_002 as T
>>> T.cycle((1,2,3,4,5,6))
0:(1, 2, 3, 4, 5, 6)
1:(4, 2, 2, 2, 2, 4)
2:(2, 2, 0, 0, 2, 2) # This is the tuple that will repeat ...
3:(0, 2, 2, 2, 2, 0) # Note that this tuple is just a shifted version of the tuple from the previous line ...
1 # This is the period ...

[jaap]

It does not say that cyclic shifts should be considered the same.

[mdean]

He does have a point. If it's a circle, it doesn't really have a beginning or end. If it has the same exact numbers in the same exact order, isn't it the same circle?

[skoczian]

@skoczian

Here:
n = 5 can have a period of 3 (This I can reproduce)
n = 6 can have a period of 2 (This I cannot reproduce)

But where does the text state that the circle for n = 6 has to start with the numbers (1, 2, 3, 4, 5, 6)? It has to contain 6 integers, but they can have any value, as far as I can see.

[pjt33]

He does have a point. If it's a circle, it doesn't really have a beginning or end. If it has the same exact numbers in the same exact order, isn't it the same circle?

No, it isn't. It may help to paint one of the buckets in a different colour to the rest to make an arbitrary fixed reference point.

[pri_gua]

@jaap: Not treating cyclic shifts as the same helps with S(6). Thanks.

I have code as you have seen in the posts above that simply simulates the process described in the problem, I have little reason to believe the code is flawed, yet I get S(30) = 20376. I am making the assumption that starting the procedure with the tuple (1,2,3,4,5,6,...,n) will give the period other than 1 if it exists. Period of 1 can be achieved for any n, by using the starting tuple (0,0,0,...,0). Is that a safe assumption to make ...

[neverforget]

the period other than 1 if it exists

For some values of n, there can be multiple periods other than 1. The problem wants you to find them all. I think it could help to clarify this and counting rotations as distinct within the problem statement.

[pri_gua]

Got the missing 5 thanks to clarifications and hints by some fellow members ... Just for future readers of this thread:
Note: for some n, we can have more than 2 periods. (0,0,0,...,0) gives a period of 1, (1,2,3,4,5,6,...,n) gives for most part a period other than 1. In addition to this, there may be another period or more for this particular n. As far as getting the correct answer for S(30) (which can be computed by simulation alone) you will have to come up with some different class of inputs to get the missing 5 ...

[pri_gua]

[post deleted by moderator because it gave partial answers and discussed solution approaches]

[RobertStanforth]

Thank you all for the clarifying questions.
Concerning the possibility of a single $n$ having multiple periods, we have tweaked the wording of the $S(6)$ example to emphasise this.

[pri_gua]

I think we still need to emphasize that more than 2 periods are possible for some numbers. This is clarified here by neverforget, but I believe it should be mentioned in the problem text.

[skoczian]

I think we still need to emphasize that more than 2 periods are possible for some numbers. This is clarified here by neverforget, but I believe it should be mentioned in the problem text.

There is no reason to think that only 1 or 2 different periods are possible for the same n. Just because the numbers up to 6 have this property? It's generally wrong to assume properties of a problem that are neither explicitly stated nor provable from the stated facts.