52

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 ...


34

Mathematica, 11 bytes PartitionsP Explanation ¯\_(ツ)_/¯


25

Mathematica, 79 bytes Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]-2⌊(2#)^.5+.5⌋+⌈Sqrt[8#+1]~Mod~1⌉& Explanation I couldn't be bothered to implement the algorithm in the challenge, so I wanted to look for a shortcut to the solution. While I found one, unfortunately it doesn't beat the Mathematica answer that does implement the algorithm. That said, I'm sure ...


19

Brachylog, 7 bytes ~+ℕᵐ.↔ᵐ Try it online! Surprisingly not that slow. Explanation (?)~+ . Output is equal to the Input when summed ℕᵐ. Each element of the Output is a positive integer .↔ᵐ(.) When reversing each element of the Output, we get the Output


18

Haskell, 37 34 bytes s#l@(c:d)|s>=c=(s-c)#l+s#d s#_=0^s Usage example: 26 # [1,5,10,25] -> 13. Simple recursive approach: try both the next number in the list (as long as it is less or equal to the amount) and skip it. If subtracting the number leads to an amount of zero, take a 1 else (or if the list runs out of elements) take a 0. Sum those 1s and 0s....


16

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, ...


16

Brachylog, 18 bytes ∧5~lLȧᵐ≥₁∧L^₃ᵐ.+?∧ Try it online! Explanation We basically describe the problem, with the additional constraint that we want the output list to be non-increasing in terms of magnitudes: this forces Brachylog to properly backtrack over all possible combinations of 5 values, instead of infinitely backtracking over the value of the last ...


15

Mathematica, 35 22 bytes Thanks to miles for suggesting FrobeniusSolve and saving 13 bytes. Length@*FrobeniusSolve Evaluates to an unnamed function, which takes the list of coins as the first argument and the target value as the second. FrobeniusSolve is a shorthand for solving Diophantine equations of the form a1x1 + a2x2 + ... + anxn = b for the xi ...


14

Brachylog, 11 bytes Thanks Fatalize for saving one byte ~+l₅≥₁.√₃ᵐ∧ Try it online! Firstly ~+ enforces that the output (.) must sum to the input. l₅ again constrains the output, dictating that it must have a length of 5. ≥₁ declares that the list must be in decreasing order (I believe that this is necessary to stop the program entering an infinite loop) ...


13

CJam, 20 19 bytes {ee::+W%}_q~%z%:+:* This takes in CJam style unary list in an ascending order. For example: [[1] [1 1 1] [1 1 1] [1 1 1 1 1]] gives 115200 How it works This version is provided by Dennis and it uses the fact that a Block ArrayList % still works in CJam :D { }_ e# Put this block on stack and make a copy q~ ...


13

Pyth, 3 bytes l./ Try it here! or Try a test Suite. The answer took much longer to format than writing the code itself :P. How? Pyth is the right tool for the job. l./ Full program with implicit input. ./ Integer partitions. Return all sorted lists of positive integers that add to the input. l Length. Implicitly output the result.


12

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 _{ }% ...


12

Jelly (fork), 2 bytes æf This relies on a branch of Jelly where I was working on implementing Frobenius solve atoms so unfortunately you cannot try it online. Usage $ ./jelly eun 'æf' '12' '[1,5,10]' 4 $ ./jelly eun 'æf' '26' '[1,5,10,25]' 13 $ ./jelly eun 'æf' '19' '[2,7,12]' 2 $ ./jelly eun 'æf' '13' '[2,8,25]' 0 Explanation æf Input: total T, ...


12

Pyth, 8 bytes /sM{yS*E Raw brute force, too memory intensive for actual testing. This is O(2mn), where n is the number of coins and m is the target sum. Takes input as target\n[c,o,i,n,s]. /sM{yS*EQQ (implicit Q's) *EQ multiply coin list by target S sort y powerset (all subsequences) { remove ...


11

Python, 67 bytes f=lambda n,R=[1]:n-sum(R)and f(n,[R+[R[-1]+1],R[1:]][sum(R)>n])or R An oddly straightforward strategy: search for the interval R with the right sum. If the sum is too small, shift the right endpoint of the interval up one by appending the next highest number. If the sum is too large, shift up the left endpoint by removing the smallest ...


11

Haskell, 37 bytes f 0=[[]] f n=[a:x|a<-[1..n],x<-f$n-a] xnor saved two bytes.


10

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 ...


10

Python, 56 bytes f=lambda n:[x+[n-i]for i in range(n)for x in f(i)]or[[]] A recursive solution: The ordered partitions of n are a partition of some smaller i with 0<=i<n, followed by the remainder n-i as the last element. For a base case, n=0 only has the empty partition.


10

Python 2, 61 bytes f=lambda n,s='1,':1/n*[eval(s)]or f(n-1,'1+'+s)+f(n-1,'1,'+s) This isn't the shortest, but I really like the method because it's so weird. Recursively generates and evaluates 2**(n-1) strings, like 1+1+1+1, 1,1+1+1, 1+1,1+1, 1,1,1+1, 1+1+1,1, 1,1+1,1, 1+1,1,1, 1,1,1,1, for n=4. These strings evaluate to tuples representing all the ...


10

JavaScript (ES6), 153 176 bytes EDIT: In non-strict mode, JS interprets 0-prefixed numerical expressions as octal (e.g. 017 is parsed as 15 in decimal). This is a fixed version that supports leading zeros. let f = s=>[...Array(3**(l=s.length,l-1))].map((_,n)=>m=eval((x=s.replace(/./g,(c,i)=>c+['','+','-'][o=(n/3**i|0)%3,j-=!o,o],j=l))....


10

Python 2, 58 57 54 bytes def f(n):k=(n**3-n)/6;return[v**3for v in~k,1-k,n,k,k] Try it online! -2 bytes, thanks to Rod -1 byte, thanks to Neil


10

Wolfram Language (Mathematica), 44 bytes Max[PermutationOrder/@Permutations@Range@#]& Try it online! Wolfram Language (Mathematica), 31 bytes @DanielSchepler has a better solution: Max[LCM@@@IntegerPartitions@#]& Try it online!


9

Python 2, 194 182 bytes from random import* h=m=H,M=input() while[h,m]!=[H,M/5]: h=m=0;s=[] for n in 1,1,2,3,5:c=randint(0,3);h+=c%2*n;m+=c/2*n;s=zip(*(["WRGB"[c]*n]*n+s)[::-1]) for L in s:print"".join(L) The algorithm is just rejection sampling, so it keeps generating clocks until it gets one that's right. The clock is built by starting with nothing, ...


9

JavaScript (ES6), 51 48 bytes f=(n,a,[c,...b]=a)=>n?n>0&&c?f(n-c,a)+f(n,b):0:1 Accepts coins in any order. Tries both using and not using the first coin, recursively calculating the number of combinations either way. n==0 means a matching combination, n<0 means that the coins exceed the quantity while c==undefined means that there are no ...


9

Haskell, 37 bytes s%(h:t)=sum$map(%t)[s,s-h..0] s%_=0^s Using some multiple of the first coin h decreases the required sum s to a non-negative value in the decreasing progression [s,s-h..0], which then must be made with the remaining coins. Once there's no coins left, check that the sum is zero arithmetically as 0^s.


9

Python 2, 82 79 bytes f=lambda n:min([f(n-k)+[k]for k in range(1,n+1)if`k`==`k`[::-1]]or[[]],key=len) Try it online!


9

05AB1E, 4 bytes ÅTg< Try it online! Perfect tool for the job. ÅT yields the list of Åll Triangular numbers up to and including N (unfortunately includes 0 too, otherwise it would be 3 bytes), g< gets the length and decrements it.


9

Jelly, 8 bytes p*ƓIFẹ+d This is a monadic link that takes the number as argument and reads n from STDIN. Try it online! How it works p*ƓIFẹ+d Main link. Argument: k p Cartesian product; yield all pairs [b, a] with b and a in [1, ..., k]. Ɠ Get; read an integer n from STDIN. * Power; map each [b, a] to [b**n, a**n]. I ...


9

Python 2, 46 45 bytes thanks to xnor for -1 byte f=lambda n:n>0and f(n-2)+f(n-3)+f(n-5)or n==0 Try it online!


9

Python 3, 65 bytes def f(n):k=(n-n**3)//6;return[n**3,(k+1)**3,(k-1)**3,-k**3,-k**3] Try it online! I mean, an explicit formula is even here (although he abstracted the construction behind an existential)


Only top voted, non community-wiki answers of a minimum length are eligible