Dado un número entero positivo N
, genera el número de pares de números enteros 0 <= a <= b < 2**N
tal que a*b >= 2**N
.
Reglas
- Puede suponer que
N
es menor o igual que el ancho de bits máximo para enteros en su lenguaje (por ejemplo, para C,N
no excederá32
o64
, dependiendo de la arquitectura de la máquina). Si su idioma es capaz de manejar enteros de ancho arbitrario, entonces no hay límite superiorN
.
Casos de prueba
1 0
2 3
3 19
4 96
5 437
6 1876
7 7804
8 31904
9 129170
10 520135
11 2088143
12 8369175
13 33512744
14 134128704
15 536681553
16 2147082274
a <= b
condición.{0, 3, 19, 96, 437, 1876, 7804, 31904, 129170, 520135, 2088143, 8369175, 33512744, 134128704, 536681553, 2147082274, 8589086503, 34357951447}
Respuestas:
Python 2,
7568 bytesPruébalo en línea!
Esto se ejecuta en operaciones O (2 n / 2 ) en lugar de O (2 n ) u O (2 2 · n ), por lo que funciona en entradas mucho más grandes.
(Tenga en cuenta que existe un algoritmo O (2 n / 3 ) aún más rápido ) .
fuente
x=0;y=0
porx=y=0
2^{N/3}
solución también.Jalea ,
1210 bytesTermina los casos de prueba combinados en menos de 3 segundos.
Pruébalo en línea!
Cómo funciona
fuente
MATL ,
109 bytesPruébalo en línea!
Esto intenta todos los pares posibles. Se queda sin memoria en el intérprete en línea por exceso de entrada
12
.Explicación
fuente
Brachylog , 21 bytes
Pruébalo en línea!
fuente
A
a esa variable, guardando un byte.05AB1E ,
1312 bytes-1 byte gracias a Emigna
Pruébalo en línea!
Explicación
fuente
P
es suficiente aquí.JavaScript (ES7),
706560 bytesCasos de prueba
Mostrar fragmento de código
fuente
Mathematica, 37 bytes
Pruébelo en línea en http://sandbox.open.wolframcloud.com . Mathematica no tiene límite en los enteros, y este algoritmo se ejecuta en el tiempo 2 n , por lo que es muy lento para grandes
n
.fuente
Clojure, 78 bytes
fuente
En realidad , 13 bytes
Pruébalo en línea!
Una implementación literal del problema. Bastante lento.
fuente
╙;r;∙♂S╔♂π♀≥Σ
(edición menor a la versión que publiqué en el chat )PHP , 62 bytes
Pruébalo en línea!
fuente
Python 2 , 53 bytes
Pruébalo en línea!
fuente
Jalea , 11 bytes
Pruébalo en línea!
Una implementación literal del problema. Bastante lento.
fuente