Finden Sie das n-te Fibohexaprim

23

Die Herausforderung besteht diesmal darin, das n- te Fibohexaprim zu finden . Die Definition eines Fibohexaprims lautet wie folgt:

Wir beobachten zunächst eine Liste mit Fibonacci-Zahlen:

N  | Fibonacci number
1  | 1 
2  | 1 
3  | 2 
4  | 3 
5  | 5 
6  | 8 
7  | 13 
8  | 21 
9  | 34 
10 | 55 
11 | 89 
12 | 144 
13 | 233 
14 | 377 
15 | 610
16 | 987 
17 | 1597

Danach konvertieren wir die Zahlen in Hexadezimalzahlen:

N  | Fib  | Hex 
1  | 1    | 1
2  | 1    | 1
3  | 2    | 2
4  | 3    | 3
5  | 5    | 5
6  | 8    | 8
7  | 13   | D
8  | 21   | 15
9  | 34   | 22
10 | 55   | 37
11 | 89   | 59
12 | 144  | 90
13 | 233  | E9
14 | 377  | 179
15 | 610  | 262
16 | 987  | 3DB
17 | 1597 | 63D

Aus den hexadezimalen Zahlen filtern wir die Buchstaben heraus. Wir haben nur noch Zahlen. Wir müssen prüfen, ob diese Zahlen Primzahlen sind:

hex |  filtered |  is prime? |  N =
1   >  1        >  false
1   >  1        >  false
2   >  2        >  true         1
3   >  3        >  true         2
5   >  5        >  true         3
8   >  8        >  false
D   >  0        >  false
15  >  15       >  false
22  >  22       >  false
37  >  37       >  true         4
59  >  59       >  true         5
90  >  90       >  false
E9  >  9        >  false
179 >  179      >  true         6
262 >  262      >  false
3DB >  3        >  true         7
63D >  63       >  false

Wenn die gefilterte Zahl eine Primzahl ist, nennen wir dies ein Fibohexaprime . Sie können sehen, dass für N = 7die verwandte Fibonacci-Nummer 987 ist.

Die Aufgabe ist einfach, wenn eine Eingabe mit STDIN oder einer akzeptablen Alternative gegeben wird, ein Programm oder eine Funktion zu schreiben, die das n-te Fibohexaprime mit STDOUT oder einer akzeptablen Alternative ausgibt.

Testfälle

Input - Output
1     - 2
2     - 3
3     - 5
4     - 55
5     - 89
6     - 377
7     - 987
8     - 28657
9     - 75025
10    - 121393
11    - 317811
12    - 5702887
13    - 9227465
14    - 39088169
15    - 102334155
16    - 32951280099
17    - 4052739537881
18    - 806515533049393
19    - 7540113804746346429

Die Regeln:

  • Geben Sie bei einer Ganzzahl zwischen 1und 19(die obigen Werte 20überschreiten den Maximalwert für eine 64-Bit-Ganzzahl mit Vorzeichen) den entsprechenden Wert aus.
  • Sie können eine Funktion oder ein Programm schreiben.
  • Das ist , also gewinnt die Einsendung mit der geringsten Anzahl von Bytes!
Adnan
quelle
So wie es formuliert ist, klingt es, als müssten Funktionen auch aus STDIN lesen und in STDOUT schreiben. Ist das korrekt? Normalerweise erlauben wir Funktionen, Argumente zu akzeptieren und Werte als zweckmäßig zurückzugeben.
Alex A.
2
@AlexA. Beides sind akzeptable Alternativen. Das Lesen von STDIN und die Verwendung von STDOUT ist nicht obligatorisch.
Adnan

Antworten:

4

Pyth, 27 Bytes

Leu,eGsGbU2ye.fq1lPs-.HyZGQ

Demonstration

yberechnet die n-te Fibonacci-Zahl. Eine .fSchleife findet das Fibohexaprim entsprechend der Eingabe.

isaacg
quelle
12

MATL , 28 Bytes

Hierfür wird die MATL-Version 1.0.0 verwendet , die am 12. Dezember in Esolangs veröffentlicht wurde .

