Divide and divide and conquer

Question

Sometimes, when I'm idly trying to factor whatever number pops up in front of me¹, after a while I realize it's easier than I thought. Take 2156 for example: it eventually occurs to me that both 21 and 56 are multiples of 7, and so certainly 2156 = 21 x 100 + 56 is also a multiple of 7.

Your task is to write some code that identifies numbers that are easier to factor because of a coincidence of this sort.

More precisely:

Write a program or function that takes a positive integer n as input, and returns a truthy value if there exists a divisor d (greater than 1) such that n can be chopped in two to yield two positive integers, each of which is a multiple of d; return a falsy value if not.

• "Chopped in two" means what you think: the usual base-10 representation of n partitioned at some point into a front half and a back half to yield two other base-10 integers. It's okay if the second integer has a leading zero (but note that it must be a positive integer, so splitting 1230 into 123 and 0 is not valid).
• The truthy and falsy values can depend on the input. For example, if any nonzero integer is truthy in your language of choice, then you are welcome to return the divisor d or one of the "pieces" of n (or n itself for that matter).
• For example, any even number with at least two digits in the set {2, 4, 6, 8} will yield a truthy value: just split it after the first even digit. Also for example, any prime number n will yield a falsy value, as will any one-digit number.
• Note that it suffices to consider prime divisors d.
• You may assume the input is valid (that is, a positive integer).

This is code-golf, so the shortest code in bytes wins. But solutions in all languages are welcome, so we can strive for the shortest code in each language, not just the shortest code overall.

Test cases

(You only have to output a truthy or falsy value; the annotations below are just by way of explanation.) Some inputs that yield truthy values are:

39  (3 divides both 3 and 9)
64  (2 divides both 6 and 4)
497  (7 divides both 49 and 7)
990  (splitting into 99 and 0 is invalid; but 9 divides both 9 and 90)
2233  (11 divides both 22 and 33)
9156  (3 divides both 9 and 156; or, 7 divides both 91 and 56)
11791  (13 divides both 117 and 91)
91015  (5 divides both 910 and 15)
1912496621  (23 divides both 1912496 and 621; some splittings are multiples of 7 as well)
9372679892  (2473 divides both 937267 and 9892; some splittings are multiples of 2 as well)

Some inputs that yield falsy values are:

52
61
130  (note that 13 and 0 is not a valid splitting)
691
899
2397
9029
26315
77300  (neither 7730 and 0 nor 773 and 00 are valid splittings)
2242593803

¹ yes I really do this

Answer 1

Retina, 31 29 bytes

,$';$`
\d+
$*
;(11+)\1*,\1+;

Try it online!

Outputs a positive integer for valid inputs and zero for invalid ones.

I wouldn't recommend waiting for the larger test cases...

Explanation

,$';$`

At each position of the input insert a comma, then everything before that position, then a semicolon, then everything after this position. What does that do? It gives us all possible splittings of a number (split by ,, separated by ;), and then the input again at the end. So input 123 becomes

,123;1,23;12,3;123,;123
     ^     ^     ^

where I've marked the original input characters (the stuff that isn't marked is what we inserted). Note that this creates invalid splittings that aren't actual splittings and it also doesn't care whether the trailing component is all zeros, but we'll avoid accepting those later. The benefit of creating the invalid splittings is that we know that each valid splitting has a ; in front and after it, so we can save two bytes on word boundaries.

\d+
$*

Convert each number to unary.

;(11+)\1*,\1+;

Match a splitting by matching both halves as multiples of some number that's at least 2.

Answer 2

Brachylog (2), 8 bytes

~c₂ḋᵐ∋ᵐ=

Try it online!

Explanation

~c₂ḋᵐ∋ᵐ=
~c₂       Split the input into two pieces
    ᵐ ᵐ   On each of those pieces:
   ḋ ∋      Choose a prime factor
       =  such that both the chosen factors are equal

Clearly, if the same number (greater than 1) divides both pieces, the same prime number will divide both. Requiring the factor to be prime neatly disallows 1 as a factor. It also prevents a literal 0 being chosen as a segment of a number (because 0 has no prime factorization, and will cause ḋ to fail).

There's no need to check against matching internal zeroes; if a split of x and 0y is valid, x0 and y will work just as well (and going the other way, if x0 and y works, then we have a working solution regardless of whether x and 0y would work or not).

A Brachylog full program, like this one, returns a Boolean; true. if there's some way to run it without failure (i.e. to make choices such that no error occurs), false. if all paths lead to failure. That's exactly what we want here.

Answer 3

Jelly, 14 12 11 10 bytes

ŒṖḌo1g/€P>

Thanks to @JonathanAllan for golfing off 1 byte!

Try it online!

How it works

ŒṖḌo1g/€P>  Main link. Argument: n

ŒṖ          Compute all partitions of n's decimal digits.
  Ḍ         Undecimal; convert each array in each partition back to integer.
   o1       OR 1; replace disallowed zeroes with ones.
     g/€    Reduce (/) each (€) partition by GCD (g).
            The last GCD corresponds to the singleton partition and will always be
            equal to n. For a falsy input, all other GCDs will be 1.
        P   Take the product of all GCDs.
         >  Compare the product with n.

Answer 4

Mathematica, 63 62 bytes

(1 byte thanks to Greg Martin)

