¿Se puede escribir este número en formato (3 ^ x) - 1?

41

Reto:

Cree un programa que acepte un entero positivo y verifique si se puede escribir en forma de (3 ^ x) -1, donde X es otro entero positivo .

Si puede, salida X

Si no puede, envíe -1 o una declaración falsa .

Ejemplo de entradas / salidas

Entrada:

2

Se puede escribir como (3 ^ 1) - 1, por lo que sacamos x, que es 1

Salida:

1

Entrada:

26

26 se puede escribir como (3 ^ 3) - 1, por lo que sacamos x (3)

Salida:

3

Entrada:

1024

1024 no se puede escribir en forma de (3 ^ x) - 1, por lo que sacamos -1

Salida:

-1

Este es el por lo que gana la menor cantidad de bytes


OEIS relacionados: A024023

P. Ktinos
fuente
44
Pido la salida X porque creo que es más desafiante de esa manera. Simplemente encontrar si es de formato 3 ^ x - 1 sería demasiado fácil para un desafío, en mi opinión.
P. Ktinos
2
A menos que sea una declaración falsa en su lenguaje de programación, entonces no.
P. Ktinos
2
¿Puedo querer ingresar el número en ternario?
John Dvorak
2
tener que manejar números enteros no negativos haría 0 3^0-1 una salida válida y, por lo tanto, no se podría usar como falso,
Jasen
2
cualquiera que esté pensando en usar log()en su respuesta debe confirmar que da la respuesta correcta 5cuando se ingresa 242 .
Jasen

Respuestas:

23

Mathematica, 21 16 bytes

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

Hace uso de la computación simbólica de Mathematica. Si #+1es una potencia de tres Log[3,#+1], calculará un resultado entero que es un valor atómico. De lo contrario, nos pondremos Log[#+1]/Log[3]como están. Como este no es un valor atómico, es una expresión que siempre tiene la forma head[val1,val2,...]. En este caso, en realidad es algo así Times[Power[Log[3], -1], Log[#+1]].

Distinguimos entre los dos casos aplicando otra función al resultado. Lo que aplica realmente es que reemplaza la headparte de una expresión. Como los resultados enteros son atómicos, aplicarles cualquier función no hace nada. En particular f @@ atom == atom.

