2000 - Mercer University



Tricks

(prog1.cpp or prog1.java)

Problem Description

There is a simple trick to see if any number n is divisible by 2 – just look at the last digit. If the last digit is divisible by 2, then n is divisible by 2. This same trick will work for 5 and 10 as well.

There is a simple trick to see if any number n is divisible by 3 – just add up the digits. If this sum is divisible by 3, then n is divisible by 3. This same trick also works for 9.

There are many such tricks – but they can become complicated. For example, the trick for 6 is to take the 1’s digit of n as it is, and then multiply all the other digits (10’s, 100’s etc.) of n by 4, and add them all up. The result is divisible by 6 if and only if n is divisible by 6. For 7, there is a sequence of six integers which repeats. Multiply the first (1’s) digit of n by 1, the second (10’s) digit of n by 3, the next (100’s) by 2, then 6, then 4, then 5, then 1, then 3, etc. The resulting sum is divisible by 7 if and only if n is divisible by 7.

Define a Trick for an integer k>1 as an infinite sequence a of integers such that:

• Every term ai in the sequence is between 0 and k-1, inclusive

• If you take any number n, and multiply its lowest digit (1’s place) by a1, its next lowest (10’s place) by a2, and so on, then add up all of those, the resulting sum is divisible by k if and only if n is divisible by k.

• At some finite point in the sequence a, a finite subsequence of terms repeats infinitely.

If we use parentheses to wrap the repeating part, then:

The trick for k=2 looks like this: 1 (0)

The trick for k=3 looks like this: (1)

The trick for k=6 looks like this: 1 (4)

The trick for k=7 looks like this: (1 3 2 6 4 5)

Given a selection of integers k, compute the trick for each.

Input (standard input)

Each line of input will have a single integer k, 2 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download