16
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The first number to check, odd integer > 1, is 3. Which sum of primes produces 3? Don't I see the obvious? \$\endgroup\$ – user unknown May 16 '12 at 5:31
  • \$\begingroup\$ 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). \$\endgroup\$ – boothby May 16 '12 at 7:53
  • \$\begingroup\$ A single value is not a sum. I would suggest simply starting with values > 3 instead of introducing negative values. \$\endgroup\$ – user unknown May 16 '12 at 12:39
  • 1
    \$\begingroup\$ A single value is a sum. The comment about negative values was a smartass remark, as explicitly noted. \$\endgroup\$ – boothby May 16 '12 at 18:34
  • 2
    \$\begingroup\$ "substring (not necessarily consecutive; just in order...)" This is called a subsequence. \$\endgroup\$ – Joey Adams May 17 '12 at 2:52

10 Answers 10

3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ nicely done! I think no language could beat J at this challenge. \$\endgroup\$ – Cristian Lupascu May 23 '12 at 14:53
8
\$\begingroup\$

Mathematica, 38

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

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ G,o,l,d,*b,a;c(h) is a nice touch! \$\endgroup\$ – Joel Cornett May 15 '12 at 20:15
  • \$\begingroup\$ this fails for n=3 \$\endgroup\$ – boothby May 17 '12 at 21:08
  • \$\begingroup\$ @boothby, you're right, it only finds some of 5 primes, not less. \$\endgroup\$ – ugoren May 18 '12 at 4:32
  • \$\begingroup\$ user_unknown has a good solution for this: consider zero prime for the sake of the sum \$\endgroup\$ – boothby May 18 '12 at 7:29
  • \$\begingroup\$ @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. \$\endgroup\$ – ugoren May 19 '12 at 13:05
6
\$\begingroup\$

Brachylog, 9 bytes

~+.ṗᵐl≤5∧

Try it online!

~+.          Output (.) should sum to the input,
   ṗᵐ        consist of all primes,
     l≤5     and have length ≤ 5.
        ∧    (Don't unify that 5 with the implicit output variable.)
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a byte by changing the order. Also note that the question states that the input is odd \$\endgroup\$ – H.PWiz May 4 '18 at 16:49
  • 1
    \$\begingroup\$ @H.PWiz And another one like this. \$\endgroup\$ – Erik the Outgolfer May 4 '18 at 16:57
4
\$\begingroup\$

Ruby 138 124 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]
...

Test: http://ideone.com/rua7A

\$\endgroup\$
  • 1
    \$\begingroup\$ Just putting #db on line 3 would be enough for the bonus: you'll get the ach from .each. \$\endgroup\$ – Ilmari Karonen May 15 '12 at 14:41
  • 1
    \$\begingroup\$ What do you mean 'fixed output format'? This one's totally open -- you can nix the spaces if you like. \$\endgroup\$ – boothby May 15 '12 at 15:35
  • \$\begingroup\$ @IlmariKaronen Great tip! I've edited my post. Thanks! \$\endgroup\$ – Cristian Lupascu May 15 '12 at 18:50
  • \$\begingroup\$ @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. \$\endgroup\$ – Cristian Lupascu May 15 '12 at 18:51
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Hmm... your submitted code doesn't seem to work. You've got a some funny stuff ~õ;} at the end... \$\endgroup\$ – boothby May 15 '12 at 23:20
  • \$\begingroup\$ ~õ (chr(245)) is shorthand for "\n". In this instance, it's not actually necessary. I'll remove it from the solution. \$\endgroup\$ – primo May 16 '12 at 11:19
  • \$\begingroup\$ code fails for n=3. \$\endgroup\$ – boothby May 17 '12 at 21:04
  • \$\begingroup\$ @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? \$\endgroup\$ – primo May 17 '12 at 21:43
  • \$\begingroup\$ 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. \$\endgroup\$ – boothby May 18 '12 at 0:26
2
\$\begingroup\$

Ruby 2 -rmathn, 66 bytes - 8 = 58

g=->o,*l{o==l.reduce(:+)?p(l):l[5]||b=Prime.each(o){|x|g[o,*l,x]}}

Heavily based on GolfWolf's answer, but since it's 6 years old I'm going to post my own instead of nitpicking. Advances in technology include the stabby lambda, using reduce instead of inject for the free d, a terse way of stopping at partitions of 5, and Prime.each(o), which iterates over all primes less than or equal to o (and furnishes an ach). Maybe in another 6 years there'll be a better way of using the b.

\$\endgroup\$
1
\$\begingroup\$

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)}
}
\$\endgroup\$
  • \$\begingroup\$ I'm not familiar with Scala. How does this get called? Can you post a working example to ideone.com? \$\endgroup\$ – boothby May 17 '12 at 20:09
  • \$\begingroup\$ 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 \$\endgroup\$ – user unknown May 17 '12 at 20:44
  • \$\begingroup\$ 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. \$\endgroup\$ – boothby May 17 '12 at 21:05
  • \$\begingroup\$ 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. \$\endgroup\$ – user unknown May 17 '12 at 22:30
  • \$\begingroup\$ 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). \$\endgroup\$ – boothby May 18 '12 at 0:21
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I don't have access to mupad -- can somebody check that this works? \$\endgroup\$ – boothby May 21 '12 at 21:38
1
\$\begingroup\$

Jelly, 19 bytes (but very slow -- advice wanted)

ÆR;0x5Œ!ḣ€5¹©S€i³ị®

Try it online!

ÆR;0x5Œ!ḣ€5¹©€i³ị®     main link, takes one argument N
ÆR                     get all the primes less than N
  ;0x5                 add zero, and then repeat the entire list 5 times
      Œ!               get all the permutations of this huge list (takes a long time!)
        ḣ€5            for each permutation, just take the first 5 numbers
                       (this gives us all possible length-5 combinations of the primes plus zero, with some repeats)
           ¹©          save that list to register
              S€       take the sum of every permutation in the list...
                i³     and find the index of our first argument N in that list of sums
                  ị®   then recall our list of permutations, and get the correct permutation at that index!

If you have any ideas to make it faster and shorter, please let me know!

\$\endgroup\$
  • 1
    \$\begingroup\$ 12 bytes. ṗЀ5 produces all combinations of primes with lengths one through five. S=¥ checks if the sum of one of the elements is equal to the chain's argument and Ðf keeps only those elements. is only there to put all lists of primes at the same level in the list \$\endgroup\$ – dylnan May 8 '18 at 20:00
  • \$\begingroup\$ Now 10 bytes since and Ƈ have been added as aliases for Ѐ and Ðf \$\endgroup\$ – dylnan May 14 '18 at 20:47

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.