Cada longitud de ciclo posible

21

Se puede decir que una función (o programa) que toma entradas y proporciona salidas tiene un ciclo si la llamada a la función en su propia salida alcanza eventualmente el número original. Por ejemplo, tome la siguiente función:

Input:  n    1 2 3 4 5 6
Output: f(n) 5 7 1 3 4 9

Si empezamos con n=1, f(n)=5, f(f(n))=f(5)=4, f(f(f(n)))=f(4)=3, f(f(f(f(n))))=f(3)=1.

Esto esta escrito (1 5 4 3). Dado que hay 4 números únicos en este bucle, este es un ciclo de longitud 4.


Su desafío es escribir un programa o función que tenga ciclos de todas las longitudes posibles. Es decir, debe haber un ciclo de longitud 1, de longitud 2, y así sucesivamente.

Además, su función / programa debe ser de enteros positivos a enteros positivos, y debe ser biyectivo , lo que significa que debe haber exactamente un valor de entrada para cada valor de salida posible, sobre todos los enteros positivos. Para decirlo de otra manera, la función / programa debe calcular una permutación de los enteros positivos.


Detalles: Se permite cualquier sistema de entrada / salida estándar, incluidos STDIN, STDOUT, argumento de función, retorno, etc. Lagunas estándar prohibidas.

No necesita preocuparse por las limitaciones de sus tipos de datos: las propiedades anteriores solo deben mantenerse bajo el supuesto de que uno into floatpuede contener cualquier valor, por ejemplo.

No hay restricciones en el comportamiento de la función en las entradas que no son enteros positivos, y esas entradas / salidas serán ignoradas.


La puntuación es el código de golf en bytes, el código más corto gana.

isaacg
fuente
"debe haber un ciclo de longitud 1, de longitud 2, y así sucesivamente" Si esto se interpreta como "debe haber al menos un ciclo de longitud 1, al menos uno de longitud 2, y así sucesivamente" o "debe ser exactamente un ciclo de longitud 1, uno de longitud 2, y así sucesivamente ".
Bakuriu
@Bakuriu Al menos un ciclo de cada longitud positiva.
isaacg

Respuestas:

11

Pyth, 11 8 bytes

.<W-0zz1

Mucho más aburrido que mi respuesta anterior.

Cada número que contiene un 0 dígitos se asigna a sí mismo. Cualquier otro número se asigna al número que tiene sus dígitos rotados en 1. Entonces, por ejemplo:

1 -> 1
10 -> 10
15 -> 51 -> 15
104 -> 104
123 -> 231 -> 312 -> 123
orlp
fuente
8

Python 2, 56 55 54 bytes

n=input()
a=b=1
while a+b<=n:a+=b;b+=1
print(n+~a)%b+a

Aquí están las primeras 21 salidas:

[1, 3, 2, 6, 4, 5, 10, 7, 8, 9, 15, 11, 12, 13, 14, 21, 16, 17, 18, 19, 20]

El patrón es obvio si dividimos la lista en trozos así:

 1    2  3    4  5  6    7  8  9  10    11  12  13  14  15    16  17  18  19  20  21
[1]  [3, 2]  [6, 4, 5]  [10, 7, 8, 9]  [15, 11, 12, 13, 14]  [21, 16, 17, 18, 19, 20]
Sp3000
fuente
Maldición, este es el patrón que también buscaba, pero con una forma cerrada.
orlp
1
Interesante ... los valores a siguen la secuencia A000124 . Pero supongo que ya lo sabías: P
Kade
Tenga en cuenta que esta secuencia es oeis.org/A066182 .
orlp
8

Pyth, 25 bytes

