Can this number be written in (3^x) - 1 format?

Question

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 code-golf so least amount of bytes wins

---

Related OEIS: A024023

Answer 1

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.

Answer 2

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.

Answer 3

Haskell, 35 bytes

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

Usage example: f 26 -> 3.

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

Brachylog v1, 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

Answer 8

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.

Answer 9

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

Answer 10

Pyth, 11 bytes

?-JjQ3 2ZlJ

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

Answer 11

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

Answer 12

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.

Answer 13

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.

Answer 14

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.

Answer 15

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

}

Answer 16

Husk, 4 bytes

£İ3→

Returns 0 if there's no such x, try it online!

Explanation

This works because £ assumes the list to be sorted and aborts the search once it sees a larger element:

£İ3→  -- implicit input N, for example: 80
   →  -- increment N -> 81
 İ3   -- list [3,9,27,81…
£     -- if it's in the list return index; -> 4
      -- else return 0

Answer 17

PowerShell Core, 42 40 bytes

param($a)1..$a|?{"3*"*$_+"1-1-eq$a"|iex}

-2 bytes thanks to mazzy, by replacing the [Math]::Pow, nice one!

Try it online!

Answer 18

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

Answer 19

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

Answer 20

Japt, 11 bytes

o æ@U+1¥3pX

Try it here.

Big thanks to ETHproductions for helping!

Answer 21

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)

Answer 22

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

Answer 23

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

Answer 24

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.

Answer 25

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.

Answer 26

APL (Dyalog Unicode), 12 bytes^SBCS

Anonymous tacit prefix function.

(⊢×⌊=⊢)3⍟1+⊢

Try it online!

1+⊢ increment

3⍟ log₃

(…) apply the following function:

 ⌊=⊢ is the floor equal to the argument? (0 or 1)

 ⊢× multiply the argument by that

Answer 27

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

Answer 28

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

Answer 29

Vyxal r, 6 bytes

ɾ3e‹ḟ›

Try it Online! The r flag reverses the arguments of all functions.

Explanation:

ɾ       # Range from 1 to n
 3e     # 3 ^ each number in the range (not n ^ 3 because of the r flag)
   ‹    # Decrement
    ḟ   # Index of the input
     ›  # Increment because ḟ is 0 indexed

Answer 30

Vyxal, 6 bytes

3¨e‹ḟ›

Try it Online!

Decided this was different enough from the other Vyxal answers to post.

    ḟ  # find the index of the input in
3¨e    # all powers of 3
   ‹   # -1
     › # and add 1 to that index