# Do two numbers contain unique factorials?

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!

• "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? Jun 5, 2017 at 6:58
• @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. Jun 5, 2017 at 7:20

# 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.

• Æ! seems insanely useful in certain scenarios. Jun 5, 2017 at 15:30
• Is there anything to be gained by trying to elementwise-multiply the factorial-base lists directly, without taking signs? Jun 5, 2017 at 17:47
• @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. Jun 5, 2017 at 18:40

# 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!

# 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!

• I love this solution. Could you annotate it with a bit of your thinking? Jun 6, 2017 at 4:28

## 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.

# PHP, 109 Bytes

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


Try it online!

# Mathematica, 73 bytes

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


input form

[x1,x2]

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

# 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!