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

1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ If you do a*!a%%1 it will output a if true and 0 otherwise and you can skip the if thing. \$\endgroup\$ – Billywob Jan 6 '17 at 16:07
  • \$\begingroup\$ The spec says "If it can't, output -1 or a falsy statement." and 0 is interpreted as FALSE in R so I would say it's valid. \$\endgroup\$ – Billywob Jan 6 '17 at 16:19
1
\$\begingroup\$

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;}
\$\endgroup\$
  • \$\begingroup\$ I think you save bytes by using pow(3,i) instead of defining your own. Gcc complains about the missing #include <math.h> but compiles it anyway. I did have to cast to int. You also may be able to gain some by adding an r variable, initializing to -1, and then if(n==k-1)r=i;}return r;} \$\endgroup\$ – nmjcman101 Jan 6 '17 at 18:54
  • 2
    \$\begingroup\$ @nmjcman101 Thanks, but pow() produces some incorrect results because of floating point inaccuracy. (When cast to int, 2.9999 will be 2, not 3). Adding a variable r sounds like a good idea, but it actually results in a 2 bytes longer code. \$\endgroup\$ – Steadybox Jan 6 '17 at 22:33
  • \$\begingroup\$ yeah, log doesn't work, pow probably won't either. \$\endgroup\$ – Jasen Jan 7 '17 at 9:28
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Very nice solution. \$\endgroup\$ – Oliver Jan 7 '17 at 6:04
1
\$\begingroup\$

GolfScript, 11 bytes

~..3\?\)%!*

Try it online!

Uses the fact that 3n 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.)

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

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.

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

C, 76 bytes

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

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

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

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 
}
\$\endgroup\$
  • \$\begingroup\$ I think you don't have to use uint16_t. You can use normal int. \$\endgroup\$ – Roman Gräf Jan 8 '17 at 19:55
  • \$\begingroup\$ I guess I could to save a few bytes but it seemed to me that if I wasn't safeguarding against negative integer input then I wasn't following the guidelines. \$\endgroup\$ – mreff555 Jan 14 '17 at 21:04
  • \$\begingroup\$ this compile to me: int f(n){float o=log1p(n)/log(3);return o/floor(o)!=1?-1:o;} \$\endgroup\$ – RosLuP Apr 29 '17 at 15:53
  • 1
    \$\begingroup\$ @mreff555 You don't need to safeguard against negative input, you can assume positive input. \$\endgroup\$ – Erik the Outgolfer Apr 29 '17 at 16:05
1
\$\begingroup\$

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.

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

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
\$\endgroup\$
  • \$\begingroup\$ "26 can be written as (3^3) - 1" 124 can be written as (5^3)-1 but your code for 124 not print 5 print 0 \$\endgroup\$ – RosLuP Feb 2 '18 at 15:48
  • \$\begingroup\$ Ok I confuse exponent and base \$\endgroup\$ – RosLuP Feb 2 '18 at 15:51
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "26 can be written as (3^3) - 1" 124 can be written as (5^3)-1 but your code for 124 not print 5 print 0 \$\endgroup\$ – RosLuP Feb 2 '18 at 15:47
  • \$\begingroup\$ @RosLuP I believe the output of my program is correct, and other answers seem to agree \$\endgroup\$ – Mr. Xcoder Feb 2 '18 at 15:49
  • \$\begingroup\$ Ok I confuse the exponent and the base \$\endgroup\$ – RosLuP Feb 2 '18 at 15:50
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ "26 can be written as (3^3) - 1" 124 can be written as (5^3)-1 but your code for 124 not print 5 print 0 \$\endgroup\$ – RosLuP Feb 2 '18 at 15:44
  • \$\begingroup\$ Ok I confuse exponent and base \$\endgroup\$ – RosLuP Feb 2 '18 at 15:51
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ "26 can be written as (3^3) - 1" 124 can be written as (5^3)-1 but your code for 124 not print 5 print 0 \$\endgroup\$ – RosLuP Feb 2 '18 at 15:45
  • \$\begingroup\$ Ok I confuse exponent and base \$\endgroup\$ – RosLuP Feb 2 '18 at 15:52
  • \$\begingroup\$ @RosLuP you mind deleting the comments? people use to DV without much thinking when seeing these \$\endgroup\$ – Uriel Feb 3 '18 at 16:17
1
\$\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\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ This is 28 bytes in NARS, but exactly the same solution is only 14 bytes in Dyalog APL. Also, you can save two bytes by conversion to tradfn, r×r=⌊r←3⍟1+⎕, letting the program prompt for input. \$\endgroup\$ – Adám Dec 25 '17 at 16:15
  • \$\begingroup\$ @Adám i prefer functions \$\endgroup\$ – RosLuP Dec 25 '17 at 19:47
1
\$\begingroup\$

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

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.

\$\endgroup\$
  • \$\begingroup\$ I think f=(n,p,k=1)=>n<k?n>k-2&&p:f(n,-~p,k*3) works and saves 2 bytes. \$\endgroup\$ – Arnauld Jan 7 '17 at 0:24
0
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ gives wrong answer for 242 input \$\endgroup\$ – Jasen Jan 7 '17 at 9:22
  • \$\begingroup\$ @Jasen: The downvote was ridiculous, but it´s fixed now. \$\endgroup\$ – Titus Jan 7 '17 at 11:36
0
\$\begingroup\$

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 log3 the number, and if it's a integer, print it; otherwise, print -1. Could use some work.

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

\$\endgroup\$
  • \$\begingroup\$ Why is this non-competing? The Non-Competing status is only reserved for languages or language features that were added after the challenge was posted. \$\endgroup\$ – Cows quack Jan 7 '17 at 11:10
  • \$\begingroup\$ As I said, size doesn't matter, so this can compete. \$\endgroup\$ – P. Ktinos Jan 7 '17 at 20:55
  • \$\begingroup\$ @KritixiLithos Oh okay. I wasn't aware of the exact meaning of Non-Competing. Thanks. Also, I'll update the title. \$\endgroup\$ – HyperNeutrino Jan 8 '17 at 3:19
  • 1
    \$\begingroup\$ You can use interface A{...} and drop the public from main(). Why do you have (a) instead of a in the while loop. I think you can use float k=... instead of double k=.... Should be -5 bytes if I counted right. \$\endgroup\$ – Roman Gräf Jan 8 '17 at 20:04
  • \$\begingroup\$ @RomanGräf I appreciate your suggestions; however, none of them are of any use for me, unfortunately. Your first suggestion only works in Java 8, and there is already a far better Java 8 solution out there. I have (a) in the while loop because I am doing a comparison of an assignment statement, and assignment has the lowest priority on the order of operations and thus requires a set of brackets around it. Finally, I have double because Math#log returns a double and casting would obviously be much slower. Regardless, thank you for the suggestions, but I will not be incorporating them. \$\endgroup\$ – HyperNeutrino Jan 9 '17 at 3:20
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ "Trinary" is more commonly referred to as Ternary. \$\endgroup\$ – FlipTack Jan 9 '17 at 18:23
0
\$\begingroup\$

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");     
  } 
}
\$\endgroup\$
  • \$\begingroup\$ for x=1 what would return/print that above? \$\endgroup\$ – RosLuP Apr 29 '17 at 15:43
0
\$\begingroup\$

SmileBASIC, 32 bytes

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

Outputs 0 for false.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

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

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

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

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