41
\$\begingroup\$

Challenge:

Create a program that accepts a positive integer and checks if it can be written in the form of (3^x)-1, where X is another positive integer.

If it can, output X

If it can't, output -1 or a falsy statement.

Example inputs/outputs

Input:

2

It can be written as (3^1) - 1, so we output x which is 1

Output:

1

Input:

26

26 can be written as (3^3) - 1, so we output x (3)

Output:

3

Input:

1024

1024 can't be written in the form of (3^x) - 1, so we output -1

Output:

-1

This is so least amount of bytes wins


Related OEIS: A024023

\$\endgroup\$
  • 4
    \$\begingroup\$ I ask to output X because I believe it's more challenging that way. Simply finding if it is of format 3^x - 1 would be too easy for a challenge, in my opinion. \$\endgroup\$ – P. Ktinos Jan 6 '17 at 14:56
  • 2
    \$\begingroup\$ Unless if it's a falsy statement in your programming language, then no. \$\endgroup\$ – P. Ktinos Jan 6 '17 at 16:57
  • 2
    \$\begingroup\$ May I want the number to be input in ternary? \$\endgroup\$ – John Dvorak Jan 6 '17 at 17:35
  • 2
    \$\begingroup\$ having to handle non-negative intergers would make 0 3^0-1 a valid output and thus not useable as false, \$\endgroup\$ – Jasen Jan 7 '17 at 7:40
  • 2
    \$\begingroup\$ anyone thinking of using log() in their answer should confirm it giives the correct answer 5 when 242 is input. \$\endgroup\$ – Jasen Jan 7 '17 at 9:57

59 Answers 59

23
\$\begingroup\$

Mathematica, 21 16 bytes

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

Makes use of Mathematica's symbolic computation. If #+1 is a power of three then Log[3,#+1] will compute an integer result which is an atomic value. Otherwise we'll get Log[#+1]/Log[3] as is. Since this is not an atomic value, it's an expression which is always of the form head[val1,val2,...]. In this case it's actually something like Times[Power[Log[3], -1], Log[#+1]].

We distinguish between the two cases by applying another function to the result. What applying really does is that it replaces the head part of an expression. Since integer results are atomic, applying any function to them does nothing at all. In particular f @@ atom == atom.

However, in the other case, the head does get replaced. The function we're using is -1& which is a simple function that ignores its arguments and returns -1. So we get something -1&[Power[Log[3], -1], Log[#+1]] in non-integer cases, which evaluates directly to -1. Special casing via magic.

\$\endgroup\$
13
\$\begingroup\$

Python, 46 44 bytes

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

Try it online!

In this case, 0 would be the falsy value. Thanks to @mbomb007 for pointing out my incorrect output as well as a 2 bytes no [] savings.

\$\endgroup\$
  • \$\begingroup\$ you can rewrite as [n for n in range(x)if 3**n-1==x] for -4 bytes, empty list as falsy \$\endgroup\$ – Rod Jan 6 '17 at 15:53
  • \$\begingroup\$ Fixed, thank you! @Rod then it would return [n] instead of n I think \$\endgroup\$ – nmjcman101 Jan 6 '17 at 15:58
  • \$\begingroup\$ @nmjcman101 that shouldn't be a problem \$\endgroup\$ – Rod Jan 6 '17 at 16:01
  • \$\begingroup\$ @Rod I'd prefer adhering strictly to spec for now \$\endgroup\$ – nmjcman101 Jan 6 '17 at 16:14
  • \$\begingroup\$ @Rod If outputting an integer is required, you cannot output it in a list unless the OP specifically allows it. \$\endgroup\$ – mbomb007 Jan 6 '17 at 16:17
13
\$\begingroup\$

Haskell, 35 bytes

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

Usage example: f 26 -> 3.

\$\endgroup\$
  • \$\begingroup\$ PS: Try it online! supports Haskell! (Nice answer btw!) \$\endgroup\$ – flawr Jan 6 '17 at 16:11
11
\$\begingroup\$

05AB1E, 7 bytes

3IÝm<¹k

Try it online!

Explanation

3        # push 3 
 I       # push input
  Ý      # range [0 ... input]
   m     # 3^[0 ... input]
    <    # -1
     ¹k  # find index of input, return -1 if not found
\$\endgroup\$
  • \$\begingroup\$ 05AB1E is apparently good at base conversion is this really the best approach? \$\endgroup\$ – Jasen Jan 7 '17 at 7:26
  • 1
    \$\begingroup\$ @Jasen: My attempts with base conversion all turned out longer. If there is a better way than this I'm not seeing it. Feel free to prove me wrong though :) \$\endgroup\$ – Emigna Jan 7 '17 at 9:46
  • \$\begingroup\$ fair enough, I've only read the description of the language, and, so expected to see a 5 byte solution.... \$\endgroup\$ – Jasen Jan 7 '17 at 11:43
  • 1
    \$\begingroup\$ @Jasen <3zm©.ïi® is the closest I've got not using ranges like he did. \$\endgroup\$ – Magic Octopus Urn Jan 10 '17 at 15:28
  • 1
    \$\begingroup\$ 3DÝms<k... Nevermind... Can't shave off one more byte, could of sworn I could. \$\endgroup\$ – Magic Octopus Urn Jan 12 '17 at 19:33
9
\$\begingroup\$

Jelly, 5 bytes

R3*’i

Outputs x or 0 (falsy).

Try it online!

How it works

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).
\$\endgroup\$
6
\$\begingroup\$

