Czy tę liczbę można zapisać w formacie (3 ^ x) - 1?


41

Wyzwanie:

Utwórz program, który akceptuje dodatnią liczbę całkowitą i sprawdza, czy można go zapisać w postaci (3 ^ x) -1, gdzie X to kolejna dodatnia liczba całkowita .

Jeśli to możliwe, wypisz X

Jeśli nie, wypisz -1 lub instrukcję fałszowania .

Przykładowe wejścia / wyjścia

Wejście:

2

Można go zapisać jako (3 ^ 1) - 1, więc wypisujemy x, który jest 1

Wynik:

1

Wejście:

26

26 można zapisać jako (3 ^ 3) - 1, więc wypisujemy x (3)

Wynik:

3

Wejście:

1024

1024 nie można zapisać w postaci (3 ^ x) - 1, więc wypisujemy -1

Wynik:

-1

To jest więc wygrywa najmniej bajtów


Powiązany OEIS: A024023


4
Proszę o wyjście X, ponieważ uważam, że jest to trudniejsze w ten sposób. Samo stwierdzenie, czy ma format 3 ^ x - 1 byłoby zbyt łatwe do podjęcia wyzwania, moim zdaniem.
P. Ktinos

2
Chyba że jest to fałszywe stwierdzenie w twoim języku programowania, to nie.
P. Ktinos

2
Czy mogę chcieć wprowadzić liczbę w potrójnym?
John Dvorak,

2
konieczność obsługi nieujemnych intergerów sprawiłaby, że 0 byłby 3^0-1 prawidłowym wyjściem, a zatem nie byłby użyteczny jako fałsz,
Jasen

2
każdy, kto myśli o użyciu log()w swojej odpowiedzi, powinien potwierdzić, że poda prawidłową odpowiedź, 5gdy 242 zostanie wprowadzona.
Jasen

Odpowiedzi:


23

Mathematica, 21 16 bajtów

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

Wykorzystuje obliczenia symboliczne Mathematica. Jeśli #+1jest potęgą trzech, wówczas Log[3,#+1]wyliczy liczbę całkowitą, która jest wartością atomową. W przeciwnym razie dostaniemy Log[#+1]/Log[3]jak jest. Ponieważ nie jest to wartość atomowa, jest to wyrażenie, które zawsze ma formę head[val1,val2,...]. W tym przypadku tak naprawdę jest coś takiego Times[Power[Log[3], -1], Log[#+1]].

Rozróżniamy te dwa przypadki, stosując do wyniku inną funkcję. Zastosowanie naprawdę polega na tym, że zastępuje headczęść wyrażenia. Ponieważ wyniki liczb całkowitych są atomowe, zastosowanie do nich dowolnej funkcji nic nie robi. W szczególności f @@ atom == atom.

