13
\$\begingroup\$

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.

Challenge

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

Rules

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

\$\endgroup\$
  • 1
    \$\begingroup\$ If I input 1111, how do you know it is in binary, decimal or hexadecimal??? \$\endgroup\$ – J42161217 Jul 29 '17 at 10:19
  • 1
    \$\begingroup\$ @Jenny_mathy I meant for the answerer to decide what format of input they want. \$\endgroup\$ – HAEM Jul 29 '17 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 '17 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 '17 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 '17 at 7:05
7
\$\begingroup\$

Jelly, 15 14 bytes

1 byte thanks to Jonathan Allan.

’µBḊ⁸LṀ?µÐĿḊḊL

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Save a byte with: BḊCL⁸Ạ? -> BḊ⁸LṀ? \$\endgroup\$ – Jonathan Allan Jul 29 '17 at 13:09
1
\$\begingroup\$

Python 2, 103 81 bytes

n=input()-1
i=l=0
while 2**2**i<=n:
 if n==2**2**i:n=2**i;i=-1;l+=1
 i+=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.

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

RProgN 2, 75 bytes

«\`n=1\]{1-\n*\]}:[»`^=«1-`n=001{]2\^2\^ne{2\^`n=1+0}{1+}?]2\^2\^n>¬}:[»`¤=

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:

«\`n=1\]{1-\n*\]}:[»`^=
«                  »`^=`                            # 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.

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

Perl 6, 62 bytes

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

Try it online!

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