Python 2, 41 bytes

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

A recursive function that returns 0 for non-matching inputs. Repeatedly floor-divides the input by 3, counting the number of steps in i, which is output in the end. But, if any step produces a value n that isn't 2 modulo 0, the number was not of for 3^i-1, so the output is multiplied by 0.

\$\endgroup\$
6
\$\begingroup\$

Perl, 31 bytes

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

Requires -E flag to run:

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

Explanations:
grep{3**$_-1==$i}0..($i=<>) returns a list of the elements of the range 0..$_ (ie. from 0 to the input) that satisfies the test 3**$_-1==$i. Only one element at most can satisfy this test, so this instruction will return an array of 0 or 1 element. We then print this list: either the X or nothing (which is falsy).

\$\endgroup\$
5
\$\begingroup\$

Pyth, 11 bytes

?-JjQ3 2ZlJ

Converts to base 3 and checks equality to [2, 2, ..., 2].

\$\endgroup\$
  • \$\begingroup\$ You can reduce this by one byte with ?-2JjQ3ZlJ, since <col> <num> and <num> <col> are interchangeable for - in Pyth. \$\endgroup\$ – notjagan Jan 7 '17 at 5:06
5
\$\begingroup\$

JavaScript (ES7), 38 36 34 bytes

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

Or just 30 29 bytes if it's OK to exit with an error on failure:

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

Test

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

console.log(f(177146))
console.log(f(847288609442))
console.log(f(5559060566555522))
console.log(f(123456))

\$\endgroup\$
5
\$\begingroup\$

Java 8, 37 58 67 bytes

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

This lambda fits in a Function<Integer, Integer> reference and uses the simple base 3 trick.

This time it should work correctly.

\$\endgroup\$
  • 3
    \$\begingroup\$ Wouldn't that only print True or False when it can be written in the format? But I asked for the exponent when the result is True \$\endgroup\$ – P. Ktinos Jan 6 '17 at 21:22
  • 2
    \$\begingroup\$ That's genius! +1 for a very clever approach \$\endgroup\$ – DJMcMayhem Jan 6 '17 at 22:26
  • \$\begingroup\$ This is clever... i believe you can remove the parens and just make it i->. Also, if you take i as a Long, you can then use a.toString(...) (ides will give some warnings about using static functions incorrectly, but should compile). However, as OP said, you need to return the value, not just True or False. \$\endgroup\$ – FlipTack Jan 6 '17 at 23:25
  • \$\begingroup\$ If the lambda is stored in a different function type then the static trick works. I also fixed the return value. I must have missed that part. \$\endgroup\$ – user18932 Jan 7 '17 at 2:51
5
\$\begingroup\$

Processing, 60 56 bytes

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

Outputs -1 if falsy.

Explanation

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 is 1 byte shorter than using float, so that's why this function directly outputs instead of returning a value.

Alternative Solution

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

for 63 bytes, but I think this alt can be golfed to be shorter than the original solution. I'm working on it.

\$\endgroup\$
  • \$\begingroup\$ @FlipTack Yeah, I knew it wouldn't be in Java. I just asked since I wasn't sure that Processing hadn't added something along those lines. The "distinct value" to be used was -1 though, not 0. It's been changed since, though, so I'll probably clean up my comments about it. \$\endgroup\$ – Geobits Jan 6 '17 at 16:51
  • \$\begingroup\$ Wait, so can I return 0 now? \$\endgroup\$ – Cows quack Jan 6 '17 at 16:52
  • \$\begingroup\$ I'd still say no. The question gives an alternative integer value to use if falsy, but 0 is never falsy in Java/Processing that I know of. \$\endgroup\$ – Geobits Jan 6 '17 at 16:53
  • \$\begingroup\$ I thougt Processing was supposed to be less versbose than Java \$\endgroup\$ – Pavel Jan 7 '17 at 8:24
  • \$\begingroup\$ @Pavel But I don't use lambdas :/ \$\endgroup\$ – Cows quack Jan 7 '17 at 8:35
