Find All Digitroot Cyclic Sequences With Length Greater Than One

Question

Digital sum, DR, Digit root is the iterative process of summing digits of a number until you end up with a single digit root number: e.g. digit root of 12345 is 6 since 1 + 2 + 3 + 4 + 5 = 15 = 1+5. Also look at Digit root challenge.

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.

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

Example Input:

9 4

Example Output:

1 4 7
2 5 8

More details:

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

A cycle happens when going through numbers 1 trough m 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 code-golf rules are applied excepts the answer with smaller sum of digit roots of each individual byte wins.

Example program of how to calculate the Σ digit sums of your code:

from sys import stdin
score=lambda s:sum((ord(c)-1)%9+1for c in s if ord(c)>0)
bytes=lambda s:"".join(str([ord(c)for c in s]).replace(',','').replace(']','').replace('[',''))
dr_bytes=lambda s:"".join(str([(ord(c)-1)%9+1for c in s]).replace(',',' +').replace(']',' =').replace('[',''))
code="\n".join(stdin.readlines())
print(bytes(code))
print(dr_bytes(code), end=' ')
print(score(code))

Answer 1

Jelly, score = 104

x⁹Sḃ³Ṛḷ/)ƬR1¦z7MṖ’ƊPḄƊoEƊÐḟQ€

A dyadic Link accepting m on the left and n on the right that yields a list of lists of integers (each integer being a "digit").

Try it online!

The byte code is (see Jelly's code-page here):

120 137 83 231 131 182 218 47 41 152 82 49 5 122 55 77 203 253 145 80 172 145 111 69 145 15 235 81 12

So the score is:

3+2+2+6+5+2+2+2+5+8+1+4+5+5+1+5+5+1+1+8+1+1+3+6+1+6+1+9+3 = 104

How?

x⁹Sḃ³Ṛḷ/)ƬR1¦z7MṖ’ƊPḄƊoEƊÐḟQ€ - Link: m; n
         Ƭ                    - collect inputs while unique, starting with m, applying:
        )                     -   for each d (where m is implicitly treated as [1..m]):
 ⁹                            -     n
x                             -     d repeated n times                    |
  S                           -     sum -> n×d            (cheaper than ×)|
    ³                         -     m
   ḃ                          -     n×d to bijective base m
     Ṛ                        -     reverse                               |
       /                      -     reduce by:                            |
      ḷ                       -       left argument       (cheaper than Ṫ)|
          R1¦                 - change the leading m to [1..m]
             z7               - transpose with filler 7   (cheaper than Z)|
                         Ðḟ   - discard those for which:
                        Ɗ     -   last three links as a monad:
                     Ɗ        -     last three links as a monad:
                  Ɗ           -       last three links as a monad:
               M              -         maximal (1-indexed) indices
                Ṗ             -         remove the last one
                 ’            -         decrement
                   P          -        product
                    Ḅ         -        from binary [cheap no-op to help use Ɗ]
                       E      -      all equal?
                      o       -      logical OR
                           Q€ - deduplicate each

Answer 2

05AB1E, score: 139 125 (33 bytes)

Lε¸ΔR¬I*¹L¤иæ{ÙésèRнšRÙ].¡W]€нʒg≠

Inputs in the order \$m,n\$. Outputs as a list of lists.

Try it online (with ¹L¹иæ{Ùé replaced with ¯¹ƒ¹LNã«} so it won't timeout).

The codegolfed program would be 31 28 bytes:

Lε¸Δ¤I*¹L¹иæêésèθªÙ].¡ß}€нʒg≠

Try it online (with ¹L¹иæê replaced with ¯¹ƒ¹LNã«} so it won't timeout).

The bytes for this codegolfed program (in the 05AB1E codepage) would result in a score of 154 145:

[76, 6, 184, 17, 164, 73, 42, 185, 76, 185, 12, 230, 234, 233, 115, 232, 9, 170, 217, 93, 46, 161, 223, 125, 128, 14, 1, 103, 22]
4+6+4+8+2+1+6+5+4+5+3+5+9+8+7+7+9+8+1+3+1+8+7+8+2+5+1+4+4=145

Try it online.

To improve this score, the following modifications have been made:

• -3 score: θ [pop and push last item] ([9] → 9) to Rн [reverse; pop and push first item] ([82,14] → 1+5=6)
• -1 score: ß [pop and push minimum] ([223] → 7) to W [push minimum without popping] ([87] → 6)
• -6 score: ¤ ... ª [push last item without popping & append to list] ([164,170] → 2+8=10) to R¬ ... šR [reverse; push first item without popping & prepend to list; reverse] ([82,172,154,82] → 1+1+1+1=4)
• -5 score: } [close loop] ([125] → 8) to ] [close all loops] ([93] → 3)
• -2 score: ê [sorted uniquify] ([234] → 9) to {Ù [sort; uniquify] ([123,217] → 6+1=7)
• -3 score: second ¹ [push first input] ([185] → 5) to ¤ [push last item without popping] ([164] → 2)

Explanation (of the codegolfed program):

For a language that's (almost) literally called Base (05AB1E converted from hexadecimal to a base-10 integer, and then to the default base-64 string), the lack of bijective base builtins is pretty annoying.. This is now done manually (with portion ¹L¹иæêésè - which will timeout for \$m\geq4\$).

L                 # Push a list in the range [1, (implicit) input `m`]
 ε                # Map each integer to:
  ¸               #  Wrap it in a list
   Δ              #  Continue looping until the list no longer changes:
    ¤             #   Push the last item of the list (without popping)
     I*           #   Multiply it by the second input `n`
       ¹L¹иæêésè  #   Convert it to bijective base-`m`:
       ¹L         #    Push a list in the range [1, input `m`]
         ¹и       #    Repeat it `m` amount of times
           æ      #    Get the powerset of this list
            ê     #    Uniquify and sort this list of lists
             é    #    (Stable) sort again by length
              s   #    Swap so the `i*n` is at the top
               è  #    Index it into this list
        θ         #   Pop and only leave the last value
         ª        #   Append this to the list
          Ù       #   Uniquify this list
 ]                # Close both the inner fixed-point loop and map
  .¡ }            # Group the resulting lists by:
    ß             #  Their minimum
      €           # For each group:
       н          #  Only leave the first list
        ʒ         # Filter the remaining lists by:
         g        #  Where the length of the list
          ≠       #  Is NOT 1
                  # (after which the result is output implicitly)

Answer 3

Python 3, score = 937 (228 bytes)

I=int(input())
R=int(input())
D=lambda v:v and~-v%I+1
J=lambda v:[D(R*m)for m in v]
d=list(range(1,I+1))
m=J(d)
v=[]
while m not in v:v+=[m];m=J(m)
exit([frozenset(m)for m in zip(*([d]+v))if max(m)in m[1:]!=m[0]==max(m)>min(m)])

Try it online!

Bytes:

73 61 105 110 116 40 105 110 112 117 116 40 41 41 10 10 82 61 105 110 116 40 105 110 112 117 116 40 41 41 10 10 68 61 108 97 109 98 100 97 32 118 58 118 32 97 110 100 126 45 118 37 73 43 49 10 10 74 61 108 97 109 98 100 97 32 118 58 91 68 40 82 42 109 41 102 111 114 32 109 32 105 110 32 118 93 10 10 100 61 108 105 115 116 40 114 97 110 103 101 40 49 44 73 43 49 41 41 10 10 109 61 74 40 100 41 10 10 118 61 91 93 10 10 119 104 105 108 101 32 109 32 110 111 116 32 105 110 32 118 58 118 43 61 91 109 93 59 109 61 74 40 109 41 10 10 101 120 105 116 40 91 102 114 111 122 101 110 115 101 116 40 109 41 102 111 114 32 109 32 105 110 32 122 105 112 40 42 40 91 100 93 43 118 41 41 105 102 32 109 97 120 40 109 41 105 110 32 109 91 49 58 93 33 61 109 91 48 93 61 61 109 97 120 40 109 41 62 109 105 110 40 109 41 93 41

Digit root of those bytes:

1 + 7 + 6 + 2 + 8 + 4 + 6 + 2 + 4 + 9 + 8 + 4 + 5 + 5 + 1 + 1 + 1 + 7 + 6 + 2 + 8 + 4 + 6 + 2 + 4 + 9 + 8 + 4 + 5 + 5 + 1 + 1 + 5 + 7 + 9 + 7 + 1 + 8 + 1 + 7 + 5 + 1 + 4 + 1 + 5 + 7 + 2 + 1 + 9 + 9 + 1 + 1 + 1 + 7 + 4 + 1 + 1 + 2 + 7 + 9 + 7 + 1 + 8 + 1 + 7 + 5 + 1 + 4 + 1 + 5 + 4 + 1 + 6 + 1 + 5 + 3 + 3 + 6 + 5 + 1 + 5 + 6 + 2 + 5 + 1 + 3 + 1 + 1 + 1 + 7 + 9 + 6 + 7 + 8 + 4 + 6 + 7 + 2 + 4 + 2 + 4 + 4 + 8 + 1 + 7 + 4 + 5 + 5 + 1 + 1 + 1 + 7 + 2 + 4 + 1 + 5 + 1 + 1 + 1 + 7 + 1 + 3 + 1 + 1 + 2 + 5 + 6 + 9 + 2 + 5 + 1 + 5 + 2 + 3 + 8 + 5 + 6 + 2 + 5 + 1 + 4 + 1 + 7 + 7 + 1 + 1 + 3 + 5 + 1 + 7 + 2 + 4 + 1 + 5 + 1 + 1 + 2 + 3 + 6 + 8 + 4 + 1 + 3 + 6 + 3 + 5 + 2 + 2 + 7 + 2 + 8 + 4 + 1 + 5 + 3 + 3 + 6 + 5 + 1 + 5 + 6 + 2 + 5 + 5 + 6 + 4 + 4 + 6 + 4 + 1 + 1 + 3 + 7 + 1 + 5 + 5 + 6 + 3 + 5 + 1 + 7 + 3 + 4 + 1 + 5 + 6 + 2 + 5 + 1 + 1 + 4 + 4 + 3 + 6 + 7 + 1 + 1 + 3 + 3 + 7 + 7 + 1 + 7 + 3 + 4 + 1 + 5 + 8 + 1 + 6 + 2 + 4 + 1 + 5 + 3 + 5 = 937