Qué extraña función

45

Su tarea aquí será implementar una función 1 que forme una permutación en los enteros positivos (una biyección de los enteros positivos en sí mismos). Esto significa que cada entero positivo debería aparecer exactamente una vez en la permutación. El problema es que su función debe tener una mayor probabilidad de generar un número impar que un número par.

Ahora esto puede parecer extraño o imposible. ¿Seguramente hay tantos números impares como pares? Y aunque esta intuición es correcta para conjuntos finitos, en realidad no es válida para conjuntos infinitos. Por ejemplo, tome la siguiente permutación:

1 3 2 5 7 4 9 11 6 13 15 8 17 19 10 21 23 12 25 27 14 29 31 16 33 35 18 37 39 20 41 43 22 45 47 24 49 51 26 53 55 ...

Si toma cualquier subsección de la secuencia con un tamaño mayor que 1 , tendrá al menos tantos números impares como pares, por lo que parece que la probabilidad de que cualquier término aleatorio sea impar es mayor que la de ser par. También notará que cada número impar o par eventualmente aparecerá en la secuencia y solo puede aparecer una vez. Así, la secuencia es una verdadera permutación.

Definición de probabilidad

Para evitar confusiones o ambigüedades, voy a exponer claramente lo que se entiende por probabilidad en esta pregunta.

Digamos que tenemos una función . La probabilidad de que un número sea impar se definirá como el límite de la proporción de miembros impares del conjunto al tamaño del conjunto ya que tiende hacia el infinito.ff{1n}n

limn|{x:x{1n},odd(f(x))}|n

Por ejemplo, la función mencionada tendría una probabilidad de ser impar de 2/3 .


Este es el por lo que las respuestas se puntuarán en bytes, siendo mejores menos bytes.


Retos extra

Aquí hay algunas ideas divertidas para jugar y quizás intentar implementar. Estos son solo por diversión y no afectan la puntuación de ninguna manera. Algunas de estas ni siquiera son soluciones válidas para este desafío, y una respuesta que solo incluye soluciones para los desafíos 2 o 3 no es una respuesta válida y es probable que se elimine .

  • Escribe una permutación con una probabilidad impar de 1 . (Esto es posible)

  • Escriba una permutación que tenga más números impares que números pares en para cualquier pero tiene una probabilidad impar de .f{1n}n1/2

  • Escriba una permutación que no tenga una probabilidad definida (es decir, no hay límite).


1: Aquí la función significará programa o función. Es solo un fragmento de código que toma entrada y produce salida.

Asistente de trigo
fuente

Respuestas:

22

Jalea , 7 bytes

Æf^<¥4P

Intercambia 2 sy 3 s en la factorización prima de la entrada. La probabilidad de probabilidades es 2/3 .

Pruébalo en línea!

Cómo funciona

Æf^<¥4P  Main link. Argument: n

Æf       Compute all prime factors of n, with duplicates.
    ¥4   Combine the two links to the left into a dyadic chain and call it with
         right argument 4.
   <       Compare each prime factor with 4. Yields 1 for 2 and 3, 0 otherwise.
  ^        Bitwise XOR the results with the corresponding prime factors.
         This maps 2 to 3, 3 to 2, and all other primes to themselves.
      P  Take the product of the resulting primes.
Dennis
fuente
Esta respuesta es bastante inteligente. Creo que entiendo por qué funciona, pero es posible que desee incluir una prueba de que funciona porque al principio me pareció poco intuitivo.
Wheat Wizard
66
Prueba de que esto es una permutación: la función es su propio inverso. Prueba de relación: la probabilidad de que un resultado sea impar es la probabilidad de que el original no tuviera factores 3, que es exactamente cuando no es divisible por tres. Esa posibilidad es 2/3.
tomsmeding
15

Casco , 11 10 bytes

-1 byte gracias a Leo, y una función ligeramente diferente

Esto tiene una probabilidad extraña de 1

!uΣz:NCNİ1

Pruébalo en línea!

Indiza la secuencia:

[1,2,3,5,7,9,11,4,13,15,17,19,21,23,25,27,29,6,31,33]
1 odd, 1 even, 5 odd, 1 even, 9 odd, 1 even, 13 odd...

