| Bytes | Lang | Time | Link |
|---|---|---|---|
| 039 | Haskell + hgl | 240814T173947Z | Wheat Wi |
| 046 | Perl 5 | 170325T092608Z | Dada |
| 069 | Python 2 | 170326T025915Z | Dennis |
| 069 | Python 3 | 170325T042923Z | Dennis |
| 117 | Python 3 | 170324T211941Z | hyper-ne |
| 070 | JavaScript ES6 | 170324T220359Z | Neil |
| 008 | Brachylog 2 | 170325T233926Z | user6213 |
| 010 | Jelly | 170325T002134Z | Dennis |
| 057 | Haskell | 170325T092404Z | Laikoni |
| 062 | Mathematica | 170325T001933Z | Not a tr |
| 135 | C | 170324T225632Z | Steadybo |
| 090 | QBIC | 170324T220215Z | steenber |
| 029 | Retina | 170324T211229Z | Martin E |
Haskell + hgl, 39 bytes
ay(U$nrP.*ubs 10)<fn(few[0]<st)<sPN<bs0
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 nswandF new. - Shortcuts for
ubs xandubS xwherexis a small integer. In particular we wantubs 10andubS 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
- I think there should probably be shortcuts for
lA<χandlA<nχ. Possibly alsolA<kB. - I should get around to implementing functions surrounding the
Readclass.
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.
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.
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.
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)
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
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.
Brachylog (2), 8 bytes
~c₂ḋᵐ∋ᵐ=
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.
Jelly, 14 12 11 10 bytes
ŒṖḌo1g/€P>
Thanks to @JonathanAllan for golfing off 1 byte!
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.
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
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 lastndigits and the remainingm-ndigits (wheremis the total number of digits).Table[1~Max~#&/@...,{n,#}]does this for everynup 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.) The1~Max~#&/@bit gets rid of zeroes, so numbers like130 -> {13,0}don't count asTrue.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.
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;}
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
Retina, 31 29 bytes
,$';$`
\d+
$*
;(11+)\1*,\1+;
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.