Is it a tetrate of two?

Question

The tetration operation consists of repeated exponentiation, and it is written ↑↑. For instance,

3↑↑3 =3 ^(3^3) = 3^27 = 7,625,597,484,987

A tetrate of two is an integer that is equal to 2↑↑n for some nonnegative integer n. As an edge case, we say that 2↑↑0=1.

In this challenge, you will be given a positive integer as input, and you must output whether the integer is a tetrate of two.

The list of tetrates of two is:

1, 2, 4, 16, 65536, 2^65536, ...

This sequence is OEIS A014221.

---

Your answer need only give the correct answer up to the limits of your datatype and/or addressable memory, but your algorithm should be theoretically correct for all inputs.

You must take an integer as input and output whether it is a terate of two. Outputting the sequence of tetrates of two is not allowed.

All standard input and output methods are allowed. Standard output distinctions for decision problems are allowed: truthy/falsy or any two consistent results.

This is code golf: shortest program in each language wins.

---

Bonus challenge: There is an extremely short solution for this challenge in Pyth. Whenever a Pyth solution is posted, I'll let you know whether a shorter solution exists. If and when someone matches or beats my program, I'll give them a 200 point bounty.

Answer 1

05AB1E, 5 bytes

Δ.²}d

Attempt This Online!

Takes log 2 until it doesn't change, and tests if it's nonnegative. In 05AB1E for \$x\leq0\$, when log 2 isn't defined, it's \$x\$, so for tetrates the fixed point will be 0, and for other numbers it will be a negative value.

Answer 2

Pyth, 2 bytes

Outputs via exit code

ul

Attempt This Online!

This method mirrors @Command Master's answer, repeatedly applying log base 2 until stable, but log(0) is considered an error, thus bypassing the need for checks.

Pyth, 5 bytes

.x!ul

Attempt This Online!

Same as above, but uses a try/catch to output to stdout instead of as a exit code

Answer 3

J, 7 bytes

2&^.^:_

Attempt This Online!

Similarly to Command Master's 05AB1E answer, this applies log 2 to the input until it doesn't change. The difference is that the logarithm is also defined on zero, positive/negative infinity, and complex numbers.

For tetrations of two, the logarithm eventually hits 0, and then it jumps over a couple of complex infinities to finally get to _ (infinity).

For other values, it looks like every possible input eventually converges to the fixed point of complex logarithm with base 2, which is the complex number

$$ 0.82467854614201552277 + 1.56743212384969488049 i $$

This Math.SE answer seems to support it, showing that logarithm with base 2 is stable since 2 > 1.96.

So the output format of this function is two consistent values, _ for truthy and 0.824679j1.567432 for falsy.

Answer 4

Haskell, 21 bytes

f n=until(>=n)(2^)0>n

Try it online!

Outputs True/False negated

Starts with i=0 and does i=2^i until i>=n, then checks whether the result is greater than n versus exactly n. Except this is all point-free using until, so i is never mentioned.

Answer 5

Python 3, 36 bytes

f=lambda n,i=0:i>n or f(n,2**i)^i//n

Try it online!

Outputs 0 for yes, 1 for no.

Also 36 bytes:

f=lambda n,i=0:i<n>0<f(n,2**i)or i>n

Try it online!

Answer 6

Uiua ^SBCS, 9 bytes

±⍢(ₙ2|>0)

Try it!

Outputs 0 if the input is a tetrate and ¯1 if not. Very similar to other answers that repeatedly take log2, but I have to get a bit more specific than taking a fixed point because everything ends up at NaN if you do that.

Answer 7

Python, 35 bytes

f=lambda x,t=1:x<t or x*f(x,2**t)>t

Attempt This Online!

Answer 8

Python, 32 bytes

f=lambda n,i=1:n==i or f(n,2**i)

Attempt This Online!

My idea was invalid in JS, because the recursion limit isn't guaranteed, but it's OK in Python because of that difference. Output via exit code, errors out to indicate false.

In the test harness I set the recursion limit to a very low number because with the default limit of 1000, it would take quite a while to check any false test cases.

Answer 9

Python, 37 bytes

f=lambda x:x>0<f(len(bin(x))-3)+~-x&x

Attempt This Online!

Python, 38 bytes

f=lambda x:x<2or~-x&x<f(len(bin(x))-3)

Attempt This Online!

Answer 10

Nekomata + -e, 8 bytes

0ʷ{ᵖ>Ë}=

Attempt This Online!

A port of @xnor's Haskell answer.

0ʷ{ᵖ>Ë}=
0           Push 0
 ʷ{   }     While:
   ᵖ>           it is smaller than the input
     Ë          Take the power of 2
       =    Check if the result is equal to the input

Answer 11

x86 32-bit machine code, 10 bytes

0F BD C8 0F BB C8 91 E3 F7 C3

Try it online!

