Задача на этот раз состоит в том, чтобы найти n- й фибогексаприм . Определение фибогексаприма следующее:

Сначала мы наблюдаем список с числами Фибоначчи:

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

После этого мы конвертируем числа в шестнадцатеричные:

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

Из шестнадцатеричных чисел мы отфильтровываем буквы. Все, что нам осталось, это числа. Нам нужно проверить, просты ли эти числа:

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

Если отфильтрованное число является простым, мы называем это Fibohexaprime . Вы можете видеть, что для N = 7связанного числа Фибоначчи 987.

Задача проста: когда вводится с использованием STDIN или приемлемой альтернативы, напишите программу или функцию, которая выводит n-й фибогексаприм с использованием STDOUT или приемлемой альтернативы.

Контрольные примеры

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

Правила:

• Учитывая целое число между 1и 19(приведенные выше значения 20превышают максимальное значение для 64-разрядного целого числа со знаком), выведите соответствующее значение.
• Вы можете написать функцию или программу.
• Это код-гольф , поэтому выигрывает представление с наименьшим количеством байтов!

Pyth, 27 байт

Leu,eGsGbU2ye.fq1lPs-.HyZGQ

демонстрация

yвычисляет n-е число Фибоначчи. .fЦикл находит fibohexaprime в соответствии с входным.

MATL , 28 байт

При этом используется версия 1.0.0 MATL , которая была опубликована в Esolangs 12 декабря, ранее, чем эта проблема.

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

пример

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

объяснение

Код похож на тот, что был в ответе Мартина Бюттнера .

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

CJam, 28 байтов

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

Проверьте это здесь.

объяснение

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.

Perl 6 , 62 байта

Мой первый проход просто заставить его работать:

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

Сочетая grepи map, я могу удалить 10 байтов

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

Если я использую grepвместо map, я сохраню еще 5 байтов:

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

использование:

# 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

Mathematica 111 байтов

Там еще может быть место для дополнительного игры в гольф.

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

Юлия, 123 байта

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

Это анонимная функция, которая принимает целое число и возвращает целое число. Чтобы назвать его, дайте ему имя, например 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

GAP , 204 байта

Этот ответ довольно ничем не примечателен, за исключением того, что GAP достаточно крут, чтобы иметь возможность находить следующую пару фибогексапримов (и, что еще круче, он находит их за миллисекунды с заданным кодом).

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

Обратите внимание, что f (24) находится между 2 ^ 216 и 2 ^ 217.

Вот код:

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;

Там, вероятно, еще можно поиграть в гольф. Я думаю, что реализация довольно проста.

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;

C 186 183 байта

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

Тест на простоту очень неэффективен, поэтому вычисления будут немного бороться n > 16и долго мучаться n = 19. Тем не менее это работает и дает ожидаемые результаты.

Код предполагает, что size_tэто 64-битный тип, что справедливо как для 64-битных Linux, так и для Windows.

Бонус: к сожалению, мы обязаны использовать 64-битные типы, что приводит к дополнительным издержкам в 33 байта. Следующая версия работает для n <= 15использования intи имеет длину 150 байт:

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

Основной тест:

#include <stdio.h>

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

Python 2, 127 байт

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

Алгоритм может быть намного более эффективным. В частности, проверка на первичность (t>1)*all(t%x for x in range(2,t))проверяет потенциальные факторы вплоть до того t-1момента, когда на самом деле нужно будет только проверить до уровня квадратного корня . Поскольку rangeв Python 2 хранится весь список в памяти, это приводит к значению MemoryErrorat N=17(на моей машине используются настройки по умолчанию).

Рубин, 160 байт

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

Использование:

# 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

R 164 байта

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

С отступом, с новыми строками:

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

Примеры:

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