Diferencias de pares de divisores MaxMin (DMDP)

18

Hablemos de divisores ...

Dejando a un lado los cuadrados perfectos (por un momento), todos los enteros positivos se pueden expresar como el producto de 2 de sus divisores. Ejemplo rápido de 126: Aquí están todos los divisores de126
ingrese la descripción de la imagen aquí

Como puede ver, todos los divisores se pueden emparejar. Esto es lo que llamaremos los pares divisores :
[1, 126], [2, 63], [3, 42], [6, 21], [7, 18], [9, 14]

Para este desafío, solo necesitaremos el último par de esta lista (que es el par central de la imagen):
[9,14]llamaremos a este par el par divisor MaxMin .
La diferencia de MaxMin Divisor Pair (DMDP) es la diferencia de los dos elementos del par, que es [9,14]=5
un ejemplo más 544. Los divisores son:

[1, 2, 4, 8, 16, 17, 32 , 34, 68, 136, 272, 544]

y DMDP (544) = 15 porque32-17=15

¿Qué pasa con los cuadrados perfectos ? Todos los cuadrados perfectos tienen DMDP = 0
Tomemos por ejemplo 64con divisores

{1, 2, 4, 8 , 16, 32, 64}

Como puede ver en este caso, el par divisor MaxMin es el [8,8]que DMDP=0
casi hemos terminado.

El reto

Dado un número entero n>0, genere cuántos enteros menores o iguales que 10000 , tienen DMDP menor que n

Casos de prueba

entrada -> salida

1->100 (those are all the perfect squares)
5->492  
13->1201
369->6175  
777->7264  
2000->8478  
5000->9440  
9000->9888  
10000->10000   
20000->10000

Este es el La respuesta más corta en bytes gana .


fuente
¿No tendría más sentido tener la entrada 10000como segunda variable?
Jonathan Allan
1
Sí, pensé en eso, pero no agregaría nada al desafío. De esta manera, creo que es más fácil para todos entender el desafío.
1
Relacionado
Peter Taylor

Respuestas:

5

JavaScript (ES7), 60 bytes

f=(n,i=1e4,j=i**.5|0)=>i?i%j?f(n,i,j-1):(i/j-j<n)+f(n,i-1):0

Probablemente exceda su límite de recursión, por lo que puede preferir la versión iterativa para 70 bytes:

n=>[...Array(1e4)].map(g=(j=++i**.5|0)=>i%j?g(j-1):k+=i/j-j<n,i=k=0)|k
Neil
fuente
4

Jalea , 13 bytes

1 byte gracias a Jonathan Allan.

ȷ4RÆDạU$Ṃ€<⁸S

Pruébalo en línea!

Monja permeable
fuente
ÆDạ"Ṛ$Ṃte ahorra un byte ÆDạ:@¥⁸Ṃ(tenía ạ"ṚṂ... ȷ4RÆDÇ€<⁸Spor 15 - demasiado similar - EDITAR: hmm o no, no :involucrado ... ¿qué piensas?)
Jonathan Allan
@JonathanAllan Creo que deberías publicar este 13-byter
Leaky Nun
Oh wow. no, ve por ello, ¡te guardé un byte que ahorra otros 2!
Jonathan Allan
¿Podría agregar una explicación?
Kevin Cruijssen
4

Java 8, 151 111 110 101 bytes

n->{int r=0,x=10000,i;for(;x-->0;r-=i-n>>-1)for(i=x;i-->1;)if(x>=i*i&x%i<1){i=x/i-i;break;}return r;}

-10 bytes gracias a @Nevay .

Explicación:

Pruébalo aquí