Following the regparm(1) calling convention, this function takes a number in EAX and returns a number in EAX, which uses reversed truthy/falsy – it is 0 for tetrates of two and nonzero otherwise.

In assembly:

f:  bsr ecx, eax    # Set ECX to the highest position of a 1 bit in EAX.
        # If EAX was 0, the new value of ECX is officially undefined,
        # but on at least some CPUs it is unchanged, as this program needs.
        # In particular, if EAX is 2^n, ECX is n.
    btc eax, ecx    # Invert that bit in EAX.
                    # This makes EAX zero iff it was a power of 2.
    xchg eax, ecx   # Exchange the values of EAX and ECX.
    jecxz f         # Jump back, to repeat, if ECX is 0.
    ret             # Return. EAX holds the return value.
        # For tetrates of 2, the process ends at 0.
        #  ECX is 0 after the penultimate iteration, and is left unchanged
        #  before being swapped into EAX in the last iteration, returning 0.
        # For non-tetrates of 2, it ends at some nonzero non-power of 2.
        #  Its highest position of a 1 bit is nonzero, and that's returned.

Answer 12

Charcoal, 18 14 bytes

ＮθＷ›θⅈＪＸ²ⅈ⁰⁼θⅈ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a tetrate, nothing if not. Explanation:

Ｎθ

Input the integer.

Ｗ›θⅈ

While it is greater than the current tetration...

ＪＸ²ⅈ⁰

... calculate the next tetration.

⁼θⅈ

Test whether the value equals the tetration.

Answer 13

Lua, 134 bytes

function t(n)if n==1 or n==2 then return 1 end if n>=0 and n<3 then return 0 end return t(math.sqrt(n))end print(t(io.read("number")))

Try it online!

---

Explanation

Prints 1 if the value is a tetration of two, otherwise 0.

We create a recursive function called t that takes a number n as the argument. If n is exactly equal to 1 or 2, we return 1. Otherwise we do another check: if n is greater than or equal to 0 and less than 3 (a decimal value, e.g., 0.541..., 1.141... and 2.852...), we return 0. If both checks are false, we take the square root of n and rerun the recursive function t.

function t(n)
    if n==1 or n==2 then
        return 1
    end
    if n>=0 and n<3 then
        return 0
    end
    return t(math.sqrt(n))
end

Finally, we call this function and print it's return.

print(t(io.read("number")))

Answer 14

Rattle, 15 bytes

|s[e.5[2q]]`g<3

Try it Online!

This outputs 2 if the number is a tetrate of 2, 0 otherwise.

Explanation

|                 take input
 s                save input to memory
  [.......]`      loop n times, n = value in memory (i.e. the input)
   e.5            exponentiate to 0.5 (square root)
      [2 ]        if equal to 2,
        q         quit (top of stack, 2, is printed implicitly)
            g     get the value in memory (the original input)
             <3   check if smaller than 3 (1,2 are special cases)
                  output the result implicitly

A different (first) approach:

Rattle, 17 bytes

|s=2[[~=1q]e]~g<2

Try it Online!

This outputs 1 for tetrates of 2, 0 otherwise. This solution is not computationally efficient, but is theoretically valid for all inputs.

Explanation

|                   take input
 s                  save input to memory
  =2                set top of stack to 2
    [.......]~      loop n times, n = value in memory (i.e. the input)
     [~...]         if the top of the stack is equal to the value in memory 
                        (e.g. the input is a tetrate of 2)
       =1           set the top of the stack to 1
         q          quit, the top of the stack is printed implicitly (1)
           e        exponentiate (by 2 without an argument)
              g     get the value in memory (the original input)
               <2   check if smaller than 2 (1 is a special case) 
                    output the result implicitly 

Answer 15

MathGolf, 8 bytes

0æó_k<▲=

Port of @xnor's Haskell answer, so make sure to upvote that answer as well!

Try it online.

Explanation:

0         # Push a 0
      ▲   # Do while true with pop,
 æ        # using 4 character as inner code-block:
  ó       #  Take 2 to the power the current integer
   _      #  Duplicate it
    k     #  Push the input-integer
     <    #  Check that the duplicated integer is smaller than the input
       =  # After the do-while: check if the integer equals the (implicit) input
          # (after which the entire stack is output implicitly as result)

Answer 16

C (gcc), 37 bytes

f(x){x=x&&f(__builtin_ctz(x))+~-x&x;}

Try it online!

Answer 17

Haskell + hgl, 22 bytes

eq~<F yyc 0<lii(2^)<ge

This version uses the lii function which is not yet available in the online version.

Explanation

First we create a function that applies (2^) to the input if its greater than or equal to the input:

lii(2^)<ge

Then we apply that to zero until it reaches a fixed point:

F yyc 0

And we check if that equals the initial input:

eq

Works on ato, 27 bytes

