Skip to main content
9 of 18
added 1 character in body

Find All Digitroot Cyclic Sequences With Length Greater Than One

Input:

Given integers m and n which are the modular and multiplier for sequence.

Output:

Return all cyclic sequences of length greater than one for Digit roots of n * i in base m

  • \$1\$\$i\$\$m-1\$
  • \$1\$\$DR(n*i) \$\$m-1\$
  • \$DR(i) = i \$
  • \$DR(-m) = -1 \$
  • \$|DR(-x)| \equiv DR(x) \equiv -DR(x)\$ (mod \$ m-1) \$
  • \$DR(a+b) = DR(DR(a)+DR(b))\$
  • \$DR(a-b) \cong (DR(a)-DR(b))\$ (mod \$ m-1) \$

Example Input:

10 4

Example Output:

1 4 7
2 5 8

More details:

n=4, m=9
DR(4*1) -> 4
DR(4*4) -> 7
DR(4*7) -> 1 = first i

A cycle happens when going through numbers 1 trough m-1 taking digit root of n * i and then digit root of n * result of previous call and so on until returns to the first i.

Note that if there is no cycle taking digit root of n * i would simply result to i.

So we store this sequence in something like a hash set for all the i's and then return all the sequences.

Challenge

All the normal rules are applied excepts the answer with smaller sum of digit roots of each individual byte wins.