Aproxima la proporción de enteros con factores vecinos

11

Si 1 no se cuenta como factor, entonces

  • 40 tiene dos factores vecinos (4 y 5)
  • 1092 tiene dos factores vecinos (13 y 14)
  • 350 no tiene dos factores vecinos (de sus factores 2, 5, 7, 10, 14, 25, 35, 50, 70 y 175, no hay dos consecutivos)

La proporción de enteros positivos que tienen esta propiedad es la proporción divisible por cualquiera de 6 (2 × 3), 12 (3 × 4), 20 (4 × 5), 30, 56,…. Si solo calculamos la proporción divisible por el primer n de estos, obtenemos una aproximación que se vuelve más precisa a medida que n aumenta.

Por ejemplo, para n = 1 , encontramos la proporción de enteros divisibles por 2 × 3 = 6, que es 1/6. Para n = 2 , todos los enteros divisibles por 3 × 4 = 12 también son divisibles por 6, por lo que la aproximación sigue siendo 1/6. Para n = 3 , la proporción de enteros divisibles por 6 o 20 es 1/5, y así sucesivamente.

Aquí están los primeros valores:

1  1/6                0.16666666666666666
3  1/5                0.20000000000000000
6  22/105             0.20952380952380953
9  491/2310           0.21255411255411255
12 2153/10010         0.21508491508491510
15 36887/170170       0.21676558735382265
21 65563/301070       0.21776663234463747
24 853883/3913910     0.21816623274423785
27 24796879/113503390 0.21846817967287144

Para valores de n entre los valores proporcionados, la salida debe ser la misma que la salida para el valor anterior (por ejemplo, n = 5 → 1/5).

Su programa debe tomar n y generar una respuesta fraccionaria o decimal. Puede tomar n en cualquier desplazamiento (por ejemplo, indexación 0 o indexación 2 en esta secuencia, en lugar de indexación 1).

Para la salida decimal, su programa debe tener una precisión de al menos 5 dígitos para todos los casos de prueba indicados.

La puntuación es el , con el código más corto ganador.

Inspirado por ¿Qué proporción de enteros positivos tienen dos factores que difieren en 1? por marty cohen - específicamente, por la respuesta de Dan .

Pomo de la puerta
fuente
1
¿Qué tan precisa tiene que ser una respuesta decimal? Una estrategia natural parece ser contar los enteros con un divisor válido en un rango enorme y dividirlos por la longitud del rango, lo que mejora como una aproximación a medida que el rango aumenta.
xnor
@xnor Ya he abordado eso en la publicación.
Pomo de la puerta

Respuestas:

6

Jalea ,  14 13  10 bytes

-1 usando la idea de Erik the Outgolfer para tomar la media de una lista de ceros y unos.
-3 mediante la indexación 3 (como se permite en la pregunta) - gracias a Dennis por señalar esto.

ḊPƝḍⱮ!Ẹ€Æm

Un enlace monádico que acepta un número entero n+2, lo que produce un flotador.

Pruébalo en línea! (¡muy ineficiente ya que prueba la divisibilidad en el rango)[2,(n+2)!]

(Comenzó como +2µḊPƝḍⱮ!§T,$Ẉ, tomando ny cediendo [numerator, denominator], sin reducir)

¿Cómo?

ḊPƝḍⱮ!Ẹ€Æm - Link: integer, x=n+2
Ḋ          - dequeue (implicit range of) x  - i.e. [2,3,4,...,n+2]
  Ɲ        - apply to neighbours:
 P         -   product                             [2×3,3×4,...,(n+1)×(n+2)]
     !     - factorial of x                        x!
    Ɱ      - map across (implicit range of) x! with:
   ḍ       -   divides?                            [[2×3ḍ1,3×4ḍ1,...,(n+1)×(n+2)ḍ1],[2×3ḍ2,3×4ḍ2,...,(n+1)×(n+2)ḍ2],...,[2×3ḍ(x!),3×4ḍ(x!),...,(n+1)×(n+2)ḍ(x!)]]
       €   - for each:
      Ẹ    -   any?  (1 if divisible by any of the neighbour products else 0)
        Æm - mean
