# Tag Info

53

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 ¯\_(ツ)_/¯

28

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

15

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

14

JavaScript (ES7),  36  35 bytes Similar to other answers. Using a Black Magic formula instead of a lookup table. f=n=>n&&(n%10)**29%3571%4+f(n/10|0) Try it online! Here is a script that looks for $(p,m)$ pairs such that $(n^p\bmod m)\bmod 4=a_n$ for all $n\in[0..9]$. It's worth noting that this code takes IEEE-754 precision errors into ...

14

Husk, 11 9 8 bytes Edit: -1 byte thanks to caird coinheringaahing ṁo⌈½ṁB5d Try it online! d # get the digits ṁB5 # convert them all to base-5 # (this gives a 1 for each 5-denomination coin needed, # as well as the leftover for each digit. # We'll need 2 more coins for those with leftover 3 or 4, # ...

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

Haskell, 37 bytes f 0=[[]] f n=[a:x|a<-[1..n],x<-f$n-a] xnor saved two bytes. 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 Python 2, 82 79 bytes f=lambda n:min([f(n-k)+[k]for k in range(1,n+1)ifk==k[::-1]]or[[]],key=len) Try it online! 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)).replace(/\... 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! 10 Haskell, 55…41 40 bytes -1 byte thanks to xnor, for using a string instead of the hard-coded list. a=0:tail[i+read[j]|i<-a,j<-"0112212233"] Try it online! a is the infinite sequence. How? It's not hard to find the recursive formula $$a(n)=a\left(\left\lfloor\frac{n}{10}\right\rfloor\right)+a(n \operatorname{mod} 10)$$ with the base cases ... 9 Python 2, 179 bytes from random import* m=r=input();i=q=r+1;h=[1]+[0]*q*q;exec"h[i]=h[i+~q]+h[i-i%q*q];i+=1;"*r*q while r: x=random()*sum(h[r*q:r*q-~m]);m=0 while x>0:m+=1;x-=h[r*q+m] print m;r-=m I used formula (39) from this Knuth extract, which gives the number of partitions of n that have exactly m parts. This happens to equal the number ... 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.

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