# Sum of (at most) 5 primes

Terence Tao recently proved a weak form of Goldbach's conjecture! Let's exploit it!

Given an odd integer `n > 1`, write `n` as a sum of up to 5 primes. Take the input however you like, and give output however you like. For example,

``````def g(o):
for l in prime_range(o+1):
if l == o:
return l,
for d in prime_range(l+1):
for b in prime_range(d+1):
if l+d+b == o:
return l,d,b
for c in prime_range(b+1):
for h in prime_range(c+1):
if l+d+b+c+h == o:
return l,d,b,c,h
``````

is Sage code that takes an integer as input, and returns a list of integers as output whose sum is `n`. By Tao's theorem, this will always terminate!

Input

An odd integer `n`. You decide how to take the input, but if it's weird, explain it.

Output

Rather open-ended. Return a list. Print a string. Gimme one, a few, or all. Leave crap lying around on the stack (GS, Piet, etc) or in a consecutive (reachable) memory block (BF, etc) in a predictable manner. For these later cases, explain the output. In all cases, what you return / print / whathaveyou should be a straightforward representation of a partition of `n` into primes with fewer than 6 parts.

Scoring

This is code golf, smallest byte count wins.

Bonus! if the word 'goldbach' appears as a subsequence (not necessarily consecutive; just in order. Case doesn't matter) of your program subtract 8 points. The code above is an example of this.

-
The first number to check, odd integer > 1, is 3. Which sum of primes produces 3? Don't I see the obvious? – user unknown May 16 '12 at 5:31
The 'obvious' is linguistic. Since 3 is prime, it's the sum of 1 prime. Smartass response: Conway would say that 3 is the sum 7 + (-1) + (-1) + (-1) + (-1). – boothby May 16 '12 at 7:53
A single value is not a sum. I would suggest simply starting with values > 3 instead of introducing negative values. – user unknown May 16 '12 at 12:39
A single value is a sum. The comment about negative values was a smartass remark, as explicitly noted. – boothby May 16 '12 at 18:34
"substring (not necessarily consecutive; just in order...)" This is called a subsequence. – Joey Adams May 17 '12 at 2:52

## J, 29

``````(#~y=+/@>),{5\$<0,p:i._1 p:>:y
``````

Assumes input is in `y`. Value of expression is list of boxes of list of 5 primes or 0 that sum to `y`.

```   y =. 16
(#~y=+/@>),{5\$<0,p:i._1 p:>:y
+----------+----------+----------+----------+----------+---------+----------+----------+----------+----------+----------+----------+----------+---------+---------+----------+----------+----------+----------+----------+----------+----------+---------+------...
|0 0 0 3 13|0 0 0 5 11|0 0 0 11 5|0 0 0 13 3|0 0 2 3 11|0 0 2 7 7|0 0 2 11 3|0 0 3 0 13|0 0 3 2 11|0 0 3 11 2|0 0 3 13 0|0 0 5 0 11|0 0 5 11 0|0 0 7 2 7|0 0 7 7 2|0 0 11 0 5|0 0 11 2 3|0 0 11 3 2|0 0 11 5 0|0 0 13 0 3|0 0 13 3 0|0 2 0 3 11|0 2 0 7 7|0 2 0 ...
+----------+----------+----------+----------+----------+---------+----------+----------+----------+----------+----------+----------+----------+---------+---------+----------+----------+----------+----------+----------+----------+----------+---------+------...
```

Not enough letters to earn any bonus points.

-
 nicely done! I think no language could beat J at this challenge. – w0lf May 23 '12 at 14:53

### Mathematica, 38

``````IntegerPartitions[n,5,Prime~Array~n,1]
``````
-
Can't find a way thru WA ... – belisarius May 16 '12 at 15:40
I've got access to Mathematica, and it worked on all the inputs I gave it. – boothby May 17 '12 at 16:33
imagine if the `IntegerPartitions` function was named `Goldbach`... ;) – w0lf May 21 '12 at 8:48
@w0lf even so, it'd be 1 more than J >_> – Rixius May 30 '12 at 21:36
@Rixius no, it would score 21 in that case, 8 less than J. – Mr.Wizard May 31 '12 at 3:31

## C, 192-8 = 184 chars

Contains "Goldbach" consecutively (excluding punctuation), and "Tao" as well.
When the sum is less than 5 primes (i.e. always), prints zeros (16 = `0+0+0+3+13`)
Read the number from standard input: `echo 30 | ./prog`.

``````#define T(x)for(x=0;x<=s;b=&x,c(++x))
G,o,l,d,*b,a;c(h)
{(*b-1?h<3:++*b)||c(*b%--h?h:++*b);}
main(s){
scanf("%d",&s);
T(G)T(o)T(l)T(d)T(a)o+G+l+d+a-s?0:exit(printf("%d+%d+%d+%d+%d\n",G,o,l,d,a));
}
``````

Old version (179 chars), which can find only sums of exactly 5 primes (and therefore fails for x<10):

``````#define T(x)for(x=2;x<s;b=&x,c(++x))
G,o,l,d,*b,a;c(h)
{h<3||c(*b%--h?h:++*b);}
main(s){
scanf("%d",&s);
T(G)T(o)T(l)T(d)T(a)o+G+l+d+a-s?0:exit(printf("%d+%d+%d+%d+%d\n",G,o,l,d,a));
}
``````

Explanation:
`c` sets `*b` to the next prime (including `*b` itself if it's prime).
`T` builds a for loop, which advances one of the variables `G,o,l,d,a` to the next prime.
Within all for loops, we check if the sum matches, and print&exit if it does.

-
`G,o,l,d,*b,a;c(h)` is a nice touch! – Joel Cornett May 15 '12 at 20:15
this fails for n=3 – boothby May 17 '12 at 21:08
@boothby, you're right, it only finds some of 5 primes, not less. – ugoren May 18 '12 at 4:32
user_unknown has a good solution for this: consider zero prime for the sake of the sum – boothby May 18 '12 at 7:29
@boothby, changed. Cost me more than I'd like, because my logic naturally treats 1 as prime, and when starting with 0 I need to skip it. – ugoren May 19 '12 at 13:05

## Ruby 138124 117 - 8 = 109

``````require'mathn'
def g(o,l=[])
p l if l.inject(:+)==o#db
(l.last||1..o).each{|d|d.prime?and g(o,l+[d])if l.count<5}
end
``````

Call with `g(<number>)`. Sample output:

``````[2, 2, 2, 2, 19]
[2, 2, 3, 3, 17]
[2, 2, 3, 7, 13]
...
``````
-
Just putting `#db` on line 3 would be enough for the bonus: you'll get the `ach` from `.each`. – Ilmari Karonen May 15 '12 at 14:41
What do you mean 'fixed output format'? This one's totally open -- you can nix the spaces if you like. – boothby May 15 '12 at 15:35
@IlmariKaronen Great tip! I've edited my post. Thanks! – w0lf May 15 '12 at 18:50
@boothby Thank you for noticing this. I saw the sample output and thought it was a requirement. I see now that output format is open. Updated. – w0lf May 15 '12 at 18:51

## PHP 143 122 - 8 = 114

EDIT: Saved a few bytes on output, removed the explicit function call.

``````<?function g(\$o,\$l,\$d,\$b){for(;\$o>=\$b=gmp_intval(gmp_nextprime(+\$b));)echo\$b^\$o?\$l<4&&g(\$o-\$b,\$l+1,"\$d\$b,",\$b-1):"\$d\$b
";}
``````

Unrolled:

``````<?
function g(\$o,\$l,\$d,\$b){
for(;\$o>=\$b=gmp_intval(gmp_nextprime(+\$b));)
echo\$b^\$o?\$l<4&&g(\$o-\$b,\$l+1,"\$d\$b,",\$b-1):"\$d\$b
";}
``````

Call with `@g(<number>);` Sample output for `n=27`:

``````2,2,2,2,19
2,2,3,3,17
2,2,3,7,13
2,2,5,5,13
2,2,5,7,11
2,2,23
2,3,3,19
2,3,5,17
2,3,11,11
2,5,7,13
2,7,7,11
3,3,3,5,13
3,3,3,7,11
3,3,5,5,11
3,3,7,7,7
3,5,5,7,7
3,5,19
3,7,17
3,11,13
5,5,5,5,7
5,5,17
5,11,11
7,7,13
``````
-
 Hmm... your submitted code doesn't seem to work. You've got a some funny stuff `~õ;}` at the end... – boothby May 15 '12 at 23:20 ~õ (chr(245)) is shorthand for "\n". In this instance, it's not actually necessary. I'll remove it from the solution. – primo May 16 '12 at 11:19 code fails for n=3. – boothby May 17 '12 at 21:04 @boothby I don't believe it does. For n=3, it outputs the number 3, and then terminates (as there are no other sums of primes which are 3). What were you expecting it to produce? – primo May 17 '12 at 21:43 I don't see any output. Works fine for 5, 7, 9, 11. ideone.com/cMNR8 Also, note that you're free to define the function and not call it. – boothby May 18 '12 at 0:26
show 1 more comment

### Scala 137-8=129

``````def g(o:Int)={val l=0+:(2 to o).filterNot(d=>(2 to d-1).exists(d%_==0))
for(b<-l;a<-l;c<-l;h<-l;e<-l;if(b+a+c+h+e==o))yield{(b,a,c,h,e)}}
``````

After boothby's hint: eliminated one function call, allow to interpret 3 as the sum of 3 and nothing, remove input from output - saves another 20 chars.

Bonus emphasizing:

def g(o:Int)={val l=0+:(2 to o).filterNot(d=>(2 to d-1).exists(d%_==0)) for(b<-l;a<-l;c<-l;h<-l;e<-l;if(b+a+c+h+e==o))yield{(b,a,c,h,e)}}

Invocation and result:

``````println (l(17))
Vector((17,0,0,2,2,13), (17,0,0,2,13,2), (17,0,0,3,3,11), ...
``````

The output repeats x for every list to sum up to x, and then shows the 5 summands. 0 for missing summand, i.e. 2+2+13.

Ungolfed:

``````// see if there is some x, such that o%x is 0.
def dividable (o:Int) = (2 to o-1).exists (x=> o % x == 0)

// +: is a kind of cons-operator for Vectors
def primelist (d: Int) = {
val s = 0 +: (2 to d).filterNot (b => dividable (b))
for (a <- s;
b <- s;
c <- s;
h <- s;
e <- s;
if (a+b+c+h+e == d)) yield {(a,b,c,h,e)}
}
``````
-
 I'm not familiar with Scala. How does this get called? Can you post a working example to ideone.com? – boothby May 17 '12 at 20:09 You better execute it on simply-scala because it needs less boilerplate than IDEone. For invocation, `println (l(17))` for example. The output looks typically like `Vector((17,0,0,2,2,13), (17,0,0,2,13,2), (17,0,0,3,3,11)` and means: 17 is to be summed, and the summands are 0, 0 (zero means absence of summand) 2+2+13. The link to simply scala is already documented on meta – user unknown May 17 '12 at 20:44 cool, thanks! Looks like you can save a few characters: `yield{(d,a,...` -> `yield{(a,...` and by packing the definition of `g` into `filterNot(...)`. However. This fails for n=3. – boothby May 17 '12 at 21:05 Do `(2 to d)` instead of `(2 to d-1)`, but I don't agree that 3 is the sum of 3. If you sum up a Set, yes, it can be an empty set, or a Set consisting of one number. But building a sum which leads to n - I only change my code under protest. – user unknown May 17 '12 at 22:30 As noble as your obstinate refusal to shorten your answer may be, your cause is undermined by your very answer. You're returning lists whose sum is `3`. One such should be `(0,0,0,0,3)`. – boothby May 18 '12 at 0:21

# MuPAD 113 - 8 = 105

``````g:=[0,ithprime(i)\$i=1..n]:f:=_for_in:f(l,g,f(d,g,f(b,g,f(a,g,f(c,g,if l+d+b+a+c=n then print(l,d,b,a,c)end)))))
``````

This version will also print all permutations of every solution:

``````0, 0, 0, 0, 7
0, 0, 0, 2, 5
0, 0, 0, 5, 2
0, 0, 0, 7, 0
0, 0, 2, 0, 5
...
``````

And yes, it creates a way too long list `g`. Who cares? :-)

Ungolfed version:

``````g:=[0].select([\$1..n],isprime):
for l in g do
for d in g do
for b in g do
for a in g do
for c in g do
if l+d+b+a+c=n then print(l,d,b,a,c); end;
end
end
end
end
end
``````
-
 I don't have access to mupad -- can somebody check that this works? – boothby May 21 '12 at 21:38