Problem F
Chinese
Shuffle
Input: standard input
Output: standard output
Time Limit: 1 second
Jimmy was a math student in Chicago in the
thirties of the last century. Being a student was tough those days (as it still
is), and he was always short of money. So he decided to moonlight at the casino
of his uncle. Well, casino is a big word; it was the upstairs room of a cafe,
and you had to know the guy at the back door to be alowed to enter at all.
Anyway, making profit was the main goal of his uncle, so Jimmy was expected to
do just that.
One day, sitting alone in his room, not knowing
where to start studying for his next exam, he took up a deck of playing cards
and began practicing his "Perfect Shuffle". Let me explain what a
perfect shuffle is.
In an ordinairy shuffle, the dealer splits the
deck in two roughly equal parts, takes one half in each hand and then releases
the cards alternating from his left and right hand onto a new pile on the
table. You probably know what I mean; when you try it yourself, the cards end
up all over the place. In Jimmy's perfect shuffle you start with N cards (N=52
for an ordinary deck). Take the top N/2 cards in your right hand (round down if
N is odd) and the remaining cards in your left. Now drop the bottom most card
from your left hand, cover it with the bottom most card from your right hand,
drop the next bottom most from your left hand, etc., alternating between left
and right until all the cards are in one pile again.
Let's take 10 cards, numbered 1 to 10 from top to
bottom. After one shuffle the order becomes:
RIGHT: 1 2 3 4 5, LEFT: 6 7 8 9 10 -> 1 6 2 7 3 8 4 9 5 10
With 11 cards:
RIGHT: 1 2 3 4 5, LEFT: 6 7 8 9 10 11 -> 6 1 7 2 8 3 9 4 10 5 11
Jimmy practiced
his shuffle to perfection. There is of course a great benifit in being able to
do a perfect shuffle: once you know the order of the cards before the shuffle,
you can predict the order after the shuffle. Dealing at the Black Jack table,
he made his uncle very happy. But that's beside the point now. The thing Jimmy
noticed while he was practicing, was that only 8 out of all 52! different
orderings of a standard deck of cards could be attained by repeatedly applying
his shuffle. In other words: after 8 perfect shuffles the cards were in their
original order again. He started wondering what was so special about the number
8 and added a Joker to the deck. With this new deck of 53 cards he discovered
that he needed 52 perfect shuffles to return to the original ordering. A
completely different number. Now his mathematical curiosity was roused and he
started experimenting with different numbers of cards.
For example for
9 cards:
original : 1 2 3 4 5 6 7 8 9
shuffle 1: 5 1 6 2 7 3 8 4 9
shuffle 2: 7 5 3 1 8 6 4 2 9
shuffle 3: 8 7 6 5 4 3 2 1 9
shuffle 4: 4 8 3 7 2 6 1 5 9
shuffle 5: 2 4 6 8 1 3 5 7 9
shuffle 6: 1 2 3 4 5 6 7 8 9
Here are the
results for N=3 to 20:
3: 2 shuffles
4: 2 shuffles
5: 4 shuffles
6: 4 shuffles
7: 3 shuffles
8: 3 shuffles
9: 6 shuffles
10: 6 shuffles
11: 10 shuffles
12: 10 shuffles
13: 12 shuffles
14: 12 shuffles
15: 4 shuffles
16: 4 shuffles
17: 8 shuffles
18: 8 shuffles
19: 18 shuffles
20: 18 shuffles
Completing the
list up to 53 cards, he made some preliminary conclusions:
(For N=1 and N=2
the situation is doubtful; one can argue if so few cards are
"shufflable".)
Of course he
recognised these numbers, as you probably do, but he felt that some were
missing. Notably 7, 17, 23, 31, 41, 43 and 47 had less than the maximum number
of shuffles. But for these numbers he discovered that the original order would
also be restored after N-1 shuffles. For instance it takes 8 shuffles to
restore the order of 17 cards, which means the order is also restored after 2 x
8 = 16 shuffles. Up to N=53, no other values than the mentioned ones have this
property. Jimmy had the impression that he was on to something big, but since
his hands can only hold a limited number of cards, he asks for your assistance
to calculate the result for bigger values of N. (There is this small issue of
time-warping the results back some 70 years, but that will be solved some other
time.)
Let's define a
Jimmy-number as:
A maximum of 2000 integer numbers between 54 and 2000000000 (2 billion), both inclusive, each on a line by it self, terminated by a –1, which should not be processed.
For each number in the input one
line of output: "NUMBER is a Jimmy-number" or "NUMBER is not a
Jimmy-number", whichever appropriate, where NUMBER is replaced by the
input number.
54 101 144 197 1999999973 1999999975 -1 |
54 is not a Jimmy-number 101 is a Jimmy-number 144 is not a Jimmy-number 197 is a Jimmy-number 1999999973 is a Jimmy-number
1999999975
is not a Jimmy-number |
Problem setter: Little Joey