Este número pode ser escrito no formato (3 ^ x) - 1?

41

Desafio:

Crie um programa que aceite um número inteiro positivo e verifique se ele pode ser gravado na forma de (3 ^ x) -1, onde X é outro número inteiro positivo .

Se puder, produza X

Se não puder, imprima -1 ou uma declaração falsa .

Exemplo de entradas / saídas

Entrada:

2

Como pode ser escrito como (3 ^ 1) - 1, produzimos x que é 1

Saída:

1

Entrada:

26

26 pode ser escrito como (3 ^ 3) - 1, então produzimos x (3)

Saída:

3

Entrada:

1024

1024 não pode ser escrito na forma de (3 ^ x) - 1, então produzimos -1

Saída:

-1

Isso é portanto, menos quantidade de bytes ganha


OEIS relacionado: A024023

P. Ktinos
fonte
4
Peço a saída X porque acredito que é mais desafiador dessa maneira. Simplesmente descobrir se é do formato 3 ^ x - 1 seria muito fácil para um desafio, na minha opinião.
P. Ktinos
2
A menos que seja uma declaração falsa na sua linguagem de programação, então não.
P. Ktinos
2
Posso desejar que o número seja inserido no ternário?
John Dvorak
2
ter que lidar com intergers não negativos faria 0 3^0-1 uma saída válida e, portanto, não utilizável como falsa,
Jasen
2
quem pensa em usar log()sua resposta deve confirmar que ela fornece a resposta correta 5quando 242 é inserida.
Jasen 07/01

Respostas:

23

Mathematica, 21 16 bytes

