45
\$\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\$
16
  • 5
    \$\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\$
    – Offtkp
    Jan 6, 2017 at 14:56
  • 2
    \$\begingroup\$ Unless if it's a falsy statement in your programming language, then no. \$\endgroup\$
    – Offtkp
    Jan 6, 2017 at 16:57
  • 3
    \$\begingroup\$ May I want the number to be input in ternary? \$\endgroup\$ Jan 6, 2017 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, 2017 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, 2017 at 9:57

66 Answers 66

24
\$\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\$
5
  • \$\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, 2017 at 15:53
  • \$\begingroup\$ Fixed, thank you! @Rod then it would return [n] instead of n I think \$\endgroup\$
    – nmjcman101
    Jan 6, 2017 at 15:58
  • \$\begingroup\$ @nmjcman101 that shouldn't be a problem \$\endgroup\$
    – Rod
    Jan 6, 2017 at 16:01
  • \$\begingroup\$ @Rod I'd prefer adhering strictly to spec for now \$\endgroup\$
    – nmjcman101
    Jan 6, 2017 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, 2017 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\$
1
  • \$\begingroup\$ PS: Try it online! supports Haskell! (Nice answer btw!) \$\endgroup\$
    – flawr
    Jan 6, 2017 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\$
6
  • \$\begingroup\$ 05AB1E is apparently good at base conversion is this really the best approach? \$\endgroup\$
    – Jasen
    Jan 7, 2017 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, 2017 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, 2017 at 11:43
  • 1
    \$\begingroup\$ @Jasen <3zm©.ïi® is the closest I've got not using ranges like he did. \$\endgroup\$ Jan 10, 2017 at 15:28
  • 1
    \$\begingroup\$ 3DÝms<k... Nevermind... Can't shave off one more byte, could of sworn I could. \$\endgroup\$ Jan 12, 2017 at 19:33
11
\$\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\$
0
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\$
1
  • \$\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, 2017 at 5:06
5
\$\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\$
2
  • \$\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, 2017 at 18:17
  • \$\begingroup\$ @ais523 That's correct, : is a control symbol, and ~ only works on predicates. \$\endgroup\$
    – Fatalize
    Jan 6, 2017 at 18:35
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\$
4
  • 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\$
    – Offtkp
    Jan 6, 2017 at 21:22
  • 2
    \$\begingroup\$ That's genius! +1 for a very clever approach \$\endgroup\$
    – DJMcMayhem
    Jan 6, 2017 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, 2017 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, 2017 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\$
7
  • \$\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, 2017 at 16:51
  • \$\begingroup\$ Wait, so can I return 0 now? \$\endgroup\$
    – user41805
    Jan 6, 2017 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, 2017 at 16:53
  • \$\begingroup\$ I thougt Processing was supposed to be less versbose than Java \$\endgroup\$
    – Pavel
    Jan 7, 2017 at 8:24
  • \$\begingroup\$ @Pavel But I don't use lambdas :/ \$\endgroup\$
    – user41805
    Jan 7, 2017 at 8:35
5
\$\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\$
4
\$\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\$

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

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

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I also tried the log approach but couldn't make it shorter: (0,($t=[math]::log(1+"$args",3)))[$t-eq[int]$t] \$\endgroup\$
    – Julian
    Nov 25, 2020 at 4:13
  • 1
    \$\begingroup\$ 40 bytes :) \$\endgroup\$
    – mazzy
    Nov 25, 2020 at 20:57
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\$
10
  • \$\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, 2017 at 15:56
  • \$\begingroup\$ 65 byte solution \$\endgroup\$
    – mbomb007
    Jan 6, 2017 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, 2017 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\$ Jan 6, 2017 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, 2017 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\$
0
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\$
3
  • \$\begingroup\$ Save one byte with a%3<1 instead of !(a%3). One more with 0 for falsy. \$\endgroup\$
    – Titus
    Jan 7, 2017 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\$ Jan 9, 2017 at 20:26
  • 1
    \$\begingroup\$ Suggest a%3?0:(a/=3) instead of !(a%3)&&(a/=3) \$\endgroup\$
    – ceilingcat
    Dec 11, 2018 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\$
13
  • 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, 2017 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, 2017 at 6:54
  • \$\begingroup\$ double is a type of floating point value so he problem persists. \$\endgroup\$
    – Jasen
    Jan 7, 2017 at 7:29
  • \$\begingroup\$ seems to work ok for 3^19 which is probably large enough. \$\endgroup\$
    – Jasen
    Jan 7, 2017 at 7:35
  • \$\begingroup\$ @Jasen It doesn't work for 3^10 \$\endgroup\$
    – Wade Tyler
    Jan 7, 2017 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\$
1
  • \$\begingroup\$ in what code page is that 9 bytes? (in UTF-8 it's 17 bytes) \$\endgroup\$
    – Jasen
    Dec 11, 2018 at 22:08
2
\$\begingroup\$

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
\$\endgroup\$
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\$
4
  • \$\begingroup\$ Does not output x nor -1. \$\endgroup\$
    – dfernan
    Jan 6, 2017 at 15:17
  • \$\begingroup\$ The program should output x instead of n in case of a match. \$\endgroup\$
    – dfernan
    Jan 6, 2017 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\$
    – Offtkp
    Jan 6, 2017 at 15:22
  • \$\begingroup\$ @P.Ktinos Fixed it. \$\endgroup\$
    – mbomb007
    Jan 6, 2017 at 15:31
1
\$\begingroup\$

Pyth, 10 bytes

*J@hQ3!%J1

Try it 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.