Jednak w drugim przypadku głowa zostaje wymieniona. Używamy funkcji, -1&która jest prostą funkcją, która ignoruje argumenty i zwraca -1. Otrzymujemy więc coś -1&[Power[Log[3], -1], Log[#+1]]w przypadkach niecałkowitych, co ocenia bezpośrednio na -1. Specjalna obudowa dzięki magii.


13

Python, 46 44 bajtów

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

Wypróbuj online!

W tym przypadku 0byłaby to wartość fałszowania. Dzięki @ mbomb007 za wskazanie mojej niepoprawnej pracy oraz 2 bajtów braku []oszczędności.


możesz przepisać jak [n for n in range(x)if 3**n-1==x]na -4 bajty, pusta lista jako fałsz
Rod

Naprawiono, dziękuję! @Rod to zwróci [n] zamiast n Myślę, że
nmjcman101

@ nmjcman101 to nie powinno być problemem
Rod

@Rod Na razie wolałbym ściśle przestrzegać specyfikacji
nmjcman101

@Rod Jeśli wymagane jest wypisanie liczby całkowitej, nie można jej wypisać na liście, chyba że OP na to wyraźnie zezwoli.
mbomb007


11

05AB1E , 7 bajtów

3IÝm<¹k

Wypróbuj online!

Wyjaśnienie

3        # push 3 
 I       # push input
  Ý      # range [0 ... input]
   m     # 3^[0 ... input]
    <    # -1
     ¹k  # find index of input, return -1 if not found

05AB1E jest najwyraźniej dobry w konwersji bazowej, czy to naprawdę najlepsze podejście?
Jasen

1
@Jasen: Moje próby konwersji podstawowej okazały się dłuższe. Jeśli istnieje lepszy sposób, nie widzę tego. Zapraszam do udowodnienia, że ​​się mylę :)
Emigna

uczciwie, przeczytałem tylko opis języka i, tak się spodziewałem, zobaczyłem rozwiązanie 5-bajtowe ....
Jasen

1
@Jasen <3zm©.ïi®jest najbliżej, że nie używam zakresów tak jak on.
Magic Octopus Urn

1
3DÝms<k... Nieważne ... Nie mogę zgolić jeszcze jednego bajta, mógłbym przysiąc, że mógłbym.
Magic Octopus Urn

9

Galaretka , 5 bajtów

R3*’i

Wyprowadza x lub 0 (fałsz).

Wypróbuj online!

Jak to działa

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

6

Python 2, 41 bajtów

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

Funkcja rekurencyjna, która zwraca 0niepasujące dane wejściowe. Kilkakrotnie piętro dzieli dane wejściowe przez 3, licząc liczbę kroków i, które są wysyłane na końcu. Ale jeśli jakikolwiek krok daje wartość, nktóra nie jest równa 2 modulo 0, liczba nie była dla 3^i-1, więc wynik jest mnożony przez 0.


6

Perl, 31 bajtów

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

Wymaga -Eflagi do uruchomienia:

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

Objaśnienia:
grep{3**$_-1==$i}0..($i=<>)zwraca listę elementów zakresu 0..$_(tj. Od 0 do wejścia), które spełniają test 3**$_-1==$i. Tylko jeden element może spełnić ten test, więc instrukcja zwróci tablicę 0 lub 1 element. Następnie drukujemy tę listę: albo Xalbo nic (co jest fałszem).


5

Pyth, 11 bajtów

?-JjQ3 2ZlJ

Konwertuje na bazę 3 i sprawdza równość na [2, 2, ..., 2].


Możesz to zmniejszyć o jeden bajt ?-2JjQ3ZlJ, ponieważ <col> <num>i <num> <col>są one wymienne -w Pyth.
notjagan

5

JavaScript (ES7), 38 36 34 bajtów

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

Lub tylko 30 29 bajtów, jeśli można wyjść z błędem w przypadku niepowodzenia:

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

Test


5

Java 8, 37 58 67 bajtów

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

Ta lambda pasuje do Function<Integer, Integer>odniesienia i wykorzystuje prostą sztuczkę base 3.

Tym razem powinno działać poprawnie.


3
Czy nie wydrukowałoby to tylko Prawdy czy Fałszu, gdy można je zapisać w formacie? Ale poprosiłem o wykładnik, gdy wynik jest prawdziwy
P. Ktinos

2
To geniusz! +1 za bardzo sprytne podejście
DJMcMayhem

To sprytne ... wierzę, że możesz usunąć pareny i po prostu to zrobić i->. Ponadto, jeśli weźmiesz ijako a Long, możesz użyć a.toString(...)(ides poda ostrzeżenia o niepoprawnym używaniu funkcji statycznych, ale powinno się skompilować). Jednak, jak powiedział OP, musisz zwrócić wartość, a nie tylko Prawdę czy Fałsz.
FlipTack,

Jeśli lambda jest przechowywana w innym typie funkcji, wówczas sztuczka statyczna działa. Poprawiłem również wartość zwracaną. Musiałem przegapić tę część.

5

Przetwarzanie, 60 56 bajtów

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

Wysyła, -1jeśli jest fałsz.

Wyjaśnienie

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
}

voidjest o 1 bajt krótszy niż użycie float, dlatego funkcja ta wyświetla bezpośrednio dane zamiast zwracać wartość.

Alternatywne rozwiązanie

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

dla 63 bajtów, ale myślę, że ten alt może być golfowany krótszy niż oryginalne rozwiązanie. Pracuję nad tym.


@FlipTack Tak, wiedziałem, że nie będzie w Javie. Właśnie zapytałem, ponieważ nie byłem pewien, czy Processing nie dodał czegoś w tym stylu. „Odrębną wartością”, którą należy zastosować, było -1, a nie 0. Zostało to jednak zmienione, więc prawdopodobnie posprzątam moje komentarze na ten temat.
Geobits