Explicación

!               Index the following sequence (1-indexed)
 u              remove duplicates                     [1,2,3,5,7,9,11,4,13,15...]
  Σ              Concatenate                          [1,1,2,3,5,3,7,9,11,4,13..]
   z:            Zipwith append                       [[1,1],[2,3,5],[3,7,9,11]..
     N          Natural numbers
      CNİ1      Odd numbers cut into lists of lengths [[1],[3,5],[7,9,11]...]
                corresponding to the Natural numbers
H.PWiz
fuente
1
¿Podría explicar la función?
Wheat Wizard
8

Haskell, 35 34 32 bytes

f n=n:2*n+1:2*n+3:f(n+2)
(f 0!!)

Implementa la secuencia de ejemplo [1,3,2,5,7,4,9,11,6,13,15,8,17,19,10,21,...].

Pruébalo en línea!

Para referencia: versión anterior, 34 bytes (-1 byte gracias a @xnor):

(!!)$do e<-[0,2..];[e,2*e+1,2*e+3]

Pruébalo en línea!

nimi
fuente
Ahorre un par:(!!)$do ...
xnor
8

Casco , 8 bytes

!uΣzeİ1N

Pruébalo en línea!

Esto implementa la secuencia de ejemplo ( 1,3,2,5,7,4...).

Explicación

!uΣzeİ1N
   ze       zip together
     İ1       the odd numbers
       N      with the natural (positive) numbers
  Σ         flatten the resulting list
 u          remove duplicates
!           index into the obtained sequence with the input
León
fuente
7

Todos hacen el Desafío 1, así que hagamos los otros dos.

Perl 6 , 26 bytes - Desafío 2

{($_==1)+$_-(-1)**($_%%2)}

Pruébalo en línea!

Es solo que 1 3 2 5 4 7 6...en un número par de términos, siempre hay 2 números impares más que pares. En un número impar, 1 más. Sin embargo esto tiene un límite claro de (n+2)/(2n+2) -> ½.


Perl 6 , 70 bytes - Desafío 3

{((1,),(2,4),->@a,@ {@(map(@a[*-1]+2*(*+1),^(4*@a)))}...*).flat[$_-1]}

Pruébalo en línea!

Es cierto que esto es horriblemente golf. Indexa una secuencia que contiene 2⁰ números impares, luego 2¹ pares, luego 2² impares, luego 2³ pares, y así sucesivamente.

La probabilidad después de n tales "bloques", si n es impar, es (2⁰ + 2² + 2⁴ + ... + 2ⁿ⁻¹) / (2ⁿ-1). La suma en el numerador es igual a ⅓ (4 ½ (n + 1) - 1) = ⅓ (2 n + 1 - 1). Entonces, la probabilidad después de un número impar de bloques es ⅔ (en el límite).

Si agregamos un bloque más (y hacemos un recuento par de ellos n + 1), sin embargo, no agregamos ningún número impar (el numerador permanece igual) pero ahora hay (2 n + 1 - 1) números en total . Los paréntesis se cancelan y obtenemos la probabilidad de ⅓ (en el límite).

Aparentemente, se supone que esto tiene 2 puntos de clúster diferentes, ⅓ y ⅔, para asegurarse de que el límite no exista, pero esto realmente no lo prueba. Mi intento de hacer una prueba sólida y rigurosa se puede encontrar en esta respuesta de Math.SE: https://math.stackexchange.com/a/2416990/174637 . Errores de golpe son bienvenidos.


Perl 6 , 39 bytes: el desafío principal.

{my$l=$_ div 3;$_%3??2*($_-$l)-1!!2*$l}

Pruébalo en línea!

Aunque publiqué esta respuesta debido a los desafíos 2 y 3 que ofrecían un pequeño y agradable rompecabezas matemático, existe un requisito estricto para que todas las respuestas contengan una solución al desafío central. Aquí está entonces.

Esta es la secuencia de ejemplo.

Ramillies
fuente
2
Estos son desafíos adicionales . Para que esta sea una respuesta válida, debe proporcionar una solución al desafío central. Una solución para el desafío 1 también es una solución para el desafío central, pero una solución para los desafíos 2 o 3 no lo es.
Peter Taylor
1
Bueno, los desafíos adicionales son lo que es interesante en esta pregunta para mí. El desafío central no es. Pero agregué alguna solución de todos modos.
Ramillies
Le pedí una prueba de que su respuesta al Desafío 3 no tiene límite en esta pregunta de Math.SE
Kevin - Restablezca a Monica el
@ Kevin, gracias por preguntar. Creo que te he confundido. Estaba bastante seguro de que estaba bien. Lo único es que a menudo pruebo las cosas de manera bastante rigurosa para mí mismo, solo por la tranquilidad (porque sus pies pueden resbalar con bastante facilidad, especialmente al manejar objetos infinitos como este), y no lo he hecho aquí. Eso es todo lo que quería decir.
Ramillies
1
@Kevin: así que, después de todo, superé mi pereza (¡un acto heroico!) E hice la prueba. Lo publiqué como respuesta a su pregunta de Math.SE. Esperemos que esté bien (hacer este tipo de trabajo por la noche no es realmente una buena idea :—)). Resultó que no es tan horrible como inicialmente pensé.
Ramillies
5

