Objetivo

Dada entrada ry nencuentra los primeros nnúmeros naturales de xtal manera que si rotamos el primer dígito al último lugar que obtenemos x/r.

Puede suponer eso 2 <= r <= 9y 1 <= n <= 65535.

Puede escribir un programa que tome datos de argumentos estándar o de línea de comandos; o puede escribir una función que tome ry ncomo parámetros. La salida, sin embargo, debe ser stdout. La salida debe ser una línea por valor de x, formateada como x/r=y, en orden de aumento x.

Su solución debe poder manejar todos los casos válidos en un minuto en una computadora de escritorio razonable.

Casos de prueba

Entrada: 4 5
Salida:

102564/4=25641  
205128/4=51282  
307692/4=76923  
410256/4=102564  
512820/4=128205

Entrada: 5 1
Salida:714285/5=142857

Este es el código de golf, por lo que ganan menos bytes. La respuesta ganadora será aceptada dentro de 4 semanas (2014-09-19).

Los créditos para esta pregunta van a mi colega, quien me permitió publicar esta pregunta aquí :)

Haskell, 182 179

Segunda versión, probablemente más golfable, pero con algoritmo "apropiado" esta vez. En particular, termina en unos minutos con r=4y n=65535, pero, de nuevo, mi computadora no es razonable ni de escritorio, por lo que es probable que se quede dentro de un minuto en otras máquinas.

