Para verificar se um número decimal é divisível por 7:

Apague o último dígito. Multiplique por 2 e subtraia o que resta. Se o resultado é divisível por 7, o número original é divisível por 7.

(também descrito, por exemplo, aqui )

Esta regra é boa para verificação de divisibilidade manual. Por exemplo:

2016 é divisível por 7?

Subtrair 6*2de 201; temos 189. Isso é divisível por 7? Para verificar, vamos aplicar a regra novamente.

Subtraia 9*2de 18; temos 0. Portanto, 2016 é divisível por 7.

Nesse desafio, você deve aplicar esta regra até que o status de divisibilidade seja óbvio , ou seja, o número não seja maior que 70 (no entanto, veja detalhes abaixo). Faça uma função ou um programa completo.

Entrada : um número inteiro positivo; seu código deve suportar entradas de até 32767 (o suporte a números inteiros de precisão arbitrária é um bônus; veja abaixo).

Saída : um número inteiro (possivelmente negativo), não superior a 70, resultante da aplicação da regra da divisibilidade por 7 a zero ou mais vezes.

Casos de teste:

Input                   Output      Alternative output

1                       1
10                      10          1
100                     10          1
13                      13          -5
42                      42          0
2016                    0
9                       9
99                      -9
9999                    -3
12345                   3
32767                   28          -14

---------- Values below are only relevant for the bonus

700168844221            70          7
36893488147419103232    32          -1
231584178474632390847141970017375815706539969331281128078915168015826259279872    8

Onde duas saídas possíveis são especificadas, qualquer um dos resultados está correto: o segundo corresponde à aplicação da regra mais uma vez. É proibido aplicar a regra em um número de um dígito: se você apagar o dígito, não resta nada (não 0).

Bônus : se o seu algoritmo

• Suporta números inteiros de precisão arbitrária
• Executa apenas uma passagem na entrada
• Tem complexidade de espaço o(n)(ou seja, menor que O(n)); e
• Tem complexidade de tempo O(n),

onde né o número de dígitos decimais:

Subtraia 50% da contagem de bytes do seu código.

Bônus real :

Além disso, se o seu algoritmo lê a entrada na direção normal, começando pelo dígito mais significativo, subtraia 50% mais uma vez - sua pontuação é de 25% da sua contagem de bytes (parece possível, mas não tenho certeza).

Golfscript, 27 22 bytes

{.9>{.10/\10%2*-f}*}:f

Você pode usá-lo desta maneira:

1000f

Explicação

{.9>{.10/\10%2*-f}*}:f
{                  }:f    # Define block 'f' (similar to a function)
 .                        # Duplicate the first value of the stack
  9>{            }*       # If the value on top of the stack is greater than 9 then the block is executed
     .10/\10%2*-          # Same as nb/10 - (nb%10 * 2) with some stack manipulations '.' to duplicate the top of the stack and '\' to swap the the first and second element of the stack
                f         # Execute block 'f'

5 bytes salvos graças ao Dennis!

Haskell, 35 bytes

until(<71)(\n->div n 10-2*mod n 10)

Exemplo de uso: until(<71)(\n->div n 10-2*mod n 10) 36893488147419103232-> 32.

Nada a explicar, é uma implementação direta do algoritmo.

Gelatina, 11 bytes

d⁵Uḅ-2µ>9$¿

Experimente online!

Como funciona

d⁵Uḅ-2µ>9$¿  Main link. Input: n

d⁵           Divmod; return [n : 10, n % 10].
  U          Upend; yield [n % 10, n : 10].
   ḅ-2       Convert from base -2 to integer, i.e., yield -2 × (n % 10) + (n : 10).

      µ      Push the previous chain as a link and begin a new, monadic chain.
          ¿  Apply the previous chain while...
       >9$     its return value is greater than 9.

Python 2, 38 bytes

f=lambda x:f(x/10-x%10*2)if x>70else x

