Temukan Fibohexaprime ke-n

23

Tantangan kali ini adalah menemukan Fibohexaprime ke- n . Definisi Fibohexaprime adalah sebagai berikut:

Kami pertama-tama mengamati daftar dengan angka Fibonacci:

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

Setelah itu, kami mengonversi angka menjadi heksadesimal:

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

Dari angka heksadesimal, kami menyaring surat-surat. Yang tersisa hanyalah angka. Kami perlu memeriksa apakah angka-angka ini prima:

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

Jika nomor yang difilter adalah prima, kami menyebutnya Fibohexaprime . Anda dapat melihat bahwa untuk N = 7, nomor fibonacci terkait adalah 987.

Tugasnya sederhana, ketika diberi input menggunakan STDIN atau alternatif yang dapat diterima, menulis sebuah program atau fungsi yang menghasilkan Fibohexaprime ke-11 menggunakan STDOUT atau alternatif yang dapat diterima.

Uji kasus

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

Aturan:

  • Diberikan bilangan bulat antara 1dan 19(nilai-nilai di atas 20melebihi nilai maksimum untuk bilangan bulat bertanda 64-bit), mengeluarkan nilai yang sesuai.
  • Anda dapat menulis fungsi atau program.
  • Ini adalah , jadi pengiriman dengan jumlah byte paling sedikit menang!
Adnan
sumber
Cara ini worded, sepertinya fungsi juga harus membaca dari STDIN dan menulis ke STDOUT. Apakah itu benar? Biasanya kami mengizinkan fungsi untuk menerima argumen dan mengembalikan nilai sebagai nyaman.
Alex A.
2
@AlexA. Keduanya merupakan alternatif yang dapat diterima. Membaca dari STDIN dan menggunakan STDOUT tidak wajib.
Adnan

Jawaban:

4

Pyth, 27 byte

Leu,eGsGbU2ye.fq1lPs-.HyZGQ

Demonstrasi

ymenghitung angka Fibonacci n. Sebuah .floop menemukan fibohexaprime sesuai dengan input.

isaacg
sumber
12

MATL , 28 byte

Ini menggunakan MATL versi 1.0.0 , yang diterbitkan di Esolangs pada 12 Desember, lebih awal dari tantangan ini.

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

Contoh

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

Penjelasan

Kode ini mirip dengan yang ada dalam jawaban Martin Büttner .

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
sumber
4
Jawaban MATL pertama di dunia! Kerja bagus, Luis!
gelas kimia
1
Hore untuk MATL! Selamat datang di dunia golf kode!
rayryeng
8

CJam, 28 byte

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

Uji di sini.

Penjelasan

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
sumber
7

Perl 6 , 62 byte

Pass pertama saya untuk mulai bekerja adalah:

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

Dengan menggabungkan grepdan map, saya bisa menghapus 10 byte

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

Jika saya menggunakan grepalih-alih map, saya menyimpan 5 byte lagi:

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

pemakaian:

# 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
sumber
3

Mathematica 111 byte

Mungkin masih ada ruang untuk bermain golf tambahan.

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
sumber
3

Julia, 123 byte

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

Ini adalah fungsi anonim yang menerima integer dan mengembalikan integer. Untuk menyebutnya, berikan nama, mis f=n->....

Tidak Disatukan:

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.
sumber
3

CELAH , 204 Bytes

Jawaban ini cukup biasa-biasa saja, kecuali bahwa GAP cukup keren untuk dapat menemukan pasangan fibohexaprimes berikutnya (dan lebih keren lagi, ia menemukan ini dalam milidetik dengan kode yang diberikan).

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

Perhatikan bahwa f (24) adalah antara 2 ^ 216 dan 2 ^ 217.

Ini kodenya:

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;

Mungkin masih ada beberapa golf yang bisa dilakukan. Saya pikir implementasinya cukup mudah.

Tidak Disatukan:

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
sumber
3

C, 186 183 byte

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

Tes primality sangat tidak efisien, sehingga perhitungannya akan sedikit sulit n > 16dan menjadi sangat lama n = 19. Namun demikian ia bekerja dan memberikan hasil yang diharapkan.

Kode ini mengasumsikan bahwa itu size_tadalah tipe 64bit, yang berlaku untuk Linux 64bit dan Windows.


Bonus: sayangnya kami diharuskan menggunakan jenis 64bit, yang mengarah ke overhead 33 byte. Versi berikut ini berfungsi untuk n <= 15digunakan intdan panjangnya 150 byte:

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

Tes utama:

#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
sumber
Bisakah Anda menghemat sedikit dengan menggunakan size_tdan menjatuhkan sertakan? Ini implementasi khusus, tetapi tampaknya 64-bit di Linux 64-bit dan Windows gcc (dan sejak kapan kita peduli tentang portabilitas dalam codegolf?). (catatan: %ldtidak 64-bit di Windows 64-bit; kebutuhan %lld)
Bob
@ Bob Saya memikirkannya, tetapi size_tbukan builtin, itu didefinisikan stddef.h(yang pada gilirannya secara langsung atau tidak langsung dimasukkan oleh hampir semua header lainnya). Dengan satu atau lain cara, saya membutuhkan #include. Saya masih bisa menyimpan 2 byte dengan menggunakan size_talih-alih uint64_t:)
Stefano Sanfilippo
Terima kasih juga untuk bagian ini lld, saya tidak mendapatkan kesempatan untuk mengujinya di Windows (tapi portabilitas tidak masalah, kan?)
Stefano Sanfilippo
Hm, itu pasti berasal dari stdio.hsaat saya sedang menguji. Bagaimanapun - Anda masih bisa menyelamatkan pasangan dengan memasukkan math.hbukan stddef.h.
Bob
math.htidak melakukan trik untuk saya (GCC 4,9 dengan GNU libc)
Stefano Sanfilippo
2

Python 2, 127 byte

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

Algoritme bisa menjadi jauh lebih efisien. Secara khusus, pemeriksaan awal (t>1)*all(t%x for x in range(2,t))memeriksa faktor-faktor potensial sampai t-1saat itu benar-benar hanya perlu memeriksa hingga ke lantai akar kuadrat . Karena rangemenyimpan seluruh daftar di memori dalam Python 2, ini mengarah ke MemoryErrorat N=17(di komputer saya menggunakan pengaturan default).

mathmandan
sumber
2

Ruby, 160 byte

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

Tidak Disatukan:

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

Pemakaian:

# 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
sumber
2

R, 164 byte

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

Diindentasi, dengan baris baru:

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

Contoh:

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