Um número de Proth , nomeado após François Proth, é um número que pode ser expresso como

N = k * 2^n + 1

Onde ké um número inteiro positivo ímpar e né um número inteiro positivo tal que 2^n > k. Vamos usar um exemplo mais concreto. A Tomada 3. 3 é um número de Proth porque pode ser escrito como

(1 * 2^1) + 1

e 2^1 > 1está satisfeito. 5 Também é um número de Proth porque pode ser escrito como

(1 * 2^2) + 1

e 2^2 > 1está satisfeito. No entanto, 7 não é um número de Proth porque a única maneira de escrevê-lo no formulário N = k * 2^n + 1é

(3 * 2^1) + 1

e 2^1 > 3não está satisfeito.

Seu desafio é bastante simples: você deve escrever um programa ou função que, dado um número inteiro positivo, determine se é ou não um número Proth. Você pode receber entradas em qualquer formato razoável e deve gerar um valor verdadeiro, se for um número Proth, e um valor falso, se não for. Se o seu idioma tiver funções de "detecção de número de próstata", você poderá usá-las.

Teste de E / S

Aqui estão os primeiros 46 números Proth de até 1000. ( A080075 )

3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 289, 321, 353, 385, 417, 449, 481, 513, 545, 577, 609, 641, 673, 705, 737, 769, 801, 833, 865, 897, 929, 961, 993

Qualquer outra entrada válida deve fornecer um valor falso.

Como de costume, isso é código-golfe, então as brechas padrão se aplicam e a resposta mais curta em bytes vence!

Teoria dos números - nota de lado divertida:

O maior primo conhecido que não é um primo de Mersenne é o 19249 * 2^13018586 + 1que, por acaso, também é um número de Proth!

Gelatina , 5 bytes

’&C²>

Experimente online! ou verifique todos os casos de teste .

fundo

Seja j um número inteiro estritamente positivo. j + 1 alterna todos os bits finais de j e o bit não definido adjacente. Por exemplo, 10011 ₂ + 1 = 10100 ₂ .

Como ~ j = - (j + 1) = -j - 1 , -j = ~ j + 1 , então -n aplica o acima ao NOT bit a bit de j (que alterna todos os bits), alternando todos os bits antes do último 1 .

Ao pegar j & -j - AND bit a bit de j e -j - todos os bits antes e depois do último bit definido são anulados (desde que desiguais em j e -j ), produzindo assim a potência mais alta de 2 que divide j uniformemente.

Para a entrada N , queremos aplicar o acima a N-1 para encontrar 2 ⁿ , a potência mais alta de 2 que divide N-1 . Se m = N - 1 , -m = - (N - 1) = 1 - N , então (N - 1) & (1 - N) produz 2 ⁿ .

Tudo o que resta a testar é se 2 ⁿ > k . Se k> 0 , isto é verdadeiro se e só se (2 ^N ) ² > K2 ⁿ , o que é verdade em si, se e somente se (2 ^N ) ² ≥ K2 ⁿ + 1 = N .

Finalmente, se (2 ⁿ ) ² = N = k2 ⁿ + 1 , 2 ⁿ deve ser ímpar ( 1 ) para que as paridades de ambos os lados possam corresponder, implicando que k = 0 e N = 1 . Neste caso (N - 1) & (1 - N) = 0 & 0 = 0 e ((N - 1) & (1 - N)) ² = 0 <1 = N .

Portanto, ((N - 1) e (1 - N)) ² > N é verdadeiro se e somente se N for um número Proth.

Como funciona

’&C²>  Main link. Argument: N

’      Decrement; yield N - 1.
  C    Complement; yield 1 - N.
 &     Take the bitwise AND of both results.
   ²   Square the bitwise AND.
    >  Compare the square to N.

Python, 22 bytes

lambda N:N-1&1-N>N**.5

Esta é uma porta da minha resposta Jelly . Teste em Ideone .

Como funciona

