Objectif

Étant donné l'entrée ret ntrouver les premiers nnombres naturels xtels que si nous tournons le premier chiffre au dernier endroit que nous obtenons x/r.

Vous pouvez supposer cela 2 <= r <= 9et 1 <= n <= 65535.

Vous pouvez écrire un programme qui accepte les entrées de stdin ou des arguments de ligne de commande; ou vous pouvez écrire une fonction qui prend ret ncomme paramètres. Cependant, la sortie devrait être stdout. La sortie doit être une ligne par valeur de x, formatée x/r=yen ordre croissant x.

Votre solution doit être capable de gérer tous les cas valides en une minute sur un ordinateur de bureau raisonnable.

Cas de test

Entrée: 4 5
Sortie:

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

Entrée: 5 1
Sortie:714285/5=142857

Il s'agit de code-golf, donc le moins d'octets est gagnant. La réponse gagnante sera acceptée dans 4 semaines (2014-09-19).

Les crédits pour cette question vont à mon collègue, qui m'a permis de poster cette question ici :)

Haskell, 182 179

Deuxième version, probablement plus jouable au golf, mais avec un "bon" algorithme cette fois. En particulier, il se termine en quelques minutes avec r=4et n=65535, mais là encore, mon ordinateur n'est ni raisonnable ni un ordinateur de bureau, il est donc probable que cela reste en une minute sur d'autres machines.

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

Il est basé sur l'idée que x=10^k*a + m, où son premier chiffre 0≤a≤9est déplacé à la fin pour obtenir y=10*m+a. Un peu de mathématiques révèle que mpeut être obtenu comme a*(10^k-r)/(10*r-1), donc nous Numérisez simplement asur [1..9]pour chaque kde 0 à l' infini, et conserver et imprimer les premiers nrésultats pour lesquels l'expression ci - dessus pour mfait partie intégrante.

Le fromIntegralest nécessaire car la readcréation d'une liste avec l' nun de ses éléments dans main, en combinaison avec l'utilisation de nin take, forcerait rà Inttravers, ce qui entraîne des débordements désagréables avec les grands nombres en question. J'aurais pu utiliser genericTake, mais cela nécessite un import.

Ce code a également l'avantage d'être presque trivial pour s'étendre à des bases autres que 10.

L'entrée est lue stdin, les deux valeurs peuvent être séparées par n'importe quel espace.

Pure Bash (pas d'utilitaires externes), 80 octets

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

Notez que bash ne fait que de l'arithmétique entière et non en virgule flottante, nous vérifions donc si x == y * rau lieu de x / r == y. De plus, la multiplication devrait généralement être plus rapide. Pourtant, cela est loin de répondre à l'exigence de performance.

Production:

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

(Certains sauts de ligne non comptés dans le nombre d'octets ont été ajoutés ci-dessus pour éliminer les barres de défilement. Oui, le saut de ligne final est compté.)

Attend des arguments sur la ligne de commande et suppose que la sortie standard accepte ASCII. Le temps d'exécution est O (nombre d'octets en sortie) = O (n * n).

Non, je ne peux pas utiliser printf. Cela prend trop de temps et pousse le programme au-delà de la limite des minutes sur mon bureau. En l'état, certains cas de test prennent environ 30 secondes.

L'algorithme traite la sortie comme des chaînes, et non comme des nombres, car elles deviennent rapidement énormes et il existe de forts schémas dans la sortie.

Assez peu 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;
            }
        }
    }
}

Preuve

que le programme résout le problème:

(Dans la preuve, prenez tous les opérateurs et fonctions pour être les vraies fonctions mathématiques, pas les opérations informatiques qui les rapprochent. ^Dénote l'exponentiation, pas le xor au niveau du bit.)

Pour plus de clarté, je vais utiliser une fonction ToDecpour décrire le processus ordinaire d'écriture d'un nombre sous la forme d'une séquence de chiffres décimaux. Sa gamme est l'ensemble de tuples ordonnés sur {0...9}. Par exemple,

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

Pour un entier positif n, définissez L(n)comme étant le nombre de chiffres dans la représentation décimale de n; ou,

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

Pour un entier positif ket un entier non négatif navec L(n)<k, définissez Rep_k(n)comme étant le nombre réel obtenu en ajoutant des zéros devant les chiffres décimaux de n, si nécessaire pour obtenir le ktotal des chiffres, puis en répétant à l'infini ces kchiffres après le point décimal. Par exemple

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

La multiplication Rep_k(n) * 10^kdonne les chiffres d' navant la virgule décimale et les chiffres (remplis de zéro) ninfiniment répétés après la virgule décimale. Donc

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

Étant donné un entier positif r, supposons xune solution au problème, et

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

où x_1 != 0et k = L(x).

Pour être une solution, xest un multiple de r, et

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

L'application de la Rep_kfonction donne une belle équation:

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

En utilisant sa forme fermée d'en haut,

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

x_1doit être dans l'ensemble {1 ... 9}. ra été spécifié pour être dans l'ensemble {2 ... 9}. Maintenant, la seule question est: pour quelles valeurs kla formule ci-dessus xdonne-t-elle un entier positif? Nous considérerons chaque valeur possible rindividuellement.

Quand r= 2, 3, 6, 8 ou 9, 10r-1est respectivement 19, 29, 59, 79 ou 89. Dans tous les cas, le dénominateur p = 10r-1est premier. Dans le numérateur, seul 10^k-1peut être un multiple de p, ce qui se produit lorsque

10^k = 1 (mod p)

L'ensemble des solutions est fermé sous addition et sous soustraction qui n'aboutit pas à un nombre négatif. Ainsi, l'ensemble comprend tous les multiples d'un facteur commun, qui est également la solution la moins positive pour k.

Quand r = 4et 10r-1 = 39; ou quand r = 7et 10r-1 = 69, le dénominateur est 3 fois un nombre premier différent p=(10r-1)/3. 10^k-1est toujours un multiple de 3, et là encore aucun autre facteur du numérateur ne peut être un multiple de p, donc encore une fois le problème se réduit à

10^k = 1 (mod p)

et encore une fois les solutions sont tous les multiples de la solution la moins positive pour k.

[Pas terminé...]

Python - 91 90

Voici un premier coup:

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, c'est probablement un moyen de ralentir pour respecter le délai de 1 minute requis pour les numéros 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)}}

non golfé:

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 octets

Implémentation Python de la solution 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

Courir:

• python3 <whatever you named it>.py
• Prend une entrée sur stdin
• Espace d'entrée séparé

Production:

$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

Résultats:

https://oeis.org/A092697 est la première valeur pour chaque r.

Il semble que seules certaines valeurs de k produisent des réponses, et que l'intervalle soit régulier. Par exemple pour 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]

Les intervalles sont:

• 2 = 18
• 3 = 28
• 4 = 6
• 5 = 6 (5 semble être une anomalie, car pour la plupart des valeurs de r, il y a des blocs de 9, 5 forme des blocs de 9 et 1 (avec seulement a = 7 en fonctionnement), voir ci-dessous)
• 6 = 58
• 7 = 22
• 8 = 13
• 9 = 44

Cela forme https://oeis.org/A094224 .

En utilisant ces valeurs, une version plus efficace peut être construite:

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)

Cependant, je ne peux pas (encore) prouver que cela continue mathématiquement.

Résultats pour 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]