9
\$\begingroup\$

I was working on a math question with a friend of mine, and we decided to write a script that finds the answer. The original question is as follows:

The difference of two natural numbers is 2010 and their greatest common denominator is 2014 times smaller than their lowest common multiply. Find all the possible solutions.

We started writing the program independently of each other, and when it worked we decided to golf it up to get the least amount of bytes we could manage. We ended up with this beautiful line of code at a marvelous 89 bytes.

from fractions import*;print[i for i in range(10**6)if i*(i+2010)/gcd(i,i+2010)**2==2014]

We wanted to see if anyone manages to write a shorter piece of code, that enumerates the first 1 million i's. If you are brave enough to compete, you may use any language you like, but we would prefer Python 2 to be able to compare your code with ours.

Usual rules apply, shortest bytes win. The standard code golf loopholes apply. Standard "loopholes" which are no longer funny

Have fun!

\$\endgroup\$
  • 2
    \$\begingroup\$ @Rainbolt: Ok, allowed any language. The python limitation was for comparison purposes. But just do whatever you want :D \$\endgroup\$ – sammko Dec 11 '14 at 21:47
  • \$\begingroup\$ Are there answers other than 3 and 5092? Can't find anything else before 10,000,000. \$\endgroup\$ – kennytm Dec 11 '14 at 21:59
  • \$\begingroup\$ @KennyTM: I got 4 and 5092. And yes, I dont think there are any others. \$\endgroup\$ – sammko Dec 11 '14 at 22:01
  • \$\begingroup\$ Hey, I have edited your title to better reflect what you are asking. Feel free to change it if you feel like I missed something. \$\endgroup\$ – FryAmTheEggman Dec 11 '14 at 22:06
  • \$\begingroup\$ Removed python tag by the way. \$\endgroup\$ – Timtech Dec 11 '14 at 22:08

11 Answers 11

21
\$\begingroup\$

Mathematica, 8 bytes

{4,5092}

Proof that 4 and 5092 are the only solutions: The original problem can be rewritten as

x (x + 2010) = 2014 GCD(x, x+2010)2

Let's write x as 2a2 3a3 5a5… and x + 2010 as 2b2 3b3 5b5… Then the equation becomes

2a2+b2 3a3+b3 5a5+b5… = 2014 22min(a2,b2) 32min(a3,b3) 52min(a5,b5)

Since 2014 = 2 × 19 × 53, we have

ap + bp = 2min(ap, bp) + { 1 if p ∈ {2, 19, 53}, 0 else }

Thus

ap = bp if p ≠ 2, 19, 53
ap = bp±1 else

Thus

x + 2010 = 2±1 19±1 53±1 x

There are only 8 possible choices, and we could easily check that 4 and 5092 are the only positive integer solutions.

Wait, I hear people screaming standard loophole…

Mathematica, 45 bytes

