Start from ones

Given a strictly positive integer n, follow these steps:

1. Create an array A with n 1s.
2. If A only has one element, terminate. Otherwise, starting from the first element, replace each pair of A with its sum, leaving the last element as is if A's length is odd, and repeat this step.

The output should contain A's state after each step in order from the first step to the last. Usage of standard loopholes is forbidden. This is a challenge, so the solution with the fewest bytes in each language wins.

Test cases

Each line in the output of these examples is a state. You can output via any reasonable format.

Input: 1



Input: 4

[1, 1, 1, 1]
[2, 2]


Input: 13

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[2, 2, 2, 2, 2, 2, 1]
[4, 4, 4, 1]
[8, 5]


Input: 15

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[2, 2, 2, 2, 2, 2, 2, 1]
[4, 4, 4, 3]
[8, 7]

• Can I copy this questions idea for the reverse order? Given number n, output stepwise A, and so on until you reach n 1s? – pixma140 Aug 22 at 11:22
• @pixma140 That would be essentially the same challenge, just with the output reversed afterwards. The modification is trivial. – Erik the Outgolfer Aug 22 at 11:39

Å1Δ=2ôO

Try it online!

MATL, 10 bytes

:gt2estnq

Try it online!

How it works

:     % Input n (implicit). Range [1 2 ... n]
g     % Convert to logical. Gives [1 1 ... 1]
% Do...while
t   %   Duplicate
2   %   Push 2
e   %   Reshape as 2-column matrix, in column-major order, padding with 0 if needed
s   %   Sum of each column
t   %   Duplicate
n   %   Number of elements
q   %   Subtract 1. This will be used as loop condition
% End (implicit). If top of the stack is not zero run new iteration
% Display stack, bottom to top (implicit)

L€+2/Ƭ

Try it online!

R, 65 bytes

-1 byte thanks to Giuseppe.

n=scan();while(T<2*n){cat(rep(+T,n%/%T),if(n%%T)n%%T,"\n");T=2*T}

Try it online!

Try it online!

Stax, 10 bytes

Çë⌐ⁿ┤5π»Å╡

Run and debug it

Procedure:

1. Generate 0-based range.
2. Repeatedly halve each element until all items are zero.
3. Calculate run-lengths for each unique array.

Annotated Source:

r       main:[0 .. 5]
{{hmgu  main:[[0 .. 5], [0, 0, 1, 1, 2, 2], [0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 0]]
m:GJ    main:"1 1 1 1 1 1"

JavaScript (V8), 109 bytes

f=n=>g(Array(n).fill(1));g=(a,i=1)=>{console.log(a);if(a[i]){for(;a[i];)a.splice(i-1,2,a[i-1]+a[i++]);g(a);}}

Try it online!

Ohm v2, 8 bytes

@Dv·Ω2σΣ

Try it online!

If output in scientific notation is allowed, otherwise:

Ohm v2, 9 bytes

@Dv·Ω2σΣì

Try it online!

• If the scientific notation numbers are actually a natural number type (such as floats) in Ohm then sure, it's reasonable. – Erik the Outgolfer Aug 22 at 12:48

Gaia, 12 bytes

ċ)¦⟨:q2/Σ¦⟩ª

Try it online!

ċ)¦		| generate array of n 1's (really, generate array of n 0's and increment each)
⟨      ⟩ª	| do the following until you get to a fixed point:
:q		| dup and print with a newline
2/	| split into groups of 2, with last group possibly being smaller
Σ¦	| take the sum

Perl 6, 38 bytes

{1 xx$_,*.rotor(2,:partial)>>.sum...1} Try it online! There's some shortcut to partial rotoring that I'm not remembering right now... Explanation: { } # Anonymous code block ... # Return a sequence 1 xx$_,            # Starting with a list of 1s with input length
*           # Where each element is
.rotor(2,:partial)        # The previous list split into chunks of 2 or less
>>.sum  # And each chunk summed
1  # Until the list is length 1

g x|x!!0<2=[x]|1>0=(g$(\z->filter(0/=)[-div(-z)2,div z 2])=<<x)++[x] Try it online! Works backwards from the list [n] until it reaches a list of just ones. Going forwards, I could get 80 bytes using chunksof from Data.List.Split: import Data.List.Split f x=g$1<$[1..x] g[n]=[[n]] g x=x:(g$map sum\$chunksOf 2 x)