Write a function or program which takes a positive decimal number, call it A, and output two positive numbers, B and C, such that:

  • A == B bitxor C
  • B and C must not contain any of the digits 0, 3 or 7 in its decimal representation.


>>> decompose(3)
1, 2
>>> decompose(7)
1, 6
>>> decompose(718)
121, 695
>>> decompose(99997)
2, 99999
>>> decompose(4294967296)
4294968218, 922
>>> decompose(5296080632396965608312971217160142474083606142654386510789497504098664630388377556711796340247136376)

Since the decomposition is not unique, your function/program does not need to output the exact same results as these provided examples.

Very detailed rules

  1. Submissions should be in the form of a complete function or program. import statements do count towards the final score.

  2. You may assume the input A always contains at least a digit of 0, 3 or 7.

  3. You may assume a decomposition always exist.

  4. You may use BigInt if they are part of the standard libraries of the language, or can be installed through the language's de jure package manager.

  5. The function should be fast. It should take no more than 20 seconds to run on reasonably modern computer when fed a 100-digit number, and no more than 2 seconds when fed a 10-digit number.

  6. The function/program should support input up to at least 100 digits.

    • If the function/program can only support integers up to N<100 digits, there will be a penalty of +10×(100/N - 1) bytes to the final score. This is to encourage golfers to support a wider range of numbers even if importing may be verbose.
  7. There is no restriction on the presentation of input/outputs as long as they are clearly in decimal representation.

    • The function may input and output strings/BigInts if the built-in integer types are not sufficient.
    • The input may come from the function parameter, command line argument or STDIN.
    • The function may return the result, or just print the result directly to STDOUT.
    • However, signed overflow in the input/outputs are not allowed.
    • Approximate answers are not tolerated, the input/outputs must be exact.


This is a . Shortest solution in bytes win.

There is a penalty if the program can only support numbers less than 100 digits:

  • 64-bit integers (19 digits) = +42 bytes
  • 63-bit integers (18 digits) = +45 bytes
  • 53-bit integers (15 digits) = +56 bytes
  • 31/32-bit integers (9 digits) = +101 bytes
  • 2
    \$\begingroup\$ Are you sure such decomposition is always possible? Can you sketch me a proof? \$\endgroup\$ Nov 7, 2014 at 10:28
  • 4
    \$\begingroup\$ 100 digits? that means Python wins straight away, as it is the only commonly used language here that supports arbitrary precision integers. Why not 19 digits, which fits in a 64-but unsigned integer? (2^64= 18 446 744 073 709 551 616) \$\endgroup\$ Nov 7, 2014 at 12:38
  • 6
    \$\begingroup\$ @steveverrill Mathematica... GolfScript... CJam... \$\endgroup\$ Nov 7, 2014 at 14:26
  • 1
    \$\begingroup\$ You've caught me out there @MartinBüttner! :-) Maybe "only python" was an exaggeration. What I meant to say is that many people's favourite languages (OK, my favourite languages) are effectively excluded because they don't support arbitrary precision integers. Mathematica, Golfscript and CJam win everything anyway. But the last two tend to get less upvotes than other languages, because a lot of people can't understand the code. \$\endgroup\$ Nov 7, 2014 at 16:02
  • 1
    \$\begingroup\$ And Java (had to say that) \$\endgroup\$
    – Ypnypn
    Nov 7, 2014 at 16:20

4 Answers 4


Common Lisp, 240 224 183 173 169 bytes

Common Lisp is a bit verbose for golfing. However, this decomposes 100-digit numbers in under a second, and 200-digit integers in less than ten seconds, so no need for penalties. The algorithm is deterministic.