Brain-Flak , 120 bytes

(({})<{{({}[()]<({}(()[{}]))>)}{}({}[({})]<({}<>{}<({}())>)><>)}>)<>({}[()]){{}((<>{}<>[{}]){}[()])<>}{}{(({}){})<>{}}<>

Pruébalo en línea!

Realiza la siguiente función:

función

Esta función genera la secuencia.

2 4 1 6 3 5 7 8 9 11 13 15 17 19 21 10 23 25 27 29...

La función tiene una probabilidad impar de 1

0 '
fuente
4

R, 82 bytes (desafío adicional 1)

f<-function(n){if(sqrt(n)==floor(sqrt(n))){2*sqrt(n)}else{2*(n-floor(sqrt(n)))-1}}

Pruébalo en línea!

Si la entrada es un cuadrado perfecto, da un número par. De lo contrario, da un número impar. Los cuadrados perfectos tienen densidad natural 0, lo que significa que esta secuencia da números impares con probabilidad 1.

KSmarts
fuente
¿Podría agregar un enlace TIO por favor?
H.PWiz
1
58 bytes
Giuseppe
56 bytes
Giuseppe
53 bytes
Giuseppe
3

C (gcc) , 29 bytes

f(n){return n&3?n+n/2|1:n/2;}

Pruébalo en línea!

Cada cuarto número es par:

1 3 5   7 9 11   13 15 17   19 21 23   25 27 29
      2        4          6          8          10

Desafío adicional 1, 52 bytes

f(n,i){for(i=0;n>>i/2;i+=2);return n&n-1?2*n-i-1:i;}

Pruébalo en línea!

Devuelve 2 * (x + 1) si n es igual a 2 x y números impares consecutivos de lo contrario:

    1   3 5 7   9 11 13 15 17 19 21    23 25
2 4   6       8                     10      
nwellnhof
fuente
3

Cerebro-Flak , 140 138 136 bytes

({}<(((()())()()))((<>[()])[()()])>){({}[()]<(({}(({}({}))[({}[{}])]))[({}[{}])]<>(({}(({}({}))[({}[{}])]))[({}[{}])])<>)>)}{}({}<{}{}>)

Pruébalo en línea!

Explicación

Esto realiza una función similar a la sugerida en la pregunta.

2 3 1 4 7 5 6 11 9 8 15 13 10 17 15 ...

Funciona principalmente en base a un fragmento que hice para rodar la pila para pilas de tamaño 3.

(({}(({}({}))[({}[{}])]))[({}[{}])])

Configuramos dos pilas, una con valores de acumulador (dos impares, par) y otra con los números 4 4 2. En cada iteración tiramos ambas pilas y agregamos la parte superior de la pila izquierda a la parte superior de la pila derecha.

(({}(({}({}))[({}[{}])]))[({}[{}])]<>(({}(({}({}))[({}[{}])]))[({}[{}])])<>)

Esto incrementará cada número impar en 4 y el número par en 2. A medida que avanzamos, obtenemos un patrón de 2 pares 1 impares, con cada número entero positivo golpeado. Por lo tanto, simplemente repetimos los ntiempos con nser la entrada. Esto tiene una probabilidad asintótica de 2/3 .

