Find the nth Fibohexaprime

Question

The challenge this time is to find the nth Fibohexaprime. The definition of a Fibohexaprime is as following:

We first observe a list with Fibonacci numbers:

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

After that, we convert the numbers to hexadecimal:

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

From the hexadecimal numbers, we filter out the letters. All we are left with are numbers. We need to check if these numbers are prime:

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

If the filtered number is a prime, we call this a Fibohexaprime. You can see that for N = 7, the related fibonacci number is 987.

The task is simple, when given an input using STDIN or an acceptable alternative, write a program or a function which outputs the nth Fibohexaprime using STDOUT or an acceptable alternative.

Test cases

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

The rules:

• Given an integer between 1 and 19 (the values above 20 exceed the max value for a 64-bit signed integer), output the corresponding value.
• You may write a function or a program.
• This is code-golf, so the submission with the least amount of bytes wins!

Answer 1

MATL, 28 bytes

This uses MATL version 1.0.0, which was published in Esolangs on December 12, earlier than this challenge.

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

Example

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

Explanation

The code is similar to that in Martin Büttner's answer.

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

Answer 2

CJam, 28 bytes

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

Test it here.

Explanation

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.

Answer 3

Perl 6, 62 bytes

My first pass of just get it to work was:

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

By combining the grep and the map, I can remove 10 bytes

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

If I use grep instead of map, I save 5 more bytes:

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

usage:

# 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

Answer 4

Pyth, 27 bytes

Leu,eGsGbU2ye.fq1lPs-.HyZGQ

Demonstration

y computes the nth Fibonacci number. A .f loop finds the fibohexaprime according to the input.

Answer 5

Mathematica 111 bytes

There may still be room for additional golfing.

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

Answer 6

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])

This is an anonymous function that accepts an integer and returns an integer. To call it, give it a name, e.g. 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

Answer 7

GAP, 204 Bytes

This answer is pretty unremarkable, except that GAP is cool enough to be able to find the next couple fibohexaprimes (and cooler still, it finds these in milliseconds with the given code).

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

Note that f(24) is between 2^216 and 2^217.

Here is the 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;

There's probably still some golfing that could be done. I think the implementation is pretty straightforward.

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;

Answer 8

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;}

The primality test is very inefficient, so the computation will struggle a bit for n > 16 and become painfully long for n = 19. Nevertheless it works and gives the expected results.

The code assumes that size_t is a 64bit type, which is true for both 64bit Linux and Windows.

---

Bonus: unfortunately we are required to use 64bit types, which lead to an overhead of 33 bytes. The following version works for n <= 15 using int and is 150 byte long:

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;}

---

Test main:

#include <stdio.h>

int main() {
  printf("Input - Output\n");
  for (int i = 1; i < 20; ++i) {
    printf("%2d    - %ld\n", i, F(i));
  }
}

Answer 9

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

The algorithm could be a lot more efficient. In particular, the primality check (t>1)*all(t%x for x in range(2,t)) checks potential factors all the way up to t-1, when really it would only have to check up to the floor of the square root. Since range stores an entire list in memory in Python 2 , this leads to a MemoryError at N=17 (on my machine using default settings).

Answer 10

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]
}

Usage:

# 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

Answer 11

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)}

Indented, with new lines:

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)
    }

Examples:

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

Answer 12

Husk, 13 bytes

!föṗdf≤9B16İf

Try it online!

Using Husk here is just about cheating cause it has an infinite fibonacci sequence builtin.

Explanation

!föṗdf≤9B16İf
           İf infinite list of fibonacci numbers
 fö           filtered on the following four functions:
        B16   base 16 digits of the number
     f≤9      filter out the digits > 9
    d         interpret in base 10
   ṗ          is that prime?
!             get element at input index 

Answer 13

Jelly, 14 bytes

ÆḞb⁴<Ƈ⁵ḌẒµ#ṪÆḞ

Try it online!

Husk's infinite lists just beating me out.

How it works

ÆḞb⁴<Ƈ⁵ḌẒµ#ṪÆḞ - Main link. Takes no arguments
         µ#    - Read an integer n from STDIN and do the following for each integer, i = 0, 1, 2, ... until n return true and return the i's that return true:
ÆḞ             -   The ith Fibonacci number...
        Ẓ      -   ...is prime when...
  b⁴           -   ...converted to base-16,...
    < ⁵        -   ...values less than 10...
     Ƈ         -   ...are removed...
       Ḍ       -   ...then is converted back to base-10
           Ṫ   - Take the last i
            ÆḞ - Return the ith Fibonacci number

Answer 14

Vyxal, 11 bytes

ÞF'Hkd↔⌊æ;i

Try it Online!

Infinite Fibonacci and hexadecimal conversion builtins go brr

ÞF          # All fibonacci numbers
  '      ;i # Find the nth where...
   H        # In hexadecimal
    kd↔     # Keeping only digits
       ⌊æ   # Is it prime?