Sin embargo, en el otro caso, la cabeza se reemplaza. La función que estamos utilizando es -1&una función simple que ignora sus argumentos y devuelve -1. Entonces obtenemos algo -1&[Power[Log[3], -1], Log[#+1]]en casos no enteros, que se evalúa directamente en -1. Carcasa especial a través de la magia.

Martin Ender
fuente
13

Python, 46 44 bytes

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

Pruébalo en línea!

En este caso, 0sería el valor falso. Gracias a @ mbomb007 por señalar mi salida incorrecta, así como a 2 bytes sin []ahorro.

nmjcman101
fuente
puede reescribir como [n for n in range(x)if 3**n-1==x]-4 bytes, lista vacía como falso
Rod
Fijo, gracias! @ Rod entonces regresaría [n] en lugar de n, creo
nmjcman101
@ nmjcman101 eso no debería ser un problema
Rod
@ Rod Preferiría seguir estrictamente las especificaciones por ahora
nmjcman101
@Rod Si se requiere generar un número entero, no puede generarlo en una lista a menos que el OP lo permita específicamente.
mbomb007
13

Haskell, 35 bytes

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

Ejemplo de uso: f 26-> 3.

nimi
fuente
PD: ¡ Pruébalo en línea! apoya a Haskell! (¡Buena respuesta por cierto!)
error
11

05AB1E , 7 bytes

3IÝm<¹k

Pruébalo en línea!

Explicación

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
fuente
05AB1E es aparentemente bueno en la conversión de bases. ¿Es este realmente el mejor enfoque?
Jasen
1
@Jasen: Mis intentos de conversión de base fueron más largos. Si hay una mejor manera que esta, no la estoy viendo. No obstante
siéntete
bastante justo, solo he leído la descripción del lenguaje y, por lo tanto, esperaba ver una solución de 5 bytes ...
Jasen
1
@Jasen <3zm©.ïi®es lo más cerca que no estoy usando rangos como lo hizo.
Magic Octopus Urn
1
3DÝms<k... No importa ... No puedo afeitarme un byte más, podría haber jurado que podría.
Urna de pulpo mágico el
9

Jalea , 5 bytes

R3*’i

Salidas x o 0 (Falsy).

Pruébalo en línea!

Cómo 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
fuente
6

Python 2, 41 bytes

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

Una función recursiva que devuelve 0entradas no coincidentes. Repetidamente el piso divide la entrada por 3, contando el número de pasos i, que se emite al final. Pero, si algún paso produce un valor nque no es 2 módulo 0, el número no era para 3^i-1, por lo que la salida se multiplica por 0.

xnor
fuente
6

Perl, 31 bytes

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

Requiere -Ebandera para correr:

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

Explicaciones:
grep{3**$_-1==$i}0..($i=<>)devuelve una lista de los elementos del rango 0..$_(es decir, de 0 a la entrada) que satisface la prueba 3**$_-1==$i. Solo un elemento como máximo puede satisfacer esta prueba, por lo que esta instrucción devolverá una matriz de 0 o 1 elemento. Luego imprimimos esta lista: ya sea el Xo nada (lo cual es falso).

Dada
fuente
5

Pyth, 11 bytes

?-JjQ3 2ZlJ

Convierte a base 3 y comprueba la igualdad a [2, 2, ..., 2].

orlp
fuente
Puede reducir este por un byte con ?-2JjQ3ZlJ, puesto <col> <num>y <num> <col>son intercambiables para -en Pyth.
notjagan
5

JavaScript (ES7), 38 36 34 bytes

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

O solo 30 29 bytes si está bien salir con un error en caso de error:

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

Prueba

Arnauld
fuente
5

Java 8, 37 58 67 bytes

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

Este lambda encaja en una Function<Integer, Integer>referencia y utiliza el sencillo truco de base 3.

Esta vez debería funcionar correctamente.


fuente
3
¿No imprimiría eso solo verdadero o falso cuando se puede escribir en el formato? Pero pregunté por el exponente cuando el resultado es Verdadero
P. Ktinos
2
Eso es genial! +1 para un enfoque muy inteligente
DJMcMayhem
Esto es inteligente ... creo que puedes eliminar los parens y simplemente hacerlo i->. Además, si lo toma icomo un Long, puede usarlo a.toString(...)(ides dará algunas advertencias sobre el uso incorrecto de las funciones estáticas, pero debe compilarse). Sin embargo, como dijo OP, debe devolver el valor, no solo Verdadero o Falso.
FlipTack
Si el lambda se almacena en un tipo de función diferente, entonces el truco estático funciona. También arreglé el valor de retorno. Debo haber perdido esa parte.
5

Procesamiento, 60 56 bytes

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

Salidas -1si es falso.

Explicación

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
}

voides 1 byte más corto que el uso float, por eso esta función genera directamente en lugar de devolver un valor.

Solución alternativa

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

para 63 bytes, pero creo que este alt puede ser más corto que la solución original. Estoy trabajando en ello.

Kritixi Lithos
fuente
@FlipTack Sí, sabía que no estaría en Java. Solo pregunté porque no estaba seguro de que Processing no hubiera agregado algo en ese sentido. Sin embargo, el "valor distintivo" que se usó fue -1, no 0. Se ha cambiado desde entonces, por lo que probablemente limpiaré mis comentarios al respecto.
Geobits
Espera, ¿puedo volver 0ahora?
Kritixi Lithos
Todavía diría que no. La pregunta proporciona un valor entero alternativo para usar si es falso, pero 0nunca lo es en Java / Processing, que yo sepa.
Geobits
Pensé que el procesamiento se suponía que era menos versátil que Java
Pavel
@Pavel Pero no uso lambdas: /
Kritixi Lithos
4

Brachylog , 8 bytes

,3:.^-?,

Pruébalo en línea!

Emite el valor si es verdadero y false.si esto es imposible.

Explicación

Esta es una transcripción directa de la relación dada:

,     ,      (Disable implicit unification)
 3:.^        3^Output…
     -?              … - 1 = Input
Fatalizar
fuente
Casi puede jugar golf hasta 7 bytes +~^r~:3, pero desafortunadamente ~:no hace lo que podría esperar (probablemente porque :es una sintaxis en lugar de una incorporada), y parece ser tratado de manera idéntica :.
@ ais523 Eso es correcto, :es un símbolo de control y ~solo funciona en predicados.
Fatalize
3

Perl 6 ,  25  24 bytes

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

Intentalo

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

Eliminar el espacio después de los **trabajos porque es más largo que el otro operador infijo que podría coincidir *.
Entonces …***…se analiza como en … ** * …lugar de … * ** ….

Intentalo

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
fuente
3

R, 24 bytes

¡Un enfoque diferente de la respuesta de plannapus , y un byte más corto!

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

Genera todos los enteros de 3^1-1a 3^99-1y comprueba si stdin coincide. Si es así, devuelve el índice en el que coincide, que es x. Si no, devuelve NAcomo valor falso.

Por cierto, aceptará múltiples valores como entrada y los probará a todos, lo cual es una característica interesante.

rturnbull
fuente
3

Prólogo, 20 bytes

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

Este lenguaje es genial como el infierno.

| ?- d(1024,X).

no
| ?- d(26,X).

X = 3

yes
| ?- d(2,X).

X = 1

yes
Nombre McChange
fuente
2

05AB1E , 9 bytes

DÝ3sm<Q1k

Pruébalo en línea!

Imprime -1 para falsedad.

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
fuente
2

MATL , 8 bytes

3i:^qG=f

Esto genera el número xsi existe, o no genera nada, lo cual es falso.

Pruébalo en línea!

Explicación

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
fuente
2

Japt , 11 bytes

o æ@U+1¥3pX

Probarlo aquí .

¡Muchas gracias a ETHproductions por ayudar!

Oliver
fuente
2

Python 3, 74 66 64 bytes

-10 bytes gracias a @ mbomb007, @FlipTack y @ nmjcman101

from math import*
def f(n):x=ceil(log(n,3));print((3**x-1==n)*x)
dfernan
fuente
Puede poner todo su código en una línea y usarlo from math import*. También return n==3**x-1and x.
mbomb007
@ mbomb007 Las funciones pueden imprimir el resultado STDOUT, por lo que puede cambiar ese retorno a una impresión.
FlipTack
Si presenta esto como una solución SageMath en lugar de Python, puede eliminar la primera línea por completo.
Federico Poloni
Junto con la otra reducción a 65 bytes, puede usar import mathy math.ceilpara un solo byte. También puede recurrir 3**x-1==n and xax*(3**x-1==n)
nmjcman101
2

Rubí, 30 bytes.

Devuelve nil(un valor falso) si no se encontró ningún número. [Pruébalo en línea]

->n{(0..n).find{|i|3**i-1==n}}
Tinta de valor
fuente
2

C, 56 bytes

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

agregue uno a la entrada y luego divida repetidamente por tres hasta que encuentre un resto, si se alcanza el uno, devuelva el recuento de divisiones más -1

Jasen
fuente
Ahorre un byte con en a%3<1lugar de !(a%3). Uno más con 0falso.
Titus
Suponiendo que está utilizando GCC para compilar, puede guardar un total de 10 (11) bytes: no necesita inicializar n a cero si sabe que llamará a esta función solo una vez, desde entonces n será cero de forma predeterminada ( porque es global): son 4 bytes menos; Además, no necesita la declaración de devolución, al escribir a=--a?-1:n;ahorrará 5 bytes. Si una función no nula no tiene retorno, solo usará la última asignación. También lo que dijo @Titus.
Etaoin Shrdlu
1
Sugerir en a%3?0:(a/=3)lugar de!(a%3)&&(a/=3)
ceilingcat
2

Utilidades Bash / Unix, 37 35 bytes

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

Pruébalo en línea!

Utiliza dc para convertir a base 3, comprueba que la cadena resultante es todo 2s, cuenta el número de caracteres (incluida una nueva línea) y luego usa bc para restar 1.

Si el número en la base 3 no es todo 2, entonces grep no genera nada (ni siquiera una nueva línea), por lo que el recuento de caracteres es 0, y restando 1 produce -1.

Mitchell Spector
fuente
2

C compilado con 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;}