n->{               // Method with integer as parameter and return-type
  int r=0,         //  Result-integer
      x=10000,     //  Index-integer starting at 10,000
      i;           //  Another index-integer for the inner loop
  for(;x-->0;      //  Loop (1) from 10,000 down to 0
      r-=i-n>>-1)  //   If the MaxMin-Divisor Pair's difference is lower than the input,
                   //    add 1 to the result (after every iteration)
    for(i=x,       //   Set `i` to `x`
        i-->1;)    //   Inner loop (2) from `i` downwards to 1
      if(x>=i*i    //    If the current square-root of `x` is smaller than or equal to `i`,
         &x%i<1){  //    and if the current `x` is divisible by `i`:
        i=x/i-i;   //     Calculate the MaxMin-Division difference
        break;}    //     And leave the inner loop (2)
                   //   End of inner loop (2) (implicit / single-line body)
                   //  End of loop (1) (implicit / single-line body)
  return r;        //  Return the result
}                  // End of method
Kevin Cruijssen
fuente
1
Puede usar for(i=1,i+=Math.sqrt(x);--i>0;)if(...para guardar 1 byte.
Nevay
No tengo tiempo para probarlo yo mismo, pero ¿sería más corto hacer que el bucle interno comience desde x y tener una variable adicional para el mínimo actual?
JollyJoker
1
101 bytes:n->{int r=0,x=10000,i;for(;x-->0;r-=i-n>>-1)for(i=x;i-->1;)if(x>=i*i&x%i<1){i=x/i-i;break;}return r;}
Nevay
@Nevay Gracias de nuevo, realmente necesito recordar x>=i*icomo alternativa para usar Math.sqrt, ya que esta es la segunda vez que juegas eso en mi código.
Kevin Cruijssen
2

R , 73 77 bytes

Gracias a @Guiseppe por los 4 bytes

sum(sapply(1:1e4,function(x)min(abs((w=which(x%%1:x<1))-rev(w))))<scan())

Pruébalo en línea!

Perdí la función vectorizar para calcular el DMDP y ahora está usando una aplicación sobre la función. Las verdades para los elementos que son menores que la entrada se suman para el resultado.

MickyT
fuente
¡Ah, no noté que el DMDP es la diferencia mínima de esa lista de factores! Muy agradable. Creo que sum(sapply(1:1e4,function(x)min(abs((w=which(x%%1:x<1))-rev(w))))<scan())es un poco más corto
Giuseppe
2

Mathematica, 64 bytes

Count[Divisors~Array~1*^4,a_/;#+a[[i=⌈Tr[1^a]/2⌉]]>a[[-i]]]&

Pruébalo en Wolfram Sandbox

Uso

f = Count[Divisors~Array~1*^4,a_/;#+a[[i=⌈Tr[1^a]/2⌉]]>a[[-i]]]&

 

f[1]
100
f /@ {1, 5, 13, 369, 777, 2000, 5000, 9000, 10000, 20000}
{100, 492, 1201, 6175, 7264, 8478, 9440, 9888, 10000, 10000}

Explicación

Divisors~Array~1*^4

Genere las listas de divisores, desde 1hasta 10000. (las listas de divisores se ordenan automáticamente)

Count[ ..., a_/; ... ]

Cuente las ocurrencias de elementos a, de modo que ...

#+a[[i=⌈Tr[1^a]/2⌉]]>a[[-i]]]

(input) + (left one of the middle element(s)) > (right one of the middle element(s)) Si solo hay un elemento central, izquierda = derecha.

JungHwan Min
fuente
2

05AB1E , 19 18 17 16 15 12 bytes

4°ƒNÑÂα{нI‹O

Pruébalo en línea!

Explicación

4°ƒ            # for N in [0 ... 10**4] do:
   NÑ          # push divisors of N 
     Â         # bifurcate
      α        # element-wise absolute difference
       {       # sort
        н      # pop the head (smallest difference)
         I‹    # is it smaller than the input?
           O   # sum the stack
Emigna
fuente
1

MATL , 20 bytes

1e4:"@Z\2Y"dJ2/)G<vs

El código agota el tiempo de espera en TIO. Aquí hay un ejemplo ejecutado con el compilador fuera de línea:

>> matl 1e4:"@Z\2Y"dJ2/)G<vs
> 13
1201
Luis Mendo
fuente
1

R , 91 bytes

function(n)sum(sapply(1:1e4,function(x,d=(1:x)[x%%1:x<1])diff(d[median(seq(d))+.5*0:1]))<n)

Adopta un enfoque diferente (peor) para calcular el DMDP que la solución de MickyT mediante el uso de indexación de matriz y diffpara calcularlo. Pobre de mí.

Pruébalo en línea!

Giuseppe
fuente
1

Mathematica, 119115 bytes

(n=#;Tr[1^Select[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+(1+Length@Divisors@#)/2]]&/@Range@10000),#<n&]])&

Me finalmente conseguí esta cosa de trabajo y he estado tratando durante la última media hora. ._.

Ejecución de ejemplo

no hay descripción para ti!

totalmente humano
fuente
Caseses 4bytes más corto: Tr[1^Cases[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+(1+Length@Divisors@#)/2]]&/@Range@10000),n_/;n<#]]&. Mira este consejo .
ngenisis
1
@ngenisis en realidad Countes incluso más corto que Cases. Count[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+‌​(1+Length@Divisors@#‌​)/2]]&/@Range@10000)‌​,n_/;n<#]&
JungHwan Min
Además, 10^4o 1*^4es más corto que 10000, y /@Range@es equivalente a ~Array~.
JungHwan Min
1

Mathematica, 78 bytes

(s=#;Tr[1^Select[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^4}],#<s&]])&
J42161217
fuente
Caseses 4bytes más corto: Tr[1^Cases[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^4}],s_/;s<#]]&. Mira este consejo .
ngenisis
1
@ngenisis Countes aún más corto:Count[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^‌​4}],s_/;s<#]&
JungHwan Min
1

Casco , 19 bytes

#ȯV<⁰Sz≠↔§f`¦ḣḣ□100

No hay enlace TIO, ya que se agota el tiempo de espera. Esta versión usa 100 en lugar de 10000 y termina en un par de segundos.

Explicación

Husk no tiene divisores incorporados o soporte para notación científica todavía.

#ȯV<⁰Sz≠↔§f`¦ḣḣ□100  Input is n (accessed with ⁰).
               □100  Square of 100: 10000
              ḣ      Inclusive range from 1.
#                    Count number of elements for which
 ȯ                   this composition of 3 functions gives truthy result:
                       Argument k, say k = 12.
         §f`¦ḣ         Divisors of k:
             ḣ           Range: [1,2,3,..,12]
         §f              Filter by
           `¦            divides k: [1,2,3,4,6,12]
     Sz≠↔              Absolute differences of divisor pairs:
        ↔                Reverse: [12,6,4,3,2,1]
     Sz                  Zip with divisor list
       ≠                 using absolute difference: [11,4,1,1,4,11]
  V<⁰                  Is any of these less than n?
Zgarb
fuente
1

Japt , 25 19 17 bytes

L²õÈâ ®aX/ZÃd<UÃè

Pruébalo


Explicación

Entrada implícita de entero U.

L²õ

Genere una matriz de enteros ( õ) de 1 a 100 ( L) al cuadrado.

Èâ          Ã

Pase cada uno a través de una función (donde Xestá el elemento actual) que genera una matriz de los divisores ( â) de X.

®    Ã

Mapa sobre ese conjunto de divisores, donde Zestá el elemento actual.

aX/Z

Obtenga la diferencia absoluta ( a) de Zy Xdividida por Z.

d<U

¿Alguno de los elementos ( d) en la matriz resultante es menor que U?

è

Cuente los elementos de verdad y genere implícitamente el resultado.

Lanudo
fuente
1

TI-BASIC, 46 bytes

Tenga en cuenta que TI-BASIC es un lenguaje tokenizado. Además, la E en la línea 2 es una E pequeña mayúscula, que se encuentra presionando 2ND +,.

Input A
DelVar DFor(B,1,E4
For(C,1,√(B
If not(fPart(B/C
B/C-C<A
End
D+Ans→D
End

El resultado estará en D y Ans inmediatamente después de la ejecución del programa. Si se va a mostrar, Anssería suficiente agregar dos bytes más (nueva línea y ).

Josiah Winslow
fuente
0

Python 2 , 134 bytes

lambda i:len(filter(lambda n:n<i,[reduce(lambda x,y:y-x,[[x,n/x]for x in range(1,int(n**.5+1))if n%x<1][-1])for n in range(1,10001)]))

Pruébalo en línea!

Eugh ... necesito hacerlo mucho mejor.

totalmente humano
fuente
125 bytes (-9 bytes) usando su enfoque actual, pero reemplazando len(filter(lambda n:n<i,...))consum(n<i for n in ....)
Mr. Xcoder
114 bytes basados ​​en el comentario de Mr.Xcoder.
2017
113 bytes basados ​​en el comentario de ovs.
Sr. Xcoder
0

Python 2 , 83 bytes

Un poco lento, usa 5 segundos por caso de prueba

lambda x:sum(x>min(abs(y/t-t)for t in range(1,y+1)if y%t<1)for y in range(1,10001))

Pruébalo en línea!

Halvard Hummel
fuente
0

PHP, 94 + 1 bytes

for(;$n++<1e4;$c+=$d<$argn)if(($i=$n**.5)>~~$i){while($n%++$i);for($d=1;$n%--$i;)$d++;}echo$c;

Ejecutar como tubería -nRo probarlo en línea .

Tito
fuente
0

VB.NET (.NET 4.5) 116115 bytes

Function A(n)
For i=1To 10^4
Dim s As Byte=Math.Sqrt(i)
While i Mod s>0
s-=1
End While
A-=i/s-s<n
Next
End Function

Explicación:

Una función que toma ncomo parámetro y devuelve el resultado.

Comienza en la raíz cuadrada y busca el número entero más cercano que se divide de manera uniforme (será el más pequeño de los MaxMin Divisor Pair). Luego obtiene el mayor del par ( i/s), encuentra la diferencia y compara con la entrada.


Estrategias de golf utilizadas:

  • Dim es caro, por lo que cuantas menos variables declaro mejor.
  • Empiezo a buscar en la raíz cuadrada, pero solo quiero mirar enteros. Al declararme scomo un tipo integral, se echa al suelo por mí.
  • VB utiliza ^como exponente. Entonces, si bien 10000tiene 5 caracteres, 10^4solo tiene 4.
  • VB crea una variable automática con el mismo nombre y tipo que la definición de la función (en mi caso A). Al final de la función, si no hay return, se devolverá el valor de la variable de función. Así que guardo los caracteres al no declarar una variable separada y al no usar una declaración de retorno.
  • VB tiene mecanografía / casting muy indulgente. ise supone Integerporque asigné un literal entero. Ase supone, Objectpero tan pronto como agrego un número entero, se comporta como un Integer.
  • En lugar de ifcomprobar que la diferencia es satisfactoria, agréguela directamente al resultado convirtiendo el valor booleano en un entero. Sin embargo, VB usa -1for True, así que resta para obtener el signo correcto.
  • Técnicamente, queremos Modno serlo 0. Tomar el módulo de un número negativo en VB.NET dará un resultado negativo. Pero, todo es positivo, así que puedo guardar un byte convirtiéndome <>en >.
  • El número más grande para verificar es 10000. La raíz cuadrada de eso es 100. Así que solo necesito un Bytepara almacenar eso, guardando bytes en la declaración usando un tipo con nombre más corto.

Pruébalo en línea!

Brian J
fuente