Divide and divide and conquer

Question

Sometimes, when I'm idly trying to factor whatever number pops up in front of me1, 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

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

• hyperneutrino: Quick question about Retina: What does the leading newline do?
• Martin Ender: @HyperNeutrino Well the first line is the first regex we match, and we want to match the empty regex, in order to insert the substitution into every single position between characters.
• hyperneutrino: Oh, okay. Thanks! I should probably look a bit more at Retina; since it seems largely regex based it might be good for kolmogorov-complexity problems.
• Riley: Could the last line be ;(11+)+,1円+;
• Martin Ender: @Riley that doesn't guarantee that the first segment is a multiple of the same factor.

Answer 2

Brachylog (2), 8 bytes

~c2ḋm∋m=

Try it online!

Explanation

~c2ḋm∋m=
~c2 Split the input into two pieces
 m m 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.

• Jonathan Allan: I think you can drop the D, as make_digits is in effect for ŒṖ.
• Dennis: For some reason, I assumed that would create a range... Thanks!

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.

• Greg Martin: Nice answer! You can save one byte with either {#~Mod~10^n,#/10^n} or {Mod[#,t=10^n],#/t}.
• Not a tree: I tried #~Mod~10^n, but it seems to get bracketed like Mod[#,10]^n instead of Mod[#,10^n]. I didn't think of your second suggestion, though!
• Greg Martin: fair point on Mod[#,10]^n

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.

• user81655: Saves two bytes: (c,i) -> c, i+1 -> ++i, t='' -> i=t='', this trick is useful any time you need to use 1-based indices and have somewhere to initialise i to 0.
• user81655: Also I believe t='' could be t=0, since adding c coerces it to a string anyway.
• Neil: @user81655 This happened because I originally sliced from and to i, so I didn't need 1-based indices, but then I golfed the first slice to t+=c.
• user81655: Ah, OK. Also one last thing, I think this could also be shorter as a recursive function: f=(x,y,z)=>z?x%y?g(y,x%y):y:x?f(x,y,1)>1||f(x.slice(1),~~y+x[0]):0. I combined your GCD function with f as well. Could probably be golfed further. Last suggestion, I promise! :P
• Neil: @user81655 Sadly my oversimplified gcd function doesn't work when x=0, and working around that and your typo took me to 72 bytes, so it was fortunate that I was then able to golf away 2 bytes.

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

• Dead Possum: from fractions import* would save 3 bytes
• Dead Possum: It returns True for 900. I guess, that is wrong. Mb you should change inner any to all? If that's the case, you may change all that part to i(j[k:])and i(j[:k]) bringing it all to 125 bytes. Here are fixes
• ovs: You can replace the and and all by multiplication : any(i(j[k:])*i(j[:k])*~-gcd(i(j[k:]),i(j[:k]))for k in range(1,len(j)))
• hyperneutrino: @DeadPossum Oh right, I should have done that. And yeah, my current method has a lot of golfable parts in it, but I'm going to be following ovs's suggestions. Thanks for pointing that out! (really should've tested it myself... oh well...)
• caird coinheringaahing: You can remove a byte (almost nothing) by remove the whitespace between )) for

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.

• Dada: If anyone knows how to render a $<backquote> in SE markdown, I'd be grateful if you tell me how.
• user62131: You can do it via using explicit <code> ... </code> (rather than ` ... `), then escaping the backquotes as \`. Also, this comment was a pain to write, because it has to be double-escaped (and the two sets of escaping rules are different!).

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.

Answer 13

Haskell + hgl, 39 bytes

ay(U$nrP.*ubs 10)<fn(few[0]<st)<sPN<bs0

Attempt This Online!

Using parsers, 39 bytes

ay(U$nrP.*ubS 10)<uP(h_<*lA(nχ 0))<bS0

Inverted output (invalid), 38 bytes

mF(U(rPr.*ubs 10)*/*few[0]<st)<sPN<bs0

This outputs True when the number has no easy factors and False when it has none. Basically this behaves like a primality test.

The challenge doesn't permit this sort of IO but it's significantly different from the other solution so I thought I would include it.

Reflection

I don't have any expectation that hgl do well on number theoretic challenges like this (yet). However I feel that most the length here doesn't come from the number theory. The machinery around it seems to be a big part of the issue.

• Built-ins for F nsw and F new.
• Shortcuts for ubs x and ubS x where x is a small integer. In particular we want ubs 10 and ubS 10. Either of these would have saved 3 bytes on our total answer.
• There should be something for "not all". This challenge doesn't allow inverted output so it would be needed in place of mF for the last example to be valid.
• I think there should probably be shortcuts for lA<χ and lA<nχ. Possibly also lA<kB.
• I should get around to implementing functions surrounding the Read class.