Alienese cycles

Question

Alienese refers to two "languages" in the show Futurama. In actuality, they are two ciphers of English text with a pictographic alphabet. The first is a simple substitution cipher, but the second is slightly more complex. The second is a type of autokey cipher that follows these steps:

• Take a word to be encrypted, e.g. FUTURAMA
• Replace each letter with its 0-index in the alphabet: [5, 20, 19, 20, 17, 0, 12, 0]
  • Note that, due to the next step, zero indexing is important and 1 indexing cannot be used
• Take the cumulative sums of the array: [5, 25, 44, 64, 81, 81, 93, 93]
• Modulo each term by 26 to bring it within bounds: [5, 25, 18, 12, 3, 3, 15, 15]
• Index into the alphabet: FZSMDDPP

We can iterate this process until we reach our original word again. For example, for FUTURAMA, the full list, space separated, is

FUTURAMA FZSMDDPP FEWILODS FJFNYMPH FOTGEQFM FTMSWMRD FYKCYKBE FDNPNXYC FIVKXUSU FNISPJBV FSASHQRM FXXPWMDP FCZOKWZO FHGUEAZN FMSMQQPC FRJVLBQS FWFALMCU FBGGRDFZ FGMSJMRQ FLXPYKBR FQNCAKLC FVIKKUFH FAISCWBI FFNFHDEM FKXCJMQC FPMOXJZB FUGURAZA FZFZQQPP FEJIYODS FJSAYMPH FOGGEQFM FTZFJZEQ FYXCLKOE FDACNXLP FIIKXUFU FNVFCWBV FSNSUQRM FXKCWMDP FCMOKWZO FHTHRNMA FMFMDQCC FRWILBDF FWSALMPU FBTTEQFZ FGZSWMRQ FLKCYKBR FQACAKLC FVVXXHSU FAVSPWOI FFASHDRZ FKKCJMDC FPZBKWZB FUTUEAZA FZSMQQPP FEWIYODS FJFNLZCU FOTGRQSM FTMSJZRD FYKCLKBE FDNPAKLP FIVKKUFU FNISCWBV FSASUQRM FXXPJZQC FCZOXWMO FHGURNZN FMSMDQPC FRJVYODF FWFAYMPU FBGGEQFZ FGMSWMRQ FLXPLXOE FQNCNKYC FVIKXHFH FAISPWBI FFNFUQRZ FKXCWMDC FPMOKWZB FUGUEAZA FZFZDDCC FEJILOQS FJSALZPH FOGGRQFM FTZFWMRD FYXCYKBE FDACAKLP FIIKKUFU FNVFPJOI FSNSHQEM FXKCJZDP FCMOXWZO FHTHEAZN FMFMQQPC FRWIYODF FWSAYMPU FBTTRDSM FGZSJMEQ FLKCLXBR FQACNKLC FVVXKUFH FAVSCWBI FFASUQRZ FKKCWMDC FPZBXJMO

and takes 104 steps to return to FUTURAMA. I conjecture that, for any non-empty string of letters, this process always returns to the original string in a finite number of steps.

---

You are to "prove" this conjecture. That is, write a program that takes a non-empty string of letters (ABCDEFGHIJKLMNOPQRSTUVWXYZ, or abcdefghijklmnopqrstuvwxyz, you may choose), and outputs the number of steps to return to the original input, by iterating this autokey cipher. Note that, by listing the terms, the list should either start or end with the input, which counts as either the first or last step.

You may take input in any convenient format, including taking the input as an array of characters. You may only take the input as an array of code points if you are unable to input as characters or as a string (e.g. brainfuck).

This is code-golf, so the shortest code in bytes wins.

Test cases

J -> 1
NK -> 2
TQR -> 52
NAK -> 4
AAAQ -> 1
CGCC -> 13
CAIRD -> 26
NNNNX -> 8
FUTURAMA -> 104
ALIENESE -> 104
NANNANNAN -> 16
ZBDMBCWJQJPWF -> 208
MUJJEKIBPULKWRHW -> 2704
HWGYIBRBRBLADVYTXL -> 5408

---

