22
\$\begingroup\$

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 , 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

\$\endgroup\$

12 Answers 12

7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Quick question about Retina: What does the leading newline do? \$\endgroup\$ – HyperNeutrino Mar 24 '17 at 21:20
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Mar 24 '17 at 21:20
  • \$\begingroup\$ 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. \$\endgroup\$ – HyperNeutrino Mar 24 '17 at 21:21
  • \$\begingroup\$ Could the last line be ;(11+)+,\1+; \$\endgroup\$ – Riley Mar 26 '17 at 1:08
  • \$\begingroup\$ @Riley that doesn't guarantee that the first segment is a multiple of the same factor. \$\endgroup\$ – Martin Ender Mar 26 '17 at 5:31
6
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ I think you can drop the D, as make_digits is in effect for ŒṖ. \$\endgroup\$ – Jonathan Allan Mar 25 '17 at 17:36
  • \$\begingroup\$ For some reason, I assumed that would create a range... Thanks! \$\endgroup\$ – Dennis Mar 25 '17 at 19:25
3
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice answer! You can save one byte with either {#~Mod~10^n,#/10^n} or {Mod[#,t=10^n],#/t}. \$\endgroup\$ – Greg Martin Mar 25 '17 at 1:00
  • \$\begingroup\$ 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! \$\endgroup\$ – Not a tree Mar 25 '17 at 1:07
  • \$\begingroup\$ fair point on Mod[#,10]^n \$\endgroup\$ – Greg Martin Mar 25 '17 at 1:40
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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;}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – user81655 Mar 25 '17 at 9:59
  • \$\begingroup\$ Also I believe t='' could be t=0, since adding c coerces it to a string anyway. \$\endgroup\$ – user81655 Mar 25 '17 at 10:15
  • \$\begingroup\$ @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. \$\endgroup\$ – Neil Mar 25 '17 at 10:24
  • \$\begingroup\$ 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 \$\endgroup\$ – user81655 Mar 25 '17 at 10:27
  • \$\begingroup\$ @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. \$\endgroup\$ – Neil Mar 26 '17 at 0:25
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ from fractions import* would save 3 bytes \$\endgroup\$ – Dead Possum Mar 24 '17 at 21:45
  • \$\begingroup\$ 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 \$\endgroup\$ – Dead Possum Mar 24 '17 at 22:02
  • \$\begingroup\$ 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))) \$\endgroup\$ – ovs Mar 24 '17 at 22:23
  • \$\begingroup\$ @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...) \$\endgroup\$ – HyperNeutrino Mar 24 '17 at 23:08
  • \$\begingroup\$ You can remove a byte (almost nothing) by remove the whitespace between )) for \$\endgroup\$ – caird coinheringaahing Mar 25 '17 at 23:58
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ If anyone knows how to render a $<backquote> in SE markdown, I'd be grateful if you tell me how. \$\endgroup\$ – Dada Mar 25 '17 at 9:28
  • 1
    \$\begingroup\$ 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!). \$\endgroup\$ – user62131 Mar 25 '17 at 23:55
  • \$\begingroup\$ @ais523 Wonderful, thank you very much! :) \$\endgroup\$ – Dada Mar 27 '17 at 8:03
0
\$\begingroup\$

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.

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