Generate lists in which every sublist has a unique element

Question

The problem is defined as follows:

Create a function that takes an integer and returns a list of integers, with the following properties:

• Given a positive integer input, n, it produces a list containing n integers ≥ 1.
• Any sublist of the output must contain at least one unique element, which is different from all other elements from the same sublist. Sublist refers to a contiguous section of the original list; for example, [1,2,3] has sublists [1], [2], [3], [1,2], [2,3], and [1,2,3].
• The list returned must be the lexicographically smallest list possible.

There is only one valid such list for every input. The first few are:

f(2) = [1,2]         2 numbers used
f(3) = [1,2,1]       2 numbers used
f(4) = [1,2,1,3]     3 numbers used

Answer 1

APL, 18

{+⌿~∨⍀⊖(⍵/2)⊤2×⍳⍵}

1 + number of trailing zeros in base 2 of each natural from 1 to N.

Example

      {+⌿~∨⍀⊖(⍵/2)⊤2×⍳⍵} 32
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6

Answer 2

GolfScript (20 18 chars)

{,{.)^2base,}%}:f;

This is a simple binary ruler function, A001511.

Equivalently

{,{).~)&2base,}%}:f;
{,{~.~)&2base,}%}:f;
{,{).(~&2base,}%}:f;
{,{{1&}{2/}/,)}%}:f;

Thanks for primo for saving 2 chars.

Answer 3

Sclipting, 26 23 characters

감⓶上가增❷要❶감雙是가不감右⓶增⓶終終丟丟⓶丟終并

This piece of code generates a list of integers. However, if run as a program it will concatenate all the numbers together. As a stand-alone program, the following 25-character program outputs the numbers separated by commas:

감⓶上가增❷要감嚙是가不⓶增⓶終終丟丟⓶丟껀終合鎵

Example output:

Input: 4

Output: 1,2,1,3

Input: 10

Output: 1,2,1,3,1,2,1,4,1,2

Answer 4

Python 2.7, 65 characters

print([len(bin(2*k).split('1')[-1]) for k in range(1,input()+1)])

The number of trailing zeros in 2, 4, 6, ..., 2n.

Answer 5

Haskell, 40 characters

n&p=n:p++(n+1)&(p++n:p)
f n=take n$1&[]

Example runs:

λ: f 2
[1,2]
λ: f 3
[1,2,1]
λ: f 4
[1,2,1,3]
λ: f 10
[1,2,1,3,1,2,1,4,1,2]
λ: f 38
[1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2]

Answer 6

Golfscript - 1 character

,

I'm pretty sure this meets the criteria, but it does seem weirdly worded.