Encontre a repetição da representação decimal!

12

Em este desafio há 2 anos, encontramos o período de uma fração de unidade ( 1/n where n is a natural number).

Agora, sua tarefa é escrever um programa / função para encontrar a repetição de uma fração de unidade.

O repetir é a parte da expansão decimal que se repete infinitamente, como:

  • A representação decimal de 1/6é 0.16666..., então a repetição é 6.
  • A representação decimal de 1/11é 0.090909..., então a repetição é 09.
  • A representação decimal de 1/28é 0.0357142857142857142857..., então a repetição é 571428.

Especificações

  • Entrada em qualquer formato razoável.
  • Saída repetida em decimal, string ou lista .
  • Para 1/7( 0.142857142857...), você deve produzir em 142857vez de 428571.
  • Para 1/13( 0.076923076923076923...), você deve produzir em 076923vez de 76923.
  • Sem força bruta, por favor.

Casos de teste

Input    Output
1        0
2        0
3        3
7        142857
13       076923
17       0588235294117647
28       571428
70       142857
98       102040816326530612244897959183673469387755
9899     000101020305081321345590463683200323264976260228305889483786241034447924032730578846348115971310233356904737852308313971108192746742095161127386604707546216789574704515607637135064147893726639054449944438832205273259925244974239822204263056874431760783917567431053641781998181634508536215779371653702394181230427315890493989291847661379937367410849580765733912516415799575714718658450348520052530558642287099707041115264168097787655318719062531568845337912920497019901

Pontuação

Isso é código-golfe . A solução mais curta em bytes ganha.

Nenhuma resposta seria aceita, porque o objetivo não é encontrar o idioma capaz de produzir a solução mais curta, mas a solução mais curta em cada idioma.

Entre os melhores

Mostrar snippet de código

code-golf math arithmetic number-theory Freira Furada
fonte
Vamos continuar esta discussão no chat .
Rɪᴋᴇʀ
1
Como você decide que a repetição de 13 é 076923 e não 769230?
aditsu saiu porque SE é MAU 29/04
@aditsu Porque 1/13é 0.076923076923...não0.769230769230...
Leaky Nun
3
Afirmar abertamente que você nunca aceitará uma resposta praticamente faz deste um catálogo. Apenas não diga nada e nunca aceite uma resposta.
Dennis
1
Você pode adicionar um snippet de pilha para mostrar a solução mais curta para cada idioma.
aditsu saiu porque SE é MAU 30/04

Respostas:

5

Java, 150 bytes:

String p(int n){int a=1,p;String r="";for(;n%10<1;n/=10);for(;n%2<1;n/=2)a*=5;for(;n%5<1;n/=5)a*=2;for(p=a%=n;;){p*=10;r+=p/n;if(a==(p%=n))return r;}}

Espaço em branco adicionado:

String p(int n){
    int a=1,p;
    String r="";
    for(;n%10<1;n/=10);
    for(;n%2<1;n/=2)
        a*=5;
    for(;n%5<1;n/=5)
        a*=2;
    for(p=a%=n;;){
        p*=10;
        r+=p/n;
        if(a==(p%=n))
            return r;
    }
}

Programa completo e não-destruído:

import java.util.Scanner;

public class A036275 {
    public static String period(int a,int n){
        if(n%10==0) return period(a,n/10);
        if(n%2==0) return period(a*5,n/2);
        if(n%5==0) return period(a*2,n/5);
        a %= n;
        int pow = a;
        String period = "";
        while(true){
            pow *= 10;
            period += pow/n;
            pow %= n;
            if(pow == a){
                return period;
            }
        }
    }
    public static String period(int n){
        return period(1,n);
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();
        System.out.println(period(n));
    }
}
Freira Furada
fonte
for(;;)haveria menos bytes do que while(2<3)se não fosse um loop infinito! (e menos bytes do que while(1)também @Maltysen)
Marv
@Marv Como pude esquecer isso? Obrigado!
Leaky Nun
Coloque as declarações para ae rnos loops for. Salva bytes!
CalculatorFeline
1
@CatsAreFluffy Isso os tornaria inacessíveis ... #
Leaky Nun
3

CJam, 26

riL{_XW$%A*:X|X@-}g_X#>\f/

Experimente online

Explicação:

O programa gera uma série de dividendos envolvidos no cálculo da expansão decimal, até encontrar um dividendo que já viu antes. Depois, pega todos os dividendos que começam com esse e os divide por n para obter os dígitos da repetição.

ri       read the input and convert to integer (n)
L        push an empty array (will add the dividends to it)
{…}g     do … while
  _      copy the current array of dividends
  X      push the latest dividend (initially 1 by default)
  W$     copy n from the bottom of the stack
  %A*    calculate X mod n and multiply by 10
  :X     store in X (this is the next dividend)
  |      perform set union with the array of dividends
  X@     push X and bring the old array to the top
  -      set difference; it is empty iff the old array already contained X
          this becomes the do-while loop condition
