Fermat numbers are positive integers that can be expressed as 22x+1 with an integer x.

Let us now define an attribute of a number called "Fermat-ness":

  • The Fermat-ness of the number is one less than the length of the chain of powers of two, starting from the base, with powers of two expanded so as to maximize the fermat-ness.
  • A number that is not a Fermat number has the Fermat-ness of zero.

So, 17 (=22220+1) has Fermat-ness three.


Given a positive nonzero integer as input, output the Fermat-ness of the number.


  • You may take the input in binary, decimal, hexadecimal, as a bignum, or whatever format lets you golf best
  • Your solution must be able to process numbers with bit-lengths over 64 whichever representation you use.
  • Nonnegative integer powers only.
  • Standard loopholes are of course prohibited.
  • This is , so shortest answer wins.

Test cases

These are in format input->output. The input is in hexadecimal to save space.

10000000000000000000000000000000000000000000000000000000000000001 -> 2
1000000000000BC00000000000000000000000000000000001000000000000001 ->0
1234567890ABCDEF -> 0
100000000000000000000000000000001 -> 1
5 -> 2
11 -> 3
10001 -> 4
101 -> 1

The same in decimal:

115792089237316195423570985008687907853269984665640564039457584007913129639937 -> 2
115792089237316497527923305698859709742143344804209838213621568094470773145601 -> 0
1311768467294899695 -> 0
340282366920938463463374607431768211457 -> 1
5 ->2
17 -> 3
65537 -> 4
257 -> 1

Thanks to geokavel for invaluable input in the sandbox.

  • 1
    \$\begingroup\$ If I input 1111, how do you know it is in binary, decimal or hexadecimal??? \$\endgroup\$
    – ZaMoC
    Jul 29, 2017 at 10:19
  • 1
    \$\begingroup\$ @Jenny_mathy I meant for the answerer to decide what format of input they want. \$\endgroup\$
    – HAEM
    Jul 29, 2017 at 10:21
  • \$\begingroup\$ @Mr.Xcoder It came up in the sandbox that there really aren't a lot of Fermat numbers of 64 bits or less. I'm claiming the question is intrinsically about bignums so I can demand bignum processing. \$\endgroup\$
    – HAEM
    Jul 29, 2017 at 10:26
  • 2
    \$\begingroup\$ @HeikkiMäenpää Remember, no matter what others may recommend, the challenge is yours, and you can make it what you want. \$\endgroup\$
    – isaacg
    Jul 29, 2017 at 10:42
  • 3
    \$\begingroup\$ I think it's too early too accept. Usually wait 1 or 2 weeks. Some say to never accept! \$\endgroup\$
    – geokavel
    Jul 31, 2017 at 7:05

4 Answers 4


Jelly, 15 14 bytes

1 byte thanks to Jonathan Allan.


Try it online!

  • 2
    \$\begingroup\$ Save a byte with: BḊCL⁸Ạ? -> BḊ⁸LṀ? \$\endgroup\$ Jul 29, 2017 at 13:09

Python 2, 103 81 bytes

while 2**2**i<=n:
 if n==2**2**i:n=2**i;i=-1;l+=1
print l

Try it online!

I realized not being stupid would help lower my byte count, so I did that. Also exponentiation as opposed to logarithms.


RProgN 2, 75 bytes


Try it online!

It's only 70 bytes if you don't add the «»'¤= which assigns the Fermatness calculation to the ¤ character. If you do that, you'll need to put the number in the Header section of TIO instead of in the Footer like it is now.

This effectively uses the same logic as my Python answer, so if you don't care about how RProgN 2 works, just look at that one for an explanation of what's going on. Otherwise

Code breakdown:

«                  »`^=`                            # Create a local function and assign it to the ^ character (x y ^ is x to the power of y)
 \`n=                                               # Swap the top two values of the stack and assign the new top to the variable n
     1\]                                            # Push a 1 (our starting point for x to the y), swap with the y value, then duplicate y
        {       }:                                  # Start a while loop that pops the top stack value and loops if it is truthy
         1-                                         # Subtract 1 from y to keep a tally of how many multiplications we've done
           \n*                                      # Swap the counter with our current value and multiply it by n
              \]                                    # Swap this new value with the current value of y, and duplicate it to be used as the truthy value for the loop

«1-`n=001{]2\^2\^ne{2\^`n=1+0}{1+}?]2\^2\^n>¬}:[»`¤=# The main Fermatness function (x ¤ to get the Fermatness of x)
«                                               »`¤=# Create another local function for this calculation
 1-`n=                                              # Decrement the input by 1 and assign it to n
      001                                           # Push a counter for Fermatness, a counter for calculating 2^2^i, and an initial truthy value
         {                                   }:     # Start a while loop for calculating the Fermatness
          ]2\^2\^ne                                 # Duplicate i, calculate 2^2^i, and compare it to n
                   {         }{  }?                 # Start an if statement based on the equality of 2^2^i and n
                    2\^`n=                          # n==2^2^i, so set n to 2^i (same as saying n=log_2(n))
                          1+0                       # Increment the Fermatness counter and reset i
                               1+                   # n!=2^2^i, so just increment i
                                   ]2\^2\^n>¬       # Duplicate the counter and check if 2^2^i<=n, if true the loop continues, else it exits
                                               [    # Pop i from the stack, leaving us with just the Fermatness counter

Unfortunately the log function Š and the normal exponentiation function ^ lack the precision to do this natively, so I had to redefine how exponentiation worked since multiplication carries much more precision. Without that redefine, this answer would be 23 bytes shorter.


Perl 6, 62 bytes

{my@a=first :kv,*>=0,(^∞).map(2**2** *+1-$_);++@a[0]*!@a[1]}

Try it online!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.