¿Dos números contienen factoriales únicos?

11

Divide dos números en sus factoriales; si comparten alguno, devuelva un valor falsey. De lo contrario, devuelva un valor verdadero. (inspirado por esta pregunta reciente )

En otras palabras, escriba cada número de entrada como la suma de factores (de enteros positivos) de la manera más codiciosa posible; devuelve un valor verdadero si no aparece factorial en ambas representaciones, un valor falso de lo contrario.

Ejemplo

Dado 20 y 49:

20 = 3! + 3! + 3! + 2!
49 = 4! + 4! + 1!

No aparece factorial en ambas representaciones, por lo tanto, devuelva un valor verdadero.

Dado 32 y 132:

132 = 5! + 3! + 3!
 32 = 4! + 3! + 2!

3! aparece en ambas representaciones, así que devuelve un valor falsey.

I / O

La entrada y salida pueden ser a través de cualquier medio estándar .

La entrada siempre será dos enteros no negativos; sin límite superior en estos enteros que no sea el que requiere su idioma.

La salida debe ser un valor verdadero o falso . Estos valores no necesariamente tienen que ser consistentes para diferentes entradas, siempre y cuando cada salida sea correctamente verdadera / falsa.

Casos de prueba

Si una entrada es 0, la respuesta siempre será veraz. Otros casos de prueba de verdad:

{6, 3}, {4, 61}, {73, 2}, {12, 1}, {240, 2}, {5, 264}, {2, 91}, {673, 18},
 {3, 12}, {72, 10}, {121, 26}, {127, 746}

Si ambas entradas son enteros impares, o si ambas entradas son el mismo entero positivo, entonces la salida siempre será falsa. Otros casos de prueba de falsey:

{8, 5}, {7, 5}, {27, 47}, {53, 11}, {13, 123}, {75, 77}, {163, 160}, {148, 53},
 {225, 178}, {285, 169}, {39, 51}, {207, 334}, {153, 21}, {390, 128}, {506, 584},
 {626, 370}, {819, 354}

Este es el código de golf , ¡por lo que gana menos bytes!

code-golf arithmetic decision-problem integer factorial Greg Martin
fuente
"escribe cada número de entrada como la suma de factores (de enteros positivos) de la manera más codiciosa posible" ¿no te refieres a la forma más perezosa posible ?
user41805
44
@KritixiLithos no. Se refiere a la clase de algoritmos conocidos como algoritmos codiciosos, que funcionan maximizando algunas métricas después de cada paso. Como en, siempre tomando tanto como puedan.
John Dvorak

Respuestas:

9

Jalea , 7 bytes

Æ!ṠḄ&/¬

Pruébalo en línea!

Cómo funciona

Æ!ṠḄ&/¬  Main link. Argument: (x, y) (pair of integers)

Æ!       Convert x and y to factorial base.
  Ṡ      Apply the sign function to each digit.
   Ḅ     Unbinary; convert each resulting Boolean array from base 2 to integer.
    &/   Reduce the resulting pair of integers by bitwise AND.
      ¬  Take the logical NOT of the result.
Dennis
fuente
Æ!Parece increíblemente útil en ciertos escenarios.
Magic Octopus Urn
¿Hay algo que ganar tratando de multiplicar por elementos la lista factorial-base directamente, sin tomar signos?
Greg Martin
@ GregMartin No lo creo. Las matrices de dígitos tendrían que rellenarse o truncarse a la misma longitud, lo que probablemente costará más bytes de los que ahorra.
Dennis
3

Python 2 , 47 bytes

h=lambda a,b,d=2:a<1or a%d*(b%d)<h(a/d,b/d,d+1)

Pruébalo en línea!

xnor
fuente
Amo esta solución ¿Podría anotarlo con un poco de su pensamiento?
Chas Brown
2

JavaScript (ES6), 71 bytes

(a,b,g=(n,e=1,f=1)=>n>=f&&g(n,++e,f*e)+((n/f|0)%e&&1<<e))=>!(g(a)&g(b))

Los enteros de JavaScript están limitados a 53 bits de precisión, ¡lo cual es suficiente para 18 !; Esto significa que puedo usar una máscara de 18 bits para rastrear qué factoriales son necesarios.

Neil
fuente
2

PHP, 109 bytes

for(;$a?:$a=$argv[++$i];$a-=$r[$i][]=$f,$i<2?:$t+=in_array($f,$r[1]))for($c=$f=1;($a/$f*=$c)>=++$c;);echo!$t;

Pruébalo en línea!

Jörg Hülsermann
fuente
0

Mathematica, 73 bytes

F[x_]:=First@IntegerPartitions[x,99,Range[99]!];!IntersectingQ[F@#,F@#2]&

formulario de entrada

[x1, x2]

J42161217
fuente
Recibo varios errores al probar esto ...
Scott Milner
Simplemente escriba al final [x1, x2]
J42161217
Ah Estaba ingresando una lista, en lugar de dos enteros separados. Puedes jugar más golf con ±x_:=First@IntegerPartitions[x,99,Range[99]!];!IntersectingQ[±#,±#2]&[4,61](69 bytes). En la codificación ISO 8859-1, el ±es un byte.
Scott Milner
0

C, 122 119 bytes

G(q,i){return gamma(q+1)>i?gamma(q):G(q+1,i);}
Q(a,b,u,v){while(a&&b){a-=u=G(1,a);b-=v=G(1,b);if(a==b)exit();}exit(0);}

QEs la función principal. Debe invocarse con exactamente dos valores enteros positivos. Esto sale con un código de salida de 0verdadero y 1falso.

Aunque esto no parece funcionar en TIO, funciona en mi sistema con el Homebrew proporcionado gcc 7.1.0.

No he jugado al golf en Cmucho tiempo, por lo que los consejos de golf son muy apreciados.

R. Kap
fuente