4
\$\begingroup\$

Brachylog, 8 bytes

,3:.^-?,

Try it online!

Outputs the value if true and false. if this is impossible.

Explanation

This is a direct transcription of the given relation:

,     ,      (Disable implicit unification)
 3:.^        3^Output…
     -?              … - 1 = Input
\$\endgroup\$
  • \$\begingroup\$ You can almost golf this down to 7 bytes as +~^r~:3, but unfortunately ~: doesn't do what you might expect (likely because : is syntax rather than a builtin), and seems to be treated identically to :. \$\endgroup\$ – user62131 Jan 6 '17 at 18:17
  • \$\begingroup\$ @ais523 That's correct, : is a control symbol, and ~ only works on predicates. \$\endgroup\$ – Fatalize Jan 6 '17 at 18:35
3
\$\begingroup\$

Perl 6,  25  24 bytes

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

Try it

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

Removing the space after ** works because it is longer than the other infix operator that could match *.
So …***… is parsed as … ** * … rather than … * ** ….

Try it

Expanded:

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

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

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

}
\$\endgroup\$
3
\$\begingroup\$

R, 24 bytes

A different approach from plannapus' answer, and one byte shorter!

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

Generates all integers from 3^1-1 to 3^99-1, and checks if stdin matches. If so, it returns the index at which it matches, which is x. If not, returns NA as falsy value.

Incidentally, it will accept multiple values as input, and test all of them, which is a neat feature.

\$\endgroup\$
3
\$\begingroup\$

Prolog, 20 bytes

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

This language is cool as hell.

| ?- d(1024,X).

no
| ?- d(26,X).

X = 3

yes
| ?- d(2,X).

X = 1

yes
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 9 bytes

DÝ3sm<Q1k

Try it online!

Prints -1 for falsy.

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
\$\endgroup\$
2
\$\begingroup\$

MATL, 8 bytes

3i:^qG=f

This outputs the number x if it exists, or otherwise outputs nothing, which is falsy.

Try it online!

Explanation

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
\$\endgroup\$
2
\$\begingroup\$

Japt, 11 bytes

o æ@U+1¥3pX

Try it here.

Big thanks to ETHproductions for helping!

\$\endgroup\$
2
\$\begingroup\$

Python 3, 74 66 64 bytes

-10 bytes thanks to @mbomb007, @FlipTack and @nmjcman101

from math import*
def f(n):x=ceil(log(n,3));print((3**x-1==n)*x)
\$\endgroup\$
  • \$\begingroup\$ You can put all of your code on one line and use from math import*. Also return n==3**x-1and x. \$\endgroup\$ – mbomb007 Jan 6 '17 at 15:56
  • \$\begingroup\$ 65 byte solution \$\endgroup\$ – mbomb007 Jan 6 '17 at 16:16
  • \$\begingroup\$ @mbomb007 Functions are allowed to print the result to STDOUT, so you can change that return to a print. \$\endgroup\$ – FlipTack Jan 6 '17 at 16:43
  • \$\begingroup\$ If you present this as a SageMath solution rather than a Python one, you can drop the first line altogether. \$\endgroup\$ – Federico Poloni Jan 6 '17 at 17:00
  • \$\begingroup\$ Along with the other reduction to 65 bytes, you can use import math and math.ceil for a single byte. Also you can turn 3**x-1==n and x to x*(3**x-1==n) \$\endgroup\$ – nmjcman101 Jan 6 '17 at 22:00
2
\$\begingroup\$

Ruby, 30 bytes

Returns nil (a falsy value) if no number was found. [Try it online]

->n{(0..n).find{|i|3**i-1==n}}
\$\endgroup\$
2
\$\begingroup\$

C, 56 bytes

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

add one to the input and then repeatedly divide by three until a remainder is found, if the one is reached return the count of divides else -1

