Objetivo

Dada a entrada re nencontre os primeiros nnúmeros naturais, de xmodo que, se girarmos o primeiro dígito para o último local, obteremos x/r.

Você pode assumir que 2 <= r <= 9e 1 <= n <= 65535.

Você pode escrever um programa que receba informações dos argumentos stdin ou da linha de comando; ou você pode escrever uma função que aceita re ncomo parâmetros. A saída, no entanto, deve ser stdout. A saída deve ser uma linha por valor de x, formatada como x/r=y, em ordem crescente x.

Sua solução deve ser capaz de lidar com todos os casos válidos dentro de um minuto em um computador desktop razoável.

Casos de teste

Entrada: 4 5
Saída:

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

Entrada: 5 1
Saída:714285/5=142857

Isso é código-golfe, então o mínimo de bytes ganha. A resposta vencedora será aceita daqui a quatro semanas (19/09/2014).

Os créditos para esta pergunta vão para o meu colega, que me permitiu postar esta pergunta aqui :)

Haskell, 182 179

Segunda versão, provavelmente ainda mais jogável, mas com o algoritmo "adequado" desta vez. Em particular, ele termina dentro de alguns minutos com r=4e n=65535, mas, novamente, meu computador não é razoável nem desktop, portanto, é provável que isso permaneça dentro de um minuto em outras 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

É baseado na ideia de que x=10^k*a + m, onde seu primeiro dígito 0≤a≤9é movido para o final para obter y=10*m+a. Um pouco de matemática revela que mpode ser obtido como a*(10^k-r)/(10*r-1), de modo que basta digitalizar amais [1..9]para cada kde 0 a infinito, e manter e imprimir os primeiros nresultados para o qual a expressão acima para mé integral.

A fromIntegralé necessária porque reading uma lista com ncomo um de seus elementos main, em combinação com o uso de nno take, forçaria ra Inttoda, o que resulta em excessos desagradáveis com os grandes números em questão. Eu poderia ter usado genericTake, mas isso requer um import.

Esse código também tem o benefício de ser quase trivial expandir para bases diferentes de 10.

A entrada é lida stdin, os dois valores podem ser separados por qualquer espaço em branco.

Pure Bash (sem utilitários externos), 80 bytes

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

Observe que o bash apenas aritmético inteiro e não o ponto flutuante; portanto, verificamos se, em x == y * rvez de x / r == y. Também a multiplicação geralmente deve ser mais rápida. Ainda assim, isso não chega nem perto de atender aos requisitos de desempenho.

Resultado:

$ ./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);}}

(Algumas linhas novas não contadas na contagem de bytes foram adicionadas acima para eliminar as barras de rolagem. Sim, a nova linha final é contada.)

Espera argumentos na linha de comando e assume que a saída padrão aceita ASCII. O tempo de execução é O (número de bytes de saída) = O (n * n).

Não, eu não posso usar printf. Isso leva muito tempo e leva o programa além do limite de minutos na minha área de trabalho. Como é, alguns casos de teste levam cerca de 30 segundos.

O algoritmo trata a saída como seqüências de caracteres, não como números, uma vez que elas rapidamente se tornam enormes e existem padrões fortes na saída.

Um pouco não-destruído:

#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;
            }
        }
    }
}

Prova

que o programa resolve o problema:

(Na prova, considere todos os operadores e funções como as funções matemáticas reais, não as operações do computador que as aproximam. ^Denota exponenciação, não xor a bit).

Para maior clareza, usarei uma função ToDecpara descrever o processo comum de escrever um número como uma sequência de dígitos decimais. Seu alcance é o conjunto de tuplas ordenadas {0...9}. Por exemplo,

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

Para um número inteiro positivo n, defina L(n)como o número de dígitos na representação decimal de n; ou,

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

Para um número inteiro positivo ke um número não negativo ncom L(n)<k, defina Rep_k(n)como o número real obtido adicionando zeros na frente dos dígitos decimais de n, se necessário, para obter o ktotal de dígitos e, em seguida, repetindo infinitamente esses kdígitos após o ponto decimal. Por exemplo

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

A multiplicação Rep_k(n) * 10^kfornece os dígitos nanteriores ao ponto decimal e os dígitos (preenchidos com zero) de ninfinitamente repetidos após o ponto decimal. então

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

Dado um número inteiro positivo r, suponha que xseja uma solução para o problema e

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

onde x_1 != 0e k = L(x).

Para ser uma solução, xé um múltiplo de re

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

A aplicação da Rep_kfunção fornece uma boa equação:

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

Usando sua forma fechada de cima,

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

x_1deve estar no conjunto {1 ... 9}. rfoi especificado para estar no conjunto {2 ... 9}. Agora, a única questão é: para quais valores ka fórmula acima xfornece um número inteiro positivo? Vamos considerar cada valor possível rindividualmente.

Quando r= 2, 3, 6, 8 ou 9, 10r-1é 19, 29, 59, 79 ou 89, respectivamente. Em todos os casos, o denominador p = 10r-1é primo. No numerador, só 10^k-1pode haver um múltiplo de p, o que acontece quando

10^k = 1 (mod p)

O conjunto de soluções é fechado em adição e subtração que não resulta em um número negativo. Portanto, o conjunto compreende todos os múltiplos de algum fator comum, que também é a solução menos positiva para k.

Quando r = 4e 10r-1 = 39; ou quando r = 7e 10r-1 = 69, o denominador é 3 vezes um primo diferente p=(10r-1)/3. 10^k-1é sempre um múltiplo de 3 e, novamente, nenhum outro fator no numerador pode ser múltiplo de p, portanto, novamente o problema se reduz a

10^k = 1 (mod p)

e novamente as soluções são todos os múltiplos da solução menos positiva para k.

[Não finalizado...]

Python - 91 90

Aqui está um primeiro 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

Edit: Ok, provavelmente é uma maneira lenta de cumprir o limite de tempo de 1 minuto necessário para 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)}}

não jogou golfe:

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

Implementação em Python da solução de 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

Corre:

• python3 <whatever you named it>.py
• Aceita entrada em stdin
• Espaço de entrada separado

Resultado:

$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

Constatações:

https://oeis.org/A092697 é o primeiro valor para cada r.

Parece que apenas certos valores de k produzem respostas e que o intervalo é regular. Por exemplo, 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]

Os intervalos são:

• 2 = 18
• 3 = 28
• 4 = 6
• 5 = 6 (5 parece ser uma anomalia, como para a maioria dos valores de r, existem aglomerados de 9, 5 agrupamentos de formas de 9 e 1 (com apenas a = 7 funcionando), veja abaixo)
• 6 = 58
• 7 = 22
• 8 = 13
• 9 = 44

Este formulário https://oeis.org/A094224 .

Usando esses valores, uma versão mais eficiente pode ser criada:

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)

No entanto, ainda não posso provar que isso continua matematicamente.

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]