Kann diese Zahl im Format (3 ^ x) - 1 geschrieben werden?

41

Herausforderung:

Erstellen Sie ein Programm, das eine positive Ganzzahl akzeptiert und prüft, ob es in Form von (3 ^ x) -1 geschrieben werden kann, wobei X eine andere positive Ganzzahl ist .

Wenn dies möglich ist, geben Sie X aus

Wenn dies nicht möglich ist, geben Sie -1 oder eine falsche Anweisung aus.

Beispiel Ein- / Ausgänge

Eingang:

2

Es kann geschrieben werden als (3 ^ 1) - 1, also geben wir x aus, was 1 ist

Ausgabe:

1

Eingang:

26

26 kann geschrieben werden als (3 ^ 3) - 1, also geben wir x (3) aus

Ausgabe:

3

Eingang:

1024

1024 kann nicht in Form von (3 ^ x) - 1 geschrieben werden, daher geben wir -1 aus

Ausgabe:

-1

Dies ist also gewinnt die geringste Anzahl von Bytes


Verwandte OEIS: A024023

P. Ktinos
quelle
4
Ich bitte, X auszugeben, weil ich glaube, dass es auf diese Weise herausfordernder ist. Es wäre meiner Meinung nach zu einfach, herauszufinden, ob es das Format 3 ^ x - 1 hat.
P. Ktinos
2
Es sei denn, es ist eine falsche Aussage in Ihrer Programmiersprache, dann nein.
P. Ktinos
2
Darf ich die Nummer ternär eingeben?
John Dvorak
2
mit nicht negativen Intergern umgehen zu müssen, würde 0 zu 3^0-1 einer gültigen Ausgabe machen und somit nicht als falsch verwendbar sein,
Jasen
2
jemand Denken der Verwendung log()in ihrer Antwort sollte es bestätigen giives die richtige Antwort , 5wenn 242 eingegeben wird.
Jasen

Antworten:

23

Mathematica, 21 16 Bytes

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

Verwendet die symbolische Berechnung von Mathematica. Wenn #+1eine Log[3,#+1]Dreierpotenz ist, wird ein ganzzahliges Ergebnis berechnet, das ein atomarer Wert ist. Ansonsten werden wir bekommen, Log[#+1]/Log[3]wie es ist. Da dies kein atomarer Wert ist, ist es ein Ausdruck, der immer von der Form ist head[val1,val2,...]. In diesem Fall ist es tatsächlich so etwas wie Times[Power[Log[3], -1], Log[#+1]].

Wir unterscheiden die beiden Fälle, indem wir eine andere Funktion auf das Ergebnis anwenden. Was das Anwenden wirklich bewirkt, ist, dass es den headTeil eines Ausdrucks ersetzt. Da ganzzahlige Ergebnisse atomar sind, hat das Anwenden einer Funktion auf sie überhaupt nichts zu tun. Insbesondere f @@ atom == atom.

