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

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

• 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. Commented Jan 6, 2017 at 14:56
• Unless if it's a falsy statement in your programming language, then no. Commented Jan 6, 2017 at 16:57
• May I want the number to be input in ternary? Commented Jan 6, 2017 at 17:35
• having to handle non-negative intergers would make 0 3^0-1 a valid output and thus not useable as false, Commented Jan 7, 2017 at 7:40
• anyone thinking of using log() in their answer should confirm it giives the correct answer 5 when 242 is input. Commented Jan 7, 2017 at 9:57

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

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

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

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


Usage example: f 26 -> 3.

• PS: Try it online! supports Haskell! (Nice answer btw!) Commented Jan 6, 2017 at 16:11

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


# 05AB1E, 7 bytes

3IÝm<¹k


Try it online!

Explanation

3        # push 3
I       # push input
Ý      # range [0 ... input]
m     # 3^[0 ... input]
<    # -1

• 05AB1E is apparently good at base conversion is this really the best approach? Commented Jan 7, 2017 at 7:26
• @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 :) Commented Jan 7, 2017 at 9:46
• fair enough, I've only read the description of the language, and, so expected to see a 5 byte solution.... Commented Jan 7, 2017 at 11:43
• @Jasen <3zm©.ïi® is the closest I've got not using ranges like he did. Commented Jan 10, 2017 at 15:28
• 3DÝms<k... Nevermind... Can't shave off one more byte, could of sworn I could. Commented Jan 12, 2017 at 19:33

# 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


# 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

• 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 :.
– user62131
Commented Jan 6, 2017 at 18:17
• @ais523 That's correct, : is a control symbol, and ~ only works on predicates. Commented Jan 6, 2017 at 18:35

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

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

# Pyth, 11 bytes

?-JjQ3 2ZlJ


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

• You can reduce this by one byte with ?-2JjQ3ZlJ, since <col> <num> and <num> <col> are interchangeable for - in Pyth. Commented Jan 7, 2017 at 5:06

## JavaScript (ES7), 3836 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))

# Java 8, 3758 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.

• 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 Commented Jan 6, 2017 at 21:22
• That's genius! +1 for a very clever approach Commented Jan 6, 2017 at 22:26
• 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. Commented Jan 6, 2017 at 23:25
• 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.
– user18932
Commented Jan 7, 2017 at 2:51

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

• @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. Commented Jan 6, 2017 at 16:51
• Wait, so can I return 0 now? Commented Jan 6, 2017 at 16:52
• 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. Commented Jan 6, 2017 at 16:53
• I thougt Processing was supposed to be less versbose than Java Commented Jan 7, 2017 at 8:24
• @Pavel But I don't use lambdas :/ Commented Jan 7, 2017 at 8:35

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

# 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 }  # 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  # 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! • I also tried the log approach but couldn't make it shorter: (0,($t=[math]::log(1+"$args",3)))[$t-eq[int]$t] Commented Nov 25, 2020 at 4:13 • 40 bytes :) Commented Nov 25, 2020 at 20:57 # 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  # 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  ## Japt, 11 bytes o æ@U+1¥3pX  Try it here. Big thanks to ETHproductions for helping! # Python 3, 7466 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)  • You can put all of your code on one line and use from math import*. Also return n==3**x-1and x. Commented Jan 6, 2017 at 15:56 • 65 byte solution Commented Jan 6, 2017 at 16:16 • @mbomb007 Functions are allowed to print the result to STDOUT, so you can change that return to a print. Commented Jan 6, 2017 at 16:43 • If you present this as a SageMath solution rather than a Python one, you can drop the first line altogether. Commented Jan 6, 2017 at 17:00 • 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) Commented Jan 6, 2017 at 22:00 # 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}}  # 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 • Save one byte with a%3<1 instead of !(a%3). One more with 0 for falsy. Commented Jan 7, 2017 at 11:36 • 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. Commented Jan 9, 2017 at 20:26 • Suggest a%3?0:(a/=3) instead of !(a%3)&&(a/=3) Commented Dec 11, 2018 at 18:34 # 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.

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

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

# APL (Dyalog Unicode), 12 bytesSBCS

Anonymous tacit prefix function.

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


Try it online!

1+⊢ increment

3⍟ log3

() apply the following function:

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

⊢× multiply the argument by that

# 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


# Pyt, 10 9 bytes

←⁺3ĽĐĐƖ=*


Explanation:

←                Get input
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

• in what code page is that 9 bytes? (in UTF-8 it's 17 bytes) Commented Dec 11, 2018 at 22:08

# Vyxalr, 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


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