Jonathan Allan
fuente
Hm ... sospecho que lo que hace esto más corto que el mío es el uso de en !lugar de æl/... Ah, las alegrías de las reglas cambian mientras duerme.
Erik the Outgolfer
@EriktheOutgolfer sí, ¡métodos muy similares cuando miro más de cerca! puedes usar Ppara bajar a 13?
Jonathan Allan
En lugar de Ẹ€? Me temo que Pes lo mismo ׃1$, así que no funcionará. (Y eso sería 14 de todos modos ...) Si en lugar de æl/, tal vez ( P es LCM * k después de todo).
Erik the Outgolfer
@EriktheOutgolfer en lugar deæl/
Jonathan Allan
Sí, creo que puedo hacer eso, y el resultado sería teóricamente tan preciso como æl/supongo. (El golf nocturno tiene problemas ...) EDITAR: Sí, aunque tendré que reducir la discusión sobre TIO a 4...: P
Erik the Outgolfer
3

05AB1E , 15 bytes

Ì©!Lε®LüP¦Öà}ÅA

Puerto de la respuesta Jelly de @JonathanAllan , por lo que también es extremadamente lento.

Pruébelo en línea o verifique los primeros tres casos de prueba .

Explicación:

Ì                 # Add 2 to the (implicit) input
                  #  i.e. 3 → 5
 ©                # Store this in the register (without popping)
  !               # Take the factorial of it
                  #  i.e. 5 → 120
   L              # Create a list in the range [1, (input+2)!]
                  #   i.e. 120 → [1,2,3,...,118,119,120]
    ε       }     #  Map over each value in this list
     ®            #  Push the input+2 from the register
      L           #  Create a list in the range [1, input+2]
                  #   i.e. 5 → [1,2,3,4,5]
       ü          #  Take each pair
                  #    i.e. [1,2,3,4,5] → [[1,2],[2,3],[3,4],[4,5]]
        P         #   And take the product of that pair
                  #    i.e. [[1,2],[2,3],[3,4],[4,5]] → [2,6,12,20]
         ¦        #  Then remove the first value from this product-pair list
                  #   i.e. [2,6,12,20] → [6,12,20]
          Ö       #  Check for each product-pair if it divides the current map-value
                  #  (1 if truthy; 0 if falsey)
                  #   i.e. [1,2,3,...,118,119,120] and [6,12,20]
                  #    → [[0,0,0],[0,0,0],[0,0,0],...,[0,0,0],[0,0,0],[1,1,1]]
           à      #  And check if it's truthy for any by taking the maximum
                  #   i.e. [[0,0,0],[0,0,0],[0,0,0],...,[0,0,0],[0,0,0],[1,1,1]]
                  #    → [0,0,0,...,0,0,1]
             ÅA   # After the map, take the mean (and output implicitly)
                  #  i.e. [0,0,0,...,0,0,1] → 0.2
Kevin Cruijssen
fuente
3

JavaScript (ES6),  94 92  90 bytes

Guardado 2 bytes gracias a @Shaggy + 2 bytes más desde allí

Devuelve una aproximación decimal.

n=>(x=2,g=a=>n--?g([...a,x*++x]):[...Array(1e6)].map((_,k)=>n+=a.some(d=>k%d<1))&&n/1e6)``

Pruébalo en línea!


JavaScript (ES6), 131 bytes

Una solución mucho más larga que devuelve un resultado exacto como un par .[numerator,denominator]

f=(n,a=[],p=x=1)=>n?f(n-1,[...a,q=++x*-~x],p*q/(g=(a,b)=>a?g(b%a,a):b)(p,q)):[...Array(p)].map((_,k)=>n+=a.some(d=>-~k%d<1))&&[n,p]

Pruébalo en línea!

