Números x tais que x ^ 2 divide 7 ^ x-1

16

Tarefa

Há um conjunto de números x, que x^2divide 7^x-1.

Sua tarefa é encontrar esses números. Dada a entrada n, o código imprimirá o enésimo número que segue esta regra.

Exemplos 1-index

In   Out
3    3
9    24
31   1140

A sequência relevante pode ser encontrada aqui .

Regras

A resposta mais curta será o vencedor *

Aplicam-se regras de golfe padrão

Não são permitidas brechas

Sua resposta pode ser 0 ou 1 indexada, indique na sua resposta

George
fonte
@ nimi Escrevi isso no planejamento e nunca os implementei. Eu atualizei a pergunta
george
Quais são os limites n? Posso dar o resultado correto com n=9, mas n=10já está me causando problemas.
Briantist
@ briantist Se você está obtendo o resultado errado para valores de entrada mais altos, sua resposta está errada. Se estiver demorando muito, isso pode depender da implementação.
precisa saber é o seguinte
Não está demorando muito tempo. n=10me dá 32; é porque ele começa a usar o dobro em vez de números inteiros e o mod está errado depois disso. :(
briantist 19/01

Respostas:

8

Haskell, 34 bytes

([x|x<-[1..],mod(7^x-1)(x^2)<1]!!)

Isso usa indexação baseada em 0. Exemplo de uso: ([x|x<-[1..],mod(7^x-1)(x^2)<1]!!) 30-> 1140.

É uma implementação direta da definição. Ele cria uma lista de todos os números xe escolhe o nth.

nimi
fonte
5

Pitão , 10 bytes

e.f!%t^7Z*

Um programa que recebe a entrada de um número inteiro e imprime um valor indexado um.

Experimente online!

Como funciona

e.f!%t^7Z*     Program. Input: Q
e.f!%t^7Z*ZZQ  Implicit variable fill
               Implicitly print
e              the last
 .f         Q  of the first Q positive integers Z
     t^7Z      for which 7^Z - 1
    %          mod
         *ZZ   Z^2
   !           is zero
TheBikingViking
fonte
5

JavaScript (ES7), 40 bytes

f=(n,i=1)=>n?f(n-!((7**++i-1)%i**2),i):i

Isso perde a precisão rapidamente, devido ao fato de o JS perder a precisão 7**19. Aqui está uma versão ES6 de precisão quase arbitrária:

f=(n,i=0)=>n?f(n-!(~-(s=++i*i,g=j=>j?g(j-1)*7%s:1)(i)%s),i):i

Isso termina em cerca de um segundo para o caso de teste 31.

Algumas abordagens mais longas:

f=(n,i=0)=>n?f(n-!(~-(s=>g=j=>j?g(j-1)*7%s:1)(++i*i)(i)%s),i):i
f=(n,i=0)=>n?f(n-!(s=++i*i,g=(j,n=1)=>j?g(j-1,n*7%s):~-n%s)(i),i):i
f=(n,i=0)=>n?f(n-!(s=>g=(j,n=1)=>j?g(j-1,n*7%s):~-n%s)(++i*i)(i),i):i
ETHproductions
fonte
4

05AB1E , 11 bytes

µ7Nm<NnÖiN¼

Experimente online!

Por alguma razão, não consigo ½trabalhar µ7Nm<NnÖ½Nou ficaria amarrado com Pyth.

µ           # Loop until the counter equals n.
 7Nm<       # Calc 7^x+1.
     Nn     # Calc x^2.
       Ö    # Check divisibility.
        iN¼ # If divisible, push current x and increment counter.
            # Implicit loop end.
            # Implicitly return top of stack (x)

.

Urna de polvo mágico
fonte
Sim, eu tive essa mania Öna minha lista de consertos por meses, mas nunca chego a lidar com isso. De qualquer forma, você não precisa o Nquanto µemite automaticamente o último N, se a pilha está vazia.
Emigna
4

Python 2 , 48 46 bytes

Obrigado a @Dennis por -2 bytes!

f=lambda n,i=1:n and-~f(n-(~-7**i%i**2<1),i+1)

Uma função recursiva de um índice que recebe entrada por meio de argumento e retorna o resultado.

Experimente online! (Limite de recursão aumentado para permitir a execução do caso de teste final)

Como funciona

né o índice desejado e ié a variável de contagem.

A expressão ~-7**i%i**2<1retorna True(equivalente a 1) se i^2divide 7^i - 1e False(equivalente a 0) caso contrário. Cada vez que a função é chamada, o resultado da expressão é subtraído de n, diminuindo ncada vez que um hit é encontrado; itambém é incrementado.

O comportamento-circuito curto de andmeios que, quando né 0, 0é devolvido; este é o caso base. Quando isso é alcançado, a recursão para e o valor atual de ié retornado pela chamada de função original. Em vez de usar explicitamente i, isso é feito usando o fato de que para cada chamada de função, um incremento foi realizado usando o -~na frente da chamada; 0 itempos incrementais fornecem i, conforme necessário.

TheBikingViking
fonte
1
(~-7**i%i**2<1)salva alguns bytes.
Dennis
@Dennis Claro! Obrigado.
TheBikingViking
3

Python 2 , 57 53 51 bytes

-4 bytes graças a ETHproductions
-2 bytes graças a TuukkaX

i=0
g=input()
while g:i+=1;g-=~-7**i%i**2<1
print i

Experimente online!
a sequência é indexada em 1

Cajado
fonte
@ETHproductions yep c:
Rod
Um testcase falha se você remover os parênteses (7**i)? Eu os removi e funcionou para os que tentei.
Yytsi 20/01
@TuukkaX de fato, **tem uma precedência mais alta do que ~e #-
Rod
2

Python 2, 57 bytes

Isso leva um realmente, realmente muito tempo para grandes valores. Ele também usa muita memória, porque cria a lista inteira muito mais longe do que o necessário. O resultado é indexado a zero.

lambda n:[x for x in range(1,2**n+1)if(7**x-1)%x**2<1][n]

Experimente online

mbomb007
fonte
por curiosidade, há alguma prova para o 2**n+1limite máximo?
Rod
@ Rod Não que eu saiba, mas considerando que existem 50 valores <5000, tenho certeza que há muito mais que 50 < 2**50. Eu poderia usar 9**n+9, mas leva muito mais tempo. Comecei a correr f(20)há um tempo atrás (com 2**n+1); ainda não foi concluído.
precisa saber é o seguinte
Eu nem acho que há uma prova de que a sequência é infinita, sem falar em um belo limite superior para o enésimo termo!
Greg Martin
2

Mathematica, 43 bytes

Atualmente, tenho três soluções diferentes nessa contagem de bytes:

Nest[#+1//.x_/;!(x^2∣(7^x-1)):>x+1&,0,#]&
Nest[#+1//.x_/;Mod[7^x-1,x^2]>0:>x+1&,0,#]&
Nest[#+1//.x_:>x+Sign@Mod[7^x-1,x^2]&,0,#]&
Martin Ender
fonte
Qual é o caráter entre x ^ 2 e (7 ^ x ... na primeira linha Parece que um tubo, mas mais curto?
Sefa
@Sefa É o caractere Unicode do símbolo matemático "divide" e é usado pelo Mathematica como um operador Divisible.
Martin Ender
Aqui está um em 41 bytes: com Cases[Range[#^3],x_/;x^2∣(7^x-1)][[#]]&base no argumento heurístico de que n ^ 3 é um limite superior. Eu descobri uma prova verdadeiramente maravilhosa disto, mas esta margem é muito estreita para conter :)
Kelly Lowder
2

PARI / GP , 42 bytes

Bem direto. Indexado em 1, embora isso possa ser facilmente alterado.

n->=k=1;while(n--,while((7^k++-1)%k^2,));k

ou

n->=k=1;for(i=2,n,while((7^k++-1)%k^2,));k
Charles
fonte
1

Python 3 , 45 bytes

f=lambda n,k=2:n<2or-~f(n-(7**k%k**2==1),k+1)

Retorne True para a entrada 1 , que é permitida por padrão .

Experimente online!

Dennis
fonte
Não posso testar isso no momento, mas presumo que ele retorne um valor para outras entradas? Em vez de um bool?
george
1

R, 35 bytes

Isso só funciona para n<=8.

z=1:20;which(!(7^z-1)%%z^2)[scan()]

No entanto, aqui está uma versão mais longa que funciona n<=25para 50 bytes :

z=1:1e6;which(gmp::as.bigz(7^z-1)%%z^2==0)[scan()]
rturnbull
fonte
Isso funciona apenas 8porque se torna um int longo?
george
1
@george Sim, você perde a precisão, pois o padrão é R para números inteiros de 32 bits. A segunda versão do código usa um pacote gmp, que permite números inteiros arbitrariamente grandes. No entanto, fiquei rapidamente sem memória RAM para calcular qualquer coisa acima n=25.
precisa saber é o seguinte
0

PHP, 47 49 bytes

while($n<$argv[1])$n+=(7**++$x-1)%$x**2<1;echo$x;

Funciona apenas para n <9 ( 7**9é maior que PHP_INT_MAXcom 64 bits)

62 bytes usando números inteiros de comprimento arbitrário: (não testado; o PHP na minha máquina não tem bcmath)

for($x=$n=1;$n<$argv[1];)$n+=bcpowmod(7,++$x,$x**2)==1;echo$x;

Corra com php -nr '<code>' <n>.

pseudo-código

implicit: $x = 0, $n = 0
while $n < first command line argument
    increment $x
    if equation is satisfied
        increment $n
print $x
Titus
fonte
0

Pyke, 10 bytes

~1IX7i^tR%

Experimente aqui!

~1         -  infinite(1)
  IX7i^tR% - filter(^, not V)
    7i^    -    7**i
       t   -   ^-1
        R% -  ^ % v
   X       -   i**2
           - implicit: print nth value
Azul
fonte
0

Clojure , 83 bytes

(fn[n](nth(filter #(= 0(rem(-(reduce *(repeat % 7N))1)(* % %)))(iterate inc 1N))n))

Experimente online!

Isso cria uma lista infinita de Java BigIntegers iniciando em 1 e os filtra pela definição. Ele usa indexação baseada em zero para selecionar o n º valor da lista filtrada.

milhas
fonte
0

Perl 5, 35 bytes

Bem, isso estava faltando, então aqui está:

map{$_ if!((7**$_-1)%($_**2))}1..<>

ChatterOne
fonte
0

PowerShell, muitos bytes

Só para ver se era possível e é.

[System.Linq.Enumerable]::Range(1,10000)|?{[System.Numerics.BigInteger]::Remainder([System.Numerics.BigInteger]::Pow(7,$_)-1,$_*$_) -eq 0}
Jessica
fonte
0

Perl 6 , 35 34 bytes

{grep({(7**$_-1)%%$_²},^∞)[$_]}

Indexado a 0.

Raspou um byte graças a Brad Gilbert.

Sean
fonte
O grep é uma sub-rotina, para que você possa remover o espaço se colocar os parênteses depois dele{grep(…)}
Brad Gilbert b2gills
0

QBIC , 39 bytes

:{~(7^q-1)%(q^2)=0|b=b+1]~b=a|_Xq\q=q+1

Não consegui executá-lo no QBasic 4.5, mas parece funcionar bem no QB64. Por alguma razão inexplicável, o QBasic se recusa a dividir corretamente 13.841.287.200 por 144, mas fornece um restante de -128. Em seguida, retorna 16 como o 7º termo desta sequência em vez de 12 ...

:{      get N from the command line, start an infinite DO-loop
~       IF
(7^q-1) Part 1 of the formula (Note that 'q' is set to 1 as QBIC starts)
%       Modulus
(q^2)   The second part
=0      has no remainder
|b=b+1  Then, register a 'hit'
]       END IF
~b=a    If we have scored N hits
|_Xq    Quit, printing the last used number (q)
\q=q+1  Else, increase q by 1. 
        [DO-loop and last IF are implicitly closed by QBIC]
steenbergh
fonte
0

Maravilha , 28 bytes

@:^#0(!>@! % - ^7#0 1^#0 2)N

Indexado a zero. Uso:

(@:^#0(!>@! % - ^7#0 1^#0 2)N)2

Filtra da lista de números naturais com um predicado que determina se x^2é divisível por e 7^x-1, em seguida, obtém o enésimo item nessa lista.

Mama Fun Roll
fonte
0

Tcl , 73 bytes

while {[incr i]} {if 0==(7**$i-1)%$i**2 {incr j;if $j==$n break}}
puts $i

Experimente online!

sergiol
fonte