Czekaj, więc mogę 0teraz wrócić ?
Kritixi Lithos

Nadal powiedziałbym „nie”. Pytanie daje alternatywną wartość całkowitą do użycia, jeśli jest fałszem, ale 0nigdy nie jest fałszem w Javie / Przetwarzaniu, które znam.
Geobits

Myślę, że przetwarzanie miało być mniej sprzeczne z Javą
Pavel

@Pavel Ale nie używam lambdas: /
Kritixi Lithos

4

Brachylog , 8 bajtów

,3:.^-?,

Wypróbuj online!

Zwraca wartość, jeśli jest to prawda, a false.jeśli jest to niemożliwe.

Wyjaśnienie

To jest bezpośrednia transkrypcja danej relacji:

,     ,      (Disable implicit unification)
 3:.^        3^Output…
     -?              … - 1 = Input

Możesz prawie zagrać w golfa do 7 bajtów jako +~^r~:3, ale niestety ~:nie robi tego, czego możesz się spodziewać (prawdopodobnie dlatego, że :jest składnią, a nie wbudowaną) i wydaje się być traktowane identycznie :.

@ ais523 To prawda, :jest symbolem kontrolnym i ~działa tylko w predykatach.
Fatalize

3

Perl 6 ,  25  24 bajtów

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

Spróbuj

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

Usuwanie miejsca po zakończeniu **pracy, ponieważ jest ono dłuższe niż inny operator poprawki, który może pasować *.
Więc …***…jest parsowany jako … ** * …raczej niż … * ** ….

Spróbuj

Rozszerzony:

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

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

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

}

3

R, 24 bajty

Inne podejście niż odpowiedź plannapa i jeden bajt krótszy!

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

Generuje wszystkie liczby całkowite od 3^1-1do 3^99-1i sprawdza, czy standardowe wejście jest zgodne. Jeśli tak, zwraca indeks, do którego pasuje, czyli x. Jeśli nie, zwraca NAwartość falsy.

Nawiasem mówiąc, zaakceptuje wiele wartości jako dane wejściowe i przetestuje je wszystkie, co jest fajną cechą.


3

Prolog, 20 bajtów

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

Ten język jest świetny jak diabli.

| ?- d(1024,X).

no
| ?- d(26,X).

X = 3

yes
| ?- d(2,X).

X = 1

yes

2

05AB1E , 9 bajtów

DÝ3sm<Q1k

Wypróbuj online!

Drukuje -1 dla fałszu.

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

2

MATL , 8 bajtów

3i:^qG=f

Daje to liczbę, xjeśli istnieje, lub w inny sposób nic nie daje, co jest fałszem.

Wypróbuj online!

Wyjaśnienie

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


2

Python 3, 74 66 64 bajtów

-10 bajtów dzięki @ mbomb007, @FlipTack i @ nmjcman101

from math import*
def f(n):x=ceil(log(n,3));print((3**x-1==n)*x)

Możesz umieścić cały kod w jednym wierszu i użyć from math import*. Również return n==3**x-1and x.
mbomb007


@ mbomb007 Funkcje mogą drukować wynik STDOUT, dzięki czemu można zmienić powrót do wydruku.
FlipTack,

Jeśli przedstawisz to jako rozwiązanie SageMath zamiast Python, możesz całkowicie upuścić pierwszą linię.
Federico Poloni

Wraz z drugą redukcją do 65 bajtów możesz użyć import mathi math.ceildla jednego bajtu. Możesz także zwrócić się 3**x-1==n and xdox*(3**x-1==n)
nmjcman101


2

C, 56 bajtów

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

dodaj jeden do wejścia, a następnie kilkakrotnie podziel przez trzy, aż do znalezienia reszty, jeśli jeden zostanie osiągnięty, zwróć liczbę podziałów -1


Zaoszczędź jeden bajt za pomocą a%3<1zamiast !(a%3). Jeszcze jedno z 0falsy.
Tytus