Arnauld
fuente
1
-2 bytes
Shaggy
Esto debería funcionar, en teoría, para 82 bytes.
Shaggy
@ Shaggy Realmente no sé cuál es el consenso para respuestas como esa. Si bien funciona en teoría , no funciona en la práctica para ninguna entrada. (Personalmente, no me gustan este tipo de respuestas. Es por eso que generalmente incluyo una regla como "su código debería funcionar al menos hasta un límite dado" en mis propios desafíos cuando sospecho que obtendré respuestas como "solo funciona para n = 1 en TIO " ... o no funciona en absoluto en el presente caso.)
Arnauld
Personalmente, soy un gran admirador del tiempo infinito y el consenso de la memoria;)
Shaggy
Oh, a mí también me gusta. :) Mi única reserva es que creo que debería ser posible probar cualquier respuesta para al menos un par de entradas distintas.
Arnauld
3

Jalea , 12 bytes

Ḋב$ḍẸ¥ⱮP$Æm

Pruébalo en línea!

-2 gracias a la sugerencia de Jonathan Allan de reemplazar el LCM con el producto (es decir, el LCM multiplicado por un número entero).

Dennis notó que también puedo indexar 2.

Erik el Outgolfer
fuente
2

Carbón , 26 bytes

FN⊞υ×⁺²ι⁺³ιI∕LΦΠυ¬⌊Eυ﹪ιλΠυ

Pruébalo en línea! El enlace es a la versión detallada del código. Inevitablemente ineficiente (O (n! ²)) por lo que solo funciona hasta n=4en TIO. Explicación:

FN⊞υ×⁺²ι⁺³ι

Ingrese ny calcule los primeros nproductos de factores vecinos.

I∕LΦΠυ¬⌊Eυ﹪ιλΠυ

Tome el producto de todos esos factores y úselo para calcular la proporción de números que tienen al menos uno de esos factores.

La versión menos lenta de 30 bytes es solo O (n!), Por lo que puede hacer hasta n=6TIO:

F⊕N⊞υ⁺²ιI∕LΦΠυΣEυ∧μ¬﹪ι×λ§υ⊖μΠυ

Pruébalo en línea! El enlace es a la versión detallada del código.

La versión más rápida de 46 bytes es solo O (mcm (1..n + 2)), por lo que puede hacer hasta n=10TIO:

FN⊞υ×⁺²ι⁺³ι≔⁰η≔⁰ζW∨¬η⌈Eυ﹪ηκ«≦⊕η≧⁺⌈Eυ¬﹪ηκζ»I∕ζη

Pruébalo en línea! El enlace es a la versión detallada del código.

La versión más rápida de 45 bytes es solo O (2ⁿ), por lo que puede hacer hasta n=13TIO:

⊞υ±¹FEN×⁺²ι⁺³ιF⮌υ⊞υ±÷×ικ⌈Φ⊕ι∧λ¬∨﹪ιλ﹪κλIΣ∕¹✂υ¹

Pruébalo en línea! El enlace es a la versión detallada del código.

La versión más rápida de 54 bytes utiliza un LCM más eficiente, por lo que puede hacer hasta n=18TIO:

⊞υ±¹FEN×⁺²ι⁺³ιFEυ⟦κι⟧«W⊟κ⊞⊞Oκλ﹪§κ±²λ⊞υ±÷Π…κ²⊟κ»IΣ∕¹✂υ¹

Pruébalo en línea! El enlace es a la versión detallada del código.

Neil
fuente
2

Wolfram Language (Mathematica) , 69 68 61 52 bytes

Count[Range[#!],b_/;Or@@(# #-#&@Range[3,#]∣b)]/#!&

Pruébalo en línea!

3 indexados. Al principio iba a usar, LCM@@pero me di cuenta de que #!sería más corto ... pero ahora tiene mucha memoria para Range[#!]...

Logramos jugar golf por 2 bytes, lo cual fue agradable.


Solución numérica anterior (56 bytes):

N@Count[Range[5^8],b_/;Or@@Array[(# #-#)∣b&,#,3]]/5^8&

Pruébalo en línea!

2 indexados. Más eficiente cuando #!>5^8( #>9suponiendo que #es un número entero).

attinat
fuente
1

Python 2 , 78 bytes

lambda n:sum(any(-~i%(j*-~j)<1for j in range(2,n+2))for i in range(10**7))/1e7

Pruébalo en línea!

Devuelve el decimal aproximado a +5 dígitos; utiliza el ingenuo enfoque de fuerza bruta que xnor sugiere en los comentarios sobre la pregunta.

Chas Brown
fuente