@SteadyBox ya publicó una solución en C, pero estoy usando un enfoque diferente.

@ Gracias a Jasen por ayudar a guardar bytes.

Wade Tyler
fuente
1
si, pero funciona? comparar flotadores para la igualdad a menudo es una receta para un fracaso inesperado (pruebe entradas grandes)
Jasen
@Jasen Hmm, no lo he intentado, pero en C logvuelve, doubleasí que tal vez podría funcionar.
Wade Tyler
double es un tipo de valor de coma flotante, por lo que el problema persiste.
Jasen
parece funcionar bien para 3 ^ 19, que probablemente sea lo suficientemente grande.
Jasen
@Jasen No funciona para 3 ^ 10
Wade Tyler
2

C, 42 bytes, optimizado de Wade Tyler

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

Tratar

C, 37 bytes, sin return

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

Tratar

nes global pero (I)MULsolo puede tener su operando de destino en un registro, por lo que debe ponerlo en EAX(la opción habitual) y moverlo allí

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)))

Si la "falsedad" necesita ser la misma, 33 Bytes:

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

Pyt , 10 9 bytes

←⁺3ĽĐĐƖ=*

Explicación:

←                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)


Guardado un byte utilizando la función de incremento en lugar de agregar explícitamente 1

mudkip201
fuente
¿en qué página de códigos hay 9 bytes? (en UTF-8 son 17 bytes)
Jasen
1

Python, 64 bytes

Salidas Falsesi el número no se puede escribir en ese formato.

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

Esto también funciona en 64 bytes e imprime una cadena vacía como salida falsa:

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

Una solución creativa para 65 bytes, 0que genera falsa:

lambda n:-~",".join(`3**x-1`for x in range(n+1)).find(',%s,'%n)/2
mbomb007
fuente
No sale xni -1.
dfernan
El programa debería salir en xlugar de nen caso de una coincidencia.
dfernan
No, debería generar el entero positivo que cuando se reemplaza con X, obtiene la entrada. La pregunta se refiere a X como una variable, no como una cadena
P. Ktinos
@ P.Ktinos lo arregló.
mbomb007
1

Julia, 30 bytes

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

Es una función simple: crea un vector que tiene un truesolo en la posición correspondiente en 3^a-1, donde aes un vector que contiene enteros entre 0 y n. Encuentra la "primera" posición que es truey resta 1 (si es todo false, el hallazgo se evalúa a cero y devuelve -1).

Como lo 0:nha hecho 0en el primer punto, la resta 1 corrige la indexación y también permite la -1respuesta falsa.

Glen O
fuente
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

Intenta aquí

Barra
fuente