Interestingly, it appears as almost all words result in a number of steps either equal to 1 (a fixed point) or divisible by 13. We say a word is "interestingly-aliense" if this isn't the case, i.e. it is neither a fixed point, nor has a cycle length divisible by 13. We can see, by brute forcing all combinations of words with 2 or 3 letters, that the full list of these words is

NA NB NC ND NE NF NG NH NI NJ NK NL NM NN NO NP NQ NR NS NT NU NV NW NX NY NZ ANA ANB ANC AND ANE ANF ANG ANH ANI ANJ ANK ANL ANM ANN ANO ANP ANQ ANR ANS ANT ANU ANV ANW ANX ANY ANZ NAA NAB NAC NAD NAE NAF NAG NAH NAI NAJ NAK NAL NAM NAN NAO NAP NAQ NAR NAS NAT NAU NAV NAW NAX NAY NAZ NNA NNB NNC NND NNE NNF NNG NNH NNI NNJ NNK NNL NNM NNN NNO NNP NNQ NNR NNS NNT NNU NNV NNW NNX NNY NNZ

All of which either result in 2 or 4. We can also see that all of these contain the letter N. Indeed, we can try out some guesses for longer "interestingly-alienese" words based on this. For example, NNNNX has a cycle of 8 (NNNNX, NANAX, NNAAX, NAAAX, NNNNK, NANAK, NNAAK, NAAAK), and NANNANNAN has a cycle of 16, as shown above. Can you find any more, potentially with longer cycles?

Answer 1

K (ngn/k), ¹³ 12 bytes

#(26!+\)\65!

Try it online!

^{Git gud, Jelly. Only one byte ahead of an ASCII-only language? :P}

Takes uppercase input and computes the length of the loop. -1 byte thanks to ZippyMagician's observation that subtract 65 == mod 65.

#(26!+\)\65!     input: a string
         65!     modulo 65 ('A') from each letter (gives a numeric list)
 (     )\        repeat and collect until loop is found:
  26!+\            cumulative sum mod 26
#                length of the result

Answer 2

Wolfram Language (Mathematica), 60 bytes