-1&@@Log[3,#+1]&

Faz uso da computação simbólica do Mathematica. Se #+1for uma potência de três, Log[3,#+1]calculará um resultado inteiro que é um valor atômico. Caso contrário, teremos o Log[#+1]/Log[3]que é. Como esse não é um valor atômico, é uma expressão sempre da forma head[val1,val2,...]. Neste caso, é realmente algo parecido Times[Power[Log[3], -1], Log[#+1]].

Distinguimos entre os dois casos, aplicando outra função ao resultado. O que a aplicação realmente faz é que ela substitua a headparte de uma expressão. Como os resultados inteiros são atômicos, a aplicação de qualquer função a eles não faz nada. Em particular f @@ atom == atom.

No entanto, no outro caso, a cabeça é substituída. A função que estamos usando é -1&uma função simples que ignora seus argumentos e retornos -1. Então, obtemos algo -1&[Power[Log[3], -1], Log[#+1]]em casos não inteiros, que são avaliados diretamente para -1. Invólucro especial via mágica.

Martin Ender
fonte
13

Python, 46 44 bytes

lambda x:max(n*(3**n-1==x)for n in range(x))

Experimente online!

Nesse caso, 0seria o valor falso. Obrigado a @ mbomb007 por apontar minha saída incorreta, bem como 2 bytes sem []economia.

nmjcman101
fonte
você pode reescrever como [n for n in range(x)if 3**n-1==x]para -4 bytes, lista vazia como Falsas
Rod
Corrigido, obrigado! @Rod então ele voltaria [n] em vez de n eu acho
nmjcman101
@ nmjcman101 que não deve ser um problema
Rod
@Rod eu prefiro aderir estritamente a especificação para agora
nmjcman101
@Rod Se for necessário gerar um número inteiro, você não poderá produzi-lo em uma lista, a menos que o OP permita especificamente.
mbomb007
13

Haskell, 35 bytes

f x=last(-1:[i|i<-[1..x],3^i-1==x])

Exemplo de uso: f 26-> 3.

nimi
fonte
PS: Experimente online! suporta Haskell! (Nice resposta btw!)
flawr
11

05AB1E , 7 bytes

3IÝm<¹k

Experimente online!

Explicação

3        # push 3 
 I       # push input
  Ý      # range [0 ... input]
   m     # 3^[0 ... input]
    <    # -1
     ¹k  # find index of input, return -1 if not found
Emigna
fonte
Aparentemente, 05AB1E é bom na conversão de base. Essa é realmente a melhor abordagem?
Jasen
11
@ Jasen: Minhas tentativas de conversão de base acabaram por mais tempo. Se existe uma maneira melhor do que isso, eu não estou vendo. Sinta-se livre para me provar que estou errado embora :)
Emigna
justo o suficiente, eu só li a descrição do idioma e, portanto, espera-se que uma solução de 5 bytes ...
Jasen
11
@ Jason <3zm©.ïi®é o mais próximo que eu não tenho usando intervalos como ele fez.
Magic Octopus Urn
11
3DÝms<k... deixa pra lá ... Não posso raspar mais um byte, poderia jurar que eu poderia.
Magic Octopus Urn
9

Gelatina , 5 bytes

R3*’i

Saídas x ou 0 (falsy).

Experimente online!

Como funciona

R3*’i  Main link. Argument: n

R      Range; yield [1, ..., n].
 3*    Map each k to 3**k.
   ’   Decrement the results.
    i  First index of n (0 if not found).
Dennis
fonte
6

Python 2, 41 bytes

f=lambda n,i=0:i*0**n or n%3/2*f(n/3,i+1)

Uma função recursiva que retorna 0para entradas não correspondentes. Divide a entrada repetidamente no piso por 3, contando o número de etapas em ique é gerado no final. Mas, se qualquer etapa produzir um valor nque não seja 2 módulo 0, o número não será de 3^i-1, portanto, a saída será multiplicada por 0.

xnor
fonte
6

Perl, 31 bytes

say grep{3**$_-1==$i}0..($i=<>)

Requer -Esinalizador para executar:

perl -E 'say grep{3**$_-1==$i}0..($i=<>)' <<< 26

Explicações:
grep{3**$_-1==$i}0..($i=<>)retorna uma lista dos elementos do intervalo 0..$_(ou seja, de 0 à entrada) que satisfazem o teste 3**$_-1==$i. Somente um elemento, no máximo, pode satisfazer esse teste; portanto, esta instrução retornará uma matriz de 0 ou 1 elemento. Em seguida, imprimimos esta lista: ou the Xou nothing (o que é falso).

dada
fonte
5

Pitão, 11 bytes

?-JjQ3 2ZlJ

Converte na base 3 e verifica a igualdade em [2, 2, ..., 2].

orlp
fonte
Você pode reduzir este por um byte com ?-2JjQ3ZlJ, uma vez <col> <num>e <num> <col>são intercambiáveis para -em Pyth.
precisa saber é
5

JavaScript (ES7), 38 36 34 bytes

f=(n,k=33)=>3**k-n-1&&--k?f(n,k):k

Ou apenas 30 29 bytes, se estiver OK sair com um erro na falha:

f=(n,k)=>~(n-3**k)?f(n,-~k):k

Teste

Arnauld
fonte
5

Java 8, 37 58 67 bytes

i->{String s=i.toString(i,3);return s.matches("2*")?s.length():-1;}

Este lambda se encaixa em uma Function<Integer, Integer>referência e usa o truque simples da base 3.

Desta vez, ele deve funcionar corretamente.


fonte
3
Isso não seria impresso apenas Verdadeiro ou Falso quando puder ser escrito no formato? Mas eu pedi para o expoente quando o resultado é verdadeiro
P. Ktinos
2
Isso é genial! +1 para uma abordagem muito inteligente
DJMcMayhem
Isso é inteligente ... eu acredito que você pode remover os parênteses e apenas fazê-lo i->. Além disso, se você usar icomo a Long, poderá usá-lo a.toString(...)(o ides fornecerá alguns avisos sobre o uso incorreto de funções estáticas, mas deverá compilar). No entanto, como OP disse, você precisa retornar o valor, não apenas True ou False.
FlipTack 6/01
Se o lambda estiver armazenado em um tipo de função diferente, o truque estático funcionará. Eu também fixei o valor de retorno. Eu devo ter perdido essa parte.
5

Processando, 60 56 bytes

void q(float n){n=log(n+1)/log(3);print(n>(int)n?-1:n);}

Saídas -1se falsas.

Explicação

void q(float n){              // n is input
  n=log(n+1)/log(3);          // finds X in 3^X+1=n as a float (here we'll storing that in n)
  print(n>(int)n?-1:n);       // checks if the float is greater than
                              // the number rounded down (by int casting)
                              // if it is greater, output -1
                              // otherwise output X
}

voidé 1 byte menor que o uso float, é por isso que essa função gera diretamente em vez de retornar um valor.

Solução alternativa

void z(float n){int c=0;for(++n;n>1;c++)n/=3;print(n==1?c:-1);}

por 63 bytes, mas acho que esse alt pode ser mais curto que a solução original. Eu estou trabalhando nisso.

Kritixi Lithos
fonte
@FlipTack Sim, eu sabia que não seria em Java. Eu apenas perguntei, pois não tinha certeza de que o Processing não havia adicionado algo nesse sentido. O "valor distinto" a ser usado foi -1, porém não 0. Ele foi alterado desde então; portanto, provavelmente vou limpar meus comentários sobre ele.
Geobits
Espere, então posso voltar 0agora?
Kritixi Lithos
Eu ainda diria que não. A pergunta fornece um valor inteiro alternativo para usar se for falso, mas 0nunca é falso no Java / Processing que eu conheço.
Geobits
I thougt Processamento era suposto ser menos versbose de Java
Pavel
@Pavel Mas eu não uso lambdas: /
Kritixi Lithos
4

Braquilog , 8 bytes

,3:.^-?,

Experimente online!

Emite o valor se true e false.se isso for impossível.

Explicação

Esta é uma transcrição direta da relação fornecida:

,     ,      (Disable implicit unification)
 3:.^        3^Output…
     -?              … - 1 = Input
Fatalizar
fonte
Você quase pode jogar até 7 bytes como +~^r~:3, mas infelizmente ~:não faz o que você espera (provavelmente porque :é uma sintaxe e não um builtin), e parece ser tratado de forma idêntica :.
@ ais523 Está correto, :é um símbolo de controle e ~funciona apenas em predicados.
Fatalize
3

Perl 6 ,  25  24 bytes

{first $_==3** *-1,0..$_}

Tente

{first $_==3***-1,0..$_}

Remover o espaço após o **trabalho, porque é mais longo que o outro operador de infixo que pode corresponder *.
Então, …***…é analisado em … ** * …vez de … * ** ….

Tente

Expandido:

{  # bare block lambda with implicit parameter 「$_」

  first
    $_ == 3 ** * - 1,   # WhateverCode lambda
    #          ^- current value

    0 .. $_             # a Range up-to (and including) the input

}
Brad Gilbert b2gills
fonte
3

R, 24 bytes

Uma abordagem diferente da resposta do plannapus e um byte mais curto!

match(scan(),3^(1:99)-1)

Gera todos os números inteiros de 3^1-1até 3^99-1e verifica se stdin corresponde. Nesse caso, ele retorna o índice no qual corresponde, o que é x. Caso contrário, retorna NAcomo valor falso.

Aliás, ele aceitará vários valores como entrada e testará todos eles, o que é um recurso interessante.

rturnbull
fonte
3

Prolog, 20 bytes

d(A,X):-A#=(3**X)-1.

Essa linguagem é legal como o inferno.

| ?- d(1024,X).

no
| ?- d(26,X).

X = 3

yes
| ?- d(2,X).

X = 1

yes
Nome McChange
fonte
2

05AB1E , 9 bytes

DÝ3sm<Q1k

Experimente online!

Imprime -1 por falsidade.

D         # Duplicate the input
 Ý3sm     # Push [0 .. input]^3 (e.g. [0^3, 1^3, 2^3, 4^3 ...])
     <    # subtract 1
      Q   # push a 1 everywhere that equals the input, and 0 everywhere else
       1k # push the index of the 1, or -1 if not found
          # implicit output
Riley
fonte
2

MATL , 8 bytes

3i:^qG=f

Isso gera o número, xse existir, ou, caso contrário, não gera nada, o que é falso.

Experimente online!

Explicação

3    % Push 3
i    % Input n
:    % Range: gives `[1 2 ... n]
^    % Power, element-wise. Gives [3^1 3^2 ... 3^n]
q    % Subtract 1, element-wise. Gives [3^1-1 3^2-1 ... 3^n-1]
=    % Test for equality. Contains 'true' at the position x, if any,
     % where 3^x-1 equals n
f    % Find. Gives index of the 'true' position, which ix x; or gives
     % an empty array if no such position exists. Implicitly display
Luis Mendo
fonte
2

Japonês , 11 bytes

o æ@U+1¥3pX

Experimente aqui .

Muito obrigado à ETHproductions por ajudar!

Oliver
fonte
2

Python 3, 74 66 64 bytes

-10 bytes graças a @ mbomb007, @FlipTack e @ nmjcman101

from math import*
def f(n):x=ceil(log(n,3));print((3**x-1==n)*x)
dfernan
fonte
Você pode colocar todo o seu código em uma linha e usá-lo from math import*. Também return n==3**x-1and x.
mbomb007
@ mbomb007 As funções têm permissão para imprimir o resultado STDOUT, para que você possa alterar esse retorno para uma impressão.
FlipTack
Se você apresentar isso como uma solução SageMath em vez de uma solução Python, poderá descartar a primeira linha completamente.
Federico Poloni
Juntamente com a outra redução para 65 bytes, você pode usar import mathe math.ceilpara um único byte. Também você pode ligar 3**x-1==n and xparax*(3**x-1==n)
nmjcman101
2

Ruby, 30 bytes

Retorna nil(um valor falso) se nenhum número foi encontrado. [Experimente online]

->n{(0..n).find{|i|3**i-1==n}}
Value Ink
fonte
2

C, 56 bytes

 n;f(a){n=0;for(a++;!(a%3)&&(a/=3);++n);return --a?-1:n;}

adicione um à entrada e, em seguida, divida-o repetidamente por três até encontrar o restante, se esse for alcançado, retorne a contagem de divisões else -1

Jasen
fonte
Salve um byte com em a%3<1vez de !(a%3). Mais um 0por falsidade.
Titus
Supondo que você esteja usando o GCC para compilar, você pode salvar um total de 10 (11) bytes: você não precisa inicializar n para zero se souber que chamará essa função apenas uma vez desde então, n será zero por padrão ( porque é global) - são 4 bytes a menos; Além disso, você não precisa da declaração de retorno, escrevendo a=--a?-1:n;para economizar 5 bytes. se uma função não nula não tiver retorno, ela usará apenas a última atribuição. Também o que @Titus disse.
Etaoin Shrdlu
11
Sugerir em a%3?0:(a/=3)vez de!(a%3)&&(a/=3)
ceilingcat 11/12
2

Utilitários Bash / Unix, 37 35 bytes

bc<<<`dc<<<3o$1p|grep ^2*$|wc -c`-1

Experimente online!

Usa dc para converter na base 3, verifica se a sequência resultante é todos os 2s, conta o número de caracteres (incluindo uma nova linha) e usa bc para subtrair 1.

Se o número na base 3 não for todos os 2s, o grep não produzirá nada (nem mesmo uma nova linha); portanto, a contagem de caracteres é 0 e a subtração de 1 resulta em -1.

Mitchell Spector
fonte
2

C compilado com Clang 3.8.1, 53 , 52 , 54 , 51 bytes

n;f(y){y++;for(n=0;y%3==0;y/=3)n++;return y^1?0:n;}

A @SteadyBox já postou uma solução em C, mas estou usando uma abordagem diferente.

@ Obrigado a Jasen por ajudar a salvar bytes.

Wade Tyler
fonte
11
sim, mas funciona? comparando carros alegóricos para a igualdade é muitas vezes uma receita para o fracasso inesperado (experimente grandes entradas)
Jasen
@ Jason Hmm, não tentei isso, mas em C logretorna, doubleentão talvez possa funcionar.
Wade Tyler
double é um tipo de valor de ponto flutuante, portanto o problema persiste.
Jasen 07/01
parece funcionar bem para 3 ^ 19, que provavelmente é grande o suficiente.
Jasen 07/01
@Jasen Ele não funciona para 3 ^ 10
Wade Tyler
2

C, 42 bytes, otimizado a partir de Wade Tyler

n;f(y){for(n=0;y%3>1;y/=3)n++;return!y*n;}

Experimentar

C, 37 bytes, sem return

n;f(y){for(n=0;y%3>1;y/=3)n++;n*=!y;}

Experimentar

né global, mas (I)MULsó pode ter seu operando dest em um registro; portanto, é necessário colocar EAX(a escolha usual) e mover para lá

JavaScript 6, 32 bytes

f=(y,n)=>y%3>1?f(y/3|0,-~n):!y*n
;[1,2,3,8,12,43046720].forEach(x=>console.log(f(x)))

Se o "falso" precisar ser o mesmo, 33 bytes:

f=(y,n)=>y%3>1?f(y/3|0,-~n):!y&&n
l4m2
fonte
2

Pyt , 10 9 bytes

←⁺3ĽĐĐƖ=*

Explicação:

←                Get input
 ⁺               Add one
  3Ľ             Log base 3
    ĐĐ           Triplicate top of stack
      Ɩ          Convert top of stack to integer
       =         Check for equality between top two on stack
        *        Multiply by log_3(input+1)


Salva um byte usando a função de incremento em vez de adicionar explicitamente 1

mudkip201
fonte
em que página de código são 9 bytes? (em UTF-8 é de 17 bytes)
Jasen
1

Python, 64 bytes

Saída Falsese o número não puder ser gravado nesse formato.

def f(n):L=[3**x-1for x in range(n)];print n in L and L.index(n)

Isso também funciona em 64 bytes e imprime uma string vazia como uma saída falsa:

def f(n):
 try:print[3**x-1for x in range(n)].index(n)
 except:0

Uma solução criativa para 65 bytes, com saída 0para falsy:

lambda n:-~",".join(`3**x-1`for x in range(n+1)).find(',%s,'%n)/2
mbomb007
fonte
Não gera xnem -1.
dfernan
O programa deve produzir em xvez de nno caso de uma correspondência.
dfernan
Não, ele deve gerar o número inteiro positivo que, quando substituído por X, você obtém a entrada. A questão refere-se a X como uma variável, não como uma string
P. Ktinos
@ P.Ktinos Corrigido.
mbomb007
1

Julia, 30 bytes

n->findfirst(n.==3.^(0:n)-1)-1

É uma função simples - cria um vetor que possui trueapenas na posição correspondente em 3^a-1, onde aé um vetor que contém números inteiros entre 0 e n. Ele encontra a "primeira" posição que é truee subtrai 1 (se for tudo false, a descoberta é avaliada como zero e retorna -1).

Como 0:ntem 0, em primeiro lugar, os subtrair 1 corrige para indexação e também permite que a -1resposta falsa.

Glen O
fonte
1

Pyth 8 bytes

xm^3dUQh

     UQ  # generate all values 1..Q (Q is the input)
 m^3d    # map 3^d over this ^ list
x      h # find the input+1 (hQ) in the result of the last command

Tente aqui

Cajado
fonte