19
\$\begingroup\$

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

[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]
\$\endgroup\$
  • \$\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 Aug 22 '19 at 11:22
  • 10
    \$\begingroup\$ @pixma140 That would be essentially the same challenge, just with the output reversed afterwards. The modification is trivial. \$\endgroup\$ – Erik the Outgolfer Aug 22 '19 at 11:39

24 Answers 24

6
\$\begingroup\$

05AB1E, 7 bytes

Å1Δ=2ôO

Try it online!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Python 3, 57 bytes

def f(i,j=1):print(i//j*[j]+[i%j][:i%j]);i>j and f(i,j*2)

Try it online!

Python 2, 51 bytes

def f(i,j=1):print i/j*[j]+[i%j][:i%j];i>j>f(i,j*2)

Try it online!

-6 bytes total thanks to tsh

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Python 3 61 bytes: def f(i,j=1):l=i//j*[j]+[i%j][:i%j];print(l);i>j and f(i,j*2); Python 2 55 bytes: def f(i,j=1):l=i/j*[j]+[i%j][:i%j];print l;i>j>f(i,j*2) \$\endgroup\$ – tsh Aug 23 '19 at 4:09
  • \$\begingroup\$ @tsh Of course, thanks! i>j didn't work in my previous solution and I forgot to try it afterwards. \$\endgroup\$ – Jitse Aug 23 '19 at 6:59
3
\$\begingroup\$

Jelly, 6 bytes

L€+2/Ƭ

Try it online!

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Beat me by about 5 minutes and almost 60 bytes... But Giuseppe is right, it doesn't output the final step. \$\endgroup\$ – Sumner18 Aug 22 '19 at 13:50
  • \$\begingroup\$ @Sumner18 Should be fixed now. \$\endgroup\$ – Robin Ryder Aug 22 '19 at 14:14
  • \$\begingroup\$ +T is shorter than T+0 \$\endgroup\$ – Giuseppe Aug 22 '19 at 14:15
  • \$\begingroup\$ @Giuseppe Thanks, I knew I was forgetting something. \$\endgroup\$ – Robin Ryder Aug 22 '19 at 14:16
3
\$\begingroup\$

Pyth, 10 bytes

.u+McN2m1

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
       m1Q  # map(1, range(Q)) (implicit Q = input)

-1 byte thanks to FryAmTheEggman

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 55 54 bytes

Last@Reap[1~Table~#//.a_:>Tr/@Sow@a~Partition~UpTo@2]&

Try it online!

Finally, Sow/Reap beats an alternative!

Returns a singleton list containing a list of the steps.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

K (oK), 15 17 bytes

{{+/'0N 2#x}\x#1}

Try it online!

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

J, 20 17 bytes

_2+/\&.>^:a:<@#&1

Try it online!

-5 bytes thanks to Bubbler

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 20 bytes by eliminating [: and (). \$\endgroup\$ – Bubbler Nov 14 '19 at 9:37
  • \$\begingroup\$ Nice catch! Thanks. \$\endgroup\$ – Jonah Nov 14 '19 at 12:39
  • \$\begingroup\$ 17 bytes. \$\endgroup\$ – Bubbler Jan 10 at 5:25
  • \$\begingroup\$ Thanks @Bubbler. Out of curiosity, what brought you back to this one? \$\endgroup\$ – Jonah Jan 10 at 6:04
  • 1
    \$\begingroup\$ I just browse through random challenges that appear on "Active" to see if I can add an answer or improve existing answer(s) further. \$\endgroup\$ – Bubbler Jan 10 at 6:07
2
\$\begingroup\$

Jelly, 6 bytes

-1 byte thanks to Erik the Outgolfer.

1x+2/Ƭ

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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;
}
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Japt -R, 13 bytes

_ò mx}hUõÎü)â

Try it

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Brachylog, 17 bytes

;1j₍ẹẉ₂{ġ₂+ᵐ}ⁱ.ẉȮ

Try it online!

As horribly long as this is, I still feel a bit clever for using .ẉȮ: the obvious way to print something, then check if its length is 1 would be ẉ₂l1, ẉ₂~g, or ẉ₂≡Ȯ, where the in the last one is necessary because ẉ₂ unifies its input and output before it prints them, and Ȯ is pre-constrained to be a list of length 1, so the unification fails if the input is not a list of length 1. At the end of a predicate, this feature of ẉ₂ can be circumvented, however, by using the output variable instead of subscripting : .ẉȮ first unifies its input with the output variable, then prints the output variable, and only afterwards unifies the output variable with Ȯ.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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" 
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 19 bytes

NθIE↨⊖⊗θ²E⪪Eθ¹X²κLλ

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:

Nθ                  Input `n` into a variable
       θ            `n`
      ⊗             Doubled
     ⊖              Decremented
    ↨   ²           Converted to base 2 (i.e. ceil(log2(input)))
   E                Map
           Eθ¹      List of `1`s of length `n`
          ⪪         Split into sublists of length
               ²    Literal `2`
              X     To power
                κ   Loop index
         E          Map over each sublist
                 Lλ Take the length
  I                 Cast to string for implicit print
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 46 bytes

say$_="1 "x<>;say while s/(\d+) (\d+)/$1+$2/ge

Try it online!

Output is space separated.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Haskell, 75 bytes

g.pure
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)

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Keg, 30 bytes

(|1){!1>|^(:. ,")^
,(!2/|+")}.

Try it online!

I've actually been meaning to complete this challenge for a while (I mean, I emailed myself the link to it so I would remember), but I've never gotten around to doing so until now!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

GolfScript, 24 bytes

A horribly long answer... golfed out 1 byte by using a hard-to-read output format

~[1]*{..2/{{+}*}%\,(}do;

Try it online!

Explanation

~                        // Dump the contents of the input string
 [1]*                    // Create a 1-list with the length of the input string
     {              }do  // do ... while
                 \,(     // the length of the array is larger than 1
      .                  // Extra evolution step that we need to keep
       .                 // Create a copy of the input
        2/               // That splits into parts of 2 items
          {    }%        // For each over the splitted array:
           {+}*          // Reduce the item with addition
                         // e.g. [1] -> [1], [1 2] -> [3], etc.
                       ; // Discard the abundant copy
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\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 Aug 22 '19 at 12:48
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

APL, 28 chars

{1≢≢⎕←⍵:∇+/(⌈.5×≢⍵)2⍴⍵,0}⍴∘1

vector of 1s

⍴∘1

output the argument and check if length is different than 1: if so, go on

1≢≢⎕←⍵:

get half of the length and round up

⌈.5×≢⍵

reshape into a nx2 matrix adding a trailing 0 if needed

(⌈.5×≢⍵)2⍴⍵,0

sum of row by row

+/

recurse

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.