_X#      duplicate the array of dividends and find the position of X
>        take all dividends from that position
\f/      swap the array with n and divide all dividends by n
aditsu sair porque SE é MAU
fonte
3

Python 3.5, 79 74 73 70 bytes

f=lambda n,t=1,q=[],*d:q[(*d,t).index(t):]or f(n,t%n*10,q+[t//n],*d,t)

Economizei 3 bytes mantendo o controle dos dividendos, uma ideia que tirei da resposta CJam do @ aditsu .

Testá-lo em repl.it .

Dennis
fonte
2

Gelatina , 12 10 bytes

%³×⁵
1ÇÐḶ:

Economizei 2 bytes mantendo o controle dos dividendos, uma ideia que tirei da resposta CJam do @ aditsu .

Experimente online!

Como funciona

%³×⁵     Helper link. Argument: d (dividend)

%³       Yield the remainder of the division of d by n.
  ×⁵     Multiply by 10.


1ÇÐḶ:    Main link. Argument: n

1        Yield 1 (initial dividend).
 ÇÐḶ     Apply the helper link until its results are no longer unique.
         Yield the loop, i.e., everything from the first repeated result
         up to and including the last unique one.
    :    Divide each dividend by n.
Dennis
fonte
1

Idioma do GameMaker, 152 bytes

Com base na resposta de Kenny

n=argument0;a=1r=0while(n mod 2<1){a*=5n/=2}while(n mod 5<1){a*=2n/=5}a=a mod n;p=a;while(1){p*=10r=r*10+p/n;r=r mod $5f5e107;p=p mod n;if(a=p)return r}
Timtech
fonte
Acabei de encontrar um bug na minha abordagem e o corrigi, então talvez você precise atualizar isso também.
Leaky Nun
1

Java, 122

String f(int n){String r="";int x=1,a[]=new
int[n*10];while(a[x]++<1)x=x%n*10;do{r+=x/n;x=x%n*10;}while(a[x]<2);return r;}

Semelhante à minha solução CJam.

aditsu sair porque SE é MAU
fonte
1

Perl 6 , 37 bytes

{(1.FatRat/$_).base-repeating[1]||~0}
~0 max (1.FatRat/*).base-repeating[1]

Se você não se importa que ele funcione apenas com denominadores que se encaixam em um número inteiro de 64 bits, você pode remover a chamada de método para .FatRat.

Explicação:

# return ｢"0"｣ if ｢.base-repeating｣ would return ｢""｣
~0

# ｢&infix<max>｣ returns the numerically largest value
# or it's first value if they are numerically equal
max

(
  # turn 1 into a FatRat so it will work
  # with denominators of arbitrary size
  1.FatRat

  # divided by
  /

  # the input
  *

# get the second value from calling the
# method ｢.base-repeating｣
).base-repeating[1]

Teste:

#! /usr/bin/env perl6
use v6.c;
use Test;

my &code = ~0 max (1.FatRat/*).base-repeating[1];
# stupid highlighter */
# Perl has never had // or /* */ comments

my @tests = (
  1    => '0',
  2    => '0',
  3    => '3',
  6    => '6',
  7    => '142857',
  11   => '09',
  13   => '076923',
  17   => '0588235294117647',
  28   => '571428',
  70   => '142857',
  98   => '102040816326530612244897959183673469387755',
  9899 => '000101020305081321345590463683200323264976260228305889483786241034447924032730578846348115971310233356904737852308313971108192746742095161127386604707546216789574704515607637135064147893726639054449944438832205273259925244974239822204263056874431760783917567431053641781998181634508536215779371653702394181230427315890493989291847661379937367410849580765733912516415799575714718658450348520052530558642287099707041115264168097787655318719062531568845337912920497019901',
);

plan +@tests;

for @tests -> $_ ( :key($input), :value($expected) ) {
  is code($input), $expected, "1/$input";
}
1..12
ok 1 - 1/1
ok 2 - 1/2
ok 3 - 1/3
ok 4 - 1/6
ok 5 - 1/7
ok 6 - 1/11
ok 7 - 1/13
ok 8 - 1/17
ok 9 - 1/28
ok 10 - 1/70
ok 11 - 1/98
ok 12 - 1/9899
Brad Gilbert b2gills
fonte
0

Pitão, 63 bytes

W!%QT=/QT;J*F+1-PQ,2 5K%*F+1-L7@,2 5PQJ=NKW1=+k/=*NTJIqK=%NJB;k

Experimente online!

Tradução direta da resposta em Java .

Freira Furada
fonte
0

PHP, 169 bytes

$d=$argv[2];$a[]=$n=$argv[1];while($n%$d&&!$t){$n*=10;$r[]=$n/$d^0;$t=in_array($n%=$d,$a);$a[]=$n;}if($t)echo join(array_slice($r,array_search(end($a),$a),count($a)-1));
Jörg Hülsermann
fonte