Im anderen Fall wird der Kopf jedoch ersetzt. Die Funktion, die wir verwenden -1&, ist eine einfache Funktion, die ihre Argumente ignoriert und zurückgibt -1. So bekommen wir -1&[Power[Log[3], -1], Log[#+1]]in nicht ganzzahligen Fällen etwas, was direkt ausgewertet wird -1. Spezialgehäuse durch Magie.

Martin Ender
quelle
13

Python, 46 44 Bytes

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

Probieren Sie es online!

In diesem Fall 0wäre der Wert falsch. Vielen Dank an @ mbomb007 für den Hinweis auf meine fehlerhafte Ausgabe sowie 2 Byte keine []Einsparungen.

nmjcman101
quelle
Sie können [n for n in range(x)if 3**n-1==x]für -4 Bytes neu schreiben , leere Liste als falsch
Rod
Behoben, danke! @ Rod dann würde es zurück [n] statt n denke ich
nmjcman101
@ Nmjcman101 das sollte kein Problem sein
Rod
@ Rod Ich würde es vorziehen, mich strikt an die Spezifikation zu halten
nmjcman101
@Rod Wenn die Ausgabe einer Ganzzahl erforderlich ist, können Sie diese nur in einer Liste ausgeben, wenn das OP dies ausdrücklich zulässt.
mbomb007
13

Haskell, 35 Bytes

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

Anwendungsbeispiel: f 26-> 3.

nimi
quelle
PS: Probieren Sie es online! unterstützt Haskell! (Nette Antwort übrigens!)
Fehler
11

05AB1E , 7 Bytes

3IÝm<¹k

Probieren Sie es online!

Erläuterung

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
quelle
05AB1E ist anscheinend gut in der Grundkonvertierung. Ist dies wirklich der beste Ansatz?
Jasen
1
@Jasen: Meine Versuche mit Base Conversion sind alle länger ausgefallen. Wenn es einen besseren Weg gibt, sehe ich ihn nicht. Fühlen Sie sich frei, mich falsch zu beweisen :)
Emigna
fairerweise habe ich nur die beschreibung der sprache gelesen und so eine 5 byte lösung erwartet ....
jasen
1
@Jasen <3zm©.ïi®ist der engste Punkt, an dem ich Bereiche nicht wie er verwendet habe.
Magic Octopus Urn
1
3DÝms<k... Nevermind ... Ich kann mich kein Byte mehr rasieren, ich könnte schwören, ich könnte.
Magic Octopus Urn
9

Gelee , 5 Bytes

R3*’i

Gibt x oder 0 (falsch) aus.

Probieren Sie es online!

Wie es funktioniert

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
quelle
6

Python 2, 41 Bytes

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

Eine rekursive Funktion, die 0bei nicht übereinstimmenden Eingaben zurückgegeben wird. Dividiert die Eingabe wiederholt durch 3, wobei die Anzahl der Schritte gezählt wird i, die am Ende ausgegeben werden. Wenn jedoch ein Schritt einen Wert nergibt, der nicht 2 modulo 0 ist, war die Zahl nicht für 3^i-1, sodass die Ausgabe mit 0 multipliziert wird.

xnor
quelle
6

Perl, 31 Bytes

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

Benötigt -EFlag zum Ausführen:

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

Erläuterungen:
grep{3**$_-1==$i}0..($i=<>)Gibt eine Liste der Elemente des Bereichs 0..$_(dh von 0 bis zur Eingabe) zurück, die den Test erfüllen 3**$_-1==$i. Nur maximal ein Element kann diesen Test bestehen, daher gibt dieser Befehl ein Array mit 0 oder 1 Element zurück. Wir drucken dann diese Liste: entweder das Xoder nichts (was falsch ist).

Dada
quelle
5

Pyth, 11 Bytes

?-JjQ3 2ZlJ

Konvertiert zu Basis 3 und überprüft die Gleichheit zu [2, 2, ..., 2].

orlp
quelle
Sie können dies mit um ein Byte reduzieren ?-2JjQ3ZlJ, da <col> <num>und <num> <col>für -in Pyth austauschbar .
Notjagan
5

JavaScript (ES7), 38 36 34 Bytes

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

Oder nur 30 bis 29 Bytes, wenn das Beenden bei einem Fehler in Ordnung ist:

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

Prüfung

Arnauld
quelle
5

Java 8, 37 58 67 Bytes

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

Dieses Lambda passt in eine Function<Integer, Integer>Referenz und verwendet den einfachen Trick zur Basis 3.

Diesmal sollte es richtig funktionieren.


quelle
3
Würde das nicht nur True oder False ausgeben, wenn es im Format geschrieben werden kann? Aber ich fragte nach dem Exponenten, als das Ergebnis wahr ist
P. Ktinos
2
Das ist genial! +1 für einen sehr cleveren Ansatz
DJMcMayhem
Das ist klug ... ich glaube, Sie können die Parens entfernen und es einfach machen i->. Wenn Sie ials nehmen Long, können Sie auch verwenden a.toString(...)(IDs geben einige Warnungen über die Verwendung statischer Funktionen falsch, sollten aber kompilieren). Wie OP sagte, müssen Sie jedoch den Wert zurückgeben, nicht nur True oder False.
FlipTack
Wenn das Lambda in einem anderen Funktionstyp gespeichert ist, funktioniert der statische Trick. Ich habe auch den Rückgabewert festgelegt. Ich muss diesen Teil verpasst haben.
5

Verarbeitung, 60 56 Bytes

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

Ausgänge -1wenn falsy.

Erläuterung

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
}

voidist 1 Byte kürzer als die Verwendung float, daher gibt diese Funktion direkt aus, anstatt einen Wert zurückzugeben.

Alternative Lösung

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

Für 63 Bytes, aber ich denke, diese Alternative kann kürzer als die ursprüngliche Lösung sein. Ich arbeite dran.

