# Write program which verifies Erdős–Straus conjecture

Write program, which verifies Erdős–Straus conjecture.
Program should take as input one integern (3 <= n <= 1 000 000) and print triple of integers satisfying identity 4/n = 1/x + 1/y + 1/z, 0 < x < y < z.

Shortest code wins.

Some examples:

3 => {1, 4, 12}
4 => {2, 3, 6}
5 => {2, 4, 20}
1009 => {253, 85096, 1974822872}
999983 => {249996, 249991750069, 62495875102311369754692}
1000000 => {500000, 750000, 1500000}


Note that your program may print other results for these numbers because there are multiple solutions.

• Does the program need to output every possible solution or only one? For example there are 2 possibilities for n=5. – izlin Jul 21 '14 at 12:06
• Only one is enough. – Somnium Jul 21 '14 at 12:43
• It is somewhat misleading that your only test case is not a valid input according to the spec. – Peter Taylor Jul 21 '14 at 14:28
• I'll change it, example added durron597. – Somnium Jul 21 '14 at 14:39
• I added that example because my research suggested it was a particularly difficult one to do. The hardest ones are primes that are congruent to {1, 121, 169, 289, 361, 529} modulo 840. – durron597 Jul 22 '14 at 15:09

### Ruby, 119 106 characters

f=->s,c,a{m=s.to_i;c<2?m<s||(p a+[m];exit):(1+m...c*s).map{|k|f[s/(1-s/k),c-1,a+[k]]}}
f[gets.to_r/4,3,[]]


The code uses minimal bounds for each variable, e.g. n/4<x<3n/4, similarly for y. Even the last example returns instantaneous (try here).

Examples:

> 12
[4, 13, 156]

> 123
[31, 3814, 14542782]

> 1234
[309, 190654, 36348757062]

> 40881241801
[10220310451, 139272994276206121600, 22828913614743204775214996005450198400]

• Cool solution, however bounds are a bit tight, because your program for 1 000 000 finds greater solution (see my example). – Somnium Jul 21 '14 at 14:56
• @user2992539 My code returns the lexicographically first solution (250001 < 500000). – Howard Jul 21 '14 at 15:00

# Mathematica 62

This plain-vanilla solution works fine--most of the time.

f@n_ := FindInstance[4/n == 1/x + 1/y + 1/z && 0 < x < y < z, {x, y, z}, Integers]


Examples and Timings (in secs)

AbsoluteTiming[f[63]]
AbsoluteTiming[f[123]]
AbsoluteTiming[f[1003]]
AbsoluteTiming[f[3003]]
AbsoluteTiming[f[999999]]
AbsoluteTiming[f[1000000]]


{0.313671, {{x -> 16, y -> 1009, z -> 1017072}}}
{0.213965, {{x -> 31, y -> 3814, z -> 14542782}}}
{0.212016, {{x -> 251, y -> 251754, z -> 63379824762}}}
{0.431834, {{x -> 751, y -> 2255254, z -> 5086168349262}}}
{1.500332, {{x -> 250000, y -> 249999750052, z -> 1201920673328124750000}}}
{1.126821, {{x -> 375000, y -> 1125000, z -> 2250000}}}

But it does not constitute a complete solution. There are a some numbers that it cannot solve for. For example,

AbsoluteTiming[f[30037]]
AbsoluteTiming[f[130037]]


{2.066699, FindInstance[4/30037 == 1/x + 1/y + 1/z && 0 < x < y < z, {x, y, z}, Integers]}
{1.981802, FindInstance[4/130037 == 1/x + 1/y + 1/z && 0 < x < y < z, {x, y, z}, Integers]}

• The right tool for the right job. +1 – William Barbosa Jul 21 '14 at 15:40
• @WilliamBarbosa I'd argue that FindInstance is not the right tool since it cannot guarantee a result... – Howard Jul 21 '14 at 15:44
• @Howard I was talking about Mathematica, actually – William Barbosa Jul 21 '14 at 15:47
• Reduce seems to solve the stubborn cases, though it often takes time. E.g. 15 minutes to find 82 solutions for n=10037. – DavidC Jul 21 '14 at 18:39

# C#

Disclamer: this is not a serious answer

This just bruteforces all the possibilities from 1 to 1<<30. It's huge, it's slow, I don't even know if it works correctly, but it follows the specifications quite literally, as it checks the condition every single time, so that's nice. I haven't tested this because ideone has a 5 second time limit for programs and therefore this won't finish executing.

(In case anyone was wondering: this is a whopping 308 bytes long)

static double[]f(double n)
{
for(double x=1;x<1<<30;x++)
{
for(double y=1;y<1<<30;y++)
{
for(double z=1;z<1<<30;z++)
{
if(4/n==1/x+1/y+1/z)
return new[]{x,y,z};
}
}
}
return null;
}