+hK/*J/h@h*8tQ2 2tJ2%-QKJ

Esta es la misma secuencia que @ Sp3000, pero con una forma cerrada. La forma cerrada es:

M (n) = piso ((1 + sqrt (1 + 8 * (n - 1))) / 2) B (n) = M (n) * (M (n) - 1) / 2 f (n) = B (n) + ((n - B (n) + 1) mod M (n))

orlp
fuente
5

Python3, 40 bytes

n=input();print([n[1:]+n[0],n]['0'in n])

Cada número que contiene un 0 dígitos se asigna a sí mismo. Cualquier otro número se asigna al número que tiene sus dígitos rotados en 1. Entonces, por ejemplo:

1 -> 1
10 -> 10
15 -> 51 -> 15
104 -> 104
123 -> 231 -> 312 -> 123
orlp
fuente
1
¡Deja Vu! ¡Genial verlo en dos idiomas!
Denham Coote
3

Rubí, 22 + 1 = 23

Con el indicador de línea de comando -p, ejecute

~/(.)(.?)/
$_=$1+$'+$2

Cuando se le da como entrada una representación de cadena de un número (sin nueva línea final), mantiene constante el primer dígito, luego gira el resto hacia la izquierda, por lo que 1234 convierte 1342.

Esto se puede reducir a 21 caracteres con $_=$1+$'+$2if/(.)(.)/, pero imprime una advertencia.

histocrat
fuente
3

Rubí, 16 + 1 = 17

Con el indicador de línea de comando -p, ejecute

$_=$_[/.0*$/]+$`

Esta es una función más complicada que mi otra respuesta, pero resulta más fácil de jugar (y tolerante a las nuevas líneas). Toma el último dígito distinto de cero de la entrada, más los ceros finales, y lo mueve al comienzo del número. Así se 9010300convierte 3009010. Cualquier número con n dígitos distintos de cero será parte de un ciclo de n longitudes.

La entrada es una cadena en cualquier base a través de STDIN, la salida es una cadena en esa base.

histocrat
fuente
2

Python, 43

La inversa de la función de Sp3000 , implementada recursivamente.

f=lambda n,k=1:n>k and k+f(n-k,k+1)or n%k+1

La función es un ciclo seguido de dos ciclos seguido de tres ciclos, ...

(1)(2 3)(4 5 6)(7 8 9 10)(11 12 13 14 15)...

La operación n%k+1actúa como un kciclo en los números 1..k. Para encontrar el apropiado kpara usar, cambie todo hacia abajo k=1, luego k=2, y así sucesivamente, hasta n<=k.

xnor
fuente
2

Pyth, 15 bytes

La respuesta más corta hasta el momento que utiliza operaciones numéricas en lugar de operaciones de cadena.

.|.&Q_=.&_=x/Q2

    Q                input
            /Q2      input div 2
           x   Q     that XOR input
          =          assign that to Q
         _           negate that
       .&       Q    that AND Q
      =              assign that to Q
     _               negate that
  .&                 input AND that
.|               Q   that OR Q

El efecto de esta función en la representación binaria es extender el bloque más a la derecha de 1s al siguiente 0; o si no hay 0, para restablecerlo de nuevo a un solo 1:

10010110100000 ↦  
10010110110000 ↦  
10010110111000 ↦  
10010110111100 ↦  
10010110111110 ↦  
10010110111111 ↦
10010110100000  

Pyth, 26 bytes, variante divertida

.|.&Q_h.&/Q2+Qy=.&/Q2_h.|y

    Q                           input
         /Q2                    input div 2
             Q                  input
                  /Q2           input div 2
                         yQ     twice input
                       .|  Q    that OR input
                     _h         NOT that
                .&              (input div 2) AND that
               =                assign that to Q
              y                 twice that
            +                   input plus that
       .&                       (input div 2) AND that
     _h                         NOT that
  .&                            input AND that
.|                          Q   that OR Q

Realiza la operación anterior simultáneamente en todos los bloques de 1s, no solo en el más a la derecha, aún utilizando solo operaciones bit a bit y aritméticas.

1000010001001 ↦
1100011001101 ↦
1110011101001 ↦
1111010001101 ↦
1000011001001 ↦
1100011101101 ↦
1110010001001 ↦
1111011001101 ↦
1000011101001 ↦
1100010001101 ↦
1110011001001 ↦
1111011101101 ↦
1000010001001
Anders Kaseorg
fuente
1

Swift 1.2, 66 bytes

func a(b:Int){var c=0,t=1,n=b
while n>c{n-=c;t+=c++}
print(n%c+t)}
Input:  1,   2, 3,  4, 5, 6,   7, 8, 9, 10,   11, 12, 13, 14, 15
Output: 1,   3, 2,  5, 6, 4,   8, 9, 10, 7,   12, 13, 14, 15, 11
David Skrundz
fuente
1

Brachylog , 5 bytes

∋0&|↺

Pruébalo en línea!

Puerto de la respuesta Pyth de @ orlp. Sale simple y ordenado:

∋0    % If input contains a 0 (since input is a single number, "contains" ∋ treats it as an array 
      %   of its digits, so this means "if any of input's digits are 0")
&     % Then output is the input
|     % Otherwise
↺     % Circularly shift the input once, and unify that with the output

Originalmente quería portar la solución Python de @ Sp3000, pero eso tomó la friolera de 23 bytes :

⟧∋B-₁⟦++₁A≤?;A--₁;B%;A+

Pruébalo en línea!

sundar - Restablecer a Monica
fuente
0

JavaScript (ES6), 43 bytes

f=(n,i=1,j=1)=>n>j?f(n,++i,j+i):n++<j?n:n-i
Neil
fuente
0

Matlab (189)

  function u=f(n),if(~n|n==1)u=n;else,u=n;y=factor(n);z=y(y~=2);if ~isempty(z),t=y(y~=max(y));if isempty(t),u=y(end)*2^(nnz(y)-1);else,g=max(t);e=primes(g*2);u=n/g*e(find(e==g)+1);end,end,end

  • La función:

    Asigna cualquier número entero de acuerdo con sus factores primos, si el número es nulo o factorizado en 2 o 1, el número se asigna a sí mismo, de lo contrario, elegimos el factor primo más grande de este número, luego incrementamos los factores primos restantes restantes por el más cercano factor primo más grande hasta que alcancemos el número biggest_prime^ndonde nestá la suma de todos los exponentes de todos los factores, una vez que alcanzamos esa cantidad, recurrimos max_prime*2^(n-1)y reproducimos el mismo ciclo nuevamente.

Abr001am
fuente
0

Matlab (137)

  function u=h(n),if(~n|n==1)u=n;else,u=n;y=factor(n);z=y(y~=2);if~isempty(z),e=nnz(y);f=nnz(z);if(~mod(e,f)&e-f)u=n/2^(e-f);else,u=u*2;end

  • Un enfoque ligeramente similar, multiplicando gradualmente cualquier número que no sea igual a {0,1,2 ^ n} por 2hasta que nos topemos con un exponente 2que sea divisible por la suma de exponentes de otros factores primos. luego nos movemos al comienzo del ciclo dividiendo por 2^(sum of exponents of other primes). los otros entumecidos se asignan a sí mismos.
Abr001am
fuente