Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
Does the program need to output every possible solution or only one? For example there are 2 possibilities for n=5. –  izlin Jul 21 at 12:06
1  
Only one is enough. –  Somnium Jul 21 at 12:43
2  
It is somewhat misleading that your only test case is not a valid input according to the spec. –  Peter Taylor Jul 21 at 14:28
    
I'll change it, example added durron597. –  Somnium Jul 21 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 at 15:09

9 Answers 9

up vote 9 down vote accepted

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]
share|improve this answer
    
Cool solution, however bounds are a bit tight, because your program for 1 000 000 finds greater solution (see my example). –  Somnium Jul 21 at 14:56
1  
@user2992539 My code returns the lexicographically first solution (250001 < 500000). –  Howard Jul 21 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]}

share|improve this answer
    
The right tool for the right job. +1 –  William Barbosa Jul 21 at 15:40
2  
@WilliamBarbosa I'd argue that FindInstance is not the right tool since it cannot guarantee a result... –  Howard Jul 21 at 15:44
2  
@Howard I was talking about Mathematica, actually –  William Barbosa Jul 21 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. –  David Carraher Jul 21 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

share|improve this answer
1  
Does not work (hint: integer division). –  Howard Jul 21 at 12:18
    
Likely it won't work because of round-off errors. –  Somnium Jul 21 at 12:49
    
@user2992539 it works for me, I tested it with 5 as input and it gave the correct result (2, 4, 20) –  HackerCow Jul 21 at 12:51
    
@HackerCow it may not work for large integers. –  Somnium Jul 21 at 13:00
1  
@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 at 7:52

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.

share|improve this answer

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
share|improve this answer

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.

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

Javascript - 99+(n.length-1)

for(n=9,x=1;x<1<<10;x++)for(y=1;y<x;y++)for(z=1;z<y;z++)if(4/n==(1/x+1/y+1/z))alert(x+","+y+","+z);

There were no rules for the input, so you have to init the variable n directly. That's why the length of my code is a bit variable.
The loop-range is not large enough, to find all cases for 3 <= n <= 1 000 000, but i wanted a version which is easy to test, because a larger range takes pretty much time and Firefox throws annoying script-warnings every few seconds. It won't change the length if you adjust it.
The code will pop warnings with every possible solution for your chosen n.

share|improve this answer

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;}
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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