1<Max@@GCD@@@Table[1~Max~#&/@Floor@{Mod[#,t=10^n],#/t},{n,#}]&

It's a function that takes an integer as input and returns True or False. If you test it on a big number, bring a book to read while you wait.

Explanation:

• Floor@{Mod[#,t=10^n],#/t} arithmetically splits the input into its last n digits and the remaining m-n digits (where m is the total number of digits).
• Table[1~Max~#&/@...,{n,#}] does this for every n up to the input number. (This is way too big. We only need to do this up to the number of digits of the input, but this way saves bytes and still gives the correct result.) The 1~Max~#&/@ bit gets rid of zeroes, so numbers like 130 -> {13,0} don't count as True.
• 1<Max@@GCD@@@... finds the greatest common divisor of each of these pairs, and checks if any of these divisors are more than 1. If they are, we've found a way to factor the number by splitting it.

Answer 5

Haskell, 57 bytes

x#n|b<-mod x n=x>n&&(b>0&&gcd(div x n)b>1||x#(10*n))
(#1)

Try it online! Usage: (#1) 2156, returns True or False

Answer 6

C, 145 142 139 138 135 bytes

i,a,b;f(){char s[99];scanf("%s",s);for(char*p=s;*p++;)for(b=atoi(p),i=*p,*p=0,a=atoi(s),*p=i,i=1;i++<b;)*s=a%i-b%i|b%i?*s:0;return!*s;}

Answer 7

JavaScript (ES6), 74 71 70 bytes

f=(s,t='',u)=>u?s%t?f(t,s%t,1):t:s&&f(t+=s[0],s=s.slice(1),1)>1|f(s,t)

<input oninput=o.textContent=f(this.value)><span id=o>

Takes input as a string, which is handy for the snippet. Edit: Saved 3 bytes thanks to @user81655.

Answer 8

Python 3, 133 118 117 bytes

i,j=int,input()
from fractions import*
print(any(i(j[k:])*i(j[:k])*~-gcd(i(j[k:]),i(j[:k]))for k in range(1,len(j))))

Certainly not the shortest, probably could be shortened a bit. Works in O(n) time. Input is taken in format \d+ and output is given in format (True|False) as per default Python boolean value
-3 bytes thanks to Dead Possum
-15 bytes thanks to ovs
-1 byte thanks to This Guy

Answer 9

QBIC, 91 90 bytes

;_LA|[a-1|B=left$(A,b)┘C=right$(A,a-b)┘x=!B!┘y=!C![2,x|~(x>1)*(y>1)*(x%c=0)*(y%c=0)|_Xq}?0

Explanation:

;               Get A$ from the command prompt
_LA|            Get the length of A$ and place it in a% (num var)
[a-1|           for b%=1; b% <= a%-1; b%++
B=left$(A,b)    break A$ in two components on index b%
C=right$(A,a-b)
x=!B!┘y=!C!     Convert both parts from string to num, assign to x% and y%
[2,x|           FOR c% = 2; c% <= x%; c%++

This next IF (~ in QBIC) is a bit ... iffy. It consists of a set of comparators.
Each comparator yields a -1 or a 0. We take the product of these. At any failed
comparison this will yield 0. When successful, it yields 1, which is seen as true by QBasic.

~(x>1)*(y>1)        IF X>1 and Y>1 --> this stops '00' and '1' splits.
*(x%c=0)*(y%c=0)    Trial divide the splits on loop counter c%.

|_Xq            Success? THEN END, and PRINT q (which is set to 1 in QBIC)
}               Close all language constructs (2 FOR loops and an IF)
?0              We didn't quit on match, so print 0

Answer 10

Python 3, 70 69 bytes

import math
f=lambda n,d=1:n>d and n%d*~-math.gcd(n//d,n%d)+f(n,10*d)

Try it online!

Answer 11

Perl 5, 46 bytes

43 bytes of code + 3 bytes for -p flag.

s~~$\|=grep!($`%$_|$'%$_),2..$`if$`*$'~ge}{

Try it online! or try this modified version allowing multiple inputs.
You probably don't want to try this on the largest input, as it might take a (very long) while.

Explanations:
We iterate through each position in the word with s~~~g, with $` containing the numbers before and $' the numbers after. If $`*$' is true (it means that none is empty, and none is 0), then we check if a number between 2 and $` divides both of them (with the grep!(...),2..$`). If so, $\|=.. will set $\ to a non-zero value, which is implicitly printed at the end thanks to -p flag.

Answer 12

Python 2, 69 bytes

f=lambda n,d=10,k=2:k<d<n and(n/d%k+n%d%k<1<n%d)|f(n,d,k+1)|f(n,10*d)

Uses recursion instead of GCD built-ins.

Try it online!

How it works

When f is called with one to three arguments (d defaults to 10, k to 2), it first checks the value of the expression k<d<n. If the inequalities k < d and d < n both hold, the expression following and gets executed and its value is returned; otherwise, f will simply return False.

In the former case, we start by evaluating the expression n/d%k+n%d%k<1<n%d.

d will always be a power of ten, so n/d and n%d effectively split the decimal digits on n into two slices. These slices are both divisible by k if and only if n/d%k+n%d%k evaluates to 0, which is tested by comparing the result with 1.

Since part of the requirements is that both slices must represent positive integers, the value of n%d is also compared with 1. Note that 1 has no prime divisors, so the more expensive comparison with 0 is not required. Also, note that d < n already ensures that n/d will evaluate to a positive integer.

Finally it recursively all f(n,d,k+1) (trying the next potential common divisor) and f(n,10*d) (trying the splitting) and returns the logical OR of all three results. This means f will return True if (and only if) k is a common divisor of n/d and n%d or the same is true for a larger value of k and/or a higher power of ten d.