Given N, output n-th element of ['A', 'B', 'AB', 'C', 'D', 'CD', 'ABCD', 'E', ...]?

Question

Consider the following list:

expected = [
'A',
'B',
'AB',
'C',
'D',
'CD',
'ABCD',
'E',
'F',
'EF',
'G',
'H',
'GH',
'EFGH',
'ABCDEFGH',
'I',
'J',
'IJ',
'K',
'L',
'KL',
'IJKL',
'M',
'N',
'MN',
'O',
'P',
'OP',
'MNOP',
'IJKLMNOP',
'ABCDEFGHIJKLMNOP',
...
]

Here's one way to look at it - you're learning how to write Chinese characters and want to learn increasingly big chunks of them, rehearsing them as you go. You start with A, then go with B, then there's already a sequence that is a pair of two so you combine it. Then you go with C and D, make another pair, practice it. Then you rehearse: ABCD. Then the same goes with E up to H, then rehearse: ABCDEFGH. The list is infinite.

The goal is to generate and print out an n-th element of this list, indexes going up from zero. Assume that after 'Z', you get 'A' again.

The winning criteria is source code length.

• Jonathan Allan: Not sure I get it, when is BC or CDEF? What decides what we concatenate and what we don't? How is it infinite if it starts at A again after Z (you mean at some point after ABCDEFGHIJKLMNOPQRSTUVWXZ we have ABCDEFGHIJKLMNOPQRSTUVWXZAB or something?)
• Stewie Griffin: Test case for letters that wrap around is appreciated (x,y,z,a,b...).
• JungHwan Min: I strongly recommend that you use the Sandbox in the future to improve your challenge. There, you would receive feedback from fellow users to make sure your challenge is suitable for the main PPCG site! Personally, I'd leave a post in the Sandbox for at least 2 days so that everybody has a chance to see the post.
• d33tah: @JungHwanMin: not OK to infinitely print the list. I'd pass returning a list of integers.
• Jonathan Allan: What does "I'd pass returning a list of integers" mean? Is output of a list of integers acceptable or not? If so what about "Assume that after 'Z', you get 'A' again" - should this be the case with this output format (after i+25 we get i again)? (Also update the post with the relevant information - don't leave specification to be found in comments.)

Answer 1

Python 2, 53 bytes

x,y=0,1
exec"x^=y-x;y+=x/y;"*input()
print range(x,y)

Try it online!

Similar to this construction with the transformation x = u-v, y = u

• xnor: What a nice simplification! The first statement can be x^=y-x for -1 byte.
• KSab: @xnor oh right, silly me

Answer 2

JavaScript (ES6), 59 bytes

We can save 2 bytes by making the sequence 1-indexed and using a simplification similar to the one used by KSab:

n=>(x=g=y=>n?g(y+=y==(x^=y-x),n--):x<y?[x++,...g(y)]:[])(1)

Try it online!

---

JavaScript (ES6), 61 bytes

Returns a list of non-wrapping integers.

n=>(g=v=>n?g(u&-u^v?v*2:!!u++,n--):v?[u-v,...g(v-1)]:[])(u=1)

Try it online!

Based upon a construction by Donald Knuth. Related OEIS entry: A182105.

How?

This is a two-stage recursive function.

We first build the sequence \$(u_n,v_n)\$ defined as \$(u_1,v_1)=(1,1)\$ and:

$$(u_{n+1},v_{n+1})=\begin{cases}(u_{n}+1,1),&\text{if }(u_{n}\operatorname{AND}-u_{n})=v_{n}\\(u_{n},2v_{n}),&\text{otherwise}\end{cases}$$

During the second pass, we build the list \$[u_n-v_n,u_n-v_n+1,\dots,u_n]\$ and eventually return it.

---

JavaScript (ES6), 97 bytes

Returns wrapping uppercase letters.

n=>(s=i='',g=v=>(s+=String.fromCharCode(65+i++%26),n--)?g(u&-u^v?v*2:!!u++):s.substr(u-v,v))(u=1)

Try it online!

Or 91 bytes in lowercase.

Answer 3

Python 2, 60 bytes

u=v=1
exec"v=u/v%2or 2*v;u+=1/v;"*input()
print range(u-v,u)

Try it online!

Based on Arnauld's use of Knuth's construction. The condition u&-u==v can be replaced with a simpler condition u/v%2>0, or alternatively u&v>0, since v is always a power of 2 that u is divisible by.

Answer 4

Wolfram Language (Mathematica), (削除) 80 (削除ここまで) 71 bytes

Range@#2+#-#2&@@Nest[If[#~BitAnd~-#==#2,{#+1,1},{#,2#2}]&@@#&,{1,1},#]&

Try it online!

Returns a list of integers instead of a wrapping string of alphabet. 0-indexed.

Uses OEIS A182105, thanks to @Arnauld.

Printing the list indefinitely, 54 bytes

Do[j=Range@i;#∣i&&Print@j[[-#;;]]&/@(2^j/2),{i,∞}]

Try it online!

1-indexed. The TIO version has lim instead of ∞ to prevent crashes.

Answer 5

Python 2, (削除) 93 (削除ここまで) (削除) 89 (削除ここまで) 82 bytes

def f(n):r=[];C=1;exec"p=C%2or 2*p;r+=[p];C=r.count(p);"*n;return range(C*p-p,C*p)

Try it online!

Returns a list of integers. Similar to Arnauld's Javascript approach.

Answer 6

Jelly, 16 bytes

1;ẎṀ+ƊẎQṭƊƊ¡ị@‘Ṿ

Try it online! TIO link works well up to and including \13ドル\$.

Full program. Prints ,-separated list of integers.

Answer 7

Charcoal, (削除) 45 (削除ここまで) (削除) 42 (削除ここまで) 35 bytes

FN⊞υ⎇∧›Lυ1=L§υ±1L§υ±2+⊟υ⊟υ§αL⭆υκ⮌⊟υ

Try it online! Link is to verbose version of code. 1-indexed. I couldn't find a simple formula to generate the result so I simply followed the procedure given in the question. Explanation:

FN

Repeat the given number n times.

⊞υ

Push the next element to the predefined empty array u, calculated as...

⎇∧›Lυ1=L§υ±1L§υ±2

... if there is more than one element in u and the last two elements have the same length...

+⊟υ⊟υ

... then append the penultimate element to the last element (which builds up the result in reverse order)...

§αL⭆υκ

... otherwise the next letter can be found by counting how many letters we've added so far and cyclically indexing into the predefined uppercase alphabet. (Taking either the sum of length or length of sum fails when the list is empty, and mapping the list into a string saves two bytes over special-casing an empty list.)

⮌⊟υ

Take the last element of u, which is the reversed nth element of the desired list, and implicitly print the reverse.