(defun s(z)(and #1=(some(lambda(q)(position q(format()"~a"z)))"037")(+ z(floor z(expt 10 #1#)))))
(defun d(x)(do((y x(or(s y)(s #3=(logxor x y))(return`(,y,#3#)))))(())))

The line feed between the functions is for typographic purposes only. Test run with the 100-digit reference input:

(time (d 5296080632396965608312971217160142474083606142654386510789497504098664630388377556711796340247136376))
took 677,000 microseconds (0.677000 seconds) to run.
      20,989 microseconds (0.020989 seconds, 3.10%) of which was spent in GC.
During that period, and with 8 available CPU cores,
     671,875 microseconds (0.671875 seconds) were spent in user mode
           0 microseconds (0.000000 seconds) were spent in system mode
 54,221,104 bytes of memory allocated.

As a bonus, I'm including a version of the code that incrementally builds the solution top-down. It can manage a 1000-digit number in less than ten seconds, but cannot compete in golf due to the additional code.

(defun decompose (x)
  (flet ((s (z)
           (mapcan #'(lambda (c) (and #1=(position c #2=(format () "~a" z))
                                 (list (- (length #2#) #1# 1))))
                   '(#\0 #\3 #\7))))
    (do ((y x (let ((p (nconc (s y) (s #3=(logxor x y)))))
                (or p (return`(,y,#3#)))
                (+ y (expt 10 (apply #'max p))))))

* (time (decompose (parse-integer (make-string 1000 :initial-element #\7))))
took 9,226,000 microseconds (9.226000 seconds) to run.
        90,966 microseconds (0.090966 seconds, 0.99%) of which was spent in GC.
During that period, and with 8 available CPU cores,
     9,234,375 microseconds (9.234375 seconds) were spent in user mode
             0 microseconds (0.000000 seconds) were spent in system mode
 487,434,560 bytes of memory allocated.
* (apply #'logxor *)

CJam, 70 bytes


Try it online.

Randomly selects integers until it finds a match. This barely complies with the 20 second limit for 64-bit integers (using the Java interpreter), so I've added 42 to the actual byte count.

Example run

$ cjam t <<< 7777777777; echo

Python 2, 103 + 42 = 145 bytes

Python natively supports bigints, but this program far exceeds 20 seconds for a 100-digit number. However, it decomposes 64-bit integers in around 2 seconds.

from random import *
def d(a):
 while set(`b`+`c`)&set('037'):
 return b,c
  • 1
    \$\begingroup\$ Clever idea using randomness. If you're defining a function, you don't need a while loop to keep trying random values -- you can just call the function again. Without need for control structure, you can then collapse the function to a lambda and a ternary: from random import* d=lambda a,b=0:set(`b`+`a^b`)&set(\'037\')and d(a,randint(1,a))or(b,a^b). Though you might be better off just not using a function. \$\endgroup\$
    – xnor
    Nov 7, 2014 at 20:40
  • \$\begingroup\$ I considered recursion, but it causes a stack overflow for large numbers (even just 11 digits). \$\endgroup\$
    – Remy
    Nov 9, 2014 at 1:36

Python 3 (132 bytes)

(This is just to stimulate better solutions. This is my solution when solving the original problem in ASCII movie.)

def d(a):
 while u:
  while set(str(s)+str((a^s)//u))&set('037'):s+=u

Although the behavior of bitwise xor in decimal system is pretty complicated, there is one major observation: modifying the low digits will not affect the high digits. Therefore, we can work top-down: try to make the top digits free of 0, 3, 7, and then work on the next digit, until the whole number is worked out. This allows us to run in linear time, then processing a thousand-digit number can complete under 1 second. (The Common Lisp solution is also using the same technique I believe.)

  • \$\begingroup\$ But fixing low digits may affect high digits. For instance, 997^8 == 1005. I think there is a kernel of an idea here, but it isn't obvious. \$\endgroup\$ Nov 11, 2014 at 17:33
  • \$\begingroup\$ @KeithRandall: Yes it is just like 999…999 + 1, but, given the choice of {1,2,4,5,6,8,9}, there would be some of them that won't affect the high digits. (e.g. 997^2 == 999). The inner while loop does the exhaustion to find the choice that keeps the high digits valid. \$\endgroup\$
    – kennytm
    Nov 11, 2014 at 17:37
  • \$\begingroup\$ right, but then it's not obvious (to me, at least) that there is definitely a digit that will work. \$\endgroup\$ Nov 11, 2014 at 17:38

Your Answer

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

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