Experimente aqui !

Abordagem recursiva simples. Imprime x se <70 aplica a regra de divisibilidade e chama a si mesma com o resultado.

Pitão, 13 bytes

.W>H9-/ZTyeZQ

Experimente on-line: Demonstration or Test Suite

Isso imprimirá todas as respostas alternativas.

Explicação:

.W>H9-/ZTyeZQ   
            Q   read a number from input
.W              while
  >H9              the number is greater than 9
                do the following with the number:
      /ZT          divide it by 10
     -             and subtract
         yeZ       2*(number%10)

Julia, 27 26 bytes

f(x)=x>9?f(x÷10-x%10*2):x

Esta é uma função recursiva que aceita um número inteiro e retorna a BigInt. Se a entrada for um número grande, como no último exemplo, Julia a analisa como uma BigInt, portanto, nenhuma conversão manual é necessária.

A abordagem é apenas uma implementação direta do algoritmo. Ele produzirá as saídas alternativas. Tomar o módulo ao dividir por 10 gera o último dígito e o quociente da divisão inteira por 10 gera tudo, menos o último dígito.

Guardado um byte graças a Dennis!

Pitão, 17 bytes

L?<b70by-/bT*%bT2

Experimente aqui!

A mesma abordagem recursiva da minha resposta em python . Define um lambda yque é chamado assim: y12345.
O contador de bytes no intérprete online mostra 19 bytes porque adicionei a chamada lambda a ele, para que você possa experimentá-lo pressionando o botão de execução.

Explicação

L?<b70by-/bT*%bT2

L                  # Defines the lambda y with the parameter b
 ?<b70             # if b < 70:
      b            # return b, else:
       -/bT*%bT2   # calculate b/10 - b%10*2 and return it

CJam - 19 bytes

Versão do while:

r~A*{`)]:~~Y*-_9>}g

Experimente on-line ou Enquanto versão nº 1:

r~{_9>}{`)]:~~Y*-}w

Experimente online ou Enquanto a versão 2:

r~{_9>}{_A/\A%Y*-}w

Experimente online .

