15
\$\begingroup\$

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.

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

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]
\$\endgroup\$
  • \$\begingroup\$ Cool solution, however bounds are a bit tight, because your program for 1 000 000 finds greater solution (see my example). \$\endgroup\$ – Somnium Jul 21 '14 at 14:56
  • 1
    \$\begingroup\$ @user2992539 My code returns the lexicographically first solution (250001 < 500000). \$\endgroup\$ – Howard Jul 21 '14 at 15:00
7
\$\begingroup\$

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]}

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

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Does not work (hint: integer division). \$\endgroup\$ – Howard Jul 21 '14 at 12:18
  • \$\begingroup\$ Likely it won't work because of round-off errors. \$\endgroup\$ – Somnium Jul 21 '14 at 12:49
  • \$\begingroup\$ @user2992539 it works for me, I tested it with 5 as input and it gave the correct result (2, 4, 20) \$\endgroup\$ – Christoph Böhmwalder Jul 21 '14 at 12:51
  • \$\begingroup\$ @HackerCow it may not work for large integers. \$\endgroup\$ – Somnium Jul 21 '14 at 13:00
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Alchymist Jul 22 '14 at 7:52
3
+100
\$\begingroup\$

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).

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

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.

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

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
\$\endgroup\$
1
\$\begingroup\$

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.

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

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;}
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

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.