Kritixi Lithos
quelle
@FlipTack Ja, ich wusste, dass es nicht in Java wäre. Ich habe nur gefragt, weil ich nicht sicher war, ob Processing etwas in diese Richtung hinzugefügt hat. Der zu verwendende "eindeutige Wert" war jedoch -1, nicht 0. Er wurde jedoch seitdem geändert, sodass ich wahrscheinlich meine Kommentare dazu bereinigen werde.
Geobits
Warten Sie, also kann ich 0jetzt zurückkehren?
Kritixi Lithos
Ich würde immer noch nein sagen. Die Frage gibt einen alternativen ganzzahligen Wert an, der verwendet werden kann, wenn er falsch ist, aber 0in Java / Processing, von dem ich weiß, niemals falsch ist.
Geobits
Ich dachte, Processing sollte weniger versiert sein als Java
Pavel
@Pavel Aber ich benutze keine Lambdas: /
Kritixi Lithos
4

Brachylog , 8 Bytes

,3:.^-?,

Probieren Sie es online!

Gibt den Wert aus, wenn dies wahr und false.unmöglich ist.

Erläuterung

Dies ist eine direkte Transkription der angegebenen Beziehung:

,     ,      (Disable implicit unification)
 3:.^        3^Output…
     -?              … - 1 = Input
Tödlich
quelle
Sie können fast bis zu 7 Bytes Golf spielen +~^r~:3, ~:tun aber leider nicht das, was Sie erwarten (wahrscheinlich, weil :es sich eher um eine Syntax als um eine eingebaute handelt), und scheinen damit identisch zu sein :.
@ ais523 Das stimmt, :ist ein Kontrollsymbol und ~funktioniert nur bei Prädikaten.
Fatalize
3

Perl 6 ,  25  24 Bytes

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

Versuch es

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

Entfernen des Leerzeichens nach der **Arbeit, da es länger ist als der andere übereinstimmende Infix-Operator *.
Also …***…wird da … ** * …eher geparst als … * ** ….

Versuch es

Erweitert:

{  # 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
quelle
3

R, 24 Bytes

Ein anderer Ansatz als die Antwort von Plannapus und ein Byte kürzer!

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

Erzeugt alle Ganzzahlen von 3^1-1bis 3^99-1und prüft, ob stdin übereinstimmt. In diesem Fall wird der Index zurückgegeben, zu dem die Übereinstimmung besteht x. Wenn nicht, wird NAals falscher Wert zurückgegeben.

Übrigens werden mehrere Werte als Eingabe akzeptiert und alle getestet, was eine nette Funktion ist.

rturnbull
quelle
3

Prolog, 20 Bytes

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

Diese Sprache ist verdammt cool.

| ?- d(1024,X).

no
| ?- d(26,X).

X = 3

yes
| ?- d(2,X).

X = 1

yes
Nennen Sie McChange
quelle
2

05AB1E , 9 Bytes

DÝ3sm<Q1k

Probieren Sie es online!

Gibt -1 für falsch aus.

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

MATL , 8 Bytes

3i:^qG=f

Dies gibt die Nummer aus, xwenn sie existiert, oder gibt sonst nichts aus, was falsch ist.

Probieren Sie es online!

Erläuterung

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

Japt , 11 Bytes

o æ@U+1¥3pX

Probieren Sie es hier aus .

Ein grosses Dankeschön an ETHproductions für die Hilfe!

Oliver
quelle
2

Python 3, 74 66 64 Bytes

-10 Bytes dank @ mbomb007, @FlipTack und @ nmjcman101

from math import*
def f(n):x=ceil(log(n,3));print((3**x-1==n)*x)
dfernan
quelle
Sie können Ihren gesamten Code in eine Zeile schreiben und verwenden from math import*. Auch return n==3**x-1and x.
mbomb007
65-Byte-Lösung
mbomb007
@ mbomb007 Funktionen dürfen das Ergebnis an drucken STDOUT, damit Sie die Rückkehr zu einem Ausdruck ändern können.
FlipTack
Wenn Sie dies als SageMath- Lösung und nicht als Python-Lösung präsentieren, können Sie die erste Zeile vollständig löschen.
Federico Poloni
Zusammen mit der anderen Reduzierung auf 65 Byte können Sie import mathund math.ceilfür ein einzelnes Byte verwenden. Sie können sich auch 3**x-1==n and xum x*(3**x-1==n)
nmjcman101 vom
2

Ruby, 30 Bytes

Gibt nil(einen falschen Wert) zurück, wenn keine Nummer gefunden wurde. [Online ausprobieren]

->n{(0..n).find{|i|3**i-1==n}}
Wert Tinte
quelle
2

C 56 Bytes

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

addiere eins zur Eingabe und dividiere dann wiederholt durch drei, bis ein Rest gefunden wird. Wenn eins erreicht ist, gib die Anzahl der Teilungen zurück, sonst -1

Jasen
quelle
Speichern Sie ein Byte mit a%3<1anstelle von !(a%3). Eins noch mit 0wegen Falschheit.
Titus
Wenn Sie GCC zum Kompilieren verwenden, können Sie insgesamt 10 (11) Bytes speichern: Sie müssen n nicht auf Null initialisieren, wenn Sie wissen, dass Sie diese Funktion nur einmal aufrufen, da n dann standardmäßig Null ist ( weil es global ist) - das sind 4 Bytes weniger; Außerdem benötigen Sie die return-Anweisung nicht. Durch das Schreiben a=--a?-1:n;sparen Sie 5 Bytes. Wenn eine Non-Void-Funktion kein Return hat, wird nur die letzte Zuweisung verwendet. Auch was @Titus gesagt hat.
Etaoin Shrdlu
1
Schlagen Sie a%3?0:(a/=3)stattdessen vor!(a%3)&&(a/=3)
ceilingcat
2

Bash / Unix-Dienstprogramme, 37-35 Byte

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

Probieren Sie es online!

Konvertiert mit dc zur Basis 3, überprüft, ob die resultierende Zeichenfolge alle 2 ist, zählt die Anzahl der Zeichen (einschließlich einer neuen Zeile) und subtrahiert dann mit bc 1.

Wenn die Zahl in der Basis 3 nicht alle 2s ist, gibt grep nichts aus (nicht einmal eine neue Zeile), sodass die Zeichenanzahl 0 ist und das Subtrahieren von 1 -1 ergibt.

Mitchell Spector
quelle
2

C kompiliert mit 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 hat bereits eine Lösung in C gepostet, aber ich benutze einen anderen Ansatz.

@Danke an Jasen für die Unterstützung beim Speichern von Bytes.

Wade Tyler
quelle
1
Ja, aber funktioniert es? Der Vergleich von Floats auf Gleichheit ist oft ein Rezept für unerwartete Fehler (versuchen Sie es mit großen Eingaben)
Jasen
@Jasen Hmm, habe das noch nicht ausprobiert, aber in C logkehrt das zurück, doublealso könnte es vielleicht funktionieren.
Wade Tyler
double ist eine Art Gleitkommawert, sodass das Problem weiterhin besteht.
Jasen
scheint für 3 ^ 19 ok zu funktionieren, was wahrscheinlich groß genug ist.
Jasen
@Jasen Es funktioniert nicht für 3 ^ 10
Wade Tyler
2

C, 42 Bytes, optimiert von Wade Tyler

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

Versuchen

C, 37 Bytes, ohne return

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

Versuchen

nist global, (I)MULkann aber nur seinen dest-Operanden in einem Register haben, muss also in EAX(die übliche Wahl) gestellt und dort verschoben werden

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

Wenn das "falsch" gleich sein muss, 33 Bytes:

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

Pyt , 10 9 Bytes

←⁺3ĽĐĐƖ=*

Erläuterung:

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


Mit der Inkrementierungsfunktion ein Byte gespeichert, anstatt explizit 1 hinzuzufügen

mudkip201
quelle
In welcher Codepage sind das 9 Bytes? (in UTF-8 sind es 17 Bytes)
Jasen
1

Python, 64 Bytes

Gibt aus, Falseob die Nummer nicht in diesem Format geschrieben werden kann.

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

Dies funktioniert auch in 64 Bytes und gibt einen leeren String als falsche Ausgabe aus:

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

Eine kreative Lösung für 65 Bytes, die 0fälschlicherweise ausgibt:

lambda n:-~",".join(`3**x-1`for x in range(n+1)).find(',%s,'%n)/2
mbomb007
quelle
Wird weder ausgegeben xnoch -1.
6.
Das Programm sollte im Falle einer Übereinstimmung ausgegeben xwerden n.
6.
Nein, es sollte die positive Ganzzahl ausgeben, die beim Ersetzen durch X die Eingabe ergibt. Die Frage bezieht sich auf X als Variable, nicht als Zeichenfolge
P. Ktinos
@ P.Ktinos Es wurde behoben.
mbomb007
1

Julia, 30 Bytes

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

Es ist eine einfache Funktion - sie erzeugt einen Vektor, der truenur an der entsprechenden Position in a steht 3^a-1, wobei aein Vektor Ganzzahlen zwischen 0 und enthält n. Es findet die "erste" Position, die 1 ist, trueund subtrahiert sie (wenn alles ist false, wird der Wert 0 angenommen, und es wird -1 zurückgegeben).

Wie 0:nhat 0im ersten Spot, ermöglicht die subtrahieren 1 korrigiert für die Indizierung und die -1falsche Antwort.

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

Versuch es hier

Stange
quelle