\$\endgroup\$
  • \$\begingroup\$ Save one byte with a%3<1 instead of !(a%3). One more with 0 for falsy. \$\endgroup\$ – Titus Jan 7 '17 at 11:36
  • \$\begingroup\$ Assuming you're using GCC to compile you can save a total of 10(11) bytes: you don't need to initialize n to zero if you know you'll call this function only once since then n will be zero by default (because it's global) - that's 4 bytes less; also you don't need the return statement, by writing a=--a?-1:n; you'll save 5 bytes. if a non-void function has no return, it'll just use the last assignment. Also what @Titus said. \$\endgroup\$ – Etaoin Shrdlu Jan 9 '17 at 20:26
  • 1
    \$\begingroup\$ Suggest a%3?0:(a/=3) instead of !(a%3)&&(a/=3) \$\endgroup\$ – ceilingcat Dec 11 '18 at 18:34
2
\$\begingroup\$

Bash / Unix utilities, 37 35 bytes

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

Try it online!

Uses dc to convert to base 3, checks that the resulting string is all 2s, counts the number of characters (including a newline), and then uses bc to subtract 1.

If the number in base 3 is not all 2s, then grep outputs nothing (not even a newline), so the character count is 0, and subtracting 1 yields -1.

\$\endgroup\$
2
\$\begingroup\$

C compiled with 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 already posted a solution in C, but I'm using a different approach.

@Thanks to Jasen for helping save bytes.

\$\endgroup\$
  • 1
    \$\begingroup\$ yeah, but does it work? comparing floats for equality is often a recipe for unexpected failure (try large inputs) \$\endgroup\$ – Jasen Jan 7 '17 at 6:49
  • \$\begingroup\$ @Jasen Hmm, haven't tried that, but in C log returns double so maybe it might work. \$\endgroup\$ – Wade Tyler Jan 7 '17 at 6:54
  • \$\begingroup\$ double is a type of floating point value so he problem persists. \$\endgroup\$ – Jasen Jan 7 '17 at 7:29
  • \$\begingroup\$ seems to work ok for 3^19 which is probably large enough. \$\endgroup\$ – Jasen Jan 7 '17 at 7:35
  • \$\begingroup\$ @Jasen It doesn't work for 3^10 \$\endgroup\$ – Wade Tyler Jan 7 '17 at 7:37
2
\$\begingroup\$

C, 42 Bytes, optimized from Wade Tyler's

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

Try

C, 37 Bytes, without return

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

Try

n is global but (I)MUL can only have its dest operand in a register, so have to put into EAX(the usual choice) and mov there

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

If the "falsy" need to be same, 33 Bytes:

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

Pyt, 10 9 bytes

←⁺3ĽĐĐƖ=*

Explanation:

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


Saved a byte by using the increment function instead of explicitly adding 1

\$\endgroup\$
  • \$\begingroup\$ in what code page is that 9 bytes? (in UTF-8 it's 17 bytes) \$\endgroup\$ – Jasen Dec 11 '18 at 22:08
1
\$\begingroup\$

Python, 64 bytes

Outputs False if the number cannot be written in that format.

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

This also works in 64 bytes, and prints empty string as a falsy output:

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

A creative solution for 65 bytes, outputting 0 for falsy:

lambda n:-~",".join(`3**x-1`for x in range(n+1)).find(',%s,'%n)/2
\$\endgroup\$
  • \$\begingroup\$ Does not output x nor -1. \$\endgroup\$ – dfernan Jan 6 '17 at 15:17
  • \$\begingroup\$ The program should output x instead of n in case of a match. \$\endgroup\$ – dfernan Jan 6 '17 at 15:20
  • \$\begingroup\$ No, it should output the positive integer that when replaced with X, you get the input. The question refers to X as a variable, not as a string \$\endgroup\$ – P. Ktinos Jan 6 '17 at 15:22
  • \$\begingroup\$ @P.Ktinos Fixed it. \$\endgroup\$ – mbomb007 Jan 6 '17 at 15:31
1
\$\begingroup\$

Pyth, 10 bytes

*J@hQ3!%J1

Try it here!

\$\endgroup\$
1
\$\begingroup\$

Julia, 30 bytes

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

It's a simple function - it creates a vector that has a true only in the corresponding position in 3^a-1, where a is a vector containing integers between 0 and n. It finds the "first" position that is true and subtracts 1 (if it's all false, the find evaluates to zero, and it returns -1).

As 0:n has 0 in the first spot, the subtract 1 corrects for indexing and also enables the -1 false response.

\$\endgroup\$
1
\$\begingroup\$

Pyke, 9 6 bytes

3m^Qh@

Try it here!

3m^    -  map(3**i, range(input))
     @ - V in ^
   Qh  -  input + 1

Old 9 byte version:

b3'l}\2q*

Try it here!

\$\endgroup\$
1
\$\begingroup\$

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

Try here

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.