12
\$\begingroup\$

Break two numbers up into their factorials; if they share any, return a falsey value. Otherwise, return a truthy value. (inspired by this recent question)

In other words, write each input number as the sum of factorials (of positive integers) in the greediest possible way; return a truthy value if no factorial appears in both representations, a falsey value otherwise.

Example

Given 20 and 49:

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

No factorial appears in both representations, so return a truthy value.

Given 32 and 132:

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

3! appears in both representations, so return a falsey value.

I/O

Input and output can be through any standard means.

Input will always be two nonnegative integers; no upper bound on these integers other than what your language requires.

Output should be a truthy or falsey value. These values don't necessarily have to be consistent for different inputs, as long as every output is correctly truthy/falsey.

Test Cases

If one input is 0, the answer will always be truthy. Other truthy test cases:

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

If both inputs are odd integers, or if both inputs are the same positive integer, then the output will always be falsey. Other falsey test cases:

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

This is , so fewest bytes wins!

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ "write each input number as the sum of factorials (of positive integers) in the greediest possible way" don't you mean the laziest possible way instead? \$\endgroup\$
    – user41805
    Jun 5, 2017 at 6:58
  • 4
    \$\begingroup\$ @KritixiLithos no. He's referring to the class of algorithms known as greedy algorithms, which work by maximizing some metric after each step. As in, always taking as much as they can. \$\endgroup\$
    – John Dvorak
    Jun 5, 2017 at 7:20

7 Answers 7

Reset to default
9
\$\begingroup\$

Jelly, 7 bytes

Æ!ṠḄ&/¬

Try it online!

How it works

Æ!ṠḄ&/¬  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.
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Æ! seems insanely useful in certain scenarios. \$\endgroup\$
    – Magic Octopus Urn
    Jun 5, 2017 at 15:30
  • \$\begingroup\$ Is there anything to be gained by trying to elementwise-multiply the factorial-base lists directly, without taking signs? \$\endgroup\$
    – Greg Martin
    Jun 5, 2017 at 17:47
  • \$\begingroup\$ @GregMartin I don't think so. The digits arrays would have to be padded or truncated to the same length, which will probably cost more bytes than it saves. \$\endgroup\$
    – Dennis
    Jun 5, 2017 at 18:40
3
\$\begingroup\$

Python 3, 93 91 bytes

lambda a,b:k(a)&k(b)=={0}
k=lambda t,n=1,a=1:{t}&{0}or a*n>t and{a-1}|k(t-n)or k(t,n*a,a+1)

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python 2, 47 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I love this solution. Could you annotate it with a bit of your thinking? \$\endgroup\$
    – Chas Brown
    Jun 6, 2017 at 4:28
2
\$\begingroup\$

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

JavaScript's integers are limited to 53 bits of precision, which is just about enough for 18!; this means that I can use a mask of 18 bits to track which factorials are needed.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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;

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 73 bytes

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

input form

[x1,x2]

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I'm getting several errors testing this... \$\endgroup\$
    – Scott Milner
    Jun 5, 2017 at 22:41
  • \$\begingroup\$ Just type at the end [x1,x2] \$\endgroup\$
    – ZaMoC
    Jun 5, 2017 at 22:46
  • \$\begingroup\$ Ah. I was inputting a list, instead of two separate integers. You can golf it further with ±x_:=First@IntegerPartitions[x,99,Range[99]!];!IntersectingQ[±#,±#2]&[4,61] (69 bytes). In ISO 8859-1 encoding, the ± is one byte. \$\endgroup\$
    – Scott Milner
    Jun 5, 2017 at 22:52
0
\$\begingroup\$

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

Q is the main function. It should be invoked with exactly two positive integer values. This exits with an exit code of 0 for truthy and 1 for falsy.

Although this does not seem to work on TIO, it works on my system with the Homebrew provided gcc 7.1.0.

I have not golfed in C in quite a while, so golfing tips are very much appreciated!

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.