11
\$\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!

\$\endgroup\$
  • \$\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\$ – Cows quack Jun 5 '17 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 '17 at 7:20
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.
\$\endgroup\$
  • \$\begingroup\$ Æ! seems insanely useful in certain scenarios. \$\endgroup\$ – Magic Octopus Urn Jun 5 '17 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 '17 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 '17 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!

\$\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!

\$\endgroup\$
  • \$\begingroup\$ I love this solution. Could you annotate it with a bit of your thinking? \$\endgroup\$ – Chas Brown Jun 6 '17 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.

\$\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!

\$\endgroup\$
0
\$\begingroup\$

Mathematica, 73 bytes

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

input form

[x1,x2]

\$\endgroup\$
  • \$\begingroup\$ I'm getting several errors testing this... \$\endgroup\$ – Scott Milner Jun 5 '17 at 22:41
  • \$\begingroup\$ Just type at the end [x1,x2] \$\endgroup\$ – J42161217 Jun 5 '17 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 '17 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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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