Seja j um número inteiro estritamente positivo. j + 1 alterna todos os bits finais de j e o bit não definido adjacente. Por exemplo, 10011 ₂ + 1 = 10100 ₂ .

Como ~ j = - (j + 1) = -j - 1 , -j = ~ j + 1 , então -n aplica o acima ao NOT bit a bit de j (que alterna todos os bits), alternando todos os bits antes do último 1 .

Ao pegar j & -j - AND bit a bit de j e -j - todos os bits antes e depois do último bit definido são anulados (desde que desiguais em j e -j ), produzindo assim a potência mais alta de 2 que divide j uniformemente.

Para a entrada N , queremos aplicar o acima a N-1 para encontrar 2 ⁿ , a potência mais alta de 2 que divide N-1 . Se m = N - 1 , -m = - (N - 1) = 1 - N , então (N - 1) & (1 - N) produz 2 ⁿ .

Tudo o que resta a testar é se 2 ⁿ > k . Se k> 0 , isto é verdadeiro se e só se (2 ^N ) ² > K2 ⁿ , o que é verdade em si, se e somente se (2 ^N ) ² ≥ K2 ⁿ + 1 = N .

Finalmente, se (2 ⁿ ) ² = N = k2 ⁿ + 1 , 2 ⁿ deve ser ímpar ( 1 ) para que as paridades de ambos os lados possam corresponder, implicando que k = 0 e N = 1 . Neste caso (N - 1) & (1 - N) = 0 & 0 = 0 e ((N - 1) & (1 - N)) ² = 0 <1 = N .

Portanto, ((N - 1) e (1 - N)) ² > N é verdadeiro se e somente se N for um número Proth.

Ignorando imprecisões de ponto flutuante, isso é equivalente ao código N-1&1-N>N**.5na implementação.

Python 2, 23 bytes

lambda n:(~-n&1-n)**2>n

Mathematica, 50 48 45 40 38 35 31 29 bytes

O Mathematica geralmente é péssimo quando se trata de código de golfe, mas às vezes há um recurso interno que faz as coisas parecerem realmente boas.

1<#<4^IntegerExponent[#-1,2]&

Um teste:

Reap[Do[If[f[i],Sow[i]],{i,1,1000}]][[2,1]]

{3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 289, 321, 353, 385, 417, 449, 481, 513, 545, 577, 609, 641, 673, 705, 737, 769, 801, 833, 865, 897, 929, 961, 993}

Edit: Na verdade, se eu roubar a idéia AND de bit a bit de Dennis , posso reduzi-lo para 23 22 20 bytes.

Mathematica, 23 22 20 bytes (obrigado A Simmons )

