Start from onesl M7l Jn H Jj Bb 50L FXz Rr ldոOմKo PIiC3
Given a strictly positive integer n, follow these steps:
- Create an array A with n 1s.
- 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 code-golf 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
[1]
Input: 4
[1, 1, 1, 1]
[2, 2]
[4]
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]
[13]
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]
[15]
-
\\$\\begingroup\\$ Can I copy this questions idea for the reverse order? Given number n, output stepwise A, and so on until you reach n 1s? \\$\\endgroup\\$ – pixma140 6 hours ago
-
6\\$\\begingroup\\$ @pixma140 That would be essentially the same challenge, just with the output reversed afterwards. The modification is trivial. \\$\\endgroup\\$ – Erik the Outgolfer 6 hours ago
16 Answers
05AB1E, 7 bytes
Å1Δ=2ôO
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!
Avoids recursion. In R, %/% is integer division and %% is the modulo. For each power of 2 k=2^i, we need to print n%/%k times the value k, and then n%%k if that value is non zero. Do this for all powers of 2 smaller than \\$2n-1\\$.
Here I am using T instead of k, since it is initialized as TRUE which is converted to 1. I still need to print +T instead of T to avoid a vector of TRUEs in the output.
-
\\$\\begingroup\\$ Beat me by about 5 minutes and almost 60 bytes... But Giuseppe is right, it doesn't output the final step. \\$\\endgroup\\$ – Sumner18 4 hours ago
-
\\$\\begingroup\\$ @Giuseppe Ah yes, thanks, I hadn't seen that needed to be output as well. Actually, the final number was output only when
nis a power of 2. I switched to a while loop and think the output is correct now in all cases. \\$\\endgroup\\$ – Robin Ryder 3 hours ago -
\\$\\begingroup\\$ @Sumner18 Should be fixed now. \\$\\endgroup\\$ – Robin Ryder 3 hours ago
-
\\$\\begingroup\\$
+Tis shorter thanT+0\\$\\endgroup\\$ – Giuseppe 3 hours ago -
\\$\\begingroup\\$ @Giuseppe Thanks, I knew I was forgetting something. \\$\\endgroup\\$ – Robin Ryder 3 hours ago
MATL, 10 bytes
:g`t2estnq
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)
Python 3, 62 bytes
def f(i,j=1):l=i//j*[j]+[i%j][:i%j];print(l);l[1:]and f(i,j*2)
Try it online!
Python 2: 60 bytes
Python 3.8: 60 bytes
Recursive function. For each step, it constructs a list of powers of 2, such that the sum is smaller than or equal to the given integer. It then appends the remainder, if it is larger than 0.
Jelly, 6 bytes
-1 byte thanks to Erik the Outgolfer.
1x+2/Ƭ
Try it online!
Jelly, 6 bytes
L€+2/Ƭ
Try it online!
Wolfram Language (Mathematica), 55 bytes
Most@FixedPointList[Tr/@#~Partition~UpTo@2&,1~Table~#]&
Try it online!
Pyth, 10 bytes
.u+McN2*]1
Try it online!
.u # Apply until a result is repeated, return all intermediate steps: lambda N,Y:
+M # map by + (reduce list on +):
cN2 # chop N (current value) into chunks of 2, last one is shorter if needed
*]1Q # [1] * Q (implicit Q = input)
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...
JavaScript, 55 bytes
f=(n,t=1,r=n)=>r>t?t+[,f(n,t,r-t)]:n>t?r+`
`+f(n,t+t):r
Try it online!
This is basically the golfed version of following codes:
function f(n) {
var output = '';
t = 1;
for (t = 1; ; t *= 2) {
for (r = n; r > t; r -= t) {
output += t + ',';
}
output += r;
if (n <= t) break;
output += '\\n';
}
return output;
}
J, 28 bytes
[:(echo]_2+/\\])^:(1<#)^:_#&1
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!
-
\\$\\begingroup\\$ If the scientific notation numbers are actually a natural number type (such as floats) in Ohm then sure, it's reasonable. \\$\\endgroup\\$ – Erik the Outgolfer 5 hours ago
Charcoal, 19 bytes
ＮθＩＥ↨⊖⊗θ²Ｅ⪪Ｅθ¹Ｘ²κＬλ
Try it online! Link is to verbose version of code. Uses Charcoal's default output format, which is one number per line, with subarrays double-spaced from each other. Explanation:
Ｎθ Input `n` into a variable
θ `n`
⊗ Doubled
⊖ Decremented
↨ ² Converted to base 2 (i.e. ceil(log2(input)))
Ｅ Map
Ｅθ¹ List of `1`s of length `n`
⪪ Split into sublists of length
² Literal `2`
Ｘ To power
κ Loop index
Ｅ Map over each sublist
Ｌλ Take the length
Ｉ Cast to string for implicit print
K (oK), 15 bytes
{+/'0N 2#x}\\n#1
Try it online!
Perl 5, 46 bytes
say$_="1 "x<>;say while s/(\\d+) (\\d+)/$1+$2/ge
Try it online!
Output is space separated.
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
