Pracowałem z matematyką nad moim przyjacielem i postanowiliśmy napisać skrypt, który znajdzie odpowiedź. Pierwotne pytanie brzmi:

Różnica dwóch liczb naturalnych to 2010, a ich największy wspólny mianownik jest 2014 razy mniejszy niż ich najniższy wspólny mnożnik. Znajdź wszystkie możliwe rozwiązania.

Zaczęliśmy pisać program niezależnie od siebie, a kiedy zadziałał, postanowiliśmy go zagrać w golfa, aby uzyskać jak najmniej bajtów, którymi mogliśmy zarządzać. Skończyło się na tym pięknym wierszu kodu o cudownym 89 bajtach.

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

Chcieliśmy sprawdzić, czy komukolwiek uda się napisać krótszy fragment kodu, który wyliczy pierwszy milion I. Jeśli jesteś wystarczająco odważny, aby konkurować, możesz użyć dowolnego języka, który ci się podoba, ale wolelibyśmy, aby Python 2 mógł porównać twój kod z naszym.

Obowiązują reguły, wygrywają najkrótsze bajty. Obowiązują standardowe luki w kodzie golfowym. Standardowe „luki”, które nie są już śmieszne

Baw się dobrze!

Mathematica, 8 bajtów

{4,5092}

Dowód, że 4 i 5092 to jedyne rozwiązania: oryginalny problem można przepisać jako

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

Napiszmy x jako 2 ^{a ₂} 3 ^{a ₃} 5 ^{a ₅} … i x + 2010 jako 2 ^{b ₂} 3 ^{b ₃} 5 ^{b ₅} … Następnie równanie staje się

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

Ponieważ 2014 = 2 × 19 × 53, mamy

a _p + b _p = 2 min (a _p , b _p ) + {1 jeśli p ∈ {2, 19, 53}, 0 else}

A zatem

a _p = b _p, jeśli p ≠ 2, 19, 53
a _p = b _p ± 1 inaczej

A zatem

x + 2010 = 2 ^{± 1} 19 ^{± 1} 53 ^{± 1} x

Istnieje tylko 8 możliwych wyborów i moglibyśmy łatwo sprawdzić, czy 4 i 5092 są jedynymi dodatnimi rozwiązaniami liczb całkowitych.

Czekaj, słyszę ludzi krzyczących standardową lukę…

Mathematica, 45 bajtów

Select[Range[9^7],2014GCD[#,s=#+2010]^2==s#&]

Pyth 27 25

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

Wypróbuj online.

To używa twojego algorytmu dość naiwnie ... Być może uda mi się wymyślić coś lepszego ...

Zasadniczo odfiltrowuje wartości, które nie spełniają kryterium range(10**6)

Dzięki @xnor za wskazanie tego na czacie gcd(x,x+2010)==gcd(x,2010)

Python 3, 84 bajtów

FryAmTheEggman już zasugerował, jak zrobić rozwiązanie 88 bajtów, więc tego nie opublikuję. Ale pomyślałem, że pokażę, jak można uzyskać jeszcze mniej bajtów w Pythonie 3:

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

(Dzięki za FryAmTheEggman za wskazówki)

To nie działa w Pythonie 2, ponieważ printnie jest funkcją.

Nie jestem pewien, czy wolno nam, ale gdybyśmy mogli użyć 9**9zamiast 10**6tego, byłby to kolejny bajt.

R, 75 znaków

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

Z podziałami linii:

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

GolfScript (41 bajtów)

Różnica dwóch liczb naturalnych to 2010, a ich największy wspólny mianownik jest 2014 razy mniejszy niż ich najniższa wspólna wielokrotność. Znajdź wszystkie możliwe rozwiązania.

Łączyć się z numerami amoraz bmgdzie gcd(a, b) = 1i wlog b > a. Różnica jest taka m(b-a) = 2010i lcm(am, bm) = abm = 2014mtak ab=2014.

Czynniki 2014 roku są

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

i te, które mają różnice, które dzielą się na 2010 są

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

Ponieważ działam w języku, który nie ma wbudowanego GCD ani LCM, myślę, że ta analiza prawdopodobnie skraca program:

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

gdzie 44jest floor(sqrt(2014)).

Można zbliżyć się dość blisko za pomocą naiwnej pętli:

10 6?,1>{.2010+.2${.@\%.}do;.*2014*@@*=},`

Perl6 61 58 56 54 52

Daje dość bezpośrednie tłumaczenie twojego źródła

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

gcd jest opcją infix w Perl6.

^10**6jest skrótem od 0 ..^ 10**6, gdzie ^środki wykluczają tę liczbę z zakresu.

Oczywiście i gcd (i+2010)jest tak samo i gcd 2010, że mogę zapisać 3 znaki

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

Jeśli użyję $_zamiast i, mogę zapisać kolejną parę znaków. ( .sayjest skrótem od $_.say)

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

Mogę uratować kolejną parę postaci, używając ... && .sayzamiast .say if ..., ponieważ nie potrzebuję spacji po obu stronach, &&tak jak robię if.

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

Ponieważ zrobiłem obie poprzednie „optymalizacje”, mogę użyć formy modyfikatora instrukcji for, co oznacza, że ​​mogę usunąć {i }.

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

Myślę, że to jest tak krótkie, jak tylko mogę, bez użycia innego algorytmu.

J, 26 bajtów

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

Te przeklęte 2-bajtowe czasowniki ... :)

Dyalog APL, 29 znaków

      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

PARI / GP, 42 bajty

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

Wydaje mi się, że istnieje niezwykle eleganckie rozwiązanie wykorzystujące fordivkonstrukcję GP, ale nie mogło konkurować z tym rozwiązaniem pod względem zwięzłości.

Rakieta, 72 znaki

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

Haskell, 52 znaki

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

Działa w interaktywnym środowisku Haskell GHCi.