48
\$\begingroup\$

I found this sequence while working on Evolution of OEIS, but never got around to posting it as an answer. After writing a reference implementation in Mathematica, I thought this is a fun exercise to do as a separate challenge though, so here we go.

Let's build a numeric fission reactor! Consider a positive integer N. As an example, we'll look at 24. To fission this number, we have to find the largest number of consecutive positive integers that sum to N. In this case, that's 7 + 8 + 9 = 24. So we've split 24 into three new numbers. But this wouldn't be much of a fission reactor without chain reactions. So let's recursively repeat the process for these components:

       24
       /|\
      / | \
     /  |  \
    7   8   9
   / \     /|\
  3   4   / | \
 / \     /  |  \
1   2   2   3   4
           / \
          1   2

Notice that we stop the process whenever the number cannot be decomposed into smaller consecutive integers. Also note that we could have written 9 as 4 + 5, but 2 + 3 + 4 has more components. The Fission number of N is now defined as the number of integers obtained in this process, including N itself. The above tree has 13 nodes, so F(24) = 13.

This sequence is OEIS entry A256504.

The first 40 terms, starting from N = 1, are

1, 1, 3, 1, 5, 6, 5, 1, 6, 7, 12, 10, 12, 11, 12, 1, 8, 16, 14, 17, 18, 18,
23, 13, 21, 18, 22, 23, 24, 19, 14, 1, 22, 20, 23, 24, 31, 27, 25, 26

The first 1000 terms can be found in this pastebin.

The Challenge

Given a positive integer N, determine its Fission number F(N). (So you don't need to cover the leading 0 listed on OEIS.)

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

This is code golf, so the shortest answer (in bytes) wins.

Bonus question: Can you find any interesting properties of this sequence?

\$\endgroup\$
  • \$\begingroup\$ I notice that the OEIS seems to have an error at n = 34: starting at n = 32, it (currently) lists 1, 22, 22, 23, 24, 31, rather than 1, 22, 20, 23, 24, 31. \$\endgroup\$ – mathmandan May 28 '15 at 7:50
  • 1
    \$\begingroup\$ @mathmandan Good catch, I'll probably propose a correction (along with the first diagram). \$\endgroup\$ – Martin Ender May 28 '15 at 10:46
  • \$\begingroup\$ Related challenge: codegolf.stackexchange.com/questions/5703/… (and same question on math.SE: math.stackexchange.com/questions/139842/…) \$\endgroup\$ – Ilmari Karonen May 29 '15 at 6:22
  • \$\begingroup\$ @mathmandan FYI, I have corrected the sequence and the example now, and also added my reference implementation and the first 10k terms. \$\endgroup\$ – Martin Ender Jun 5 '15 at 10:33
  • \$\begingroup\$ Looks good! Thanks for your work! \$\endgroup\$ – mathmandan Jun 5 '15 at 13:16

12 Answers 12

16
\$\begingroup\$

Pyth, 23 22 21 bytes

Lh&lJfqbsT.:tUb)syMeJ

This defines a recursive function y. Try it online: Demonstration

Explanation:

L                      define a function y(b): return ...
            tUb          the list [1, 2, ..., b-1]
          .:   )         generate all consecutive sub-sequences
     f                   filter for sub-sequences T, which satisfy:
      qbsT                   b == sum(T)
    J                    and store them in J

                         return 
   lJ                        len(J)
  &                        and (if len(J) == 0 then 0 else ...)
                    eJ       last element of J (=longest sub-sequence) 
                  yM         recursive calls for all these numbers
                 s           sum
 h                         incremented by one (counting the current node)
\$\endgroup\$
52
\$\begingroup\$

Fission, 1328 989 887 797 bytes

This answer is a bit unreasonably long (I wish we had collapsible regions)... please don't forget to scroll past this and show the other answers some love!