BitAnd[#-1,1-#]^2>#&

05AB1E , 14 10 bytes

Agradecimentos a Emigna por salvar 4 bytes!

Código:

<©Ó¬oD®s/›

Usa a codificação CP-1252 . Experimente online! .

Explicação:

Para a explicação, vamos usar o número 241 . Primeiro decrementamos o número por um com <. Isso resulta em 240 . Agora, calculamos os fatores primos (com duplicatas) usando Ò. Os principais fatores são:

[2, 2, 2, 2, 3, 5]

Nós os dividimos em duas partes. Usando 2Q·0K, obtemos a lista de dois:

[2, 2, 2, 2]

Com ®2K, obtemos a lista dos números restantes:

[3, 5]

Finalmente, pegue o produto de ambos. [2, 2, 2, 2]resulta em 16 . O produto dos [3, 5]resultados em 15 .

Este caso de teste é verdadeiro desde 16 > 15 .

Brain-Flak , 460 350 270 266 264 188 176 bytes

Experimente online!

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

Explicação

O programa passa por potências de dois e quatro até encontrar uma potência de dois maior que N-1. Quando encontra, verifica a divisibilidade de N-1 pela potência de dois usando o módulo e gera o resultado

({}[()])      #Subtract one from input
(((<>())))    #Put three ones on the other stack
{
 {}           #Pop the crap off the top
 ([(
  ((({}<(({}){})>){}){}) #Multiply the top by four and the bottom by two
  <>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{} #Check if the power of four is greater than N-1
}
(<{}{}>) #Remove the power of 4
<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>) #Modulo N-1 by the power of two

Este programa não está limpo de pilha. Se você adicionar 4 bytes extras, poderá fazer com que a pilha fique limpa:

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

MATL , 9 bytes

qtYF1)EW<

A verdade é a saída 1. Falsy é 0ou saída vazia. (As únicas entradas que produzem saída vazia são 1e 2; o restante produz uma 0ou outra 1).

Experimente online!

Explicação

Deixe x denotar a entrada. Seja y a maior potência de 2 que divide x −1, e z = ( x −1) / y . Observe que z é automaticamente ímpar. Então x é um número Proth se e somente se y > z , ou equivalente se y ² > x −1.

q    % Input x implicitly. Subtract 1
t    % Duplicate
YF   % Exponents of prime factorization of x-1
1)   % First entry: exponent of 2. Errors for x equal to 1 or 2
E    % Duplicate
W    % 2 raised to that. This is y squared
<    % Is x-1 less than y squared? Implicitly display

Braquilog , 28 bytes

>N>0,2:N^P:K*+?,P>K:2%1,N:K=

Experimente online!

Verifique todos os casos de teste de uma só vez. (Ligeiramente modificado.)

Explicação

Brachylog, sendo um derivado do Prolog, é muito bom em provar coisas.

Aqui, provamos o seguinte:

>N>0,2:N^P:K*+?,P>K:2%1,N:K=

>N>0                           input > N > 0
     2:N^P                     2^N = P
         P:K*+?                P*K+1 = input
                P>K            P > K
                  K:2%1        K%2 = 1
                        N:K=   [N:K] has a solution

Haskell, 55 46 bytes

f x=length [x|k<-[1,3..x],n<-[1..x],k*2^n+1==x,2^n>k]>0

Edit: Graças a nimi, agora 46 bytes

f x=or[k*2^n+1==x|k<-[1,3..x],n<-[1..x],2^n>k]

ECMAScript Regex, 48 43 41 bytes

As expressões regulares de Neil e H.PWiz (ambas também com sabor ECMAScript) são bonitas por si só. Há outra maneira de fazê-lo, que por uma coincidência bastante elegante era 1 byte a mais do que o de Neil, e agora com o golfe sugerido por H.PWiz (obrigado!), É 1 byte a mais menos de H.PWiz de.

Aviso: apesar do tamanho pequeno desse regex, ele contém um grande spoiler . Eu recomendo aprender como resolver problemas matemáticos unários na expressão regular ECMAScript, descobrindo os insights matemáticos iniciais de forma independente. Foi uma jornada fascinante para mim, e não quero estragá-la para quem potencialmente queira experimentá-la, especialmente aqueles com interesse em teoria dos números. Consulte esta postagem anterior para obter uma lista de problemas recomendados consecutivamente identificados por spoilers para resolver um por um.

Portanto , não leia mais se não quiser que você estrague uma mágica avançada de expressões regulares unárias . Se você quiser tentar descobrir essa mágica, recomendo começar resolvendo alguns problemas no regex ECMAScript, conforme descrito no post acima.

Portanto, esse regex funciona de maneira bem simples: começa subtraindo um. Então encontra o maior fator ímpar, k . Em seguida, dividimos por k (usando o algoritmo de divisão explicado brevemente em um parágrafo com etiqueta de spoiler do meu número de referência do fatorial ). Sorrateiramente, fazemos uma afirmação simultânea de que o quociente resultante é maior que k . Se a divisão corresponder, temos um número Proth; se não, nós não.

Consegui eliminar 2 bytes desse regex (43 → 41) usando um truque encontrado por Grimy que pode reduzir ainda mais a divisão no caso de garantir que o quociente seja maior ou igual ao divisor.

^x(?=(x(xx)*)\1*$)((\1x*)(?=\1\4*$)x)\3*$

Experimente online!

 # Match Proth numbers in the domain ^x*$
 ^
 x                         # tail = tail - 1
 (?=(x(xx)*)\1*$)          # \1 = largest odd factor of tail
 
 # Calculate tail / \1, but require that the quotient, \3, be > \1
 # (and the quotient is implicitly a power of 2, because the divisor
 # is the largest odd factor).
 (                         # \3 = tail / \1, asserting that \3 > \1
     (\1x*)                # \4 = \3-1
     (?=\1\4*$)            # We can skip the test for divisibility by \1-1
                           # (and avoid capturing it) because we've already
                           # asserted that the quotient is larger than the
                           # divisor.
     x
 )
 \3*$
 

Julia, 16 bytes

!x=~-x&-~-x>x^.5

Créditos ao @Dennis pela resposta e algumas dicas de golfe!

R, 52 50 bytes

x=scan()-1;n=0;while(!x%%2){x=x/2;n=n+1};2^(2*n)>x

O programa começa dividindo N-1(chamado aqui Pe x) pelo 2maior tempo possível para encontrar a 2^nparte da equação, deixandok=(N-1)/2^n e depois calcular se ké ou não inferior a 2^n, usando o fato de que2^n>x/2^n <=> (2^n)²>x <=> 2^2n>x

Regex (ECMAScript), 40 38 bytes

-2 bytes graças ao Deadcode

^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$)