Update: fixed it so it actually works

• Does not work (hint: integer division). – Howard Jul 21 '14 at 12:18
• Likely it won't work because of round-off errors. – Somnium Jul 21 '14 at 12:49
• @user2992539 it works for me, I tested it with 5 as input and it gave the correct result (2, 4, 20) – Christoph Böhmwalder Jul 21 '14 at 12:51
• @HackerCow it may not work for large integers. – Somnium Jul 21 '14 at 13:00
• @HackerCow you can certainly save time by starting with y=x+1 and z=y+1. It will probably be faster to use the equivalent check 4xyz = n(xy+yz+xz), although I accept that is a longer expression and also has rounding problems. – Alchymist Jul 22 '14 at 7:52

# Python 2, 171 bytes

from sympy import*
def f(n):
for d in xrange(1,n*n):
for p in divisors(4*d+n*n):
q=(4*d+n*n)/p;x=(n+p)/4;y=(n+q)/4
if (n+p)%4+(n+q)%4+n*x*y%d<1:return x,y,n*x*y/d


Try it online!

The first answer fast enough to be exhaustively tested. This is able to find solutions for all 3 ≤ n ≤ 1000000 in about 24 minutes total, for an average of about 1.4 milliseconds each.

### How it works

Rewrite 4/n = 1/x + 1/y + 1/z as z = n·x·y/d, where d = 4·x·yn·xn·y. Then we can factor 4·d + n2 = (4·xn)·(4·yn), which gives us a much faster way to search for x and y as long as d is small. Given x < y < z, we can at least prove d < 3·n2/4 (hence the bound on the outer loop), although in practice it tends to be much smaller—95% of the time, we can use d = 1, 2, or 3. The worst case is n = 769129, for which the smallest d is 1754 (this case takes about 1 second).

## Mathematica, 99 bytes

f[n_]:=(x=1;(w=While)[1>0,y=1;w[y<=x,z=1;w[z<=y,If[4/n==1/x+1/y+1/z,Return@{x,y,z}];++z];++y];++x])


It's fairly naive brute force, so it doesn't really scale well. I'm definitely going to get to a million (so feel free to consider this invalid for the time being). n = 100 takes half a second, but n = 300 already takes 12 seconds.

# Golflua 75

Reads n from prompt (after invocation in terminal), but basically iterates as Calvin's Hobbies solution does:

n=I.r()z=1@1~@y=1,z-1~@x=1,y-1?4*x*y*z==n*(y*z+x*z+x*y)w(n,x,y,z)~$z=z+1$


An ungolfed Lua version of the above is

n=io.read()
z=1
while 1 do
for y=1,z-1 do
for x=1,y-1 do
if 4*x*y*z==n*(y*z+x*z+x*y) then
print(n,x,y,z)
return
end
end
end
z=z+1
end


Examples:

n=6     -->     3      4     12
n=12    -->     6     10     15
n=100   -->    60     75    100
n=1600  -->  1176   1200   1225


# Python, 117

n=input();r=range;z=0
while 1:
z+=1
for y in r(z):
for x in r(y):
if 4*x*y*z==n*(y*z+x*z+x*y):print x,y,z;exit()


Example:

16 --> 10 12 15


Nothing too special.

• Why do you define a function if you're only going to call it once? – isaacg Jul 22 '14 at 8:31
• @isaacg It needs to stop somehow, but using exit() instead does shorten it. – Calvin's Hobbies Jul 22 '14 at 12:15

# C# - 134

Well, I posted an answer here before, but it wasn't really that serious. As it so happens, I'm very often very bored, so I golfed it a little bit.

It calculates all the examples technically correctly (I haven't tried the last two because, again, ideone inforces a 5 second time limit) but the first ones yield the correct result (not necessarily the result you calculated, but a correct one). It strangely outputs the number out of order (I have no clue why) and it gives 10, 5, 2 for 5 (which is a valid answer according to wikipedia).

134 bytes for now, I could probably golf it up a bit more.

float[]f(float n){float x=1,y,z;for(;x<1<<30;x++)for(y=1;y<x;y++)for(z=1;z<y;z++)if(4/n==1/x+1/y+1/z)return new[]{x,y,z};return null;}


### Haskell - 150 characters

main = getLine >>= \n -> (return $head$ [(x,y,z) | x <- [1..y], y <- [1..z], z <- [1..], (4/n') == (1/x) + (1/y) + (1/z)]) where n' = read n

This ought to work, but I've not compiled it yet. It's almost certainly very very slow. It checks every possible triplet of valid integers, and should stop when it sees a set that works.