If[#!=##2,1+Accumulate@#~Mod~26~#0~##,0]&[LetterNumber@#-1]&

Try it online!

Input a list of characters. Determines the period through recursion. Times out (or reaches the recursion limit) for larger test cases.

---

Wolfram Language (Mathematica), 69 65 63 bytes

s1//.j_/;!Drop[LetterNumber@s-1,-j]~Mod~#1:>j#&//#@2#@13&

Try it online!

Input a list of characters. Computes the period. The private-use characters are \[Function] and \[VectorLess].

                                              &             g: i =>
1//.j_/;!                                 :>j#                least power of i (=j) such that
         Drop[LetterNumber@s-1,-j]~Mod~#1                      no elements divisible by i outside the final j
                                               //#@2#@13&   g(2)*g(13)

Explanation:

Denote the \$n\$th accumulation of the list \$A=(a_1,a_2,...,a_l)\$ by \$A[n]=(a[n]_1,a[n]_2,...,a[n]_l)\$, and the length of the cycle of \$A\$ modulo \$m\$ by \$c_m(A)\$. Then, in general,
\$a[n]_k=\displaystyle\sum_{i=0}^{k-1}\frac{n^{(i)}}{1^{(i)}}a_{k-i}=a_k+\sum_{i=1}^{k-1}\frac{n^{(i)}}{1^{(i)}}a_{k-i}\$, where \$x^{(y)}\$ is the rising factorial. (These are the diagonals of Pascal's triangle).
By definition of a cycle, for any \$n\$ where \$A[n]\equiv A\pmod m\$, that is, \$a[n]_k\equiv a_k\pmod{m}\$ for all \$k\$, \$c_m(A)\mid n\$.

Since 2 and 13 are relatively prime, \$c_{26}(A)=\operatorname{LCM}(c_2(A),c_{13}(A))\$.

First consider cycles mod 2. Let \$2^x\$ be the least integer power of 2 such that \$2\mid a_i\$ for all \$a_i\le l-2^x\$, i.e. the final \$2^x\$ elements contain all those not divisible by 2. Consider the \$2^x\$th accumulation \$A[2^x]\$:
\$\begin{align*} a[2^x]_k&=a_k+\sum_{i=1}^{k-1}\frac{(2^x)^{(i)}}{1^{(i)}}a_{k-i}\\ &=a_k+\sum_{\substack{1\le &i<k\\&i<2^x}}\frac{(2^x)^{(i)}}{1^{(i)}}a_{k-i} \end{align*}\$
It can be fairly easily be shown that \$2\mid\frac{(2^x)^{(i)}}{1^{(i)}}\$ for all \$0<i<2^x\$, so \$A[2^x]\equiv A\pmod2\$ and \$c_2(A)\mid2^x\$.

Because of the way we defined \$2^x\$ there exists minimal \$p\$ such that \$a_p\not\equiv0\pmod2\$ and \$2^{x-1}\le l-p<2^x\$. Then
\$\begin{align*} a[2^{x-1}]_{p+2^{x-1}}&=a_{p+2^{x-1}}&&+\sum_{i=1}^{p+2^{x-1}-1}\frac{(2^{x-1})^{(i)}}{1^{(i)}}a_{p+2^{x-1}-i}\\ &=a_{p+2^{x-1}}&&+\sum_{i=1}^{2^{x-1}-1}\underbrace{\frac{(2^{x-1})^{(i)}}{1^{(i)}}}_{\equiv0\pmod2}a_{p+2^{x-1}-i}\\ &&&+\underbrace{\frac{(2^{x-1})^{(2^{x-1})}}{1^{(2^{x-1})}}a_p}_{\text{both }\not\equiv0\pmod2}\\ &&&+\sum_{i=1}^{p-1}\frac{(2^{x-1})^{(i+2^{x-1})}}{1^{(i+2^{x-1})}}\underbrace{a_{p-i}}_{\equiv0\pmod2}\\ &\not\equiv a_{p+2^{x-1}}&&\pmod2,\\ \end{align*}\$
using primality of 2 to show that the middle term must \$\not\equiv0\pmod2\$.

Therefore \$A[2^{x-1}]\not\equiv A\pmod2\$, so \$c_2(A)\not\mid2^{x-1}\$. Since 2 is prime, \$c_2(A)=2^x\$.
(\$p\$ does not exist if \$2^x=1\$, but in that case the only integer \$c_2(A)\mid1\$ is \$c_2(A)=1\$).

An analogous argument works mod 13, so we can let \$c_{13}(A)=13^y\$, where \$13^y\$ is defined in a similar fashion to \$2^x\$, and \$c_{26}(A)=2^x13^y\$.

Answer 3

Jelly, 14 12 bytes

ØAiⱮ’Ä%26ƊƬL

Try it online!

Answer 4

Ruby, 69 64 bytes

->s{g=h=s.bytes;1.step.find{r=0;g==h=h.map{|b|(r+=b-13)%26+65}}}

Try it online!

Answer 5

Python 3.8 (pre-release), 83 bytes

lambda s:(g:=lambda r,i=1:all(ord(c)%r==~r%2for c in s[:-i])or g(r,i*r)*r)(2)*g(13)

Try it online!

Port of my second Mathematica solution, and probably a bit easier to understand. Python plays nicer with out-of-bounds slices.

Answer 6

QBasic, 119 bytes

INPUT w$
n$=w$
1s=0
FOR i=1TO LEN(n$)
s=s+ASC(MID$(n$,i))-65
MID$(n$,i)=CHR$(s MOD 26+65)
NEXT
r=r+1
IF n$<>w$GOTO 1
?r

Try it at Archive.org!

Explanation

INPUT w$
n$ = w$

Input w$ (the original word) and set n$ (the next encrypted form) to w$.

1 s = 0

Label 1 is the start of our main loop. Initialize s (the cumulative sum) as 0.

FOR i = 1 TO LEN(n$)

Loop over the indices of the characters in n$.

s = s + ASC(MID$(n$, i)) - 65

Get the ASCII code of the ith character of n$, subtract 65, and add to the cumulative sum.

MID$(n$, i) = CHR$(s MOD 26 + 65)

Take s mod 26, add 65, convert from ASCII code, and set the ith character of n$ to that character.

NEXT
r = r + 1

End of FOR loop. Increment r (the number of repetitions we've gone through).

IF n$ <> w$ THEN GOTO 1

If the next encrypted form is different from the original word, loop.

PRINT r

Otherwise, print the number of repetitions.

---

In QB64, we can get down to 106 bytes using the extended forms of ASC instead of MID$:

INPUT w$
n$=w$
1s=0
FOR i=1TO LEN(n$)
s=s+ASC(n$,i)-65
ASC(n$,i)=s MOD 26+65
NEXT
r=r+1
IF n$<>w$GOTO 1
?r

Answer 7

JavaScript (Node.js),  62  61 bytes

Expects the input in lowercase, as suggested by @UnrelatedString (-1 byte).

f=(s,q)=>s!=q&&1+f(Buffer(s).map(c=>(t+=c+7)%26+97,t=0),q||s)

Try it online!

Or 56 bytes by taking a Buffer as input.

Commented

f = (s,            // s = input string
        q) =>      // q = reference string, initially undefined
  s != q &&        // stop as soon as s == q
  1 +              // otherwise: increment the final result
  f(               // do a recursive call:
    Buffer(s)      //   turn s into a Buffer
    .map(c =>      //   for each ASCII code c in the Buffer:
      (t += c + 7) //     add c + 7 to t
                   //     (where 7 is -(97 mod 26) + 26)
      % 26         //     reduce t modulo 26
      + 97,        //     add the ASCII code of 'a'
      t = 0        //     start with t = 0
    ),             //   end of map()
    q              //   pass the reference string q,
    || s           //   or s if q is still undefined (1st iteration)
  )                // end of recursive call

Answer 8

Joy, 166 bytes

DEFINE i == rotate 1 + rotate [0]swap[[dup dup size 1 - at]dip +[]cons concat]step rest[26 rem]map.
DEFINE a == 0 swap[ord 65 -]map dup i[equal not][i]while pop pop.

Crashes on the longer inputs, but as far as I can tell that's because of the implementation.
Explanation:

DEFINE sumScan == [0]swap[[dup dup size 1 - at]dip +[]cons concat]step rest.
DEFINE iter == rotate 1 + rotate (* increment counter *)
    sumScan[26 rem]map. (* sum scan, then mod 26 *)
DEFINE alienese == 0 swap[ord 65 -]map (* convert to numbers and set counter *)
    dup iter[equal not][iter]while pop pop. (* iterate until it's equal again, then pop off values that aren't counter *)

Answer 9

Python 3, 136 bytes

s=k=input();n=1
while 1:
 l=[ord(x)-65for x in s];s=''.join(chr(sum(l[:x+1])%26+65)for x in range(len(l)))
 if s==k:break
 n+=1
print(n)

Try it online!

Answer 10

Pari/GP, 79 bytes

s->d=Mod(1-x,x^#s);p=Mod(Polrev(Vecsmall(s))-65/d,26);i=1;while(p*d^i!=p,i++);i

Try it online!

Convert the string to an element \$P\$ in the ring \$\mathbb{Z}[X]/(26,X^n)\$, where \$n\$ is the length of the string, and find the smallest \$i>0\$ such that \$P*(1-X)^i=P\$.

Answer 11

Husk, 16 bytes

LU¡₁m(-65D
m%26∫

Try it online!

Explanation:

    m(-65D    # map codepoint - 65
LU¡₁          # length of longest unique prefix of iteration of function on next line
m%26∫         # map %26 on cumsum

Answer 12

Pyth, 23 bytes

l.usmC+65%sd26._m-Cd65N

Try it online!

l.usmC+65%sd26._m-Cd65N         # Full program
 .u                             # Collect until input found
                m     N         # Map over current value (variable d)
                  Cd            # Code point of d
                 -  65          # Minus 65 (Index of alphabet)
              ._                # Prefixes
    m                           # Map over (on prefixes with d)
          sd                    # Sum current prefix
         %  26                  # Modulo 26
      +65                       # Add 65 (Code point)
     C                          # ASCII char
   s                            # Join list
l                               # Length of whole scan-fixedpoint

Answer 13

05AB1E, 17 15 bytes

1µAskηOAsèDIQ}N

-2 bytes thanks to @Neil.

Input as a lowercase list of characters.

Try it online or verify all test cases (except for the last two, which time out).

Slightly faster minor alternative (thanks to @Neil):

Ask©1µηO₂%D®Q}N

Try it online or verify all test cases (except for the last two, which still time out).

Explanation:

1µ            # Loop until the counter is 1:
    k         #  Get the indices
   s          #  of the current list of characters (this will be the implicit
              #                                     input in the first iteration)
  A           #  in the lowercase alphabet
     η        #  Get the prefixes of this list
      O       #  And sum each inner prefix-list
       Asè    #  Modular index this list into the lowercase alphabet
          D   #  Duplicate it
           IQ #  Pop the copy, and check if it's equal to the input
              #  (if this is truthy, implicitly increase the counter by 1)
 }N           # After the loop: output the last 0-based index of the loop
              # (after which it is output implicitly as result)

Answer 14

Python, 108 bytes

i=s=[ord(c)-65for c in input()];a=0
while a<1or s!=i:s=[sum(s[:j+1])%26for j in range(len(i))];a+=1
print(a)

Attempt This Online!

This isn't a very interesting answer.

If only Python wasn't bad, we could have this for 105 bytes:

lambda s:1+len([*iter(lambda:(t:=([sum(t[:j+1])%26for j in range(len(s))])),(t:=[ord(c)-65for c in s]))])

Explanation:

lambda s:                      # xxx
[ord(c)-65for c in s]          # convert input string to list of alphabet indeces
(t:=)                          # assign to `t` initially
iter(lambda: ,)                # repeat until t recurs:
            [sum(t[:j+1])%26   # cumulative sums of `t`
      for j in range(len(s))]  
           (t:=)               # reassign to `t`
1+len([*])                     # length of repeating segment

But in the inner lambda, the list comprehension binds t as a free variable to the inner lambda, rather than a free variable to the outer lambda. If there was a way to do nonlocal in a lambda, we could avoid this.

Here's a bit of a hack that does actually work: Attempt This Online!

Answer 15

Japt v1.4.5, 24 bytes

;@=mnB å+ £BgXu26Ã eNg}a

Try it Switched to array of characters to save 1

;       - 2nd set of predef. Vars
@...}a  - repeat until true
          return number of times
=       - reassign U(input) by
mnB       * index each in ALPHA
å+        * cumulative sum
£Bg       * each: get[ABCD..]
Xu26Ã       at X%26
eNg     -  compare to orignal input

Answer 16

Charcoal, 32 28 25 bytes

ＩΠＥ⟦²¦¹³⟧ＸιＬ↨⌈Ｅ⮌θ∧﹪⌕αλιμι

Try it online! Link is to verbose version of code. Explanation: Uses @Nitrodon/@att's closed form formula: for each of the prime factors of 26, the offset from the end of the word of the first letter whose alphabet index is not divisible by that prime is rounded up to the next power of the prime and the two values are multiplied together.

   ⟦²¦¹³⟧                   Literal list `2,13`
  Ｅ                         Map over the two primes
          ι                 Current prime
         Ｘ                  Raised to power
                θ           Input word
               ⮌            Reversed
              Ｅ             Map over letters
                     λ      Current letter
                   ⌕α       Index in alphabet
                  ﹪         Modulo
                      ι     Current prime
                 ∧          Logical And
                       μ    Current index
             ⌈              Take the maximum
            ↨               Converted to base
                        ι   Current prime
           Ｌ                Take the length
 Π                          Take the product
Ｉ                           Cast to string
                            Implicitly print

Conveniently base conversion of zero is the empty list with length zero so that the prime power is simply 1 for a single letter or a word only containing the letter A.

Previous 28-byte brute-force version:

Ｗ¬№υθ«⊞υθ≔⭆θ§αΣＥ…θ⊕λ⌕αμθ»ＩＬυ

Try it online! Link is to verbose version of code. Explanation:

Ｗ¬№υθ«

Repeat until a cycle is detected. (Since cumulative sum is invertible, this will always be the original word.)

⊞υθ

Save the previous value.

≔⭆θ§αΣＥ…θ⊕λ⌕αμθ

For each letter, take the prefix so far, convert each letter to its alphabet index, take the sum, and take the letter at that index.

»ＩＬυ

Output the cycle length.

Much faster 36 32-byte version:

≔ＥＳ⌕αιθＷ¬№υθ«⊞υθ≔﹪ＥθΣ…θ⊕λ²⁶θ»ＩＬυ

Try it online! Link is to verbose version of code. Explanation:

≔ＥＳ⌕αιθ

Map the input letters to their alphabet index.

Ｗ¬№υθ«

Repeat until a cycle is detected. (Since cumulative sum is invertible, this will always be the original word.)

⊞υθ

Save the previous value.

≔﹪ＥθΣ…θ⊕λ²⁶θ

Calculate the cumulative sum modulo 26.

»ＩＬυ

Output the cycle length.

The intermediate values for a string of n+1 Ns can be read from the columns below, with N represented by 1 and A by 0:

0   1(1...)
1   10(10...)
2   1100(1100...)
3   1000(1000...)
4   11110000(11110000...)
5   10100000(10100000...)
6   11000000(11000000...)
7   10000000(10000000...)
8   1111111100000000(...)
    (...)
11  1000100000000000(...)
12  1111000000000000(...)
    (...)
15  1000000000000000(...)
    (...)

The 2ᵏᵗʰ row consists of a cycle of twice its length given by 2ᵏ 1s and 2ᵏ 0s. Over the next 2ᵏ-1 rows the 1s decay into a single 1 as they did for the first 2ᵏ rows, and then the next row doubles in cycle length.

Answer 17

ayr, 14 bytes

Unfortunately can't beat Bubbler's K answer, but it comes close. This is practically a direct translation, except for the fact that 65| is the same as _65+ in this specific case. Takes capital input.

:#(26|+\)$:65|

Explanation

:                    A non J-style train
                65|  Input mod 65
       ( ... )$:     Fixpoint
     +\                Cumulative sum
  26|                  Mod 26
 #                   Size

Answer 18

Haskell, 89 bytes

import Data.Char
s!o|t==o=1|True=1+t!o where t=scanl1(\x y->chr$(ord x+ord y)`mod`26+65)s

Try it online

(65 * 2 mod 26 conveniently equals 0.)

Answer 19

TI-Basic, 129 131 bytes

Input Str1
"ABCDEFGHIJKLMNOPQRSTUVWXYZ→Str2
Str1
Repeat Ans=Str1
cumSum(seq(inString(Str2,sub(Ans,I,1))-1,I,1,length(Ans
1+remainder(Ans,26→R
J+1→J
sub(Str2,ʟR(1),1
For(I,2,dim(ʟR
Ans+sub(Str2,ʟR(I),1
End
End
J

+1 byte if not run on a TI-84+/SE with the 2.53 MP OS by replacing remainder(Ans,26 with 26fPart(Ans/26.

Output is stored in Ans and displayed.

Answer 20

Burlesque, 32 bytes

m{**65.%}J1{{++26.%}pa}C~[-jFi+.

Try it online!

m{      # Map each char
 **     # Ord(a)
 65.%   # Mod 65
}       # <-- converted to alphabet index
J       # Duplicate
1       # Prefix Arg to infinite loop
{       #
 {      #
  ++    # Sum
  26.%  # Mod 26
 }      #
 pa     # Partial (applied to each init)
}       #
C~      # Infinite list of function evaluated successively on arg
[-      # Drop first element (original converted string)
j       # Swap in duplicated original
Fi      # Find index of original in list
+.      # Increment by 1 (0 indexed)

Answer 21

Python3, 101 bytes:

import itertools as i
s,c=(n:=[ord(j)-65for j in n]),1
while(s:=[j%26for j in i.accumulate(s)])!=n:c+=1

If anything, a cleaner and more efficient way to produce the cumulative sums.