Encuentra la enésima Fibohexaprima

23

El reto esta vez es encontrar el n º Fibohexaprime . La definición de una Fibohexaprima es la siguiente:

Primero observamos una lista con números de 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

Después de eso, convertimos los números a hexadecimales:

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

De los números hexadecimales, filtramos las letras. Todo lo que nos queda son los números. Necesitamos verificar si estos números son primos:

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

Si el número filtrado es primo, lo llamamos Fibohexaprime . Puede ver que para N = 7, el número de Fibonacci relacionado es 987.

La tarea es simple, cuando se le da una entrada usando STDIN o una alternativa aceptable, escriba un programa o una función que genere la enésima Fibohexaprime usando STDOUT o una alternativa aceptable.

Casos de prueba

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

Las normas:

  • Dado un número entero entre 1y 19(los valores anteriores 20exceden el valor máximo para un entero con signo de 64 bits), genera el valor correspondiente.
  • Puedes escribir una función o un programa.
  • Este es el , por lo que gana el envío con la menor cantidad de bytes.
Adnan
fuente
Por la forma en que está redactado, parece que las funciones también deben leer desde STDIN y escribir en STDOUT. ¿Es eso correcto? Por lo general, permitimos que las funciones acepten argumentos y devuelvan valores según sea conveniente.
Alex A.
2
@AlexA. Ambas son alternativas aceptables. Leer desde STDIN y usar STDOUT no es obligatorio.
Adnan

Respuestas:

4

Pyth, 27 bytes

Leu,eGsGbU2ye.fq1lPs-.HyZGQ

Demostración

ycalcula el enésimo número de Fibonacci. Un .fbucle encuentra la fibohexaprima de acuerdo con la entrada.

isaacg
fuente
12

MATL , 28 bytes

Utiliza la versión 1.0.0 de MATL , que se publicó en Esolangs el 12 de diciembre, antes de este desafío.

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

Ejemplo

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

Explicación

El código es similar al de la respuesta de 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
fuente
44
¡La primera respuesta MATL del mundo! Buen trabajo, Luis!
vaso de precipitados
1
¡Hurra por MATL! ¡Bienvenido al mundo del golf de código!
rayryeng - Restablecer Monica
8

CJam, 28 bytes

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

Pruébalo aquí.

Explicación

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

Perl 6 , 62 bytes

Mi primer paso de simplemente ponerlo a trabajar fue:

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

Al combinar el grepy el map, puedo eliminar 10 bytes

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

Si uso en greplugar de map, guardo 5 bytes más:

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

uso:

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

Mathematica 111 bytes

Todavía puede haber espacio para golf adicional.

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

Esta es una función anónima que acepta un entero y devuelve un entero. Para llamarlo, dale un nombre, por ejemplo f=n->....

Sin golf:

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

BRECHA , 204 bytes

Esta respuesta es bastante sencilla, excepto que GAP es lo suficientemente genial como para poder encontrar las próximas dos fibohexaprimas (y aún más fresco, las encuentra en milisegundos con el código dado).

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

Tenga en cuenta que f (24) está entre 2 ^ 216 y 2 ^ 217.

Aquí está el código:

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;

Probablemente todavía se pueda jugar al golf. Creo que la implementación es bastante sencilla.

Sin golf:

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

C, 186183 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;}

La prueba de primalidad es muy ineficiente, por lo que la computación tendrá dificultades y será n > 16dolorosamente larga.n = 19 . Sin embargo, funciona y da los resultados esperados.

El código supone que size_tes un tipo de 64 bits, lo cual es cierto tanto para Linux como para Windows de 64 bits.


Bonificación: desafortunadamente estamos obligados a usar tipos de 64 bits, lo que lleva a una sobrecarga de 33 bytes. La siguiente versión funciona para n <= 15usar inty tiene una longitud de 150 bytes:

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

Prueba principal:

#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
fuente
¿Podrías ahorrar un poco usando size_ty soltando la inclusión? Es específico de la implementación, pero parece ser de 64 bits en gcc de Linux y Windows de 64 bits (¿y desde cuándo nos preocupamos por la portabilidad en codegolf?). (nota al margen: %ldno es de 64 bits en Windows de 64 bits; necesita %lld)
Bob
@Bob Lo pensé, pero size_tno es una función integrada, está definida en stddef.h(que a su vez está incluida directa o indirectamente en prácticamente cualquier otro encabezado). De una forma u otra, necesito un #include. Todavía puedo guardar 2 bytes usando en size_tlugar de uint64_t, aunque :)
Stefano Sanfilippo
También gracias por el lldbit, no tuve la oportunidad de probarlo en Windows (pero la portabilidad no importa, ¿verdad?)
Stefano Sanfilippo
Hm, debe haber venido stdio.hmientras estaba probando. En cualquier caso, aún podría salvar un par al incluirlo en math.hlugar de hacerlo stddef.h.
Bob
math.hno me sirve (GCC 4.9 con 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

El algoritmo podría ser mucho más eficiente. En particular, la verificación de primalidad (t>1)*all(t%x for x in range(2,t))comprueba los factores potenciales hasta el final t-1, cuando realmente solo tendría que verificar hasta el piso de la raíz cuadrada . Como rangealmacena una lista completa en la memoria en Python 2, esto lleva a un MemoryErrorat N=17(en mi máquina usando la configuración predeterminada).

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

Sin golf:

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

Uso:

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

Sangrado, con nuevas líneas:

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

Ejemplos:

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