Given a word, treat every letter as it's number in English alphabet (so a becomes 1, b becomes 2, z becomes 26 and so on), and check if all of them, including duplicates, are pairwise coprime.

The input is exactly one word of lowercase English letters. The output is the fact if the word is coprime: any truthy/falsey values, but only two variants of them. Standard loopholes are forbidden.

Test cases:

  • man: True
  • day: True (thanks to Ørjan Johansen)
  • led: False (l=12 and d=4 have gcd=4)
  • mana: True (though a occurs multiple times, 1 and 1 are coprimes)
  • mom: False (gcd(13,13)=13))
  • of: False (thanks to xnor; though 15∤6, gcd(15,6)=3)
  • a: True (if no pairs of letters, treat the word as coprime too)

This is a , so the shortest code in bytes wins!

  • 1
    Can we output 0 if they are coprime and 1 if not? – dylnan Sep 27 at 1:08
  • 2
    Suggested test case that would have caught a buggy answer: day: True – Ørjan Johansen Sep 27 at 6:00
  • 1
    I'd also suggest of: False to have a false example where no value is a multiple of another. – xnor Sep 27 at 6:04
  • @dylnan no, it's contr-intuitive. Anyway, Dennis'es answer is better ;-) – bodqhrohro Sep 27 at 9:37
  • @LuisMendo any truthy/falsey, but only two. – bodqhrohro Sep 27 at 9:51

26 Answers 26

Wolfram Language (Mathematica), 36 bytes

CoprimeQ@@LetterNumber@Characters@#&

Try it online!


Wolfram Language (Mathematica), 33 bytes

  • Thanks to Misha Lavrov for this three bytes shorter version.