n#r=take n$[s(10^k*a+d)++'/':s r++'=':s d++s a|k<-[0..],a<-[1..9],let(d,m)=divMod(a*(10^k-r))(10*r-1),m<1]
s=show
main=interact$unlines.(\(r:n:_)->n#fromIntegral r).map read.words

Se basa en la idea de que x=10^k*a + m, donde 0≤a≤9se mueve su primer dígito hasta el final para obtener y=10*m+a. Un poco de matemáticas revela que mse puede obtener como a*(10^k-r)/(10*r-1), por lo que sólo tiene que escanear amás [1..9]por cada kde 0 a infinito, y mantenemos e imprimir los primeros nresultados para los cuales la expresión anterior para mes integral.

Se fromIntegralrequiere porque readincluir una lista ncomo uno de sus elementos en main, en combinación con el uso de nin take, obligaría ra Inttodo, lo que da como resultado desbordamientos desagradables con los grandes números en cuestión. Podría haber usado genericTake, pero eso requiere un import.

Este código también tiene el beneficio de ser casi trivial para expandirse a otras bases que no sean 10.

La entrada se lee stdin, los dos valores se pueden separar por cualquier espacio en blanco.

Pure Bash (sin utilidades externas), 80 bytes

for((;++x,c<$2;));{
y=$[10#${x:1}${x:0:1}]
((y*$1==x))&&echo $x/$1=$y&&((c++))
}

Tenga en cuenta que bash solo hace aritmética de enteros y no coma flotante, por lo que verificamos si en x == y * rlugar de x / r == y. También la multiplicación generalmente debería ser más rápida. Aún así, esto no está cerca de cumplir con el requisito de rendimiento.

Salida:

$ ./rotdiv.sh 4 5
102564/4=25641
205128/4=51282
307692/4=76923
410256/4=102564
512820/4=128205
$ ./rotdiv.sh 5 1
714285/5=142857
$ 

C 468

#include <stdlib.h>
#include <stdio.h>
#define a(s)fputs(s,stdout);
#define b(c)putchar(c);
int r;int z(char*s,int m){for(int i=0;i++<=m;)a(s)b(47)b(r+48)b(61)char*t=s;
while(*++t==48);a(t)while(m--)a(s)b(*s)b(10)}char x[10][60];
int main(int c,char**v){r=atoi(v[1]);int n=atoi(v[2]),q=10*r-1,d=0,p;
while(d++<9){p=r*d;char*y=x[d];do{p*=10;*y++=p/q+48;p%=q;}while(p!=r*d);}
d=1;p=q=0;while(n--){r==5&p<6?z(x[7],7*q+p++):(z(x[d],(r==5&d==7)?7*q+6:q),
++d>9?q+=d=1,p=0:0);}}

(Algunas líneas nuevas no contadas en el recuento de bytes se han agregado anteriormente para eliminar las barras de desplazamiento. Sí, se cuenta la línea nueva final).

Espera argumentos en la línea de comando y supone que la salida estándar acepta ASCII. El tiempo de ejecución es O (número de bytes de salida) = O (n * n).

No, no puedo usar printf. Eso lleva demasiado tiempo y empuja el programa por encima del límite de minutos en mi escritorio. Tal como están las cosas, algunos casos de prueba tardan unos 30 segundos.

El algoritmo trata la salida como cadenas, no números, ya que rápidamente se vuelven enormes, y hay patrones fuertes en la salida.

Algo sin golf:

#include <stdlib.h>
#include <stdio.h>

/* r is as in the problem description */
int r;

void show_line(const char* num, int repeats) {
    for (int i=0; i <= repeats; ++i)
        fputs(num, stdout);
    printf("/%c=", '0'+r);

    /* Assume the repeated num is a solution. Just move the first
       digit and skip any resulting leading zeros. */
    const char* num_tail = num;
    ++num_tail;
    while (*num_tail=='0')
        ++num_tail;
    fputs(num_tail, stdout);
    while (repeats--)
        fputs(num, stdout);
    printf("%c\n", *num);
}

/* sol[0] is unused. Otherwise, sol[d] is the repeating digits in the
   decimal representation of (r*d)/(10*r-1). */
char sol[10][60];

int main(int argc, char** argv) {
    r = atoi(argv[1]);
    int n = atoi(argv[2]);
    int q = 10*r-1;
    int d = 0;

    /* Populate the strings in sol[]. */
    while (d++<9) {
        int p = r*d;
        char* sol_str = sol[d];

        /* Do the long division p/q in decimal, stopping when the remainder
           is the original dividend. The integer part is always zero. */
        do {
            p *= 10;
            *sol_str++ = p/q + '0';
            p %= q;
        } while (p != r*d);
    }

    /* Output the answers. */
    d = 1;
    int repeats = 0;
    int r5x7_repeats = 0;
    while (n--) {
        if (r==5 && r5x7_repeats<6) {
            show_line(x[7], 7*repeats + r5x7_repeats);
        } else {
            if (r==5 && d==7)
                show_line(x[d], 7*repeats + 6);
            else
                show_line(x[d], repeats);
            if (++d > 9) {
                d = 1;
                ++repeats;
                r5x7_repeats = 0;
            }
        }
    }
}

Prueba

que el programa resuelve el problema:

(En la prueba, considere que todos los operadores y funciones son las funciones matemáticas reales, no las operaciones de la computadora que las aproximan. ^Denota exponenciación, no bit a xor).

Para mayor claridad, usaré una función ToDecpara describir el proceso ordinario de escribir un número como una secuencia de dígitos decimales. Su rango es el conjunto de tuplas ordenadas {0...9}. Por ejemplo,

ToDec(2014) = (2, 0, 1, 4).

Para un entero positivo n, defínalo L(n)como el número de dígitos en la representación decimal de n; o,

L(n) = 1+floor(log10(n)).

Para un entero positivo ky un entero no negativo ncon L(n)<k, defina Rep_k(n)como el número real obtenido agregando ceros delante de los dígitos decimales de n, si es necesario para obtener kdígitos totales, y luego repitiendo infinitamente esos kdígitos después del punto decimal. P.ej

Rep_4(2014) = .201420142014...
Rep_5(2014) = .020140201402...

Multiplicar Rep_k(n) * 10^kda los dígitos nanteriores al punto decimal, y los dígitos (rellenos con cero) de ninfinitamente repetidos después del punto decimal. Entonces

Rep_k(n) * 10^k = n + Rep_k(n)
Rep_k(n) = n / (10^k - 1)

Dado un número entero positivo r, supongamos que xes una solución al problema, y

ToDec(x) = ( x_1, x_2, ..., x_k )

donde x_1 != 0y k = L(x).

Para ser una solución, xes un múltiplo de ry

ToDec(x/r) : ( x_2, x_3, ..., x_k, x_1 ).

Aplicar la Rep_kfunción da una buena ecuación:

10*Rep_k(x) = x_1 + Rep_k(x/r)

Usando su forma cerrada desde arriba,

10x / (10^k - 1) = x_1 + x / r / (10^k - 1)
x = x_1 * r * (10^k-1) / (10r - 1)

x_1debe estar en el set {1 ... 9}. rse especificó para estar en el conjunto {2 ... 9}. Ahora la única pregunta es, ¿para qué valores de kla fórmula anterior xda un número entero positivo? Consideraremos cada valor posible de forma rindividual.

Cuando r= 2, 3, 6, 8 o 9, 10r-1es 19, 29, 59, 79 u 89, respectivamente. En todos los casos, el denominador p = 10r-1es primo. En el numerador, solo 10^k-1puede ser un múltiplo de p, lo que sucede cuando

10^k = 1 (mod p)

El conjunto de soluciones se cierra con sumas y restas que no resultan en un número negativo. Entonces, el conjunto comprende todos los múltiplos de algún factor común, que también es la solución menos positiva para k.

Cuando r = 4y 10r-1 = 39; o cuando r = 7y 10r-1 = 69, el denominador es 3 veces un primo diferente p=(10r-1)/3. 10^k-1siempre es un múltiplo de 3, y nuevamente ningún otro factor en el numerador puede ser múltiplo de p, por lo que nuevamente el problema se reduce a

10^k = 1 (mod p)

y nuevamente las soluciones son todos los múltiplos de la solución menos positiva para k.

[Sin terminar...]

Python - 91 90

Aquí hay un primer tiro:

r,n=input();i=1
while n:
 if int(`i`[1:]+`i`[0])*r==i:print'%d/%d=%d'%(i,r,i/r);n-=1
 i+=1

Editar: Ok, probablemente sea una forma lenta de cumplir con el límite de tiempo requerido de 1 minuto para los números de 65K.

JavaScript - 145

function f(a,b){for(d=0;d<b;d++)for(i=1;;i++){c=i/a;if(c==parseInt(i.toString().substring(1)+i.toString().charAt(0)))console.log(i+'/'+a+'='+c)}}

no golfizado:

function f(a,b){
    for(d=0;d<b;d++) //loop for the right amount
        for(i=1;;i++){ //iterating loop
            c=i/a; //actual result of the division
            if(c==parseInt(i.toString().substring(1)+i.toString().charAt(0)))
                console.log(i+'/'+a+'='+c)
        }
}

Python 3 - 223 179 bytes

Implementación de Python de la solución TheSpanishInquisition:

r,n=map(int,input().split());k=0
while 1:
 for a in range(1,10):
  D,M=divmod(a*(10**k-r),10*r-1)
  if M==0:
   print("%d/%d=%d"%(a*10**k+D,r,10*D+a));n-=1
   if n==0:exit()
 k+=1

Correr:

• python3 <whatever you named it>.py
• Toma entrada en stdin
• Espacio de entrada separado

Salida:

$python3 <whatever you named it>.py
4 8
102564/4=25641
205128/4=51282
307692/4=76923
410256/4=102564
512820/4=128205
615384/4=153846
717948/4=179487
820512/4=205128

Recomendaciones:

https://oeis.org/A092697 es el primer valor para cada r.

Parece que solo ciertos valores de k producen respuestas, y que el intervalo es regular. Por ejemplo, para r = 4:

Form: k [a, a, ...]
0 []
1 []
2 []
3 []
4 []
5 [1, 2, 3, 4, 5, 6, 7, 8, 9]
6 []
7 []
8 []
9 []
10 []
11 [1, 2, 3, 4, 5, 6, 7, 8, 9]
12 []
13 []
14 []
15 []
16 []
17 [1, 2, 3, 4, 5, 6, 7, 8, 9]
18 []
19 []
20 []
21 []
22 []
23 [1, 2, 3, 4, 5, 6, 7, 8, 9]

Los intervalos son:

• 2 = 18
• 3 = 28
• 4 = 6
• 5 = 6 (5 parece ser una anomalía, ya que para la mayoría de los valores de r, hay grupos de 9, 5 grupos de 9 y 1 (con solo a = 7 funcionando), ver más abajo)
• 6 = 58
• 7 = 22
• 8 = 13
• 9 = 44

Esto forma https://oeis.org/A094224 .

Usando estos valores, se puede construir una versión más eficiente:

import math

def A094224(n):
    return [18,28,6,6,58,22,13,44][n-2]


r,n=map(int,input().split());k=A094224(r)-1
H={}
while 1:
    for a in range(1,10):
        D,M=divmod(a*10**k-a*r,10*r-1)
        if M==0:
            print("%d/%d=%d"%(a*10**k+D,r,10*D+a));n-=1
            if n==0:exit()
    k+=A094224(r)

Sin embargo, no puedo (todavía) demostrar que esto continúa matemáticamente.

Resultados para r = 5:

0 []
1 []
2 []
3 []
4 []
5 [7]
6 []
7 []
8 []
9 []
10 []
11 [7]
12 []
13 []
14 []
15 []
16 []
17 [7]
18 []
19 []
20 []
21 []
22 []
23 [7]
24 []
25 []
26 []
27 []
28 []
29 [7]
30 []
31 []
32 []
33 []
34 []
35 [7]
36 []
37 []
38 []
39 []
40 []
41 [1, 2, 3, 4, 5, 6, 7, 8, 9]