f=l2p nø(oR**or$f<l)<nt<bi

Attempt This Online!

Outputs the opposite value, i.e. False if it is tetrate, True otherwise.

Explanation

A recursive function that converts to binary, removes the first bit, returns true if the result is empty, otherwise check whether all remaining bits are zero and if the length of the list is a tetrate of 2.

Reflection

I'm really not sure this is the most efficient way to solve the problem, but it's what I have.

I will point out that hgl just isn't good at arithmetic like this. It's always good to try and improve its capabilities, but we shouldn't expect too much.

• In the continuing saga of adding l2 variants, l2 oR can be added.

• Checking if a list is all false can be done in a bunch of 4 byte ways:

  • mF n,
  • ne T,
  • n<or,
  • n<mx,

  and an honorable mention to the 5-byte

  • no id,

  however there should be a 2-byte builtin.

• I was annoyed a bunch by the infix precedence of the l2 variants. This should be fixed.

• The precedence of (/$) should be something else.

• There should be a flipped verson of yyc. There should be a flipped version of everything that can be flipped, I have no idea why I didn't implement this before.

• There should be a builtin for checking if something is a power of 2, and other powers as well.

• I keep saying I need to add an inclusion check on monotonic lists. But I keep getting distracted. This would help here.

• Obviously I need to implement until.

Answer 18

Vyxal 3, 3 bytes

ᶨ2Ŀ

Try it Online!

Errors if falsey, outputs a list ending in zero otherwise

Answer 19

Google Sheets, 47 bytes

=let(_,lambda(_,n,if(n,_(_,log(n,2)))),_(_,A1))

Put \$n\$ in cell A1 and the formula in cell B1.

Takes \$log2(n)\$ recursively until either a zero or a negative number is reached. Returns false for true and #NUM! for false.

Cleaner solution, 64 bytes:

=let(_,lambda(_,n,ifs(n=0,1,int(n)<n,,1,_(_,log(n,2)))),_(_,A1))

Takes \$log2(n)\$ recursively until either a zero or a non-integer is reached. Returns 1 for true and blank for false.

Answer 20

Scala 3, 40 bytes

n=>Seq.iterate(0,n)(math.pow(2,_).toInt)

Attempt This Online!

Answer 21

Ada, 93 89 bytes

function T(I:Integer;D:Integer:=1)return Boolean is(I=D or else(I>D and then T(I,2**D)));

This is a recursive function that:

• Accepts I as the argument and defaults D (which will walk through all applicable tetrates) to 1
• Checks if I is equal to D, the current tetrate. If so, it short circuits out, returning True.
• Checks if I is less than D, meaning D has passed I and we don't need to check any more. If so, it short circuits out, returning False.
• Calls itself with I and the next tetrate, calculated by 2**D.

Being recursive allows the use of an expression function, which has much shorter syntax, and eliminates a loop syntax.

Works up through 65536.

Answer 22

Perl 5 -p, 35 34 bytes

$_=(log)/log 2until/\.|^0$/;$_=!$_

Try it online!

Answer 23

APL (Dyalog Unicode), 5 bytes ^SBCS

Output via emitting an error. Same as @Mukundan314's answer.

2∘⍟⍣≡

Try it online!

Answer 24

PARI/GP, 52 bytes

f(n)={s=vector(n);s[1]=0;for(i=2,n,s[i]=2^s[i-1]);s}

Attempt This Online!

Answer 25

Pip, 11 7 bytes

a&RELBa

Outputs 0 for tetrates of 2, nil for other inputs. Attempt This Online!

Explanation

Uses a recursive main program to implement the repeated-logarithm approach pioneered by Command Master. In a surprising oversight for a language with operators for all six trig functions, Pip doesn't have an operator for log base 2. Now it does. :^P

a&RELBa
a&       ; ‎⁡If the argument is falsey, return it
  RE     ; ‎⁢Otherwise, recurse with this value:
    LBa  ; ‎⁣Base-2 log of the argument
         ; ‎⁤Tetrates of two end up at 0, which is falsey; other values end up at
         ; ‎⁤a negative value, whose log is nil (falsey)
💎

Created with the help of Luminespire.

Answer 26

Easyfuck, 37 33 bytes

D‘ňŰo␐SHY[­HOPC␅iě)V®ßÜ
-°Obę—ĘŢ]|‘‚ŰNBSP

^{due to lack of unicode representations for c1 control characters, they have been replaced by their superscripted abbreviations}

Decompressed:

"$>-[<!--`(0+'X)++[}`([0'X])>+<]>$0-]

The program works by right-shifting the input until a 1 is shifted off. If the number is non-zero it prints a 0 and terminates. It then checks if the number of shifts was 1, if it was, it prints a 1 and terminates, else it repeats the whole procedure on the number of shifts. The program is limited to 8-bit unsigned integers.