1Hi:"`tb+t16YAt58<)YtZp~]]1$

Beispiel

>> matl 1Hi:"`tb+t16YAt58<)YtZp~]]1$
> 10
121393

Erläuterung

Der Code ähnelt dem in Martin Büttners Antwort .

1           % number literal
H           % paste from clipboard H. Initial contents: 2
i:          % vector of equally spaced values from 1 to input value           
"           % for                      
  `         % do...while         
    t       % duplicate                           
    b       % bubble up element in stack          
    +       % addition 
    t       % duplicate                   
    16YA    % convert integer to string representation in base 16
    t       % duplicate             
    58      % number literal: first ASCII code after '9'           
    <       % is less than? (element-wise)    
    )       % reference () indexing with logical index from previous comparison
    Yt      % convert string to number 
    Zp      % true for prime numbers                                
    ~       % logical 'not'
  ]         % end                                                   
]           % end                                                   
1$          % input specification for final implicit display function
Luis Mendo
quelle
4
Die weltweit erste MATL-Antwort! Gute Arbeit, Luis!
Becher
1
Hurra für MATL! Willkommen in der Welt des Code Golfing!
Rayryeng - Monica
8

CJam, 28 Bytes

TXri{{_@+_Gb{A<},Abmp!}g}*p;

Teste es hier.

Erläuterung

TX        e# Push 0 and 1 to initialise Fibonacci computation.
ri        e# Read input and convert to integer N.
{         e# Run this block N times...
  {       e#   While the condition on top of the stack is truthy...
    _@+   e#     Compute next Fibonacci number (dropping the second-to-last one).
    _Gb   e#     Duplicate and convert to base 16.
    {A<}, e#     Keep only digits less than 10.
    Ab    e#     Convert from base 10.
    mp!   e#     Check that it's not a prime.
  }g
}*
p;        e# Print the last number we found and discard the one before.
Martin Ender
quelle
7

Perl 6 , 62 Bytes

Mein erster Versuch, es einfach zum Laufen zu bringen, war:

{(grep *[1].is-prime,map {$_,+[~] .base(16)~~m:g/\d/},(1,1,*+*...*))[$_-1;0]} # 77

Durch die Kombination von grepund mapkann ich 10 Bytes entfernen

{(map {$_ if is-prime [~] .base(16)~~m:g/\d/},(1,1,*+*...*))[$_-1]} # 67

Wenn ich grepanstelle von verwende map, spare ich 5 weitere Bytes:

{(grep {is-prime [~] .base(16)~~m:g/\d/},(1,1,*+*...*))[$_-1]} # 62

Verwendung:

# give it a name
my &code = {...}

say code $_ for 1..^20;

2
3
5
55
89
377
987
28657
75025
121393
317811
5702887
9227465
39088169
102334155
32951280099
4052739537881
806515533049393
7540113804746346429
Brad Gilbert b2gills
quelle
3

Mathematica 111 Bytes

Möglicherweise ist noch Platz für zusätzliches Golfen.

t=Table[Fibonacci@k,{k,1600}];f@n_:=PrimeQ@FromDigits[Select[n~IntegerDigits~16,#<10&]];
g@k_:=Select[t,f][[k]]

g[7]

987


g[19]

7540113804746346429

DavidC
quelle
3

Julia, 123 Bytes

n->(a=[];i=1;while endof(a)<n b=([1 1;1 0]^i)[1];(s=filter(isdigit,hex(b)))>""&&isprime(parse(s))&&push!(a,b);i+=1end;a[n])

Dies ist eine anonyme Funktion, die eine Ganzzahl akzeptiert und eine Ganzzahl zurückgibt. Um es zu nennen, geben Sie ihm einen Namen, z f=n->....

Ungolfed:

function f(n::Integer)
    # Initialize an array and an index
    a = []
    i = 1

    # Loop while we've generated fewer than n fibohexaprimes
    while endof(a) < n
        # Get the ith Fibonacci number
        b = ([1 1; 1 0]^i)[1]

        # Filter the hexadecimal representation to digits only
        s = filter(isdigit, hex(b))

        # If there are digits to parse, parse them into an
        # integer, check primality, and push the Fibonacci
        # number if prime
        s > "" && isprime(parse(s)) && push!(a, b)

        # Next
        i += 1
    end

    # Return the last generated
    return a[n]
end
Alex A.
quelle
3

GAP , 204 Bytes

Diese Antwort ist ziemlich unauffällig, außer dass GAP cool genug ist, um die nächsten paar Fibohexaprimes zu finden (und cooler noch, es findet diese in Millisekunden mit dem angegebenen Code).

gap>f(20);                                                                    
31940434634990099905
gap> f(21);
12776523572924732586037033894655031898659556447352249
gap> f(22);
971183874599339129547649988289594072811608739584170445
gap> f(23);
1324695516964754142521850507284930515811378128425638237225
gap> f(24);
187341518601536966291015050946540312701895836604078191803255601777

Beachten Sie, dass f (24) zwischen 2 ^ 216 und 2 ^ 217 liegt.

Hier ist der Code:

f:=function(n)local c,i,x;c:=1;i:=0;while c<=n do x:=HexStringInt(Fibonacci(i));RemoveCharacters(x,"ABCDEFGHIJKLMNOPQRSTUVWXYZ");x:=Int(x);if IsPrime(x) then c:=c+1;fi;i:=i+1;od;Print(Fibonacci(i-1));end;

Es gibt wahrscheinlich noch etwas Golf, das getan werden könnte. Ich denke, die Implementierung ist ziemlich unkompliziert.

Ungolfed:

f:=function(n)
    local counter,i,x;
    counter:=1;i:=0;
    while counter<=n do
        x:=HexStringInt(Fibonacci(i));
        RemoveCharacters(x,"ABCDEFGHIJKLMNOPQRSTUVWXYZ");
        x:=Int(x);
        if IsPrime(x) then
            counter:=counter+1;
        fi;
        i:=i+1;
    od;
    Print(Fibonacci(i-1));
end;
Liam
quelle
3

C, 186 183 Bytes

#include<stddef.h>
size_t a,b,c,d,m,x;size_t F(n){a=0,b=1;while(n){x=b;b+=a;a=x;c=0,m=1;while(x)d=x%16,m*=d<10?c+=m*d,10:1,x/=16;d=c>1;x=2;while(x<c)if(c%x++==0)d=0;d&&--n;}return a;}

Der Primalitätstest ist sehr ineffizient, daher wird die Berechnung ein wenig n > 16schwieriger und schmerzhaft langwieriger n = 19. Trotzdem funktioniert es und liefert die erwarteten Ergebnisse.

Der Code geht davon aus, dass size_tes sich um einen 64-Bit-Typ handelt, der sowohl für 64-Bit-Linux als auch für Windows gilt.


Bonus: Leider müssen wir 64-Bit-Typen verwenden, was zu einem Overhead von 33 Bytes führt. Die folgende Version funktioniert für die n <= 15Verwendung intund ist 150 Byte lang:

a,b,c,d,m,x;F(n){a=0,b=1;while(n){x=b;b+=a;a=x;c=0,m=1;while(x)d=x%16,m*=d<10?c+=m*d,10:1,x/=16;d=c>1;x=2;while(x<c)if(c%x++==0)d=0;d&&--n;}return a;}

Testleitung:

#include <stdio.h>

int main() {
  printf("Input - Output\n");
  for (int i = 1; i < 20; ++i) {
    printf("%2d    - %ld\n", i, F(i));
  }
}
Stefano Sanfilippo
quelle
Könnten Sie etwas sparen, size_tindem Sie das Include verwenden und löschen? Es ist implementierungsspezifisch, scheint aber 64-Bit sowohl unter 64-Bit-Linux als auch unter Windows zu sein (und seit wann kümmern wir uns um die Portabilität in Codegolf?). (Randnotiz: %ldist nicht 64-Bit in 64-Bit-Windows; muss %lld)
Bob
@ Bob Ich habe darüber nachgedacht, aber es size_tist kein eingebautes Element, es ist in stddef.h(das wiederum direkt oder indirekt von praktisch jedem anderen Header enthalten ist) definiert. So oder so, ich brauche eine #include. Ich kann immer noch 2 Bytes sparen, indem ich size_tstattdessen uint64_t:)
Stefano Sanfilippo
Auch danke für das lldbisschen, ich habe nicht die Chance bekommen, es unter Windows zu testen (aber Portabilität spielt keine Rolle, oder?)
Stefano Sanfilippo
Hm, es muss aus der stdio.hZeit gekommen sein, als ich getestet habe. Auf jeden Fall - Sie könnten immer noch ein paar sparen, indem Sie math.hanstelle von einschließen stddef.h.
Bob
math.hmacht nicht den Trick für mich (GCC 4.9 mit GNU libc)
Stefano Sanfilippo
2

Python 2, 127 Bytes

N=input();a,b=0,1
while N:a,b=b,a+b;t=int(''.join(c for c in hex(b)if ord(c)<65));N-=(t>1)*all(t%x for x in range(2,t))
print b

Der Algorithmus könnte viel effizienter sein. Insbesondere (t>1)*all(t%x for x in range(2,t))prüft die Primalitätsprüfung potenzielle Faktoren bis zu dem Punkt t-1, an dem sie tatsächlich nur bis zum Boden der Quadratwurzel prüfen müsste . Da rangein Python 2 eine ganze Liste im Speicher abgelegt ist, führt dies zu einem MemoryErrorat N=17(auf meinem Computer unter Verwendung der Standardeinstellungen).

mathmandan
quelle
2

Ruby, 160 Bytes

->i{t,o,k=[],[],0;f=->n{t[n]||=n<3?1:f[n-2]+f[n-1]};(r=('%x'%f[k]).scan(/\d/).join.to_i;(r>1&&(r==2||(2...r).none?{|j|r%j==0}))&&o<<r;k+=1)while !o[i-1];t[k-1]}

Ungolfed:

-> i {
  t, o, k = [], [], 0
  f = -> n {
    t[n] ||= n < 3 ? 1 : f[n-2] + f[n-1]
  }
  while !o[i-1] do
    r=('%x'%f[k]).scan(/\d/).join.to_i
    o << r if (r > 1 && (r == 2 || (2...r).none?{|j| r%j == 0 }))
    k+=1
  end
  t[k-1]
}

Verwendung:

# Assign the anonymous function to a variable
m = ->i{t,o,k=[],[],0;f=->n{t[n]||=n<3?1:f[n-2]+f[n-1]};(r=('%x'%f[k]).scan(/\d/).join.to_i;(r>1&&(r==2||(2...r).none?{|j|r%j==0}))&&o<<r;k+=1)while !o[i-1];t[k-1]}

m[2]
=> 3
m[19]
=> 7540113804746346429
Vasu Adari
quelle
2

R, 164 Bytes

g=function(n){f=function(m)ifelse(m<3,1,f(m-1)+f(m-2));p=0;while(n){p=p+1;x=gsub("\\D","",sprintf("%x",f(p)));x[x==""]=1;y=1:x;if(sum(!tail(y,1)%%y)==2)n=n-1};f(p)}

Mit neuen Zeilen eingerückt:

g=function(n){
    f = function(m)ifelse(m<3,1,f(m-1)+f(m-2)) #Fibonacci function
    p = 0
    while(n){
        p = p+1
        x = gsub("\\D","",sprintf("%x",f(p))) #To Hex, and get rid of non-digits
        x[x==""] = 1 #If x is empty string
        y = 1:x #Converts to integer(!) and save the 1-to-x sequence to a variable
        if(sum(!tail(y,1)%%y)==2) n = n-1 #If prime, decrements counter
        }
    f(p)
    }

Beispiele:

> g(1)
[1] 2
> g(5)
[1] 89
> g(10)
[1] 121393
> g(12)
[1] 5702887
Plannapus
quelle