Decompose a number with bit-xor without the digits 0, 3, 7

Question

Challenge

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.

Examples

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

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.

Scoring

This is a code-golf. 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

Answer 1

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.
(1864921261592819619661568919418981552559955289196969112566252282429216186594265918444566258544614425
 5891958562486995519825158818455999516899524658151445485616155916296966645869599949958954491929662561)

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

* (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.
(8889898889152488921298888992819221914229899249999918899888899888888889999989141219898898888988988898888888888899142442899924898918898898988988895189988898888924192198992454114198911989191888889898888918888988988998888891421118891899122898888998989898888898988898888999988918888898889189918889888888899888989219188898998888988892119889198888988888894888912188898989952999888888888898899998988898889228918998949999998898898991141888898999988912121292118899889998989899999892889941898888911888898889118998898888911889889888891452888998889288921141888888942189888899988891918889118888888888989892198899199914111188988889421111188889118888918989988912989999998989891119888898888888892621229888988888999619888952462219889189899998899888889989898891118989218888888898962988891188899888888888999888888888888888888888891269188921288888888998898899214191188888888898992188998898889919888889989889899988892115549998888898889218899988998911898989199918898918988898888891889888989119899888889888998918889112189998
 4184469818464841952189561886965821566229261221619858498284264289194458622668559698924621446851546256444641488616184155821914881485164244662156846141894655485889656891849662551896595944656451462198891289692696856414192264846811616261884188919426294584158925218559295881946496911489245664261126565546419851585441144861859822815144162828551969425529258169849412525611662488849586554989254181228254465226521648916188265491499166186964881248156451994924294646681548996645996894665198811511522424996844864211629888924642289925565591484541149414914699289441561496451494562955652129199261462268846144518142486845251946444998812988291119592418684842524648484689261441456645518518812265495165189812912919529151991611962525419626921619824496626511954895189658691229655648659252448158451924925658586522262194585891859285841914968868466462442488528641466655911199816288496111884591648442984864269495264612518852292965985888414945855422266658614684922884216851481646226111486498155591649619266595911992489425412191)
* (apply #'logxor *)
7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777

Answer 2

CJam, 70 bytes

ri:Q{;Qmr_Q^`1$`+730`&}g_Q^p

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
2695665494
6161166119

Answer 3

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):
 b=c=0
 while set(`b`+`c`)&set('037'):
    b=randint(1,a);c=a^b
 return b,c

Answer 4

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):
 l=len(str(a));s=int('1'*l);u=10**(l-1)
 while u:
  while set(str(s)+str((a^s)//u))&set('037'):s+=u
  u//=10
 print(s,a^s)

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