Я работал над математическим вопросом с моим другом, и мы решили написать сценарий, который найдет ответ. Оригинальный вопрос заключается в следующем:

Разница двух натуральных чисел - 2010, и их наибольший общий знаменатель в 2014 году меньше их наименьшего общего множителя. Найдите все возможные решения.

Мы начали писать программу независимо друг от друга, и когда она сработала, мы решили использовать ее, чтобы получить как можно меньше байтов. Мы закончили с этой прекрасной строкой кода с изумительными 89 байтами.

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

Мы хотели посмотреть, удастся ли кому-нибудь написать более короткий фрагмент кода, который перечисляет первые 1 миллион я. Если вы достаточно смелы, чтобы конкурировать, вы можете использовать любой язык, который вам нравится, но мы бы предпочли, чтобы Python 2 мог сравнивать ваш код с нашим.

Применяются обычные правила, выигрывают кратчайшие байты. Применяются стандартные кодовые гольф-лазейки. Стандартные "лазейки", которые больше не смешны

Радоваться, веселиться!

Mathematica, 8 байт

{4,5092}

Доказательство того, что 4 и 5092 являются единственными решениями: исходная проблема может быть переписана как

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

Давайте запишем x как 2 ^{a ₂} 3 ^{a ₃} 5 ^{a ₅} … и x + 2010 как 2 ^{b ₂} 3 ^{b ₃} 5 ^{b ₅} … Тогда уравнение становится

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

С 2014 года = 2 × 19 × 53 мы имеем

a _p + b _p = 2min (a _p , b _p ) + {1, если p ∈ {2, 19, 53}, 0 еще}

таким образом

a _p = b _p, если p ≠ 2, 19, 53
a _p = b _p ± 1, иначе

таким образом

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

Есть только 8 возможных вариантов, и мы можем легко проверить, что 4 и 5092 являются единственными положительными целочисленными решениями.

Подожди, я слышу, как люди кричат ​​в стандартную лазейку ...

Mathematica, 45 байт

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

Pyth 27 25

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

Попробуйте онлайн.

Это использует ваш алгоритм довольно наивно ... Я мог бы придумать что-то лучше ...

В основном отфильтровывает значения, которые не соответствуют критерию из range(10**6)

Спасибо @xnor за то, что указал в чате, что gcd(x,x+2010)==gcd(x,2010)

Python 3, 84 байта

FryAmTheEggman уже предложил, как сделать ваше решение 88 байтов, поэтому я не буду это публиковать. Но я решил показать, как можно получить еще меньше байтов в Python 3:

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

(Спасибо за FryAmTheEggman за советы)

Это не работает в Python 2, потому что printэто не функция.

Я не уверен, что нам разрешено, но если бы мы могли использовать 9**9вместо 10**6этого был бы другой байт.

R, 75 символов

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

С переносами строк:

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 байт)

Разница двух натуральных чисел - 2010, и их наибольший общий знаменатель в 2014 году меньше их наименьшего общего множителя. Найдите все возможные решения.

Позвоните по номерам amи bmгде gcd(a, b) = 1и влог b > a. Тогда разница есть m(b-a) = 2010и lcm(am, bm) = abm = 2014mтак ab=2014.

Факторами 2014 года являются

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

и те, которые имеют различия, которые делятся на 2010

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

Поскольку я работаю на языке, который не имеет встроенного GCD или LCM, я думаю, что этот анализ, вероятно, сокращает программу:

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

где 44находится floor(sqrt(2014)).

Можно подойти довольно близко, используя наивный цикл:

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

Perl6 61 58 56 54 52

Достаточно прямой перевод вашего источника дает

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

gcd это инфиксный оператор в Perl6.

^10**6сокращенно 0 ..^ 10**6, где ^средства исключают это число из диапазона.

Конечно так i gcd (i+2010)же, как i gcd 2010и я могу сохранить 3 символа

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

Если я использую $_вместо iя могу сохранить еще пару символов. ( .sayсокращение от $_.say)

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

Я могу сохранить еще пару символов, используя ... && .sayвместо .say if ..., потому что мне не нужны пробелы с обеих сторон, &&как для меня if.

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

Поскольку я выполнил обе предыдущие «оптимизации», я могу использовать форму модификатора оператора for, что означает, что я могу удалить {и }.

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

Я думаю, что это так коротко, как я могу обойтись без использования другого алгоритма.

J, 26 байт

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

Эти проклятые 2-байтовые глаголы ... :)

Дьялог АПЛ, 29 знаков

      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 байта

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

Я чувствую, что есть чрезвычайно элегантное решение, использующее fordivконструкцию GP, но оно не может конкурировать с этим решением за явную краткость.

Ракетка, 72 символа

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

Haskell, 52 символа

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

Работает в интерактивной среде Haskell GHCi.