Write a program that prompts the user for an even integer greater than 2.
Given Goldbach’s conjecture that every even integer greater than 2 can be expressed as the sum of two primes, print out two prime numbers which, when added together, provide the requested even number. Edit: the program only has to print A PAIR of primes, not all. For example:
4 : 2 + 2
6: 3 + 3
8: 3 + 5
10: 5 + 5 or 3 + 7
The first version is 34 symbol long and is restricted to characters from the original single-byte APL charsets, such as the one still supported in Dyalog APL:
↑c/⍨n=+/¨c←,∘.,⍨v/⍨~v∊v∘.×v←1↓⍳n←⎕
Explanation:
n←⎕ ⍝ ask for a number, store as n
v←1↓⍳n ⍝ generate all integers from 2 to n
v∘.×v ⍝ compute the product table of any two such integers
v/⍨~v∊ ⍝ select those that don't appear in the product table
c←,∘.,⍨ ⍝ generate all possible pairs of these primes
n=+/¨c ⍝ check which pairs have a sum equal to n
↑c/⍨ ⍝ take the first that does
The second version is only 22 symbol long, because it exploits the π function to check for prime numbers, but that's only available in NARS2000 which uses Unicode, so the byte count is 44 in UCS-2:
2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1
Explanation:
⎕ ⍝ ask for a number N
⍳ -1 ⍝ generate all naturals from 1 to N-1
(⍪,⌽) ⍝ arrange it into a table of all pairs of naturals with sum N
{∧/0π⍵} ⍝ check which pairs are made of all primes
2⍴(⌿⍨ ) ⍝ return the first pair that does
Examples
(⎕: is the prompt asking for a number)
2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1
⎕:
4
2 2
2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1
⎕:
6
3 3
2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1
⎕:
8
3 5
2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1
⎕:
124
11 113
¯2π⍳2πn work as a prime generator?
\$\endgroup\$
π operator do exactly?
\$\endgroup\$
π switches with ⍺: ¯2πx calculates the xth prime, ¯1πx is the first prime less than x, 0πx tests x for primality, 1πx is the first prime greater than x, 2πx is the number of primes less than x, 10πx is the number of divisors of x, 11πx is the sum of all divisors of x, 12πx and 13πx are the Möbius and totient function, respectively. Last but not least, the monadic πx returns the prime factorization of x.
\$\endgroup\$
n=input();k=m=1;p={0}
while{n-k,k}-p:m*=k*k;k+=1;p|={m%k*k}
print n-k,k
Test it on Ideone.
We use a corollary of Wilson's theorem:
At all times, the variable m is equal to the square of the factorial of k - 1; k starts at value 1 and m at value 0!² = 1. The set p will consist of 0 and all prime numbers up to the current value of k.
In each iteration, we first check if both n - k and k belong to p, which is true if and only if the set difference of {n-k, k} and p is empty. If it is, the condition is falsy and the loop continues.
Note that k > 0, and {n - k, k} will satisfy the condition for some positive value of n - k (assuming that Goldbach's conjecture is true), so the 0 in p won't lead to false positives.
In the loop, we update k and m. The new value of m is m × k² = (k - 1)!² × k² = k!², and the new value of k is k + 1, so m = (k - 1)!² still holds before and after the update.
Then, we perform set union to add the value of m % k × k to p. By the corollary of Wilson's theorem, this will add 1 × k = k if k is prime and 0 × k = 0 if not.
When the loop ends, we print the last values of n - k and k, which will be primes with sum n.
require'prime'
n=gets.to_i
Prime.find{|i|p [i,n-i]if(n-i).prime?}
<?for(;@($n%--$$n?:$o=&$argv[1]>$$n=++$n)||${++$b}^${--$o};);echo"$b+$o";
Input is taken as a command line argument.
Sample usage:
$ php goldbach.php 7098
19+7079
~(,2>.-1%]zip{{.,2>\{\%!}+,},!}?
Accepts command line argument e.g.
echo "14" | ruby golfscript.rb goldbach.gs
-> [2 12]
Finds all relevant partitions of the input number with:
(,2>.-1%]zip #If only zip were a one-character command! It is so often useful.
and then finds the first partition where no numbers are NOT prime with:
{np,!}? #For each partition, filter down to elements that are not prime, and only accept if there are no such results (since [] is falsey).
where the composite-checking block np is:
{.,2>\{\%!}+,}
this block filters down to all numbers that evenly divide a given number. If there are no such numbers (so the number is prime), the result is [], which is falsey in GolfScript.
$/=get;for grep &is-prime,^$/ {exit say $_,$_-$/ if ($/-$_).is-prime}
a=scan();b=2:a;p=b[rowSums(!outer(b,b,`%%`))<2];q=p[(a-p)%in%p][1];cat(a,":",q,a-q)
Indented:
a=scan() #Take user input as a numeric
b=2:a
p=b[rowSums(!outer(b,b,`%%`))<2] #Find all primes from 2 to user input
q=p[(a-p)%in%p][1] #Check which a-p also belong to p and takes the first one
cat(a,":",q,a-q)
Usage:
> a=scan();b=2:a;p=b[rowSums(!outer(b,b,`%%`))<2];q=p[(a-p)%in%p][1];cat(a,":",q,a-q)
1: 72
2:
Read 1 item
72 : 5 67
Old solution at 112 characters, for posterity
a=scan();b=2:a;p=b[rowSums(!outer(b,b,`%%`))<2];w=which(outer(p,p,`+`)==a,T);cat(a,":",p[w[1,1]],p[w[1,2]])
Indented:
a=scan()
b=2:a
p=b[rowSums(!outer(b,b,`%%`))<2]
w=which(outer(p,p,`+`)==a,T) #Find the index of valid combinations
cat(a,":",p[w[1,1]],p[w[1,2]]) #Prints the first valid combination
Basically an improvement on the second part of nutria's answer (I ran this on 2.7 but I think it should also work for 3.x)
p=lambda x:all(x%i!=0 for i in range(2,x))
n=input()
for i in range(2,n-1):
if p(i)&p(n-i): print i,n-i
: mandatory?
\$\endgroup\$
a=/^(xx+?)(?!(xx+)\2+$)x*(?=\1$)(?!(xx+)\3+$)/.exec("x".repeat(prompt()));alert(a[1].length+"+"+a[0].length)
Now you have a regex that tests the Goldbach conjecture, which has low requirement on special features (basic back-reference support, positive and negative look-ahead).
This uses String.prototype.repeat(), which is part of EcmaScript 6th edition proposal. Currently, this code only works on Firefox.
I really need a better language that has terse command when working with regex...
Not the fastest but it works. Call g(10) to obtain the list of goldbach pairs for 10.
def g(n:Int)={def p(n:Int,f:Int=2):Boolean=f>n/2||n%f!=0&&p(n,f+1)
s"$n : "+(for(i<-2 to n/2;j=n-i if p(i)&&p(j))yield s"$i + $j").mkString(" or ")}
Conversion to C++ is straightforward.
a,b;i(x,y){return x>y?x%y?i(x,y+1):0:x>1;}main(){scanf("%i",&a);for(b=a/2;b-->1;)i(b,2)&&i(a-
b,2)&&printf("%i:%i+%i\n",a,b,a-b);}
int declarations in your function i. You can save another 2 characters by removing the if and adding in another double ampersand: i(b,2)&&i(a-b,2)&&printf(...)
\$\endgroup\$
&&. (I'll never get used to argument type silencing...)
\$\endgroup\$
(define(p n)(=(length(factor n))1))
(define(g n)(when(even? n)(for(i 3 n 2)
(and(p i)(p(- n i))(println n {: } i { }(- n i))))))
(g(int(read-line)))
includes the code to run it. The results are over-generous...
72: 5 67
72: 11 61
72: 13 59
72: 19 53
72: 29 43
72: 31 41
72: 41 31
72: 43 29
72: 53 19
72: 59 13
72: 61 11
72: 67 5
Similar in score and feel to r.e.s.'s solution, but I think it's different enough to post.
i=n=input()
while not{i,n-i}<set(primes(n)):i-=1
print i,n-i
n=input()
i=0
p=is_prime
while p(i)*p(n-i)==0:i+=1
print i,n-i
With the above in file goldbach.sage, execute it with Sage running in a terminal:
sage: %runfile goldbach.sage
Thanks to @boothby for the p=is_prime idea.
p=is_prime.
\$\endgroup\$
Haskell, 97C
g n=head[(a,b)|let q=p n,a<-q,b<-q,a+b==n]
p n=filter c[2..n]
c p=null[x|x<-[2..p-1],p`mod`x==0]
Explanation:
g is the "goldbach" function. Calling g n gives you the pair of primes that add up to n.p is a function that generates a list of primes less than n.c is the prime checker function used to define p.Example runs:
*Main> g 4
(2,2)
*Main> g 6
(3,3)
*Main> g 8
(3,5)
*Main> g 10
(3,7)
*Main> g 12
(5,7)
*Main> map g [4,6..100]
[(2,2),(3,3),(3,5),(3,7),(5,7),(3,11),(3,13),(5,13),(3,17),(3,19),(5,19),(3,23),(5,23),(7,23),(3,29),(3,31),(5,31),(7,31),(3,37),(5,37),(3,41),(3,43),(5,43),(3,47),(5,47),(7,47),(3,53),(5,53),(7,53),(3,59),(3,61),(5,61),(7,61),(3,67),(5,67),(3,71),(3,73),(5,73),(7,73),(3,79),(5,79),(3,83),(5,83),(7,83),(3,89),(5,89),(7,89),(19,79),(3,97)]
This returns all of the solutions for the input integer.
Select[Tuples[Prime@Range@PrimePi[n = Input[]], 2], Tr@# == n &]
For example, when 1298 is input…
{{7, 1291}, {19, 1279}, {61, 1237}, {67, 1231}, {97, 1201}, {127, 1171}, {181, 1117}, {211, 1087}, {229, 1069}, {277, 1021}, {307, 991}, {331, 967}, {379, 919}, {421, 877}, {439, 859}, {487, 811}, {541, 757}, {547, 751}, {571, 727}, {607, 691}, {691, 607}, {727, 571}, {751, 547}, {757, 541}, {811, 487}, {859, 439}, {877, 421}, {919, 379}, {967, 331}, {991, 307}, {1021, 277}, {1069, 229}, {1087, 211}, {1117, 181}, {1171, 127}, {1201, 97}, {1231, 67}, {1237, 61}, {1279, 19}, {1291, 7}}
As written, it returns each solution twice.
Union[Sort/@ %]
{{7, 1291}, {19, 1279}, {61, 1237}, {67, 1231}, {97, 1201}, {127, 1171}, {181, 1117}, {211, 1087}, {229, 1069}, {277, 1021}, {307, 991}, {331, 967}, {379, 919}, {421, 877}, {439, 859}, {487, 811}, {541, 757}, {547, 751}, {571, 727}, {607, 691}}
Cases[{1,1}~FrobeniusSolve~Input[],{__?PrimeQ}] or even in 42 bytes as a function: Cases[{1,1}~FrobeniusSolve~#,{__?PrimeQ}]&.
\$\endgroup\$
~=primes;n=ARGS[]|>int
(n-~n)∩~n|>extrema|>show
If a function were acceptable, the code could be shortened to 32 bytes:
~=primes
!n=(n-~n)∩~n|>extrema
~=primes creates an alias for the built-in primes function which returns a list of all prime numbers up to its argument. n=ARGS[]|>int parses the first command-line argument as saves it in n.
To find a suitable pair of primes, we first compute the aforementioned prime range with ~n. Then, n-~n yields all differences of these primes and n.
By intersecting (∩) the result with the prime range itself, we make sure that the remaining primes p are such that n - p is also a prime.
Finally, extrema takes the lowest and highest prime in the intersection, so their sum must be n.
julia> g(n)=collect(filter((x)->sum(x)==n,combinations(primes(n),2)))
g (generic function with 1 method)
julia> g(88)
4-element Array{Array{Int64,1},1}:
[5,83]
[17,71]
[29,59]
[41,47]
For your TI-84 Calculator
`A:.5A→B@%;A,4)4$~B+1,B-1#~B,B&
No prime built-ins.
Example runs
?4
2
2
?6
3
3
?8
3
5
?10
5
5
a=prompt();function b(n){for(i=2;i<n;i++)if(n%i<1)return;return 1}for(c=2,r=1;c<a&&r;c++)if(b(c)&&b(a-c))alert(a+": "+c+" + "+(a-c)),r=0
return; instead of return 0;
\$\endgroup\$
Commented
Jan 27, 2014 at 23:16
Old version (150 characters):
p=lambda n:0 in[n % i for i in range(2,n)]
n=int(input())
[print('%d+%d'%(a, b))for b in range(2,n)for a in range(2,n)if not(a+b!=n or p(a) or p(b))]
New version (thanks to ProgramFOX):
p=lambda n:0 in[n%i for i in range(2,n)]
n=int(input())
[print('%d+%d'%(a,b))for b in range(2,n)for a in range(2,n)if not((a+b!=n)|p(a)|p(b))]
It prints every combination, for example:
4
2+2
10 7+3 5+5 3+7
| can safely be used with boolean type, so (a+b!=n)|p(a)|p(b)
\$\endgroup\$
Commented
Jan 27, 2014 at 21:09
print([(a,b)for b in range(2,n)for a in range(2,n)if not((a+b!=n)|p(a)|p(b))]) (prints a list of tuples, whose sum is n). Saves 8 bytes.
\$\endgroup\$
r=range(2,n) and referencing r saves a few more.
\$\endgroup\$
y where all each{{2=count where 0=(x mod)each til x+1}each x}each y:{a where x=sum each a:a cross a:til x}"I"$read0 0
No inbuilt function to find prime number.
Input
72
Output
5 67
11 61
13 59
19 53
29 43
31 41
41 31
43 29
53 19
59 13
61 11
67 5
A little late to the party but I am practicing my golfing skills.
I actually coded this before I found this question! So mine doesn't include the beautiful lambda that the other Python solutions use.
import math
def p(n):
if n%2==0&n>2:return False
for i in range(3,n):
if n%i==0:return False
return True
X=int(input())
for i in range(2,X):
if p(i)&p(X-i):print i,X-i;break
"Prompt the user" is the bane of every J golfer. There go all my hard-earned characters!
p:(n,n)#:i.&n,+/~p:i.n=:".1!:1]1
Explained:
".1!:1]1 - Read in a string (1!:1) from input (file handle 1) and convert it to a number (".).p:i.n=: - Assign this number to the variable n, and then take the first n primes.+/~ - Make an addition table, n wide and n high.i.&n, - Turn the table into a single list, and then find the index of the first occurrence of n, which exists if Goldbach's conjecture is true.p:(n,n)#: - Retrieve the row and column from the index, and take the corresponding primes.Usage:
p:(n,n)#:i.&n,+/~p:i.n=:".1!:1]1
666
5 661
p:(n,n)#:i.&n,+/~p:i.n=:".1!:1]1
1024
3 1021
Had the prompt not been a requirement, here's a 25 character verb:
(,~p:@#:]i.~&,+/~@:p:@i.)
_ÆRfÆR.ị
Try it online! or verify all test cases.
_ÆRfÆR.ị Main link. Argument: n (integer)
ÆR Prime range; yield all primes in [1, ..., n].
_ Subtract all primes from n.
fÆR Filter; intersect the list of differences with the prime range.
.ị At-index 0.5; yield the last and first element.
Python3 version of this one -110 bytes
p=lambda x:all(x%i!=0 for i in range(2,x))
n=int(input())
for i in range(2,n-1):
if p(i)&p(n-i): print(i,n-i)
and a super golfed version:
exec(bytes('㵰慬扭慤砠愺汬砨椥㴡‰潦湩爠湡敧㈨砬⤩渊椽瑮椨灮瑵⤨潦湩爠湡敧㈨測ㄭ㨩 晩瀠椨☩⡰⥩›牰湩⡴Ⱪ⥩','u16')[2:])
In postgresql:
create function c(c int) returns table (n int, m int) as $$
with recursive i(n) as
(select 2 union all select n+1 from i where n<c),
p as (select * from i a where not exists
(select * from i b where a.n!=b.n and mod(a.n,b.n)=0))
select * from p a, p b where a.n+b.n=c
$$ language sql;
Should be able to do it in half the space though, if it weren't for things like "no left outer join in recursion", "no subquery in recursion"...
Here's the output:
postgres=# select c(10);
c
-------
(3,7)
(5,5)
(7,3)
(3 rows)
postgres=# select c(88);
c
---------
(5,83)
(17,71)
(29,59)
(41,47)
(47,41)
(59,29)
(71,17)
(83,5)
(8 rows)
@echo off&setLocal enableDelayedExpansion&for /L %%a in (2,1,%1)do (set/aa=%%a-1&set c=&for /L %%b in (2,1,!a!)do set/ab=%%a%%%%b&if !b!==0 set c=1
if !c! NEQ 1 set l=!l!%%a,)&for %%c in (!l!)do for %%d in (!l!)do set/ad=%%c+%%d&if !d!==%1 set o=%%c + %%d
echo !o!
Set out neatly -
@echo off
setLocal enableDelayedExpansion
for /L %%a in (2,1,%1) do (
set /a a=%%a-1
set c=
for /L %%b in (2,1,!a!) do (
set /a b=%%a%%%%b
if !b!==0 set c=1
)
if !c! NEQ 1 set l=!l!%%a,
)
for %%c in (!l!) do for %%d in (!l!) do (
set /a d=%%c+%%d
if !d!==%1 set o=%%c + %%d
)
echo !o!
57, plus 1 for -nE
/^(11+?)(?!(11+)\2+$)1*(?=\1$)(?!(11+)\3+$)/;say for$1,$&
Input and output are in unary. Example:
$ perl -nE'/^(11+?)(?!(11+)\2+$)1*(?=\1$)(?!(11+)\3+$)/;say for$1,$&'
1111111111
111
1111111
WITH v(x,y,s)AS(SELECT LEVEL,LEVEL,0 FROM DUAL CONNECT BY LEVEL<=:1 UNION ALL SELECT x,y-1,s+SIGN(MOD(x,y))FROM v WHERE y>1),p AS(SELECT x FROM v WHERE x-s=2)SELECT a.x,b.x FROM p a,p b WHERE:1=a.x+b.x;
Un-golfed
WITH v(x,y,s) AS
(
SELECT LEVEL,LEVEL,0 FROM DUAL CONNECT BY LEVEL<=:1
UNION ALL
SELECT x,y-1,s+SIGN(MOD(x,y))FROM v WHERE y>1
)
,p AS (SELECT x FROM v WHERE x-s=2)
SELECT a.x,b.x
FROM p a,p b
WHERE :1=a.x+b.x;
