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

• Timtech: Wouldn't [1,2,1] be incorrect because elements 1 are the same?
• McKay: I'm sorry, you're going to have to better define "lexicographically" better over the solution space.
• McKay: e.g. why isn't [0,1] better than [1,2] for f(2)?
• user3094403: @Timtech: No, because the first 1 is in another sublist than the second 1. A sublist is a contiguous section of the original list, so there are three sublists: [1] [1,2] [1]
• user12205: @ProgramFOX and everyone who voted to close this, since this question is tagged as code-golf I think we do have an objective winning criterion?

Answer 1

APL, 18

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

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

Example

 {+⌿~∨⍀⊖(⍵/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.

• primo: ).~)& -> .)^ for 2.

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

Jelly, 4 bytes

ọ2ドル‘

Try it online!

Explanation

ọ2ドル‘
 € For each integer from 1 to {the command-line argument}
ọ calculate the number of trailing zeroes in base
 2 2
 ‘ and increment {each resulting integer} {and output them}

Answer 5

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 6

Haskell, 40 characters

n&p=n:p++(n+1)&(p++n:p)
f n=take n1ドル&[]

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 7

Japt, 9 bytes

õȤq1 ÌÊÄ

Try it

Answer 8

Haskell, 29 bytes

(`take`t)
t=1:do x<-t;[x+1,1]

Try it online!