Experimente online!

Versão comentada:

# Subtract 1 from the input N
^x

# Assert N is even.
# Capture \1 = biggest power of 2 that divides N.
# Capture \2 = 2.
(?=((xx)+?)(\1\1)*$)

# Assert no odd number > \1 divides N
(?!(\1x\2*)\4*$)

J, 10 bytes

%:<<:AND-.

Baseado na solução bit a bit do @Dennis .

Recebe uma entrada n e retorna 1 se for o número Proth mais 0.

Uso

   f =: %:<<:AND-.
   f 16
0
   f 17
1
   (#~f"0) >: i. 100  NB. Filter the numbers [1, 100]
3 5 9 13 17 25 33 41 49 57 65 81 97

Explicação

%:<<:AND-.  Input: n
        -.  Complement. Compute 1-n
   <:       Decrement. Compute n-1
     AND    Bitwise-and between 1-n and n-1
%:          Square root of n
  <         Compare sqrt(n) < ((1-n) & (n-1))

Retina 0.8.2 , 47 bytes

\d+
$*
+`(1+)\1
$+0
01
1
+`.10(0*1)$
1$1
^10*1$

Experimente online! Explicação: Dado um número Proth$k · 2^n + 1$, você pode derivar dois novos números Proth $(2k±1) · 2^{n + 1} + 1$. Podemos executar isso ao contrário até obtermos um número Proth em que$k = 1$. Isso é facilmente realizado através da transformação da representação binária.

\d+
$*

Converta para unário.

+`(1+)\1
$+0
01
1

Converta em binário.

+`.10(0*1)$
1$1

Execute repetidamente a fórmula de geração Proth ao contrário.

^10*1$

Combine o caso base da fórmula de geração Proth.

Edit: Eu acho que é realmente possível combinar um número Proth diretamente contra um número unário com uma única regex. Atualmente, isso leva 47 bytes, 7 bytes a mais que o meu código Retina atual para verificar se um número unário é um número Proth:

^.(?=(.+?)(\1\1)*$)(?=((.*)\4.)\3*$).*(?!\1)\3$

Regex ECMAScript, 42 bytes

^x(?=(x(xx)*)\1*$)(?=(x+?)((\3\3)*$))\4\1x

Experimente online! (Usando Retina)

Subtraio 1 essencialmente, divido pelo maior número ímpar possível e k, em seguida, verifico se pelo menos k+1resta.

Acontece que minha expressão regular é muito semelhante à que Neil dá no final de sua resposta . Eu uso em x(xx)*vez de (x*)\2x. E eu uso um método mais curto para verificark < 2^n

Flak cerebral , 128 bytes

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

Experimente online!

Eu usei um algoritmo muito diferente do que a solução anterior Brain-Flak .

Basicamente, divido por 2 (arredondando para cima) até atingir um número par. Depois, apenas comparo o resultado da última divisão com os dois ao poder do número de vezes que dividi.

Explicação:

({
  # (n+1)/2 to the other stack, n mod 2 to this stack
  <{({}[()]<(([{}]())<>{})<>>)}{}>
  # if 1 (n was odd) jump to the other stack and count the one
  {{}(<>)}{}
#end and push the sum -1, with a one under it
}<>[(())])
#use the one to get a power of two
{([()]{}<(({}){})>)}{}
#compare the power of two with the remainder after all the divisions
([({}[{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

Maple, 100 bytes (incluindo espaços)

IsProth:=proc(X)local n:=0;local x:=X-1;while x mod 2<>1 do x:=x/2;n:=n+1;end do;is(2^n>x);end proc:

Espaçoso para facilitar a leitura:

IsProth := proc( X )
    local n := 0;
    local x := X - 1;
    while x mod 2 <> 1 do
        x := x / 2;
        n := n + 1;
    end do;
    is( 2^n > x );
end proc:

Mesma ideia que várias outras; divida X por 2 até X não ser mais divisível por 2 e verifique os critérios 2 ^ n> x.

Java 1.7, 49 43 bytes

Mais 6 bytes de poeira graças a @charlie.

boolean g(int p){return p--<(p&-p)*(p&-p);}

Tente! (ideona)

Duas maneiras, igualmente longas. Como na maioria das respostas aqui, os créditos vão para @Dennis, é claro, para a expressão.

Tomando a raiz do lado direito da expressão:

boolean f(int p){return(p-1&(1-p))>Math.sqrt(p);}

Aplicando potência de dois no lado esquerdo da expressão:

boolean g(int p){return Math.pow(p-1&(1-p),2)>p;}

Pode cortar um único byte se um valor numérico positivo tiver permissão para representar 'verdade' e um valor negativo 'falso':

double g(int p){return Math.pow(p-1&(1-p),2)-p;}

Infelizmente, por causa da 'Narrowing Primitive Conversion', não se pode simplesmente escrever isso em Java e obter resultados corretos:

((p - 1 & (1 - p))^2) > p;

E qualquer tentativa de ampliar 'p' levará a um erro de compilação, porque os operadores bit a bit não são suportados, isto é, flutuadores ou duplos :(

Hy , 37 bytes

(defn f[n](>(**(&(- n 1)(- 1 n))2)n))

Experimente online!

Porto da resposta de @Dennis.

C (gcc) , 29 30 bytes

z;f(x){return--x<(z=x&-x)*z;}

Experimente online!

Japonês , 12 10 9 bytes

É&1-U)>Uq

Experimente online!

A Geléia do Porto de Dennis responde novamente. - 1 graças a @Shaggy.

Cjam, 11 bytes

Como muitos de nós, pegando carona na excelente solução de Dennis:

qi_(_W*&2#<

Experimente online

C (137 bytes)

int P(int N){int x=1,n=0,k=1,e=1,P=0;for(;e;n++){for(x=1,k=1;x&&x<N;k+=2){x=2<<n;x=x>k?x*k+1:0;if(x>N&&k==1)e=0;}if(x==N)P=1;}return P;}

Só vim ler as respostas depois que eu tentei.

Considerando N=k*2^n+1com a condição de k<2^n( k=1,3,5..en=1,2,3..

Com n=1nós temos um kdisponível para testar. À medida que aumentamos, ntemos mais algunsk's para testar assim:

n = 1; k = 1

n = 2; k = 1 k = 3

n = 3; k = 1 k = 3 k = 5 k = 7

...

Iterando essas possibilidades, podemos ter certeza de que N não é um número de Prouth se, por um determinado nperíodo,k=1 número obtido for maior que N e nenhuma outra iteração corresponder.

Então, meu código basicamente "força bruta" para encontrar N.

Depois de ler as outras respostas e perceber que você pode fatorar N-1 com 2 para encontrar ne condicionar k<2^n, acho que meu código pode ser menor e mais eficiente usando esse método.

Valeu a tentativa!

Testou todos os números fornecidos e alguns números "não Prouth". A função retorna 1 se o número for um número Prouth e 0 se não for.

Javascript ES7, 16 bytes

x=>x--<(-x&x)**2

Porto da minha resposta Julia, que é um porto da resposta @ Dennis's Jelly.

Obrigado @Charlie por 2 bytes salvos!

C # (.NET Core) , 17 bytes

x=>x--<(x=x&-x)*x

Experimente online!

Porta da resposta C da MegaTom .

Tentei uma solução baseada em LINQ, mas isso foi bom demais.

tinta , 60 bytes

=p(n)
~n-=n>1
~temp x=1
-(k){n%2:{n<x}->->}
~x+=x
~n=n/2
->k

Experimente online!

Com base na resposta do @ DSkoog's Maple - não foi o primeiro do gênero a ser publicado, mas foi o primeiro do gênero que eu vi.

Ungolfed

= is_proth(number) =

/* It's easy to check if a number is one less than a Proth number.
   We take the number and divide it by 2 until we can't.
   Once we can't, we've found the smallest possible "k".
   If we also keep track of how many times we divided, we have our corresponding "2^n"
   All we have to do then is compare those
*/

~ number -= (number > 1)            // So, we first subtract one. Except this implementation won't ever halt for 0, so we don't subtract if the input is 1 (this is fine since the desired outputs for inputs 1 and 2 are the same)
~ temp power_of_two = 1             // We declare a variable to store our "2^n"
- (check)
  {
  - number % 2:                     // Once we can't divide by 2 anymore, we've found the smallest possible "k"
    {number < power_of_two}         // At that point, we print whether it's smaller than the "2^n" we found
    ->->                            // And then we return to where we were called from
  }

  ~ number = number / 2             // We keep dividing by 2 until we can't.
  ~ power_of_two += power_of_two    // and update our "2^n" as we go
-> check

Código da máquina x86, 15 bytes

4F 89 F8 F7 D8 21 F8 0F AF C0 39 C7 19 C0 C3

Esses bytes definem uma função que recebe o argumento de entrada (um número inteiro não assinado) no EDIregistro, seguindo a convenção de chamada padrão do System V para sistemas x86 e retorna o resultado no EAXregistro, como todos os as convenções de chamada x86.

Em mnemônicos montadores:

4F          dec   edi            ; input -= 1
89 F8       mov   eax, edi       ; \ temp
F7 D8       neg   eax            ; |      =
21 F8       and   eax, edi       ; /        (input & -input)
0F AF C0    imul  eax, eax       ; temp *= temp
39 C7       cmp   edi, eax       ; set CF if (input < temp)
19 C0       sbb   eax, eax       ; EAX = -CF
C3          ret                  ; return with result in EAX
                                 ;  (-1 for Proth number; 0 otherwise)

Experimente online!

É uma solução bastante direta - e conceitualmente semelhante à versão C da MegaTom . Na verdade, você pode escrever isso em C da seguinte maneira:

unsigned IsProthNumber(unsigned input)
{
    --input;
    unsigned temp  = (input & -input);
    temp          *= temp;
    return (input < temp) ? -1 : 0;
}

mas o código de máquina acima é mais eficiente do que o obtido em um compilador C, mesmo quando ele está configurado para otimizar o tamanho.

O único "truque" aqui está retornando -1 como um valor "verdade" e 0 como um valor "falso". Este truque permite o uso da SBBinstrução de 2 bytes em oposição à instrução de 3 bytes SETB.