r~                     | Read and convert input
  A*                   | Multiply by 10 to get around "if" rule
     `                 | Stringify
      )                | Split last character off
       ]               | Convert stack to array
        :~             | Foreach in array convert to value
          ~            | Dump array
           Y*          | Multiply by 2
             -         | Subtract
              _        | Duplicate
               9>      | Greater than 9?
    {            }g    | do-while

Oracle SQL 11.2, 116 bytes

WITH v(i)AS(SELECT:1 FROM DUAL UNION ALL SELECT TRUNC(i/10)-(i-TRUNC(i,-1))*2 FROM v WHERE i>70)SELECT MIN(i)FROM v;

Sem golfe

WITH v(i) AS
(
  SELECT :1 FROM DUAL
  UNION ALL
  SELECT TRUNC(i/10)-(i-TRUNC(i,-1))*2 FROM v WHERE i>70
)
SELECT MIN(i) FROM v;

Haskell, 157 192 184 184 167 159 147 138 + 5 bytes - 50% = 71,5 bytes

O (1) espaço, O (n) tempo, passagem única!

h d=d%mod d 10
d%r=(quot(r-d)10,r)
p![d]=d-p*10
p![d,e]=d#(e-p)
p!(d:e:f)|(b,a)<-quotRem(2*d)10,(q,r)<-h$e-a-p=(b+q)!(r:f)
m#0=m
m#n=n-2*m
(0!)

Use como 0![6,1,0,2]para aplicar a regra a 2016, ou seja, passe um número em forma de fluxo com o número menos significativo primeiro. Dessa maneira, ele passará o número dígito por dígito, aplicando a regra com complexidade de espaço O (1).

O código não destruído está aqui:

import Data.Char

{- sub a b = sub2 0 a b
  where
    sub2 borrow (a:as) (b:bs) = res : sub2 borrow2 as bs
      where
        (borrow2, res) = subDig borrow a b
    sub2 borrow (a:as) [] = sub2 borrow (a:as) (0:[])
    sub2 _ [] _ = [] -}

--subDig :: Int -> Int -> Int -> (Int, Int)
subDig borrow a b = subDig2 (a - b - borrow)
  where
    subDig2 d = subDig3 d (d `mod` 10)
    subDig3 d r = ((r-d) `quot` 10, r)

seven ds = seven2 0 ds
seven2 borrow (d:e:f:gs) = seven2 (b + borrow2) (res:f:gs)
  where
    (a, b) = double d
    (borrow2, res) = subDig borrow e a
seven2 borrow (d:e:[]) = finalApp d (e-borrow)
seven2 borrow (d:[]) = d - borrow*10

double d = ((2*d) `mod` 10, (2*d) `quot` 10)

finalApp m 0 = m
finalApp m n = n - 2*m

num2stream :: Int -> [Int]
num2stream = reverse . map digitToInt . show
sev = seven . num2stream

A essência de como isso funciona é que ele implementa um algoritmo de subtração dígito por dígito , mas tira proveito do fato de que cada número a ser subtraído tem no máximo 2 dígitos e, portanto, podemos subtrair uma quantidade arbitrária desses números. ou números de 2 dígitos do principal (além de comer os dígitos menos significativos).

O algoritmo de subtração é O (1) e armazena apenas o valor atual de 'empréstimo'. Alterei isso para adicionar o dígito extra (0 ou 1), e notamos que esse valor de empréstimo é limitado (dentro do intervalo [-2,2], portanto, precisamos apenas de 3 bits para armazenar isso).

Os outros valores armazenados na memória são variáveis ​​temporárias que representam o número atual de 2 dígitos a ser adicionado, uma única olhada no fluxo e a aplicação de uma etapa do algoritmo de subtração (ou seja, são necessários dois dígitos e um valor emprestado e retorna um dígito e um novo valor emprestado).

Finalmente, no final, processa os dois últimos dígitos no fluxo de uma só vez para retornar um número de um dígito em vez de uma lista de dígitos.

NB A sevfunção na versão não-golfada funcionará em um Integer, convertendo-a na forma de fluxo invertido.

GNU dc, 20 15 bytes

[10~2*-d70<F]sF

Isso define minha primeira (sempre) função dc F,. Ele recebe entrada no topo da pilha e deixa sua saída no topo da pilha. Exemplo de uso:

36893488147419103232
lFxp
32

Mathematica, 47 44 bytes

If[#>70,#0[{1,-2}.{⌊#/10⌋,#~Mod~10}],#]&

Abordagem recursiva simples. Provavelmente poderia ser jogado ainda mais.

R, 43 bytes

x=scan();while(x>70)x=floor(x/10)-x%%10*2;x

Explicação:

x=scan()                                      # Takes input as a double
        ;                                     # Next line
         while(x>70)                          # While-loop that runs as long x > 70
                      floor(x/10)             # Divide x by 10 and round that down
                                 -x%%10*2     # Substract twice the last integer
                    x=                        # Update x
                                         ;    # Next line once x <= 70
                                          x   # Print x

Amostras de execuções:

> x=scan();while(x>70)x=floor(x/10)-x%%10*2;x
1: 9999
2: 
Read 1 item
[1] -3

> x=scan();while(x>70)x=floor(x/10)-x%%10*2;x
1: 32767
2: 
Read 1 item
[1] 28

JavaScript ES6, 38 bytes

a=i=>i>70?a(Math.floor(i/10)-i%10*2):i

Falha com 36893488147419103232e usando~~(1/10) também falhará700168844221

Teste:

a=i=>i>70?a(Math.floor(i/10)-i%10*2):i
O.textContent = O.textContent.replace(/(-?\d+) +(-?\d+)/g, (_,i,o) =>
  _+": "+(a(+i)==o?"OK":"Fail")
);

<pre id=O>1                       1
10                      10
100                     10
13                      13
42                      42
2016                    0
9                       9
99                      -9
9999                    -3
12345                   3
700168844221            70
36893488147419103232    32</pre>

Mathematica, 33 bytes

#//.a_/;a>70:>⌊a/10⌋-2a~Mod~10&

Caso de teste

%[9999]
(* -3 *)

Perl 5, 47 46 bytes

Teve que usar bigintpara o último caso de teste. (Retorna 20 sem)

use bigint;$_=<>;while($_>9){$_-=2*chop;}print

Não tenho certeza se é um candidato ao bônus, então não o levei em consideração. (Acho que sim, mas não estou realmente acostumado aos conceitos)

Experimente aqui!

ES6, 108 bytes

f=(s,n=0)=>s>1e9?f(s.slice(0,-1),((1+s.slice(-1)-n%10)%10*21+n-s.slice(-1))/10):s>9?f(((s-=n)-s%10*21)/10):s

Funciona para 2²⁵⁷ e 1000000000000000000001001, mas pode usar mais golfe.

JavaScript ES6, 140 142 bytes

f=s=>s>9?eval("t=s.replace(/.$/,'-$&*2');for(i=-1;0>(n=eval(u=t[c='slice'](i-4)))&&u!=t;i--);n<0?n:f(t[c](0,i-4)+('0'.repeat(-i)+n)[c](i))"):s

Essa é a verdadeira matemática de precisão arbitrária, funciona até no maior caso de teste.

Essa função remove recursivamente o último dígito da sequência e subtrai 2 * o último dígito da sequência numérica restante, incrementando iterativamente a quantidade de dígitos a serem aplicados ao minuendo até que a diferença seja positiva. Em seguida, acrescenta essa diferença ao final da string com se preenchido adequadamente 0e se chama recursivamente até que seu valor numérico seja menor ou igual a 9.

• Joguei 7 bytes graças ao @Neil (sim, eu sei que ganhei 2 bytes, mas corrigi alguns bugs que faziam com que a função congelasse ou retornasse uma saída incorreta em alguns casos).

f=s=>s>9?eval("t=s.replace(/.$/,'-$&*2');for(i=-1;0>(n=eval(u=t[c='slice'](i-4)))&&u!=t;i--);n<0?n:f(t[c](0,i-4)+('0'.repeat(-i)+n)[c](i))"):s;[['1',1],['10',1],['100',1],['13',-5],['42',0],['2016',0],['9',9],['99',-9],['9999',-3],['12345',3],['700168844221',7],['36893488147419103232',-1],['231584178474632390847141970017375815706539969331281128078915168015826259279872',8]].map(a=>document.write(`<pre>${f(a[0])==a[1]?'PASS':'FAIL'} ${a[0]}=>${a[1]}</pre>`))

C #, 111 104 bytes

int d(int n){var s=""+n;return n<71?n:d(int.Parse(s.Remove(s.Length-1))-int.Parse(""+s[s.Length-1])*2);}

Brain-Flak , 368 360 bytes

Experimente Online!

([([({})]<(())>)](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}({}<>){{}(({}))(<((()()()()()){}<>)>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>([([([(({}<{}><>)<([{}]{})(<((()()()()()){}(<>))>)<>{({}[()])<>(({}()[({}<({}())>)])){{}(<({}({}<({}[()])>))>)}{}<>}{}<>{}{}({}<>)>){}]{})]<(())>)(<>)]){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}({}<>)}{}

Explicação

Para começar, todo o código está em um loop que é executado até que o topo da pilha seja menor que zero:

([([({})]<(())>)](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}({}<>)
{{}
 ...
 ([([({})]<(())>)](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}({}<>)
}{}

Dentro do loop, executamos o divisível por sete algoritmos:

Duplique a parte superior da pilha

(({}))

Pegue o mod 10 do topo da pilha (último dígito)

(<((()()()()()){}<>)>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>)

Isso é um pouco confuso, mas faz o resto do algoritmo que eu poderia explicar mais tarde, mas não me lembro completamente como ele funciona:

([(({})<([{}]{})(<((()()()()()){}(<>))>)<>{({}[()])<>(({}()[({}<({}())>)])){{}(<({}({}<({}[()])>))>)}{}<>}{}<>{}{}({}<>)>){}]{})

C, 56 bytes - 75% = 14

Embora isso não dê exatamente os mesmos números que os casos de teste, satisfaz o espírito da pergunta (e sem dúvida mais). Ele identifica corretamente os múltiplos exatos de 7 e fornece o restante exato para outros números (já que nunca usa números negativos).

n;f(char*c){for(n=0;*c;)n-=n>6?7:'0'-n-n-*c++;return n;}

Não há multiplicação ou divisão no algoritmo, apenas adição e subtração, e os dígitos são processados ​​em uma única passagem da esquerda para a direita. Funciona da seguinte forma, começando com 0 no acumulador:

1. Subtraia 7 se necessário e novamente se ainda necessário
2. Multiplique o total atual por três e adicione o próximo dígito

A etapa "multiplicar por três" é escrita n-=-n-npara salvar um byte e evitar o operador de multiplicação.

Quando chegamos ao final, não subtraímos setes, portanto o resultado estará no intervalo de 0 a 24; se você quiser um módulo estrito (0-7), substitua *cpor *c||n>6nofor condição de loop.

Ele se qualifica para o bônus aprimorado, porque

• suporta números inteiros de precisão arbitrária
• executa apenas uma passagem na entrada, da esquerda para a direita
• possui complexidade de espaço O (1)
• possui complexidade de tempo O (n).

Programa de teste e resultados

#include <stdio.h>
int main(int argc, char **argv) {
    while (*++argv)
        printf("%s -> %d\n", *argv, f(*argv));
    return 0;
}

540 -> 15
541 -> 16
542 -> 17
543 -> 18
544 -> 19
545 -> 20
546 -> 21
547 -> 22
548 -> 23
549 -> 24
550 -> 18
99 -> 15
999 -> 12
12345 -> 11
32767 -> 7
700168844221 -> 7
36893488147419103232 -> 11
231584178474632390847141970017375815706539969331281128078915168015826259279872 -> 11

Versão alternativa

Aqui está um que se repete (você desejará permitir que as otimizações do compilador façam a transformação da chamada de cauda ou poderá sobrecarregar sua pilha; eu usei gcc -std=c89 -O3):

f(c,n)char*c;{return n>6?f(c,n-7):*c?f(c+1,n+n+n+*c-'0'):n;}

Chame-o com '0' como o segundo argumento.

Ambas as versões calculam o módulo restante sete de um número de 60.000 dígitos em menos de 50 milissegundos na minha máquina.

PHP, 50 bytes

for($n=$argv[1];$n>9;)$n=$n/10|0-2*($n%10);echo$n;

usa saída alternativa; trabalha atéPHP_INT_MAX

versão string, funciona para qualquer número (positivo) (64 bytes):

for($n=$argv[1];$n>9;)$n=substr($n,0,-1)-2*substr($n,-1);echo$n;

Java, 133 bytes

int d(int n){String s=""+n;return n<71?n:d(Integer.parseInt(s.replaceFirst(".$",""))-Integer.parseInt(""+s.charAt(s.length()-1))*2);}

Eu odeio o quão detalhado Integer.parseInté. Ungolfed:

static int div(int n) {
    if (n <= 70) {
        return n;
    } else {
        String num = ("" + n);
        int last = Integer.parseInt("" + num.charAt(num.length() - 1));
        int k = Integer.parseInt(num.replaceFirst(".$", "")) - last * 2;
        return div(k);
    }
}