17
\$\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\$
5
  • \$\begingroup\$ The first number to check, odd integer > 1, is 3. Which sum of primes produces 3? Don't I see the obvious? \$\endgroup\$ Commented May 16, 2012 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
    Commented May 16, 2012 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\$ Commented May 16, 2012 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
    Commented May 16, 2012 at 18:34
  • 2
    \$\begingroup\$ "substring (not necessarily consecutive; just in order...)" This is called a subsequence. \$\endgroup\$
    – Joey Adams
    Commented May 17, 2012 at 2:52

12 Answers 12

9
\$\begingroup\$

Mathematica, 38

IntegerPartitions[n,5,Prime~Array~n,1]
\$\endgroup\$
5
  • \$\begingroup\$ Can't find a way thru WA ... \$\endgroup\$ Commented May 16, 2012 at 15:40
  • 1
    \$\begingroup\$ I've got access to Mathematica, and it worked on all the inputs I gave it. \$\endgroup\$
    – boothby
    Commented May 17, 2012 at 16:33
  • \$\begingroup\$ imagine if the IntegerPartitions function was named Goldbach... ;) \$\endgroup\$ Commented May 21, 2012 at 8:48
  • \$\begingroup\$ @w0lf even so, it'd be 1 more than J >_> \$\endgroup\$
    – Rixius
    Commented May 30, 2012 at 21:36
  • \$\begingroup\$ @Rixius no, it would score 21 in that case, 8 less than J. \$\endgroup\$
    – Mr.Wizard
    Commented May 31, 2012 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\$
5
  • 4
    \$\begingroup\$ G,o,l,d,*b,a;c(h) is a nice touch! \$\endgroup\$ Commented May 15, 2012 at 20:15
  • \$\begingroup\$ this fails for n=3 \$\endgroup\$
    – boothby
    Commented May 17, 2012 at 21:08
  • \$\begingroup\$ @boothby, you're right, it only finds some of 5 primes, not less. \$\endgroup\$
    – ugoren
    Commented May 18, 2012 at 4:32
  • \$\begingroup\$ user_unknown has a good solution for this: consider zero prime for the sake of the sum \$\endgroup\$
    – boothby
    Commented May 18, 2012 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
    Commented May 19, 2012 at 13:05
8
\$\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\$
2
  • 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
    Commented May 4, 2018 at 16:49
  • 1
    \$\begingroup\$ @H.PWiz And another one like this. \$\endgroup\$ Commented May 4, 2018 at 16:57
4
\$\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\$
1
  • \$\begingroup\$ nicely done! I think no language could beat J at this challenge. \$\endgroup\$ Commented May 23, 2012 at 14:53
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\$
4
  • 1
    \$\begingroup\$ Just putting #db on line 3 would be enough for the bonus: you'll get the ach from .each. \$\endgroup\$ Commented May 15, 2012 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
    Commented May 15, 2012 at 15:35
  • \$\begingroup\$ @IlmariKaronen Great tip! I've edited my post. Thanks! \$\endgroup\$ Commented May 15, 2012 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\$ Commented May 15, 2012 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\$
6
  • \$\begingroup\$ Hmm... your submitted code doesn't seem to work. You've got a some funny stuff ~õ;} at the end... \$\endgroup\$
    – boothby
    Commented May 15, 2012 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
    Commented May 16, 2012 at 11:19
  • \$\begingroup\$ code fails for n=3. \$\endgroup\$
    – boothby
    Commented May 17, 2012 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
    Commented May 17, 2012 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
    Commented May 18, 2012 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\$
7
  • \$\begingroup\$ I'm not familiar with Scala. How does this get called? Can you post a working example to ideone.com? \$\endgroup\$
    – boothby
    Commented May 17, 2012 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\$ Commented May 17, 2012 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
    Commented May 17, 2012 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\$ Commented May 17, 2012 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
    Commented May 18, 2012 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\$
1
  • \$\begingroup\$ I don't have access to mupad -- can somebody check that this works? \$\endgroup\$
    – boothby
    Commented May 21, 2012 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\$
2
  • 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
    Commented May 8, 2018 at 20:00
  • \$\begingroup\$ Now 10 bytes since and Ƈ have been added as aliases for Ѐ and Ðf \$\endgroup\$
    – dylnan
    Commented May 14, 2018 at 20:47
0
\$\begingroup\$

Vyxal, 9 bytes

Ṅ'L5≤næA∧

Try it Online!

Outputs all possible sums.

Explained

Ṅ'L5≤næA∧   # Takes a single integer n and returns a list of lists
Ṅ           # Push all the integer partitions (ways to sum to) of n
 '          # and keep only those where:
  L5≤       #   the length of the partition is less than or equal to 5 (can also be 6<)
        ∧   #   and
     næA    #   all integers in the partition are prime
\$\endgroup\$
0
\$\begingroup\$

Japt, 19 bytes

Hideous, and slow as hell! Will crap out on inputs higher than 5.

ÆõÃc fj à l§5 æ@¶Xx

Try it

ÆõÃc fj à l§5 æ@¶Xx     :Implicit input of integer U
Æ                       :Map the range [0,U)
 õ                      :  Range [1,U]
  Ã                     :End map
   c                    :Flatten
     f                  :Filter
      j                 :  Prime
        à               :Combinations
          l             :Filter by length
           §5           :  <=5
              æ         :Get the first to return true
               @        :When passed through the following function as X
                ¶       :  U is equal to
                 Xx     :  Sum of X
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.