Encuentra pares de números con un LCM y MCD en particular

9

Estaba trabajando en una pregunta de matemáticas con un amigo mío, y decidimos escribir un guión que encuentre la respuesta. La pregunta original es la siguiente:

La diferencia de dos números naturales es 2010 y su máximo común denominador es 2014 veces menor que su mínimo común multiplicador. Encuentra todas las soluciones posibles.

Comenzamos a escribir el programa independientemente uno del otro, y cuando funcionó, decidimos desarrollarlo para obtener la menor cantidad de bytes que pudiéramos administrar. Terminamos con esta hermosa línea de código en un maravilloso 89 bytes.

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

Queríamos ver si alguien logra escribir un código más corto, que enumere los primeros 1 millón de i. Si eres lo suficientemente valiente como para competir, puedes usar cualquier idioma que desees, pero preferiríamos que Python 2 pudiera comparar tu código con el nuestro.

Se aplican las reglas habituales, ganan los bytes más cortos. Se aplica el código estándar de lagunas de golf. "Lagunas" estándar que ya no son divertidas

¡Que te diviertas!

sammko
fuente
2
@Rainbolt: Ok, se permite cualquier idioma. La limitación de Python fue para fines de comparación. Pero solo haz lo que quieras: D
sammko
¿Hay respuestas que no sean 3 y 5092? No puedo encontrar nada más antes de 10,000,000.
kennytm
@KennyTM: obtuve 4 y 5092. Y sí, no creo que haya otros.
sammko
Hola, he editado tu título para reflejar mejor lo que estás preguntando. Siéntase libre de cambiarlo si siente que me perdí algo.
FryAmTheEggman
Se eliminó la etiqueta de Python por cierto.
Timtech

Respuestas:

21

Mathematica, 8 bytes

{4,5092}

Prueba de que 4 y 5092 son las únicas soluciones: el problema original se puede reescribir como

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

Escribamos x como 2 a 2 3 a 3 5 a 5 ... y x + 2010 como 2 b 2 3 b 3 5 b 5 ... Entonces la ecuación se convierte en

2 a 2 + b 2 3 a 3 + b 3 5 a 5 + b 5 … = 2014 2 2min (a 2 , b 2 ) 3 2min (a 3 , b 3 ) 5 2min (a 5 , b 5 )

Desde 2014 = 2 × 19 × 53, tenemos

a p + b p = 2min (a p , b p ) + {1 si p ∈ {2, 19, 53}, 0 más}

Así

a p = b p si p ≠ 2, 19, 53
a p = b p ± 1 más

Así

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

Solo hay 8 opciones posibles, y podríamos comprobar fácilmente que 4 y 5092 son las únicas soluciones enteras positivas.

Espera, escucho a gente gritar escapatoria estándar ...

Mathematica, 45 bytes

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

Pyth 27 25

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

Pruébalo en línea.

Esto usa su algoritmo de manera bastante ingenua ... Tal vez pueda encontrar algo mejor ...

Básicamente filtra los valores que no cumplen con el criterio de range(10**6)

Gracias a @xnor por señalar en el chat que gcd(x,x+2010)==gcd(x,2010)

FryAmTheEggman
fuente
3

Python 3, 84 bytes

FryAmTheEggman ya sugirió cómo hacer que su solución sea de 88 bytes, por lo que no publicaré eso. Pero pensé en mostrar cómo puedes obtener aún menos bytes en Python 3:

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

(Gracias por FryAmTheEggman por los consejos)

Esto no funciona en Python 2 porque printno es una función.

No estoy seguro de si se nos permite, pero si podríamos usar en 9**9lugar de 10**6eso sería otro byte.

Sp3000
fuente
Sabía que había una manera de hacer esto con and/ or... aunque no habría pensado en Python 3;) Más sobre el tema: Si el orden no importa, creo que configurar x=10**6y hacer while x:x-=1;...es un byte más corto.
FryAmTheEggman
@FryAmTheEggman Desde el aspecto de la pregunta, no parece que el orden importe, así que lo pondré. ¡Gracias!
Sp3000
2

R, 75 caracteres

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

Con saltos de línea:

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

GolfScript (41 bytes)

La diferencia de dos números naturales es 2010 y su máximo común denominador es 2014 veces menor que su mínimo común múltiplo. Encuentra todas las soluciones posibles.

Llama a los números amy bmdónde gcd(a, b) = 1y wlog b > a. Entonces la diferencia es m(b-a) = 2010, y lcm(am, bm) = abm = 2014masí ab=2014.

Factores de 2014 son

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

y aquellos que tienen diferencias que se dividen en 2010 son

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

Como estoy operando en un lenguaje que no tiene GCD o LCM incorporado, creo que este análisis probablemente acorta el programa:

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

donde 44está floor(sqrt(2014)).

Es posible acercarse bastante usando un bucle ingenuo:

10 6?,1>{.2010+.2${.@\%.}do;.*2014*@@*=},`
Peter Taylor
fuente
Entonces, ¿la prueba de @ KettyTM de que (4,5092) es la única solución es incorrecta?
Optimizador
@Optimizer, lo estás leyendo mal. También demuestra que hay dos soluciones, y son las mismas que mis soluciones. Su prueba es mucho más difícil de seguir que la mía (IMAO).
Peter Taylor
Ah cierto. Y sí, el tuyo tiene más sentido que el suyo.
Optimizador
2

Perl6 61 58 56 54 52

Una traducción bastante directa de su fuente da

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

gcd es un infijo en Perl6.

^10**6es la abreviatura de 0 ..^ 10**6, donde las ^medias excluyen este número del rango.


Por supuesto, i gcd (i+2010)es lo mismo, i gcd 2010así que puedo guardar 3 caracteres

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

Si uso en $_lugar de ipuedo guardar otro par de caracteres. ( .sayes la abreviatura de $_.say)

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

Puedo guardar otro par de caracteres usando en ... && .saylugar de .say if ..., porque no necesito un espacio en ambos lados &&como lo hago para if.

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

Como hice las dos "optimizaciones" anteriores, puedo usar la forma del modificador de declaración de for, lo que significa que puedo eliminar {y }.

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

Creo que es lo más corto posible sin usar un algoritmo diferente.

Brad Gilbert b2gills
fuente
2

J 26 bytes

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

Esos malditos verbos de 2 bytes ... :)

randomra
fuente
1

Dyalog APL, 29 caracteres

      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
ngn
fuente
1

PARI / GP, 42 bytes

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

Siento que hay una solución extremadamente elegante usando la fordivconstrucción de GP, pero no podría competir con esta solución por su brevedad.

Charles
fuente
0

Raqueta, 72 caracteres

(filter(λ(i)(=(/(*(+ i 2010)i)(expt(gcd(+ i 2010)i)2))2014))(range 1e6))
Matthew Butterick
fuente
1
¿Racket funciona con ISO-8859-7? De lo contrario, no creo que λcuente como 1 byte.
kennytm
0

Haskell, 52 caracteres

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

Funciona en el entorno interactivo Haskell GHCi.

usuario2487951
fuente