Wie Fermat ist diese Nummer?

13

Fermat-Zahlen sind positive ganze Zahlen, die mit einer ganzen Zahl x als 2 2 x +1 ausgedrückt werden können .

Definieren wir nun ein Attribut einer Zahl namens "Fermat-ness":

  • Die Fermat-ness der Zahl ist eins weniger als die Länge der Kette von Zweierpotenzen, ausgehend von der Basis, wobei Zweierpotenzen erweitert werden, um die Fermat-ness zu maximieren.
  • Eine Zahl, die keine Fermat-Zahl ist, hat die Fermat-Ness von Null.

17 (= 2 2 2 2 0 +1) hat also Fermat-ness drei.

Herausforderung

Bei einer positiven Ganzzahl ungleich Null als Eingabe wird die Fermat-ness der Zahl ausgegeben.

Regeln

  • Sie können die Eingabe in Binär, Dezimal, Hexadezimal, als Bignum oder in einem beliebigen Format verwenden, mit dem Sie am besten Golf spielen können
  • Ihre Lösung muss in der Lage sein, Zahlen mit Bitlängen über 64 zu verarbeiten, je nachdem, welche Darstellung Sie verwenden.
  • Nur nichtnegative ganzzahlige Potenzen.
  • Standardlücken sind natürlich verboten.
  • Das ist , also gewinnt die kürzeste Antwort.

Testfälle

Diese sind im Format input->output. Die Eingabe erfolgt aus Platzgründen hexadezimal.

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

Das Gleiche in Dezimalzahl:

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

Dank Geokavel für unschätzbare Beiträge im Sandkasten.

HAEM
quelle
1
Wenn ich 1111 eingebe, woher weißt du, dass es binär, dezimal oder hexadezimal ist?
J42161217
1
@Jenny_mathy Ich wollte, dass der Anrufbeantworter entscheidet, welches Eingabeformat er möchte.
HAEM
@ Mr.Xcoder Es ist in der Sandbox aufgetaucht, dass es wirklich nicht viele Fermat-Zahlen von 64 Bit oder weniger gibt. Ich behaupte, dass sich die Frage im Grunde genommen um Bignums handelt, damit ich die Verarbeitung von Bignum fordern kann.
HAEM
2
@ HeikkiMäenpää Denk dran, egal was andere empfehlen, die Herausforderung liegt bei dir und du kannst sie zu dem machen, was du willst.
Isaacg
3
Ich denke, es ist zu früh, um zu akzeptieren. Normalerweise 1 oder 2 Wochen warten. Einige sagen, niemals zu akzeptieren!
Geokavel

Antworten:

7

Jelly , 15 14 Bytes

1 Byte danke an Jonathan Allan.

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

Probieren Sie es online!

Undichte Nonne
quelle
2
Speichern Sie ein Byte mit: BḊCL⁸Ạ?->BḊ⁸LṀ?
Jonathan Allan
1

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

Probieren Sie es online!

Ich erkannte, dass es mir helfen würde, meine Byteanzahl zu senken, wenn ich nicht dumm war, also tat ich das. Auch Potenzierung im Gegensatz zu Logarithmen.

Arnold Palmer
quelle
0

RProgN 2 , 75 Bytes

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

Probieren Sie es online!

Es sind nur 70 Bytes, wenn Sie nicht die addieren, die «»'¤=dem ¤Zeichen die Fermatness-Berechnung zuweist . Wenn Sie dies tun, müssen Sie die Nummer in den Header-Bereich von TIO anstatt wie bisher in die Fußzeile einfügen.

Dies verwendet praktisch die gleiche Logik wie meine Python-Antwort. Wenn Sie sich also nicht dafür interessieren, wie RProgN 2 funktioniert, schauen Sie sich einfach diese an, um zu erklären, was los ist. Andernfalls

Code-Aufschlüsselung:

«\`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

Leider fehlt der Log-Funktion Šund der normalen Exponentiation ^die Genauigkeit, um dies nativ zu tun, so dass ich neu definieren musste, wie die Exponentiation funktioniert, da die Multiplikation viel präziser ist. Ohne diese Neudefinition wäre diese Antwort 23 Byte kürzer.

Arnold Palmer
quelle