Zakładając, że używasz GCC do kompilacji, możesz zapisać łącznie 10 (11) bajtów: nie musisz inicjować n do zera, jeśli wiesz, że wywołasz tę funkcję tylko raz, ponieważ n domyślnie będzie wynosić zero ( ponieważ jest globalny) - to 4 bajty mniej; także nie potrzebujesz instrukcji return, pisząc a=--a?-1:n;, że zaoszczędzisz 5 bajtów. jeśli funkcja nie-void nie ma powrotu, użyje tylko ostatniego przypisania. Także to, co powiedział @Titus.
Etaoin Shrdlu

1
Zaproponuj a%3?0:(a/=3)zamiast!(a%3)&&(a/=3)
ceilingcat

2

Narzędzia Bash / Unix, 37 35 bajtów

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

Wypróbuj online!

Używa dc do konwersji do podstawy 3, sprawdza, czy wynikowy ciąg składa się z 2, zlicza liczbę znaków (łącznie z nową linią), a następnie używa bc do odejmowania 1.

Jeśli liczba w bazie 3 to nie wszystkie 2 s, to grep nic nie wypisuje (nawet nowej linii), więc liczba znaków wynosi 0, a odjęcie 1 daje -1.


2

C skompilowany z Clang 3.8.1, 53 , 52 , 54 , 51 bajtów

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

@ SteadyBox już opublikował rozwiązanie w C, ale używam innego podejścia.

@Dziękujemy Jasen za pomoc w oszczędzaniu bajtów.


1
tak, ale czy to działa? porównywanie liczb zmiennoprzecinkowych dla równości jest często receptą na nieoczekiwany błąd (spróbuj dużych nakładów)
Jasen

@Jasen Hmm, nie próbowałem tego, ale w C logzwraca, doublewięc może to zadziała.
Wade Tyler

double jest rodzajem wartości zmiennoprzecinkowej, więc problem utrzymuje się.
Jasen

wydaje się działać dobrze dla 3 ^ 19, co jest prawdopodobnie wystarczająco duże.
Jasen

@Jasen To nie działa dla 3 ^ 10
Wade Tyler

2

C, 42 bajty, zoptymalizowane przez Wade'a Tylera

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

Próbować

C, 37 bajtów, bez return

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

Próbować

nma charakter globalny, ale (I)MULmoże mieć tylko operand przeznaczenia w rejestrze, więc należy wprowadzić EAX(zwykły wybór) i przenieść się tam

JavaScript 6, 32 bajtów

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

Jeśli „fałsz” musi być taki sam, 33 bajty:

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

2

Pyt , 10 9 bajtów

←⁺3ĽĐĐƖ=*

Wyjaśnienie:

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


Zapisano bajt za pomocą funkcji inkrementacji zamiast jawnego dodawania 1


na jakiej stronie kodowej jest to 9 bajtów? (w UTF-8 to 17 bajtów)
Jasen

1

Python, 64 bajty

Wyprowadzane, Falsejeśli liczby nie można zapisać w tym formacie.

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

Działa to również w 64 bajtach i wyświetla pusty ciąg znaków jako wynik wyjściowy falsy:

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

Kreatywne rozwiązanie dla 65 bajtów, generujące 0falsy:

lambda n:-~",".join(`3**x-1`for x in range(n+1)).find(',%s,'%n)/2

Nie generuje xani -1.
dfernan

Program powinien wypisywać dane xzamiast nw przypadku dopasowania.
dfernan

Nie, powinna wypisać dodatnią liczbę całkowitą, którą po zastąpieniu X otrzymasz dane wejściowe. Pytanie odnosi się do X jako zmiennej, a nie łańcucha
P. Ktinos

@ P.Ktinos Naprawiono.
mbomb007


1

Julia, 30 bajtów

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

Jest to prosta funkcja - tworzy wektor, który ma truetylko w odpowiedniej pozycji w 3^a-1, gdzie awektor zawiera liczby całkowite od 0 do n. Znajduje „pierwszą” pozycję, która jest, truei odejmuje 1 (jeśli to wszystko false, znalezisko jest oceniane na zero i zwraca -1).

Jak 0:nma 0na pierwszym miejscu, odjąć 1 koryguje indeksowania, a także pozwala na -1fałszywą odpowiedź.



1

Pyth 8 bajtów

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

Wypróbuj tutaj

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.