Select[Range[9^7],2014GCD[#,s=#+2010]^2==s#&]
\$\endgroup\$
4
\$\begingroup\$

Pyth 27 25

J2010fq+J4/*T+TJ^iTJ2U^T6

Try it online.

This uses your algorithm fairly naively... I might be able to come up with something better...

Basically filters out values that don't meet the criterion from range(10**6)

Thanks to @xnor for pointing out in chat that gcd(x,x+2010)==gcd(x,2010)

\$\endgroup\$
3
\$\begingroup\$

Python 3, 84 bytes

FryAmTheEggman's already suggested how to make your solution 88 bytes so I won't post that. But I thought I'd show how you can get even fewer bytes in Python 3:

from fractions import*
x=10**6
while x:y=x+2010;x*y-gcd(x,y)**2*2014or print(x);x-=1

(Thanks for FryAmTheEggman for tips)

This doesn't work in Python 2 because print's not a function.

I'm not sure if we're allowed, but if we could use 9**9 instead of 10**6 that'd be another byte.

\$\endgroup\$
  • \$\begingroup\$ I knew there was a way to do this with and/or... wouldn't have thought of python 3 though ;) More on topic: If order doesn't matter, I think setting x=10**6 and doing while x:x-=1;... is one byte shorter. \$\endgroup\$ – FryAmTheEggman Dec 12 '14 at 3:14
  • \$\begingroup\$ @FryAmTheEggman From the looks of the question it doesn't seem like order matters so I'll put that in. Thanks! \$\endgroup\$ – Sp3000 Dec 12 '14 at 3:22
2
\$\begingroup\$

R, 75 chars

for(a in 1:1e6){q=1:a;b=a+2010;if(a*b/max(q[!a%%q&!b%%q])^2==2014)print(a)}

With line breaks:

for(a in 1:1e6){
    q=1:a
    b=a+2010
    if(a*b/max(q[!a%%q&!b%%q])^2==2014)print(a)
    }
\$\endgroup\$
2
\$\begingroup\$

GolfScript (41 bytes)

The difference of two natural numbers is 2010 and their greatest common denominator is 2014 times smaller than their lowest common multiple. Find all the possible solutions.

Call the numbers am and bm where gcd(a, b) = 1 and wlog b > a. Then the difference is m(b-a) = 2010, and lcm(am, bm) = abm = 2014m so ab=2014.

Factors of 2014 are

1 * 2014
2 * 1007
19 * 106
38 * 53

and those which have differences that divide into 2010 are

1007 - 2 => m = 2, solution is 4, 2014
53 - 38 => m = 134, solution is 5092, 7102

Since I'm operating in a language which doesn't have built-in GCD or LCM, I think this analysis probably shortens the program:

44,{).2014{.2$/\@%!}:,~\2$- 2010,***}%0-`

where 44 is floor(sqrt(2014)).

It is possible to get quite close using a naïve loop:

10 6?,1>{.2010+.2${.@\%.}do;.*2014*@@*=},`
\$\endgroup\$
  • \$\begingroup\$ So @KettyTM's proof that (4,5092) is the only solution is incorrect ? \$\endgroup\$ – Optimizer Dec 12 '14 at 11:02
  • \$\begingroup\$ @Optimizer, you're misreading it. He also proves that there are two solutions, and they're the same as my solutions. His proof is just a lot harder to follow than mine (IMAO). \$\endgroup\$ – Peter Taylor Dec 12 '14 at 12:32
  • \$\begingroup\$ Ah, true. And yes, yours make more sense than his. \$\endgroup\$ – Optimizer Dec 12 '14 at 12:37
2
\$\begingroup\$

Perl6 61 58 56 54 52

A fairly direct translation of your source gives

for ^10**6 ->\i{i.say if i*(i+2010)/(i gcd(i+2010))**2==2014}

gcd is an infix op in Perl6.

^10**6 is short for 0 ..^ 10**6, where the ^ means exclude this number from the range.


Of course i gcd (i+2010) is the same as i gcd 2010 so I can save 3 characters

for ^10**6 ->\i{i.say if i*(i+2010)/(i gcd 2010)**2==2014}

If I use $_ instead of i I can save another couple of characters. ( .say is short for $_.say )

for ^10**6 {.say if $_*($_+2010)/($_ gcd 2010)**2==2014}

I can save another couple of characters by using ... && .say instead of .say if ..., because I don't need a space on both sides of && like I do for if.

for ^10**6 {$_*($_+2010)/($_ gcd 2010)**2==2014&&.say}

Since I did both of the previous "optimizations" I can use the statement modifier form of for, which means I can remove { and }.

$_*($_+2010)/($_ gcd 2010)**2==2014&&.say for ^10**6

I think that is as short as I can go without using a different algorithm.

\$\endgroup\$
2
\$\begingroup\$

J, 26 bytes

   I.((*.=+.*4--)2010+])i.1e6
4 5092

Those damned 2-byte verbs... :)

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

Dyalog APL, 29 characters

      a←⍳10        ⍝ the integers up to 10
      a
1 2 3 4 5 6 7 8 9 10
      2010+a       ⍝ corresponding integers at distance 2010
2011 2012 2013 2014 2015 2016 2017 2018 2019 2020
      a∨2010+a     ⍝ GCD-s between elements of a and 2010+a
1 2 3 2 5 6 1 2 3 10
      ⍝ All APL functions (e.g. + and ∨) are prefix-or-infix, right-associative,
      ⍝ and of the same precedence.
      a∧2010+a     ⍝ LCM-s
2011 2012 2013 4028 2015 2016 14119 8072 6057 2020
      ⍝ For which of them is the LCM 2014 times the GCD?
      (a∧2010+a)=2014×a∨2010+a
0 0 0 1 0 0 0 0 0 0
      ⍝ 0 means false, 1 means true
      ⍝ Filter the elements of "a" corresponding to the 1-s
      ((a∧2010+a)=2014×a∨2010+a) / a
4
      ⍝ Let's abstract this as a function by using curlies.
      ⍝ Omega (⍵) stands for the right argument.
      {((⍵∧2010+⍵)=2014×⍵∨2010+⍵) / ⍵} a
4
      ⍝ Up to a million instead of up to ten:
      {((⍵∧2010+⍵)=2014×⍵∨2010+⍵) / ⍵} ⍳1e6
4 5092
      ⍝ Hey, we can save a few characters by making 2010 the left argument, alpha (⍺)
      2010 {((⍵∧⍺+⍵)=2014×⍵∨⍺+⍵) / ⍵} ⍳1e6
4 5092
      ⍝ Remove a pair of parens by using the switch operator ⍨
      ⍝ An "operator" occurs to the right of a function and modifies its behaviour.
      ⍝ In this case A f⍨ B means the same as B f A
      ⍝ Left and right are swapped, hence "switch".
      2010 {⍵ /⍨ (⍵∧⍺+⍵)=2014×⍵∨⍺+⍵)} ⍳1e6
4 5092
      ⍝ That's 32 characters (modulo whitespace).  Not bad, but we can do better.
      ⍝ A "fork" is a sequence of 3 functions in isolation: f g h
      ⍝ It is evaluated as:  ⍺(f g h)⍵  ←→  (⍺ f ⍵)g(⍺ h ⍵)
      ⍝ If the first item is an array instead of a function: A f g  ←→  {A} f g
      ⍝ Forks are right-associative: f g h k l ←→ f g (h k l)
      2010 {⍵ /⍨ (⍺(⊢∧+)⍵)=2014×(⍺(⊢∨+)⍵)} ⍳1e6
4 5092
      ⍝ The "right tack" function (⊢) simply returns its right argument
      ⍝ Let's abuse forks a little further:
      2010 {⍵ /⍨ ⍺((⊢∧+)=(2014×(⊢∨+)))⍵} ⍳1e6
4 5092
      ⍝ ... and more
      2010 {⍺ (⊢(/⍨)((⊢∧+)=(2014×(⊢∨+)))) ⍵} ⍳1e6
4 5092
      ⍝ But {⍺ f ⍵} is equivalent to f
      2010 (⊢(/⍨)((⊢∧+)=(2014×(⊢∨+)))) ⍳1e6
4 5092
      ⍝ Note that now we are not mentioning ⍺ and ⍵ at all.
      ⍝ This is called "point-free style" or "tacit programming".
      ⍝ Removing some unnecessary parens and whitespace:
      2010(⊢(/⍨)(⊢∧+)=2014×⊢∨+)⍳1e6
4 5092
      ⍝ How many characters?
      ⍴'2010(⊢(/⍨)(⊢∧+)=2014×⊢∨+)⍳1e6'
29
\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 42 bytes

[n|n<-[1..8!],2014*gcd(n,t=n+2010)^2==n*t]

I feel that there is an extremely elegant solution using GP's fordiv construct but it couldn't compete with this solution for sheer brevity.

\$\endgroup\$
0
\$\begingroup\$

Racket, 72 chars

(filter(λ(i)(=(/(*(+ i 2010)i)(expt(gcd(+ i 2010)i)2))2014))(range 1e6))
\$\endgroup\$
  • 1
    \$\begingroup\$ Does Racket work with ISO-8859-7? Otherwise I don't think λ counts as 1 byte. \$\endgroup\$ – kennytm Dec 14 '14 at 7:47
0
\$\begingroup\$

Haskell, 52 chars

show [x|x<-[1..6^8],x*(x+2010)==2014*(gcd x 2010)^2]

Works in the Haskell interactive environment GHCi.

\$\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.