Asistente de trigo
fuente
2

Jalea , 10 bytes

ÆE;0ṭ2/FÆẸ

La probabilidad de probabilidades es 2/3 .

Pruébalo en línea!

Cómo funciona

ÆE;0ṭ2/FÆẸ  Main link. Argument: n

ÆE          Compute the exponents of n's prime factorization.
  ;0        Append a 0.
     2/     Reduce all pairs by...
    ṭ         tack, appending the left argument to the right one.
            This inverts all non-overlapping pairs of exponents.
       F    Flatten the result.
        ÆẸ  Consider the result a prime factorization and compute the corresponding
            integer.
Dennis
fuente
1

C, 80 bytes

#define R if(k++==n)return
i,j,k;f(n){for(i=k=1,j=2;;i+=4,j+=2){R i;R i+2;R j;}}

Implementación del ejemplo de permutación de la pregunta.

Pruébalo en línea!

Steadybox
fuente
1

Lote, 36 bytes

@cmd/cset/an=%1*2,(-~n*!!(n%%3)+n)/3

Implementa la secuencia dada en la pregunta.

Neil
fuente
1

JavaScript, 23 bytes

n=>n/2+n/2%2+(n%4&&n-1)

Salida: 1, 3, 5, 2, 7, 9, 11, 4, 13, 15, 17, 6, 19, 21, 23, 8 ...

  • Para todos n = 4k:
    • f (n) = n / 2 = 2k
  • Para todos n = 4k + b
    • f (n) = n / 2 + b / 2 + n - 1 = 3/2 * (4k + b) + 1/2 * b - 1 = 6k + 2b - 1

Desafío 2:

n=>n^(n>1)

Salida: 1, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14

tsh
fuente
n=>n%4?1.5*n|1:n/2es 5 bytes más corto.
nwellnhof
1

CJam (21 bytes)

