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

Haskell, 35 bytes

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

Usage example: f 26 -> 3.

Answer 3

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 4

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 5

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 6

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 7

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 8

Pyth, 11 bytes

?-JjQ3 2ZlJ

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

Answer 9

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 10

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 11

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 12

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

Answer 13

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

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 16

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 17

Japt, 11 bytes

o æ@U+1¥3pX

Try it here.

Big thanks to ETHproductions for helping!

Answer 18

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

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 21

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

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 25

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 26

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

Answer 27

R, 34 25 bytes

a=log(scan()+1,3);a*!a%%1

Calculate the base 3 logarithm of the input + 1. Test if the result is an integer, if it is it outputs it, if not it outputs 0 as falsey value. Thanks to @Billywob for the extra 9 bytes off!

Test cases:

> a=log(scan()+1,3);a*!a%%1
1: 1024
2: 
Read 1 item
[1] 0

> a=log(scan()+1,3);a*!a%%1
1: 26
2: 
Read 1 item
[1] 3

Old version at 34 bytes which outputs -1 as falsey value.

a=log(scan()+1,3);`if`(!a%%1,a,-1)

Answer 28

Pyth, 10 bytes

*J@hQ3!%J1

Try it here!

Answer 29

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!

Answer 30

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.

Answer 31

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

Answer 32

C, 81 bytes

i,j,k;f(n){for(i=0;++i<n;){for(k=3,j=0;++j<i;k*=3);if(n==k-1)return i;}return-1;}

Answer 33

Japt, 8 bytes

o m!³a°U

Try it online!

This code expands into the following:

Uo m!p3 a++U

Uo            // Create the range [0...U).
   m!p3       // Map each item X to 3**X.
        a++U  // Take the index of U+1. Returns -1 if it doesn't exist.
              // Implicit: output result of last expression

Answer 34

Octave, 23 bytes

@(x)find(3.^(1:x)-1==x)

Verify all test cases!

Explanation:

This is an anonymous function that takes a positive integer x as input. .^ is element-wise power in Octave, so 3.^(1:x) is 3^1, 3^2, 3^3 .... Subtracting 1 gives 3^1-1, 3^2-1, 3^3-1 ... which can be compared to x.

find(a,b) takes a vector a as input, and attempts to find the scalar b in that vector and returns its index. If it's not found then it will output an empty matrix []. An empty matrix is a falsey value in Octave.

find(3.^(1:x)-1==x) searches for x in the vector 3^1-1, 3^2-1, 3^3-1 ... and attempts to return its index. If it's not in the vector then it returns an empty (falsey) matrix.

Answer 35

GolfScript, 11 bytes

~..3\?\)%!*

Try it online!

Uses the fact that 3ⁿ is divisible by n+1 if and only if n+1 itself is a power of 3. Outputs its input n if n+1 is a power of 3, otherwise outputs 0 (which is falsy in GolfScript).

De-golfed:

~             # eval the input, converting it from string to integer
 ..           # make two copies of the input number
   3\?        # raise 3 to the power of the input number
      \)%     # reduce the result modulo the input number plus one
         !    # boolean negate the result, mapping 0 to 1 and all other values to 0
          *   # multiply the input number with the result

Ps. Here's a simple test harness that runs the code above (minus the initial ~, which is not needed since the inputs are already numbers) on all integers from 0 to 9999 and prints those for which it returns a truthy result:

10000,{ ..3\?\)%!* },`

The output of this program should be:

[2 8 26 80 242 728 2186 6560]

(The output doesn't include 0 because, even though the formula used does correctly detect it as one less than a power of 3, the result is still 0 × 1 = 0, and thus falsy. Fortunately, 0 is not a positive integer, and thus isn't a valid input for this challenge anyway.)

Answer 36

c++ 60 bytes

int f(n){float o=log1p(n)/log(3);return o/floor(o)!=1?-1:o;}

explanation:

int f(n){             
  float o=log1p(n)/log(3);       // eval for x using log3 function 
  return o/floor(o)!=1?-1:o;     // if no remainder output X 
}

Answer 37

C, 76 bytes

main(i,a,c){scanf("%d",&a);for(c=0,++a;i<a;i*=3,++c);printf("%d",(i==a)*c);}

Answer 38

Sagemath, 45 bytes

This is simply @dfernan's solution repackaged as Sagemath (which is basically Python + some math libraries loaded by default and syntactic sugar).

In Sagemath, we can avoid the import math and we can use ^ for exponentiation, so we save a few chars.

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

Test it online

Answer 39

Python 2, 34 bytes

lambda n:(~n>>3**n%-~n*n)**4/80%80

Try it online!

Works for all Python ints, up to at least 2^100.

Answer 40

Pip, 13 bytes

aTB:3MNa=2&#a

Try it online!

Explanation

               a is 1st command-line argument (implicit)
aTB:3          Convert a to base 3 and assign back to a
     MNa=2     Does the min of a's digits equal 2?
          &    Logical-and
           #a  Length of a
               If there are non-2 digits, we get the falsey value 0; otherwise, we get
               the number of digits

Answer 41

05AB1E, 6 bytes

>3.n.ï

Try it online!

> increments, 3 pushes a 3 to the stack, .n find the logarithm with base 3, .ï checks if it is equal to its integer part.

Returns 0 for falsy: If it can't, output -1 or a falsy statement.

Answer 42

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 43

APL NARS, 14 chars or 28 bytes

{r×r=⌊r←3⍟1+⍵}

Test:

  f←{r×r=⌊r←3⍟1+⍵}
  f 2     
1
  f 26
3
  f 1024
0

Answer 44

APL (Dyalog), 11 bytes

⊢|⊢⍳⍨¯1+3*⍳

Try it online!

Uses ⎕IO←0.

How?

⍳ - range of 0 to n-1.

3* - raise 3 to the power of each element.

¯1+ - decrement each by 1.

⊢⍳⍨ - search the index of n in that list (if not exists, this would return the maximum index plus 1 - which is n.

⊢| - modulo by n. This would keep the index, if found, and zero-out numbers not contained in the list that would produce n % n = 0.

---

APL (Dyalog), 14 bytes

(∧/×≢)2=3⊥⍣¯1⊢

Try it online!

Answer 45

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 46

Befunge-93, 26 bytes

&1+>:3%v
1+\^v-1_3/\
.@.$_

Try It Online

Prints 0 as the falsey.

How it Works

&1+... Gets the input and adds one
......
......

...>:3%v    Check if the number is divisible by 3
1+\^..._3/\ If not, divide the number by 3 and increment a counter
...         Repeat until the number is not divisible by 3

.........   If the final number is a one, print the counter
....v-1_... Else pop the counter and print a 0
.@.$_       End the program

Answer 47

JavaScript (ES6), 40 bytes

f=(n,p=0,k=1)=>n<k?n>k-2&&p:f(n,p+1,k*3)

Returns false or the power. A simple port of @Arnauld's ES7 answer would have taken 43 bytes.

Answer 48

Java 7, 180 bytes

class A{public static void main(String[]q)throws Exception{int a,b=0;while((a=System.in.read()-48)>=0)b=b*10+(a);double k=Math.log(b+1)/Math.log(3);System.out.print(k%1==0?k:-1);}}

Really simple approach. Input, then add one, then log₃ the number, and if it's a integer, print it; otherwise, print -1. Could use some work.

Only works up to (3^19)-1.

Answer 49

PHP, 36 47 bytes

If log(input+1,3) differs from its integer value, print 0; else print the logarithm:
<?=(0|$x=log($argv[1]+1,3))-$x?0:$x; (36 bytes) fails for 242.
<?=strstr($x=log($argv[1]+1,3),".")?0:$x; and <?=(0|$x=log($argv[1]+1,3))-$x>1e-7?0:$x; (41 bytes) may fail for larger $x.

This version is safe:

for(;3**++$x<$n=1+$argv[1];);echo$n<3**$x?0:$x;

1.Loop $x up from 1 while 3^$x is smaller than argument+1.
2.Print 0 if the expression is larger than input+1, $x else.

Takes input from command line argument. Run with -nr.

Answer 50

Common Lisp (SBCL), 83 50 bytes

(let*((i(read))(r(log(1+ i)3)))(if(=(mod r 1)0)r))

Old version:

(let((i(read)))(if(find-if(lambda(x)(not(eq x #\2)))(format()"~3R"i))()(log(1+ i)3)))

Feedback encouraged!

Answer 51

CJam, 11 bytes

ri3b_2-!\,*

Basically it determines if the number's trinary (base 3) representation contains only 2's, and if it does, outputs the number of 2's. It outputs 0 if the number is not only 2's.

Try it online!

Explanation

ri          e# Get input as an integer
  3b        e# Convert to base 3 (an array of the digits in base 3)
    _       e# Duplicate
     2-     e# Remove all 2's from the array
       !    e# Boolean negation. Yields 1 if the array contained only 2's (and is now 
            e# empty), 0 otherwise
        \   e# Swap top 2 elements of stack
         ,  e# Take the length of the base 3 digits array
          * e# Multiply by the boolean value from before

Answer 52

C 90 bytes

f(x){i=1;for(;i<x;i++){if((pow(3,i)-1)==x){printf("%d",i);break;}if(i==(x-1))puts("-1");}}

Ungolfed Version:

void f(int x)
{
  int i=1;
  for(;i<x;i++)
  {
    if((pow(3,i)-1)==x)
    {
        printf("%d",i);
        break;      
    }   
    if(i==(x-1))
        puts("-1");     
  } 
}

Answer 53

SmileBASIC, 32 bytes

INPUT X
X=LOG(X+1,3)?X*(X==X>>0)

Outputs 0 for false.

Answer 54

Cardinal, 91 bytes

%
:
+
~
v~d<
0  /{<
+  A #-?+M?"-1"@
+  !   @.-<
+  M #  M!/        <
>~ # ^  } \       +^%

According to the specifications of Cardinal, this shouldn't work for inputs above 255. However, due to the implementation in TIO accepting values over 255, it will work past 255 up to 3^34.

Try it online!

Explanation

%
:
+

Input + 1

~
v~d<
0  /{<
+  A 
+  !  
+  M
>~ # ^

While divisible by 3

#-?+M?"-1"@

Output -1 if not divisible by 3 or equal to 1 and end program

   .-<
#  M!/        <
   } \       +^%

Output counter for how many times the input + 1 has been divided by 3 before equalling 1

Answer 55

TI-Basic (TI-84 Plus CE) 17 15 bytes

logBASE(Ans+1,3)
Ansnot(Ans-int(Ans

All tokens used are one-byte except logBASE(, which is two.

Explanation:

logBASE(Ans+1,3)   # inverse of 3^n-1 is log3(x+1)
Ansnot(Ans-int(Ans # if X is an integer, `X-int(x` is 0, so `not(X-int(X` is 1, which is multiplied by X
                   # if X is not an integer, `X-int(X` is not 0, so `not(X-int(X` is zero, which is multiplied by X
                   # last value evaluated is implicitly returned

Answer 56

QBIC, 18 bytes

:[a|c=3^b-1~c=a|?b

Explanation

:        Get 'a' from the cmd-line
[a|      FOR b=1; b<=a; b++  (this runs a lot longer than we need...)
c=3^b-1  Set c to be 3^b-1
~c=a     IF this is the input given
|?b      THEN print b
         END IF and NEXT are added implicitly

This would print multiple bs if it would be possible to have multiple solutions. Right now, it runs on after finding a solution. We could substitute ?b for _Xb to quit after finding a solution, but that adds a byte. Also, the FOR-loop [a| could be initialised as [a/3| to save us a lot of iterations, but that adds another 2 bytes.

Answer 57

Axiom,72 65 63 bytes

g(x:PI):INT==(z:=floor(y:=log(x+1.)/log(3.));y-z~=0=>-1;z::INT)

some test

(51) -> [[x,g(x)]  for x in [1,2,3,4,5,6,7,8,9,10,26,27,79,80,242]]
   (51)
   [[1,- 1], [2,1], [3,- 1], [4,- 1], [5,- 1], [6,- 1], [7,- 1], [8,2],
    [9,- 1], [10,- 1], [26,3], [27,- 1], [79,- 1], [80,4], [242,5]] 

Answer 58

J, 14 bytes

[:(*>.=])3^.>:

Try it online!

Here's a variant using a range of powers and indexing (@Dennis's method).

(~:*])>:i.~3^i.

Here's a variant using base conversion (@orlp's method).

[:(#*&(*/)2=])3&#.inv

Answer 59

JavaScript 28 bytes (where static X is passed to function)

f=(n,x)=>Math.pow(3,x)-1==n&&x

console.log(
  f(8,2)
, f(26,3)
)

67 bytes (where a Map of the possible values is created once)

m=new Map;for(x=45;x>2;m.set(Math.pow(3,--x)-1,x))
f=n=>m.get(n)||!1

console.log(
  f(8)
, f(26)
, f(1024)
)