Find pairs of numbers with a particular LCM and GCD

Question

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!

Answer 1

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

Let's write x as 2^a₂ 3^a₃ 5^a₅… and x + 2010 as 2^b₂ 3^b₃ 5^b₅… Then the equation becomes

2^a₂+b₂ 3^a₃+b₃ 5^a₅+b₅… = 2014 2^{2min(a₂,b₂)} 3^{2min(a₃,b₃)} 5^{2min(a₅,b₅)}…

Since 2014 = 2 × 19 × 53, we have

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

Thus

a_p = b_p if p ≠ 2, 19, 53
a_p = b_p±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#&]

Answer 2

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)

Answer 3

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.

Answer 4

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

Answer 5

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*@@*=},`

Answer 6

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.

Answer 7

J, 26 bytes

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

Those damned 2-byte verbs... :)

Answer 8

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

Answer 9

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.

Answer 10

Racket, 72 chars

(filter(λ(i)(=(/(*(+ i 2010)i)(expt(gcd(+ i 2010)i)2))2014))(range 1e6))

Answer 11

Haskell, 52 chars

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

Works in the Haskell interactive environment GHCi.

Answer 12

Jelly, 20 19 bytes

g²×⁽¥Æ=×
ȷ6ç+⁽¥µ$$Ƈ

Try it online!

The TIO link has been modified to only search up to \$10^4\$, as the outputs are both below that, in order to finish within 60 seconds on TIO.

And of course, the "cheaty method" is that, as \$4\$ and \$5092\$ are the only two integers (as proven by kennytm) for which this is true, this 5 byter works:

4,⁽Ñ[

Try it online!

How it works

g²×⁽¥Æ=× - Helper link. Takes n on the left and n+2010 on the right
g        - gcd(n, n+2010)
 ²       - gcd(n, n+2010)²
   ⁽¥Æ   - Compressed integer; 2014
  ×      - 2014×gcd(n, n+2010)²
       × - n²+2010n
      =  - Are the two equal?

ȷ6ç+⁽¥µ$$Ƈ - Main link. Takes no input
ȷ6         - Yield 1000000
       $$Ƈ - Yield [1, 2, ..., 1000000] and keep those, i, for which the following is true:
    ⁽¥µ    -   Compressed integer; 2010
   +       -   i+2010
  ç        -   Call the helper link with i on the left and i+2010 on the right