{2b_(&!\_,2*\1$~+2b?}

Demostración en línea que muestra las primeras 32 salidas. Este es un bloque anónimo (función).

Esta también es una solución para el desafío 1: los números asignados a números pares son las potencias de 2, por lo que la densidad de los números pares en las primeras n salidas es lg (n) / n, que tiende a cero.

Disección

{         e# Declare a block; let's call the input x
  2b      e#   Convert to base 2
  _(&     e#   Copy, pull out first digit (1) and set intersection with rest
  !       e#   Boolean not, so empty set (i.e. power of 2) maps to 1 and non-empty
          e#   to 0
  \_,2*   e#   Take another copy, find its length, and double it
  \1$~+   e#   Take the original base 2 array and append ~(2L) = -2L-1
  2b      e#   Convert from base 2, to get 2x-2L-1
  ?       e#   Take the 2L if it was a power of 2, and the 2x-2L-1 otherwise
}
Peter Taylor
fuente
1

Perl 40 bytes

$,=$";$i=4;{say$i-3,$i/2,($i+=4)-5;redo}

fuente
1

Flujo cerebral , 88 bytes

({}<(((<>)[()])[()()])>)<>(((()())()()))<>{({})({})({})({}[()]<({}<>({})<>)>)}{}{}({}){}

Pruébalo en línea!

Explicación

Esto implementa la misma función que mi última respuesta, pero utiliza el modelo FIFO de Brain-Flueue para cortar algunas esquinas. Aquí están los primeros dos términos que genera.

2 3 1 4 7 5 6 11 9 8 15 13 10 17 15 ...

La primera parte del código es solo un poco de configuración, colocamos 0,-1,-3en la primera pila y 2,4,4en la segunda pila. Se 2,4,4utilizará para recorrer los números pares e impares tal como lo hice en mi respuesta Brain-Flak.

Luego hacemos un bucle n veces, cada vez que agregamos la parte superior de la pila izquierda a la pila derecha. Dado que Brain-Flueue usa colas en lugar de pilas, los valores se mueven naturalmente a medida que los tocamos, evitando la necesidad de código adicional.

Asistente de trigo
fuente
¿Cuál es la diferencia entre Flueue y Flak?
FantaC
@tfbninja Flueue usa una cola en lugar de una pila.
Wheat Wizard
pero ... estás usando el intérprete bflk ... ¿cómo lo haces diferente?
FantaC
@tfbninja El -lflueueargumento.
Wheat Wizard
0

Python 2 , 46 104 55 bytes

lambda n:2*((n-int(n**.5))+.5,n**.5-1)[n!=1>0==n**.5%1]

Pruébalo en línea!

Leyó mal la pregunta, ahora implementó correctamente una función que puede usarse para generar una secuencia en lugar de una que genera una secuencia. También excluido 0del conjunto de salidas posibles.

La probabilidad de encontrar un número entero impar impar ahora converge 1.

Jonathan Frech
fuente
Esto debería devolver un número, no un conjunto / lista, por lo que yo entendí
Sr. Xcoder
Además, esta no es una permutación correcta, ya que contiene 0.
Sr. Xcoder
@ Mr.Xcoder Gracias por notarlo.
Jonathan Frech
0

Pyth , 9 bytes

*Fmxd<d4P

Pruébalo aquí! o prueba más de una vez!

Puede usar este código para verificar la proporción de números impares hasta cierto punto. Sustituya 10000con su límite deseado (no lo establezca mucho más alto, porque tiene errores de memoria).

Km*Fmxk<k4PdS10000clf%T2KlK

Probar aquí .

Lo anterior da aproximadamente 0.667 . La verdadera probabilidad de ocurrencias extrañas es 2/3 . Este enfoque es una implementación equivalente de la respuesta de Dennis .


Explicación

*Fmxd<d4P   Full program.

        P   Prime factors.
  m         Map over ^.
   x        Bitwise XOR between:
    d          The current prime factor.
     <d4       The integer corresponding to the boolean value of current factor < 4.
*F          Product of the list.
Sr. Xcoder
fuente
0

Java 8, 20 bytes

n->n%4>0?n+n/2|1:n/2

La respuesta C del puerto de @nwellnhof .
Algunas cosas que probé terminaron siendo unos bytes más largos o ligeramente incorrectos.

Implementos: 1,3,5,2,7,9,11,4,13,15,17,6,19,21,23,8,25,27,29,10,31,33,35,12,37,...
con una probabilidad de 3/4.

Pruébalo aquí

Kevin Cruijssen
fuente
0

Lua, 67 53 bytes

La explicación viene cuando termine de jugar golf :)

Este programa toma un número entero a través de argumentos de línea de comandos como entrada e imprime el enésimo elemento de la secuencia de ejemplo en STDOUT

n=...print(n%3<1 and n/3*2or n+math.floor(n/3)+n%3-1)

Explicaciones

n=...                              -- shorthand for the argument
print(                             -- prints out the result of the following ternary
     n%3<1                         -- if n is divisible by 3
       and n/3*2                   -- prints out the corresponding even number
       or n+math.floor(n/3)+n%3-1) -- else prints out the odd number

Los números pares de esta secuencia son el nnúmero par y el nmúltiplo de 3, por lo tanto, la fórmula n%3*2es suficiente para generarlos.

Para números impares, es un poco más difícil. Basado en el hecho de que podemos encontrarlos dependiendo de la corriente n, tenemos la siguiente tabla:

n       |  1   2   4   5   7   8   10   11  
target  |  1   3   5   7   9   11  13   15
target-n|  +0  +1  +1  +2  +2  +3  +3   +4

Llamemos al valor target-n i, podemos ver que cada vez n%3==2, ise incrementa. Ahí va nuestra fórmula:

n+math.floor(n/3)+n%3-1

Los números impares se basan nen los que agregamos i.

El valor de los iincrementos a la misma velocidad que la división euclidiana por 3, con un desplazamiento. math.floor(n/3)nos da la tasa de incremento y n%3-1nos da el desplazamiento, haciendo que ocurra en n%3==2lugar de n%3==0.

Katenkyo
fuente
Un byte podría guardarse fácilmente eliminando un espacio innecesario ( ...and (n/...).
Jonathan Frech
@JonathanFrech pudo guardar 2 en este lugar al eliminar totalmente el paréntesis, ya que and n/3*2orfunciona igual de bien
Katenkyo