Working on this code was what inspired this challenge. I wanted to add an answer in Fission to EOEIS, which led me to this sequence. However, actually learning Fission and implementing this took a few weeks working on it on and off. In the meantime, the sequence had really grown on me so I decided to post a separate challenge for it (plus, this wouldn't have been particularly far down the tree on EOEIS anyway).

So I present to you, the Monstrosity:

 R'0@+\
/  Y@</ /[@ Y]_L
[? % \  / \ J
   \$@  [Z/;[{+++++++++L
UR+++++++++>/;
9\   ;    7A9
SQS  {+L  /$     \/\/\/\/\/   5/ @  [~ &@[S\/ \  D /8/
~4X /A@[  %5                   /; &    K  } [S//~KSA /
  3    \  A$@S  S\/  \/\/\/   \/>\ /S]@A  /  \ { +X
W7           X  X    /> \      +\ A\ /   \ /6~@/ \/
        /   ~A\;     +;\      /@
    ZX [K    / {/  / @  @ }  \ X @
       \AS   </      \V /    }SZS S/
         X   ;;@\   /;X  /> \ ; X X
 ;       \@+  >/ }$S SZS\+;    //\V
           / \\  /\; X X @  @  \~K{
           \0X /     /~/V\V /   0W//
    \        Z      [K \  //\
W       /MJ $$\\ /\7\A  /;7/\/ /
       4}K~@\ &]    @\  3/\
 /     \{   }$A/1 2  }Y~K <\
[{/\  ;@\@  /   \@<+@^   1;}++@S68
@\ <\    2        ;   \    /
$  ;}++ +++++++L
%@A{/
M  \@+>/
~     @
SNR'0YK
  \  A!/

It expects that there is no trailing newline on the input, so you might want to call it like echo -n 120 | ./Fission oeis256504.fis.

The layout could probably still be more efficient, so I think there's still a lot of room for improvement here (for instance, this contains 911 581 461 374 spaces).

Before we get to the explanation, a note on testing this: the official interpreter doesn't entirely work as is. a) Mirror.cpp doesn't compile on many systems. If you run into that problem, just comment out the offending line - the affected component (a random mirror) is not used in this code. b) There are a couple of bugs that can lead to undefined behaviour (and likely will for a program this complex). You can apply this patch to fix them. Once you've done that, you should be able to compile the interpreter with

g++ -g --std=c++11 *.cpp -o Fission

Fun fact: This program uses almost every component Fission has to offer, except for # (random mirror), : (half mirror), - or | (plain mirror), and " (print mode).

What on Earth?

Warning: This will be quite long... I'm assuming you're genuinely interested in how Fission works and how one could program in it. Because if you're not, I'm not sure how I could possibly summarise this. (The next paragraph gives a general description of the language though.)

Fission is a two-dimensional programming language, where both data and control flow are represented by atoms moving through a grid. If you've seen or used Marbelous before, the concept should be vaguely familiar. Each atom has two integer properties: a non-negative mass and an arbitrary energy. If the mass ever becomes negative the atom is removed from the grid. In most cases you can treat the mass as the "value" of the atom and the energy as some sort of meta-property that is used by several components to determine the flow of the atoms (i.e. most sorts of switches depend on the sign of the energy). I will denoted atoms by (m,E), when necessary. At the beginning of the program, the grid starts with a bunch of (1,0) atoms from wherever you place on of the four components UDLR (where the letter indicates the direction the atom is moving in initially). The board is then populated with a whole bunch of components which change the mass and energy of atoms, change their directions or do other more sophisticated things. For a complete list see the esolangs page, but I'll introduce most of them in this explanation. Another important point (which the program makes use of several times) is that the grid is toroidal: an atom that hits any of the sides reappears on the opposite side, moving in the same direction.

I wrote the program in several smaller parts and assembled them at the end, so that's how I'll go through the explanation.

atoi

This component may seem rather uninteresting, but it's nice and simple and allows me to introduce a lot of the important concepts of Fission's arithmetic and control flow. Therefore, I will go through this part in quite meticulous detail, so I can reduce the other parts to introducing new Fission mechanics and pointing out higher-level components whose detailed control flow you should be able to follow yourself.

Fission can only read byte values from individual characters, not entire numbers. While that's acceptable practice around here, I figured while I was at it, I could do it right and parse actual integers on STDIN. Here is the atoi code:

     ;
 R'0@+\
/  Y@</ /[@ Y]_L
[? % \  / \ J 
   \$@  [Z/;[{+++++++++L
UR+++++++++>/;
           O

Two of the most important components in Fission are fission and fusion reactors. Fission reactors are any of V^<> (the above code uses < and >). A fission reactor can store an atom (by sending it into the character's wedge), the default being (2,0). If an atom hits the character's apex, two new atoms will be sent off to the sides. Their mass is determined by dividing the incoming mass by the stored mass (i.e. halving by default) - the left-going atom gets this value, and the right-going atom gets the remainder of the mass (i.e. mass is conserved in the fission). Both outgoing atoms will have the incoming energy minus the stored energy. This means we can use fission reactors for arithmetic - both for subtraction and division. If a fission reactor is hit from the site, the atom is simply reflected diagonally and will then move in the direction of the character's apex.

Fusion reactors are any of YA{} (the above code uses Y and {). Their function is similar: they can store an atom (default (1,0)) and when hit from the apex two new atoms will be sent off to the sides. However, in this case the two atoms will be identical, always retaining the incoming energy, and multiplying the incoming mass by the stored mass. That is, by default, the fusion reactor simply duplicates any atom hitting its apex. When hit from the sides, fusion reactors are a bit more complicated: the atom is also stored (independently of the other memory) until an atom hits the opposite side. When that happens a new atom is released in the direction of the apex whose mass and energy are the sum of the two old atoms. If a new atom hits the same side before a matching atom reaches the opposite side, the old atom will simply be overwritten. Fusion reactors can be used to implement addition and multiplication.

Another simple component I want to get out of the way is [ and ] which simply set the atom's direction to right and left, respectively (regardless of incoming direction). The vertical equivalents are M (down) and W (up) but they're not used for the atoi code. UDLR also act as WM][ after releasing their initial atoms.

Anyway, let's look at the code up there. The program starts out with 5 atoms:

  • The R and L at the bottom simply get their mass increment (with +) to become (10,0) and then stored in a fission and a fusion reactor, respectively. We will use these reactors to parse the base-10 input.
  • The L in the top right corner gets its mass decremented (with _) to become (0,0) and is stored in the side of a fusion reactor Y. This is to keep track of the number we're reading - we'll gradually increase and multiply this as we read numbers.
  • The R in the top left corner gets its mass set to the character code of 0 (48) with '0, then mass and energy are swapped with @ and finally mass incremented once with + to give (1,48). It is then redirected with diagonal mirrors \ and / to be stored in a fission reactor. We'll use the 48 for subtraction to turn the ASCII input into the actual values of the digits. We also had to increase the mass to 1 to avoid division by 0.
  • Finally, the U in the bottom left corner is what actually sets everything in motion and is initially used only for control flow.

After being redirected to the right, the control atom hits ?. This is the input component. It reads a character and sets the atom's mass to the read ASCII value and the energy to 0. If we hit EOF instead, the energy will be set to 1.

The atom continues and then hits %. This is a mirror switch. For non-positive energy, this acts like a / mirror. But for positive energy it acts like a \ (and also decrements the energy by 1). So while we're reading the characters, the atom will be reflected upwards and we can process the character. But when we're done with the input, the atom will be reflected downwards and we can apply different logic to retrieve the result. FYI, the opposite component is &.

So we've got an atom moving up for now. What we want to do for each character is to read its digit value, add that to our running total and then multiply that running total by 10 to prepare for the next digit.

The character atom first hits a (default) fusion reactor Y. This splits the atom and we use the left-going copy as a control atom to loop back into the input component and read the next character. The right-going copy will be processed. Consider the case where we've read the character 3. Our atom will be (51,0). We swap mass and energy with @, such that we can make use of the subtraction of the next fission reactor. The reactor subtracts 48 off the energy (without changing the mass), so the it sends off two copies of (0,3) - the energy now corresponds to the digit we've read. The upgoing copy is simply discarded with ; (a component that just destroys all incoming atoms). We'll keep working with the downgoing copy. You'll need to follow its path through the / and \ mirrors a bit.

The @ just before the fusion reactor swaps mass and energy again, such that we'll add (3,0) to our running total in the Y. Note that the running total itself will therefore always have 0 energy.

Now J is a jump. What it does is jump any incoming atom forward by its energy. If it's 0, the atom just keeps moving straight on. If it's 1 it will skip one cell, if it's 2 it'll skip two cells and so on. The energy is spent in the jump, so the atom always ends up with energy 0. Since the running total does have zero energy, the jump is ignored for now and the atom is redirected into the fusion reactor { which multiplies its mass by 10. The downgoing copy is discarded with ; while the upgoing copy is fed back into the Y reactor as the new running total.

The above keeps repeating (in a funny pipelined way where new digits are being processed before the previous ones are done) until we hit EOF. Now the % will send the atom downwards. The idea is to turn this atom into (0,1) now before hitting the running total reactor so that a) the total is not affected (zero mass) and b) we get an energy of 1 to jump over the [. We can easily take care of the energy with $, which increments the energy.

The issue is that ? does not reset the mass when you're hitting EOF so the mass will still be that of the last character read, and the energy will be 0 (because % decremented the 1 back to 0). So we want to get rid of that mass. To do that we swap mass and energy with @ again.

I need to introduce one more component before finishing up this section: Z. This is essentially the same as % or &. The difference is that it lets positive-energy atoms pass straight through (while decrementing the energy) and deflects non-positive-energy atoms 90 degrees to the left. We can use this to eliminate an atom's energy by looping it through the Z over and over - as soon as the energy is gone, the atom will be deflected and leave the loop. That is this pattern:

/ \
[Z/

where the atom will move upwards once the energy is zero. I will use this pattern in one form or another several times in the other parts of the program.

So when the atom leaves this little loop, it will be (1,0) and swapped to (0,1) by the @ before hitting the fusion reactor to release the final result of the input. However, the running total will be off by a factor of 10, because we've tentatively multiplied it for another digit already.

So now with energy 1, this atom will skip the [ and jump into the /. This deflects it into a fission reactor which we've prepared to divide by 10 and fix our extraneous multiplication. Again, we discard one half with ; and keep the other as output (here represented with O which would simply print the corresponding character and destroy the atom - in the full program we keep using the atom instead).

itoa

           /     \
input ->  [{/\  ;@
          @\ <\   
          $  ;}++ +++++++L
          %@A{/
          M  \@+>/
          ~     @
          SNR'0YK
            \  A!/

Of course, we also need to convert the result back to a string and print it. That's what this part is for. This assumes that the input doesn't arrive before tick 10 or so, but in the full program that's easily given. This bit can be found at the bottom of the full program.

This code introduce a new very powerful Fission component: the stack K. The stack is initially empty. When an atom with non-negative energy hits the stack, the atom is simply pushed onto the stack. When an atom with negative energy hits the stack, its mass and energy will be replaced by the atom on the top of the stack (which is thereby popped). If the stack is empty though, the direction of the atom is reversed and its energy becomes positive (i.e. is multiplied by -1).

Okay, back to the actual code. The idea of the itoa snippet is to repeatedly take the input modulo 10 to find the next digit while integer-dividing the input by 10 for next iteration. This will yield all the digits in reverse order (from least significant to most significant). To fix the order we push all the digits onto a stack and at the end pop them off one by one to print them.

The upper half of the code does the digit computation: the L with the pluses gives a 10 which we clone and feed into a fission and a fusion reactor so we can divide and multiply by 10. The loop essentially starts after the [ in the top left corner. The current value is split: one copy is divided by 10, then multiplied by 10 and stored in a fission reactor, which is then hit by the other copy at the apex. This computes i % 10 as i - ((i/10) * 10). Note also that the A splits the intermediate result after the division and before the multiplication, such that we can feed i / 10 into the next iteration.

The % aborts the loop once the iteration variable hits 0. Since this is more or less a do-while loop, this code would even work for printing 0 (without creating leading zeroes otherwise). Once we leave the loop we want to empty the stack and print the digits. S is the opposite of Z, so it's a switch which will deflect an incoming atom with non-positive energy 90 degrees to the right. So the atom actually moves over the edge from the S straight to the K to pop off a digit (note the ~ which ensures that the incoming atom has energy -1). That digit is incremented by 48 to get the ASCII code of the corresponding digit character. The A splits the digit to print one copy with ! and feed the other copy back into the Y reactor for the next digit. The copy that's printed is used as the next trigger for the stack (note that the mirrors also send it around the edge to hit the M from the left).

When the stack is empty, the K will reflect the atom and turn its energy into +1, such that it passes straight through the S. N prints a newline (just because it's neat :)). And then the atom goes thorugh the R'0 again to end up in the side of the Y. Since there are no further atoms around, this will never be released and the program terminates.

Computing the Fission Number: The Framework

Let's get to the actual meat of the program. The code is basically a port of my Mathematica reference implementation:

fission[n_] := If[
  (div = 
    SelectFirst[
      Reverse@Divisors[2 n], 
      (OddQ@# == IntegerQ[n/#] 
       && n/# > (# - 1)/2) &
    ]
  ) == 1,
  1,
  1 + Total[fission /@ (Range@div + n/div - (div + 1)/2)]
]

where div is the number of integers in the maximal partition.

The main differences are that we can't deal with half-integer values in Fission so I'm doing a lot of things multiplied by two, and that there is no recursion in Fission. To work around this, I'm pushing all the integers in a partition in a queue to be processed later. For each number we process, we'll increment a counter by one and once the queue is empty, we'll release the counter and send it off to be printed. (A queue, Q, works exactly like K, just in FIFO order.)

Here is a framework for this concept:

                      +--- input goes in here
                      v 

                     SQS ---> compute div from n          D /8/
                     ~4X               |                /~KSA /
                       3               +----------->    { +X
initial trigger ---> W                               6~@/ \/
                              4                   
                     W        ^                     /
                              |              3
                     ^     generate range    |
                     |     from n and div  <-+----- S6
                     |         -then-      
                     +---- release new trigger

The most important new components are the digits. These are teleporters. All teleporters with the same digit belong together. When an atom hits any teleporter it will be immediately move the next teleporter in the same group, where next is determined in the usual left-to-right, top-to-bottom order. These are not necessary, but help with the layouting (and hence golfing a bit). There is also X which simply duplicates an atom, sending one copy straight ahead and the other backwards.

By now you might be able to sort out most of the framework yourself. The top left corner has the queue of values still to be processed and releases one n at a time. One copy of n is teleported to the bottom because we need it when computing the range, the other copy goes into the block at the top which computes div (this is by far the single largest section of the code). Once div has been computed, it is duplicated - one copy increments a counter in the top right corner, which is stored in K. The other copy is teleported to the bottom. If div was 1, we deflect it upwards immediately and use it as a trigger for the next iteration, without enqueuing any new values. Otherwise we use div and n in the section at the bottom to generate the new range (i.e. a stream of atoms with the corresponding masses which are subsequently put in the queue), and then release a new trigger after the range has been completed.

Once the queue is empty, the trigger will be reflected, passing straight through the S and reappearing in the top right corner, where it releases the counter (the final result) from A, which is then teleported to itoa via 8.

Computing the Fission Number: The Loop Body

So all that's left is the two sections to compute div and generate the range. Computing div is this part:

 ;    
 {+L  /$     \/\/\/\/\/   5/ @  [~ &@[S\/ \
/A@[  %5                   /; &    K  } [S/
   \  A$@S  S\/  \/\/\/   \/>\ /S]@A  /  \ 
         X  X    /> \      +\ A\ /   \ /
    /   ~A\;     +;\      /@
ZX [K    / {/  / @  @ }  \ X @
   \AS   </      \V /    }SZS S/
     X   ;;@\   /;X  /> \ ; X X
     \@+  >/ }$S SZS\+;    //\V
       / \\  /\; X X @  @  \~K{
       \0X /     /~/V\V /   0W//
\        Z      [K \  //\
           \ /\7\A  /;7/\/

You've probably seen enough now to puzzle this out for yourself with some patience. The high-level breakdown is this: The first 12 columns or so generate a stream of divisors of 2n. The next 10 columns filter out those that don't satisfy OddQ@# == IntegerQ[n/#]. The next 8 columns filter out those that don't satisfy n/# > (# - 1)/2). Finally we push all valid divisors on a stack, and once we're done we empty the entire stack into a fusion reactor (overwriting all but the last/largest divisor) and then release the result, followed by eliminating its energy (which was non-zero from checking the inequality).

There are a lot of crazy paths in there that don't really do anything. Predominantly, the \/\/\/\/ madness at the top (the 5s are also part of it) and one path around the bottom (that goes through the 7s). I had to add these to deal with some nasty race conditions. Fission could use a delay component...

The code that generates the new range from n and div is this:

 /MJ $$\
4}K~@\ &]    @\  3/\
\{   }$A/1 2  }Y~K <\
 \@  /   \@<+@^   1;}++@
  2        ;   \    /

We first compute n/div - (div + 1)/2 (both terms floored, which yields the same result) and store for later. Then we generate a range from div down to 1 and add the stored value to each of them.

There are two new common patterns in both of these, that I should mention: One is SX or ZX hit from below (or rotated versions). This is a nice way to duplicate an atom if you want one copy to go straight ahead (since redirecting the outputs of a fusion reactor can sometimes be cumbersome). The S or Z rotates the atom into the X and then rotates the mirrored copy back into the original direction of propagation.

The other pattern is

[K
\A --> output

If we store any value in K we can repeatedly retrieve it by hitting K with negative energy from the top. The A duplicates the value we're interested in and sends what copy right back onto the stack for the next time we need it.

Well, that was quite a tome... but if you actually got through this, I hope you got the idea that Fission i͝s̢̘̗̗ ͢i̟nç̮̩r̸̭̬̱͔e̟̹̟̜͟d̙i̠͙͎̖͓̯b̘̠͎̭̰̼l̶̪̙̮̥̮y̠̠͎̺͜ ͚̬̮f̟͞u̱̦̰͍n͍ ̜̠̙t̸̳̩̝o ̫͉̙͠p̯̱̭͙̜͙͞ŕ̮͓̜o̢̙̣̭g̩̼̣̝r̤͍͔̘̟ͅa̪̜͇m̳̭͔̤̞ͅ ͕̺͉̫̀ͅi͜n̳̯̗̳͇̹.̫̞̲̞̜̳

\$\endgroup\$
  • 1
    \$\begingroup\$ Now with 100% fewer scrollbars. so you say .. and its still To be continued... \$\endgroup\$ – Optimizer May 28 '15 at 5:29
  • 13
    \$\begingroup\$ Still more readable than most code our junior devs pump out. \$\endgroup\$ – corsiKa May 28 '15 at 14:50
  • \$\begingroup\$ As the creator of Fission, even I haven't yet written a program that large! I'm impressed! Your explanation is spectacular and could definitely serve as a tutorial for the language. \$\endgroup\$ – C0deH4cker Jun 1 '15 at 2:19
  • \$\begingroup\$ Also, the last line of your answer kinda looks like a Fission program ;) \$\endgroup\$ – C0deH4cker Sep 4 '15 at 6:33
12
\$\begingroup\$

CJam, 42 41 bytes

ri]{_{:X,:)_few:+W%{1bX=}=}%{,(},e_}h]e_,

A simple Breadth first traversal and a stopping condition of empty next level.

How it works:

ri]                                       e# This represents the root of the fissile tree
   {                               }h     e# Now we run a do-while loop
    _{                    }%              e# Copy the nodes at the current level and map them
                                          e# via this code block to get next level nodes
      :X,:)                               e# Store the node value in X and get array [1..X]
           _few                           e# Copy the array and get continuous slices of
                                          e# length 1 through X from the array [1..X]
               :+W%                       e# Right now, we have an array of array with each
                                          e# array containing slice of same length. We join
                                          e# those arrays and reverse them to get slices of
                                          e# higher length in front of lower lengths
                   {1bX=}=                e# Choose the first slice whose sum is same as X
                                          e# The reversal above makes sure that we give
                                          e# preference to slice of higher length in case of
                                          e# multiple slices add up to X
                            {,(},         e# Filter out slices of length 1 which basically
                                          e# mean that the current node cannot be split up
                                 e_       e# Join all slices in a single array. This is our
                                          e# next level in the Fissile tree. If this is empty
                                          e# it means that all no further node can be
                                          e# decomposed. In an {}h do-while loop, this fact
                                          e# itself becomes the stopping condition for the
                                          e# loop
                                     ]e_, e# Wrap all levels in an array. Flatten the array
                                          e# and take its length

Try it online here

\$\endgroup\$
  • \$\begingroup\$ This can probably be golfed to around 35 bytes. I am trying to figure out how .. \$\endgroup\$ – Optimizer May 27 '15 at 12:37
10
\$\begingroup\$

Python 3, 112 bytes

def f(n,c=0):
 d=n-c;s=(n-d*~-d/2)/d
 return(s%1or s<1)and f(n,c+1)or+(d<2)or-~sum(f(int(s)+i)for i in range(d))

4 bytes saved thanks to @FryAmTheEggman.

Explanation coming later...

Bonus fact: Every power of 2 has a Fission number of 1. This is because the sum of an even length sequence is always the sum of the two middle numbers, which is odd, multiplied by half the length of the sequence, which is integer. The sum of an odd length sequence is the middle number multiplied by the sequence length, which is odd. So because a power of 2 doesn't have an odd divisor it can be only expressed as the sum of itself.

\$\endgroup\$
  • \$\begingroup\$ 2+3+4+5=14 which is not odd. Your argument for even length sequences should be changed to "the sum of an even length sequence is the sum of the two middle numbers, which is odd, multiplied by half the length". The rest of your statement goes through unaffected. \$\endgroup\$ – Bruno Le Floch May 28 '15 at 8:55
  • \$\begingroup\$ @BrunoLeFloch Thanks! Corrected. \$\endgroup\$ – randomra May 28 '15 at 10:04
  • \$\begingroup\$ Shouldn't your title reflect the improvements? i.e. <strike>117</strike> <strike>113</strike> 112 \$\endgroup\$ – corsiKa May 28 '15 at 14:46
  • \$\begingroup\$ @corsiKa I usually only do that for major improvements. There would be too many striked numbers otherwise. \$\endgroup\$ – randomra May 28 '15 at 15:03
8
\$\begingroup\$

Python 2, 111 102 97 bytes

Somewhat readable:

def f(n,c=0):a=n-c;b=n-a*~-a/2;return 1/a or-~sum(map(f,range(b/a,b/a+a)))if b>b%a<1else f(n,c+1)

Not-so-readable:

def f(n,a=0):b=n-a*~-a/2;return b>0and(f(n,a+1)or b%a<1and(1/a or-~sum(map(f,range(b/a,b/a+a)))))

Both 97 bytes.

b is the n minus the (a-1)th triangular number. If b % a == 0, then n is the sum of a consecutive numbers starting from b.

\$\endgroup\$
  • 8
    \$\begingroup\$ I used to consider Python a generally readable language until I joined PPCG. \$\endgroup\$ – Alex A. May 27 '15 at 17:19
  • \$\begingroup\$ I think you need to improve your definition of readable .. :P \$\endgroup\$ – Optimizer May 28 '15 at 9:02
  • \$\begingroup\$ Python 2 doesn't allow 1else. Only the 2nd solution works. It's not until Python 3 that else can immediately follow a number. \$\endgroup\$ – mbomb007 May 29 '15 at 22:00
  • \$\begingroup\$ @mbomb007 To my knowledge it works fine from 2.7.8 onwards \$\endgroup\$ – Sp3000 May 30 '15 at 1:17
  • \$\begingroup\$ Ok, I was using 2.7.2. \$\endgroup\$ – mbomb007 May 31 '15 at 3:51
7
\$\begingroup\$

Python 2, 86

f=lambda n,R={1}:n-sum(R)and f(n,R^{[min(R),max(R)+1][n>sum(R)]})or-~sum(map(f,R-{n}))

Less golfed:

def f(n,R={1}):
    d=sum(R)-n
    if d==0:return (sum(map(f,R-{n}))
    if d<0:return f(n,R|{max(R)+1})
    if d>0:return f(n,R-{min(R)})

The idea is to test potential runs of consecutive integers that sum to n. The run is stored directly directly as a set R rather than via its endpoints.

We check how the sum of the current run compares to the desired sum n via their difference.

  • If the sum is too large, we cut the smallest element in the run.
  • If the sum is too small, we extend the run by making its max bigger by 1.
  • If the sum is correct, we recurse, mapping f onto the run, summing, and adding 1 for the current node. If the run is {n}, we've tried all non-trivial possible sums, stop the recursion by removing n first.

Thanks to Sp3000 for saving 3 chars.

\$\endgroup\$
7
\$\begingroup\$

Python 2, 85

I am very proud of this answer because it already takes tens of seconds for n=9, and 5-10 minutes for n=10. In code golf this is considered a desirable attribute of a program.

f=lambda n,a=1,d=1:a/n or[f(a)+f(n-a,1+1%d*a)+1/d,f(n,a+d/n,d%n+1)][2*n!=-~d*(2*a+d)]

There is also a short-circuiting version that does not take so long and uses the same amount of bytes:

f=lambda n,a=1,d=1:a/n or~d*(2*a+d)+n*2and f(n,a+d/n,d%n+1)or f(a)+f(n-a,1+1%d*a)+1/d 

It may be faster, but at least it exceeds the default recursion limit once n goes a little above 40.

The idea is to do a brute force search for numbers a and d such that a + a+1 + ... + a+d == n, on values between 1 and n. The f(n,a+d/n,d%n+1) branch of the recursion loops through the (a, d) pairs. In the case that the equality is satisfied, I manage to avoid an expensive map(range(...)) call by splitting into just two branches regardless of how long the sequence is. The numbers a+1 through d are lumped into one call of f by setting the a parameter so that a different way to split up the sequence can't be used.

\$\endgroup\$
  • \$\begingroup\$ How does this work? \$\endgroup\$ – xnor May 29 '15 at 21:58
  • \$\begingroup\$ "I am very proud of this answer because it already takes tens of seconds for n=9, and 5-10 minutes for n=10. In code golf this is considered a desirable attribute of a program." +1'd just for that. \$\endgroup\$ – Soham Chowdhury May 30 '15 at 16:59
6
\$\begingroup\$

Haskell, 76 69 bytes

f x=head$[1+sum(map f[y..z])|y<-[1..x-1],z<-[y..x],sum[y..z]==x]++[1]

Usage:

*Main> map f [1..40]
[1,1,3,1,5,6,5,1,6,7,12,10,12,11,12,1,8,16,14,17,18,18,23,13,21,18,22,23,24,19,14,1,22,20,23,24,31,27,25,26]

How it works:

[  [y..z] |y<-[1..x-1],z<-[y..x],sum[y..z]==x]

           make a list of lists with all consecutive integers (at least 2 elements)
           that sum up to x, sorted by lowest number, e.g. 9 -> [[2,3,4],[4,5]].

1+sum(map f[...]) 

           recursively calculate the Fission Number for each list

[...]++[1]

           always append the 1 to the list of Fission Numbers.

head

           take the first element, which is either the Fission Number of the
           longest list or if there's no list, the 1 appended in the step before.  
\$\endgroup\$
3
\$\begingroup\$

Retina, 66 bytes

^|$
,
(`,(1+?)(?=(?<1>1\1)+\D)
$0;
+)`,(1*);1\1
,$1,1$1;
^,|1

.
1

Takes input and prints output in unary.

You can put each line in a single file or run the code as is with the -s flag. E.g.:

> echo -n 1111111|retina -s fission
11111

Explanation:

  • We keep a comma-delimited list of the numbers to be splitted.
  • For every number we take the smallest starting value which can crate a valid splitup and delimit it from the rest with a semicolon.
  • If there is a semicolon inside a number we change it to a comma and delimit the next properly sized (length of previous element + 1) part of the number.
  • We repeat step 2 and 3 until changes happen.
  • We get a comma for every leaf and a semicolon for every inner node plus an extra comma because we started with two comma. So we remove a comma and the numbers' parts (1's) and convert the rest to 1's.

The states of the string throughout the process with input 11111111111111 (unary 14):

,11111111111111,
,11;111111111111,
,11,1;11,1111,11;111;,
,11,1,11;,1111,11,1;11;;,
,11,1,11;,1111,11,1,11;;;,
,,;,,,,;;;,
11111111111

Many thanks for @MartinButtner for the help in chat!

\$\endgroup\$
3
\$\begingroup\$

CJam (43 bytes)

qi,{):X),_m*{{_)*2/}/-X=}=~\,>0\{~$+}/)}%W=

Online demo

I'm sure that I'm missing some tricks with the advanced loops, but this does neatly exploit the CJam property (which has previously annoyed me) that inside a % map the results remain on the stack, and can therefore be accessed using $ with a negative offset.

\$\endgroup\$
  • \$\begingroup\$ I'll have a closer look tomorrow, but for a start you don't need the , at the beginning. / and % and a few others implicitly turn numbers into ranges. \$\endgroup\$ – Martin Ender May 30 '15 at 0:23
  • \$\begingroup\$ ,_m* can be replaced with 2m*. The arithmetic progression formula can be replaced with ~,>:Y_,+:+ and ~\,>0\ becomes !Y. Finally, if you use {}# instead of {}=, you don't need the ) after X. Putting it all together: ri{):X2m*{~,>:Y_,+:+X=}#!Y{~$+}/)}%W= \$\endgroup\$ – Dennis Jun 1 '15 at 18:27
2
\$\begingroup\$

Go, 133 bytes

func 算(n int)int{Σ:=1;for i:=0;i<n;i++{for j:=0;j<n;j++{if i*i+i-j*j-j==2*n{for k:=j+1;k<=i;k++{Σ+=算(k)};j,i=n,n}}};return Σ}

This is my first code golf, sorry if I made any mistakes.

This uses the idea that the fissile "composition" can also be seen as a difference between two sequences of ordered integers. For example take the fissile "composition" for the number 13. It is 6,7. But it can be seen as the sum of integers 1...7 minus the sum of integers 1...5

  A: 1 2 3 4 5 6 7  sum = 28
  B: 1 2 3 4 5      sum = 15 
A-B:           6 7  sum = 13, which is also 28-15 = 13

Recall the formula from Gauss's school days,sum 1...n=(n^2+n)/2. So to find a composition of sequential integers for a given n, we could also say, we are searching for 'end points' p and q along the range 1...n so that (p^2+p)/2 - (q^2+q)/2 = n. In the above example, we would have been searching for 'end points' 5 and 7 because 7^2+7=56/2, 5^2+5=30/2, 56/2-30/2 = 28-15 = 13.

Now there are multiple possible ways to fissile-compose a number, as Martin noted 9 = 2 + 3 + 4 but also 4 + 5. But it seems obvious that the "lowest" starting sequence will also be the longest, because it takes more little-numbers to sum up to a big number than it does medium-sized numbers. (I have no proof unfortunately)

So to find the composition of 9, test every 'end point pair', p and q, iterating both p and q separately from 0 to 9, and test if p^p+p/2 - q^2+q/2 = 9. Or, more simply, multiply the equation by 2, to avoid the division issues of rounding and keep all math in integers. Then we are looking for p and q such that (p^p+p) - (q^q+q) = 9*2. The first match we find will be the Fissile composition endpoints because, as noted, the lowest group of numbers will also be the longest, and we are searching low-to-high (0 to 9). We break out of the loop as soon as we find a match.

Now the recursive function finds those 'fissile end points' p and q for the given n, then recalls-itself for each of the 'children' in the tree from p to q. For 9, it would find 1 and 4, (20-2=18) then it would re-call itself on 2, 3, and 4, summing the results. For numbers like 4 it simply never finds a match, and so returns '1'. This might be shortenable but this is like my third go program, and I am no recursion expert.

Thanks for reading.

\$\endgroup\$
  • \$\begingroup\$ Nice work! But why the Unicode function/variable names. That costs unnecessary bytes and surely you could have just use some normal letter? \$\endgroup\$ – Martin Ender May 31 '15 at 22:25
  • \$\begingroup\$ Thanks for your kind comment. But I asked myself, why not count characters instead of bytes :) \$\endgroup\$ – don bright May 31 '15 at 22:41
  • \$\begingroup\$ Because those are the default rules around here. :) The reason we usually count bytes and not characters is because otherwise this happens, which is little fun for all parties involved. ;) (That said, any challenge author is free to specify counting by characters instead of bytes, but I specifically didn't.) \$\endgroup\$ – Martin Ender May 31 '15 at 22:46
1
\$\begingroup\$

CJam, 40 35 33 bytes

ri{__,f-_few:+{1b1$=}=|{F}*}:F~],

Thanks to @Optimizer for suggesting few, which saved 2 bytes.

Try it online in the CJam interpreter.

How it works

ri      e# Read an integer from STDIN.
{       e# Define function F(X):
  _     e# Push X.
  _,    e# Push [0 ... X-1].
  f-    e# Subract each from X. Pushes Y := [X ... 1].
  _few  e# Push all overlapping slices of Y of length in Y.
  :+    e# Consolidate the slices of different lenghts in a single array.
  {     e# Find the first slice S such that...
    1b  e#   the sum of its elements...
    1$= e#   equals X.
  }=    e#   Since Y is in descending order, the first matching slice is also the longest.
  |     e# Set union with [X]. This adds X to the beginning of the S if S != [X].
  {F}*  e# Execute F for each element of S except the first (X).
}:F     e#
~       e# Execute F for the input.
],      e# Count the integers on the stack.
\$\endgroup\$
  • \$\begingroup\$ If you combine my first half with your second half, you get 34 : ri{_,:)_few:+W%{1b1$=}=|{F}*}:F~], \$\endgroup\$ – Optimizer May 31 '15 at 19:19
  • \$\begingroup\$ @Optimizer: Nice. That allows an additional improvement. Thanks! \$\endgroup\$ – Dennis May 31 '15 at 19:43

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.