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̳̯̗̳͇̹.̫̞̲̞̜̳
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. – mathmandan – 2015-05-28T07:50:00.417
1@mathmandan Good catch, I'll probably propose a correction (along with the first diagram). – Martin Ender – 2015-05-28T10:46:11.920
Related challenge: http://codegolf.stackexchange.com/questions/5703/in-how-many-ways-can-a-number-be-expressed-as-a-sum-of-consecutive-numbers (and same question on math.SE: http://math.stackexchange.com/questions/139842/in-how-many-ways-can-a-number-be-expressed-as-a-sum-of-consecutive-numbers)
– Ilmari Karonen – 2015-05-29T06:22:34.097@mathmandan FYI, I have corrected the sequence and the example now, and also added my reference implementation and the first 10k terms. – Martin Ender – 2015-06-05T10:33:43.707
Looks good! Thanks for your work! – mathmandan – 2015-06-05T13:16:33.427
I have posted a related question on Math.SE – Martin Ender – 2015-06-05T13:49:02.980
Generating the ASCII art tree diagram for a number would be another great code golf challenge. (Maybe ignore numbers which decompose into four or more for the sake of simplicity.) – Luke – 2015-12-10T14:06:15.283