CoprimeQ@@(ToCharacterCode@#-96)&

Try it online!

  • 1
    CoprimeQ@@(ToCharacterCode@#-96)& is three bytes shorter. – Misha Lavrov Sep 27 at 2:22
  • @MishaLavrov Thank you. – Jonathan Frech Sep 27 at 3:12

Jelly, 10 bytes

ØaiⱮgþ`P$Ƒ

Try it online!

How it works

ØaiⱮgþ`P$Ƒ  Main link. Argument: s (string)

Øa          Yield "abc...xyz".
  iⱮ        Find the 1-based index of each c of s in "abc...xyz".
        $Ƒ  Call the monadic chain to the left.
            Yield 1 if the result is equal to the argument, 0 if not.
    gþ`       Take the GCDs of all pairs of indices, yielding a matrix.
       P      Take the columnwise product.
            For coprimes, the column corresponding to each index will contain the
            index itself (GCD with itself) and several 1's (GCD with other indices),
            so the product is equal to the index.

Haskell, 48 bytes

((==).product<*>foldr1 lcm).map((-96+).fromEnum)

Try it online!

Very straightforward: converts the string to a list of numbers and then checks whether the product is equal to the LCM.

Pyth, 9 bytes

{Ism{PhxG

Test suite

Explanation:
{Ism{PhxG   | Full code
{Ism{PhxGdQ | With implicit variables filled
------------+------------------------------------------
   m      Q | For each char d in the input:
    {P      |  list the unique prime factors of
      hx d  |  the 1-based index of d in
        G   |  the lowercase alphabet
  s         | Group all prime factors into one list
{I          | Output whether the list has no duplicates

did Pyth just outgolf Jelly?

Python 2 - 122 118 bytes

-4 bytes thanks to @JonathanAllan

This is honestly terrible, but I've spent way too long to not post this.

from fractions import*
def f(n):r=reduce;n=[ord(i)-96for i in n];return r(lambda x,y:x*y/gcd(x,y),n)==r(int.__mul__,n)

Try it Online

  • 4
    96 for ~> 96for; lambda x,y:x*y ~> int.__mul__. – Jonathan Frech Sep 27 at 3:14

05AB1E, 11 bytes

Ç96-2.Æ€¿PΘ

Try it online!

Explanation

Ç96-         # convert to character codes and subtract 96
    2.Æ      # get all combinations of size 2
       €¿    # gcd of each pair
         P   # product of gcds
          Θ  # is true
  • Is the final Θ really necessary? – Mr. Xcoder Sep 27 at 6:32
  • @Mr.Xcoder: No I suppose not. I just assumed we needed to use 2 distict values, but now that I look there is nothing in the challenge about it. Truthy/Falsy should be okay then. – Emigna Sep 27 at 6:53
  • @Emigna I added a clarification for that: there should be only two variants of output values. – bodqhrohro Sep 27 at 11:46
  • @bodqhrohro: OK. I rolled back to the previous version to conform to this new requirement. – Emigna Sep 27 at 11:55

Python 2, 77 68 64 bytes

lambda a:all(sum(ord(v)%96%i<1for v in a)<2for i in range(2,26))

Try it online!

Basically, (some pair in the input is not co-prime) if and only if (there is a number i > 1 which divides more than one of the inputs).

  • Looks like we had the same idea but you beat me by a few minutes :) Can't you save those 2 bytes by using all and <2 though? – Vincent Sep 27 at 5:00

Python 3, 61 59 bytes

Using python bytes as argument:

lambda s:all(sum(c%96%x<1for c in s)<2for x in range(2,24))

The last divisor to check is 23, the largest prime below 26.

Try it online!

Thanks to @Dennis for saving two bytes.

  • 3
    c%96%x<1for c in s saves 2 bytes. – Dennis Sep 27 at 5:21

Perl 6, 34 32 bytes

-2 bytes thanks to nwellnhof

{[lcm](@_)==[*] @_}o{.ords X-96}

Try it online!

An anonymous codeblock that takes a string and returns True or False. If the lowest common multiple of the letters is equal to the product of the letters than they share no common divisors.

Explanation:

                     {.ords X-96}  # Convert the letters to a list of numbers
 {                 }o              # Pass result to the next codeblock
  [lcm](@_)           # The list reduced by the lcm
           ==         # Is equal to?
             [*] @_   # The list reduced by multiplication

Brachylog, 11 bytes

ạ{-₉₆ḋd}ᵐc≠

Try it online!

Explanation

ạ{-₉₆ḋd}ᵐc≠
ạ              Split the input into its character codes
 {     }ᵐ      For each one
  -₉₆          Subtract 96 (a -> 1, b -> 2 etc.)
     ḋd        And find the unique (d) prime factors (ḋ)
         c     Combine them into one list
          ≠    And assert they are all different

J, 36 bytes

[:(1 =[:*/-.@=@i.@##&,+./~)_96+a.&i.

Ungolfed

[: (1 = [: */ -.@=@i.@# #&, +./~) _96 + a.&i.

Explanation

[: (                            ) _96 + a.&i.  NB. apply fn in parens to result of right
                                  _96 + a.&i.  NB. index within J's ascii alphabet, minus 96.
                                               NB. gives index within english alphabet
   (1 =                         )              NB. does 1 equal...
   (    [: */                   )              NB. the product of...
   (                    #&,     )              NB. Flatten the left and right args, and then copy
   (                        +./~)              NB. right arg = a table of cross product GCDs
   (          -.@=@i.@#         )              NB. the complement of the identity matrix.
                                               NB. this removes the diagonal.

Try it online!

  • [:(1=[:*/+./~#&,~#\~:/#\)_96+a.&i. for 34 bytes You had a space in `1 =' :) – Galen Ivanov Sep 27 at 6:43
  • 1
    Thanks @GalenIvanov – Jonah Sep 27 at 15:40

JavaScript (Node.js), 60 bytes

f=(s,v=23)=>n=v<2||f(s,v-1)&&Buffer(s).every(c=>c%32%v||n--)

Try it online!

  • 62 bytes by going recursive and using every(c=>c%32%v||n--,n=1). – Arnauld Sep 27 at 8:25
  • @Arnauld Thanks. And I golfed 2 more bytes from it. – tsh Sep 27 at 9:14

Jelly, 11 bytes

ŒcO_96g/€ỊẠ

Try it online!

  • Thanks to Dennis for NOTing my booleans

ŒcO_96g/€ỊẠ
Œc           All pairs of characters without replacement
  O          Code point of each character
   _96       Subtract 96. a->1, b->2, etc.
        €    For each pair:
      g/       Get the greatest common denominator
         Ị   abs(z)<=1? If they are all 1 then this will give a list of 1s
          Ạ  "All". Gives 1 if they are coprime, 0 if not.
  • 2
    ỊẠ flips the Booleans. – Dennis Sep 27 at 5:07
  • @Dennis nice, thanks – dylnan Sep 27 at 14:18

MATL, 10 bytes

96-YF&fdA&

Outputs 1 for coprime, 0 otherwise.

Try it online! Or verify all test cases.

Explanation

Consider input 'man' for example.

96-  % Implicit input: string. Subtract 96 from (the codepoint of) each element
     % STACK: [13 1 14] 
YF   % Exponents of prime factoriation. Each number produces a row in the result
     % STACK: [0 0 0 0 0 1;
               0 0 0 0 0 0;
               1 0 0 1 0 0]
&f   % Two-output find: pushes row and column indices of nonzeros
     % STACK: [3; 3; 1], [1; 4; 6]
d    % Consecutive differences
     % STACK: [3; 3; 1], [3; 2]
A    % All: gives true if the array doesn't contain zeros
     % STACK: [3; 3; 1], 1
&    % Alternative in/out specification: the next function, which is implicit
     % display, will only take 1 input. So only the top of the stack is shown

Python 3, 90 89 bytes

-1 byte by numbermaniac

f=lambda q,*s:s==()or all(math.gcd(ord(q)-96,ord(w)-96)<2for w in s)and f(*s)
import math

Try it online!

Use as f(*'man').

Retina 0.8.2, 45 bytes


;
{`\w
#$&
}T`l`_l
M`;(##+)\1*;(#*;)*\1+;
^0

Try it online! Explanation:


;

Insert separators between each letter and at the start and end.

{`\w
#$&

Prepend a # to each letter.

}T`l`_l

Move each letter 1 back in the alphabet, deleting the as. Then repeat the above operations until all the letters have been deleted. This converts each letter to its 1-based alphabet index in unary.

M`;(##+)\1*;(#*;)*\1+;

Test whether any two values share a common factor greater than 1. (This can find more than one pair of letters with a common factor, e.g. in the word yearling.)

^0

Check that no common factors were found.

R + pracma library, 75 bytes

function(w){s=utf8ToInt(w)-96;all(apply(outer(s,s,pracma::gcd),1,prod)==s)}

I'm using the gcd function in the pracma library as to my knowledge R does not have a built-in for that. I'm using the approach of comparing the product of the gcds to the numbers themselves.

65 bytes (credit: @J.Doe)

function(w)prod(outer(s<-utf8ToInt(w)-96,s,pracma::gcd))==prod(s)

Markov algorithm, as interpreted by eMain (474 484 463 bytes, 76 78 76 rules)

a->
d->b
f->bc
h->b
i->c
j->be
l->bc
n->bg
o->ce
p->b
q->q
r->bc
t->be
u->cg
v->bk
x->bc
y->e
z->bm
cb->bc
eb->be
gb->bg
kb->bk
mb->bm
qb->bq
sb->bs
wb->bw
ec->ce
gc->cg
kc->ck
mc->cm
qc->cq
sc->cs
wc->cw
ge->eg
ke->ek
me->em
qe->eq
se->es
we->ew
kg->gk
mg->gm
qg->gq
sg->gs
wg->gw
mk->km
qk->kq
sk->ks
wk->kw
qm->mq
sm->ms
wm->mw
sq->qs
wq->qw
ws->sw
bb->F
cc->F
ee->F
gg->F
kk->F
mm->F
qq->F
ss->F
ww->F
b->
c->
e->
g->
k->
m->
q->
s->
w->
FF->F
TF->F
!->.
->!T

The first 17 rules factor the "composite letters" into their "prime letter" factors, ignoring multiplicity. (E.g., t becomes be because 20 factors as a product of a power of 2 and a power of 5.)

The next 36 rules (such as cb->bc) sort the resulting prime factors.

The next 9 rules (such as bb->F) replace a repeated prime factor by F, then 9 more rules (such as b->) get rid of the remaining single letters.

At this point, we either have an empty string, or a string of one or more Fs, and the last rule ->!T adds a !T at the beginning. Then the rules FF->F and TF->F simplify the result to either !T or !F. At this point, the !->. rule applies, telling us to get rid of ! and halt: returning T for a coprime word, and F otherwise.

(Thanks to bodqhrohro for pointing out a bug in the earlier version that caused this code to give an empty string on input a.)

  • 1
    Gives neither T nor F on a testcase. – bodqhrohro Sep 29 at 13:09
  • @bodqhrohro Thanks for the catch! (In the end, my byte count went down, because I realized I was counting every newline as two bytes.) – Misha Lavrov Sep 29 at 17:28

Japt, 14 bytes

;à2 e_®nR+CÃrj

Try it online!

Takes input as an array of characters.

How it works

;à2 e_m_nR+C} rj
;                 Use alternative predefined variables (in this case, C = "a-z")
 à2               Get all pairs
    e_            Does all pairs satisfy that...
      m_            when the character pair is mapped over...
        nR+C}         conversion from "a-z" to [1..26]
              rj    then the two numbers are coprime?

Ruby, 56 bytes

->s{s.bytes.combination(2).all?{|a,b|2>(a-96).gcd(a-b)}}

Try it online!

Java 10, 86 bytes

a->{var r=1>0;for(int i=1,s=0;++i<24;r&=s<2,s=0)for(var c:a)s+=c%96%i<1?1:0;return r;}

Port of @Vincent's Python 3 answer.

Try it online.

Explanation:

a->{                 // Method with character-array parameter and boolean return-type
  var r=1>0;         //  Result-boolean, starting at true
  for(int s=0,       //  Sum integer, starting at 0
      i=1;++i<24     //  Loop `i` in the range (1, 24)
      ;              //    After every iteration:
       r&=s<2,       //     If the sum is >= 2: change the result to false
       s=0)          //     And reset the sum to 0
     for(var c:a)    //   Inner loop over the input-characters
       s+=c%96%i<1?  //    If the current character modulo-96 is divisible by `i`
           1         //     Increase the sum by 1
          :          //    Else
           0;        //     Leave the sum the same
  return r;}         //  Return the result-boolean

Japt, 13 bytes

Takes input as a character array.

®c uHÃà2 e_rj

Try it or verify all test cases

q, 121 111 bytes

{$[1=count x;1b;1b=distinct{r:{l:{$[0~y;:x;.z.s[y;x mod y]]}[y;]'[x];2>count l where l<>1}[x;]'[x]}[1+.Q.a?x]]}

JavaScript (Node.js), 87 82 bytes

a=>!/\b(11+)\1* (1+ )*\1+\b/.exec(Buffer(a).map(x=>w+=" ".padEnd(x-95,1),w="")&&w)

Try it online!

Original approach (87B)

a=>!(b=Buffer(a)).some((x,i)=>b.some((y,j)=>i-j&&(g=(p,q)=>q?g(q,p%q):p)(x-96,y-96)>1))

Try it online!

Stax, 16 bytes

è'B╕i4à!ùà╫æor4Z

Run and debug it

Explanation

2S{M{$e96-mm{E:!m|A     #Full program, unpacked, implicit input
2S                      #Generate all combinations of size 2
  {       m             #Map for each element
   M                    #Split into size of 1 element
    {       m           #Map for each element
     $e                 #Convert to number
       96-              #Subtract 96
           {    m       #Map for each element
            E:!         #Explode array onto stack, are they coprime
                 |A     #Are all elements of array truthy

Outputs 1 for True, 0 For false.

There is probably a better way to do the converting to number part, but it works.

  • Stax author here. Thanks for giving stax a try! Here's a program using your algorithm that packs to 10 bytes. 2SOF{96-F:!* Let me know if you want to know more about it. First one is free! – recursive Oct 1 at 17:49
  • @recursive Thank you for making Stax! It's my golfing language of choice at the moment. I can see how your answer works and I'll have to keep working to improve my answers in the future. – Multi Oct 1 at 19:24

APL(NARS), 16 chars, 32 bytes

{(×/p)=∧/p←⎕a⍳⍵}

This use method other used that LCM()=×/, it is fast but overflow if input array is enough long; other alternative solutions a little slower:

{1=×/y∨y÷⍨×/y←⎕a⍳⍵} 
{1=≢,⍵:1⋄1=×/{(2⌷⍵)∨1⌷⍵}¨{x←97-⍨⎕AV⍳⍵⋄(,x∘.,x)∼⍦x,¨x}⍵}

this below it seems 10 times faster(or+) than just above functions

∇r←h m;i;j;k;v
   r←i←1⋄k←≢v←97-⍨⎕AV⍳m
A: →F×⍳i>k⋄j←i+1⋄→C
B:   →E×⍳1≠(j⌷v)∨i⌷v⋄j←j+1
C:   →B×⍳j≤k
D: i←i+1⋄→A
E: r←0
F:
∇

i prefer this last because it is easier, faster, trusted (becaise less overflow possiblity), easier to write, and how it has to be (even if it has some bytes more...)

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.