33
\$\begingroup\$

Given a list of positive integers, output whether every adjacent pair of integers in it shares a prime factor. In other words, output truthy if and only if no two neighboring integers in the list are co-prime.

In yet other terms: given a list of positive integers [a1 a2 … an], output whether

       gcd(a1, a2) > 1 && gcd(a2, a3) > 1 && … && gcd(an−1, an) > 1.

The list will always contain at least two elements (n ≥ 2).

However…

This challenge is also : the codepoints in your answer (whatever codepage it may be in) must satisfy the condition your program checks for.

For example, print 2 is a valid program. As a list of Unicode codepoints it is [112 114 105 110 116 32 50], which satisfies this condition: 112 and 114 share a factor of 2; and 114 and 105 share a factor of 3, etc.

However, main can not occur in a valid program (sorry!), as the Unicode codepoints of m and a, namely 109 and 97, are coprime. (Thankfully, your submission needn’t be a full program!)

Your program isn’t allowed to contain codepoint 0.

Test cases

Truthy:

[6 21] -> 1
[502 230 524 618 996] -> 1
[314 112 938 792 309] -> 1
[666 642 658 642 849 675 910 328 320] -> 1
[922 614 530 660 438 854 861 357 477] -> 1

Falsy:

[6 7] -> 0
[629 474 502 133 138] -> 0
[420 679 719 475 624] -> 0
[515 850 726 324 764 555 752 888 467] -> 0
[946 423 427 507 899 812 786 576 844] -> 0

This is : the shortest code in bytes wins.

\$\endgroup\$
6
  • 9
    \$\begingroup\$ For anyone attempting this challenge in a normal programming language, this is a list of characters that have prime codepoints in ASCII: %)+/5;=CGIOSYaegkmq\DEL. \$\endgroup\$ Aug 13, 2017 at 13:48
  • \$\begingroup\$ @Lynn Do Truthys have to be consistent? \$\endgroup\$
    – H.PWiz
    Aug 13, 2017 at 14:24
  • 1
    \$\begingroup\$ @H.PWiz Nope! — \$\endgroup\$
    – Lynn
    Aug 13, 2017 at 14:25
  • 1
    \$\begingroup\$ I actually intended this to be doable for some normal (non-golf) langs, and I was feeling hopeful when I noticed that print 2 was valid, but );=ae being prime is really tough, I didn’t consider that… I wonder if something like Haskell can compete? \$\endgroup\$
    – Lynn
    Aug 13, 2017 at 14:56
  • \$\begingroup\$ This restriction is easier than the reverse of this question, assume no-one use 0x02 byte. That question get nongolf valid answer in Mathematica, Logo, Haskell, Python, Perl, TI-BASIC. This one already got a Haskell, I think Mathematica is impossible, but Logo looks very likely to be possible, although I've not yet done constructing the solution. \$\endgroup\$
    – DELETE_ME
    Oct 5, 2017 at 16:13

8 Answers 8

15
\$\begingroup\$

MATL, 14 bytes

!TM1*Zdl2$Xdl-

This outputs a non-empty column vector of nonzero numbers as truthy, or a vector containing at least a zero entry as falsy.

Explanation

!     % Implicit input. Transpose
TM    % Push input to latest function again
1*    % Multiply by 1 (does nothing, but matches factors)
Zd    % Compute gcd with broadcast: matrix of gcd of all pairs
l     % Push 1
2$    % The next function will use 2 inputs
Xd    % Extract diagonal 1 (i.e. that below the main diagonal) from the matrix
l-    % Subtract 1 from each entry. Implicitly display
\$\endgroup\$
1
14
+150
\$\begingroup\$

Haskell, 103 100 bytes

EDIT:

  • -3 bytes: Used a d<-fz guard to merge and shorten the last two lines.

f is the main function, which takes a list of integers and returns a Bool.

Note that the first two ԁs (only) are Cyrillic (Komi) Unicode characters, and there's a tab character before the first one.

f	ԁ=zb[ԁ]id
zb[h:p:l]fz=z h p&&zb[p:l]fz
zb l fz=z 0 2
z 0z=z>z^0
z f fz|f<fz=z fz f|d<-fz=z d$f-d

Try it online! or test it on itself.

How it works

  • f is the main function. All it does is wrap its argument ԁ in a singleton list (because the prime ASCII value of ) makes parentheses much more awkward to use than square brackets) and call zb with that and a dummy argument (the Haskell function id happens to have just the right characters to fit here).
    • Getting the same character to fit besides both of =] is impossible with plain ASCII, so the argument is named with the 2-byte Unicode character CYRILLIC SMALL LETTER KOMI DE (ԁ), codepoint value 3*7*61=U+0501, which fits with all of those and [.
      • Since the codepoint is not even (the smallest option that is a legal identifier and also even uses three bytes), this required using a tab character instead of a space before it.
      • A seven bytes longer plain ASCII option is to rename the argument: f fz|bf<-fz=zb[bf]fz.
  • zb takes two arguments, a singleton list whose element is the real list of numbers being recursed on, and a dummy argument fz needed only to get a z before the function's =s.
    • When the inner list has at least two elements, the function z is called with the first two (named h and p), and if that returns True, zb recurses on the tail p:l of the list.
    • If the inner list has fewer than two elements, zb returns True. Since = needs to be followed by the character z, the simplest way to do this is to use a call of the z function that itself is known to return True.
  • z takes two arguments and recursively calculates their greatest common divisor using subtraction (every other relevant integer division or gcd function is unavailable), returning True if it's greater than one.
    • The recursion ends when the first argument is 0, with the second argument being the gcd. On this line the second argument is also named z. The character 1 is awkward here so z^0 is used to get the number one.
    • Otherwise, if the first argument f is smaller than the second fz, they are swapped and z recurses.
    • Otherwise, the smaller argument is subtracted from the larger, then z recurses (also swapping the arguments, although that's just to avoid parentheses.)
\$\endgroup\$
5
  • 2
    \$\begingroup\$ I knew there had to be some non-golf language that could pull it off! \$\endgroup\$
    – Lynn
    Aug 14, 2017 at 8:03
  • 3
    \$\begingroup\$ @Lynn It really helps Haskell in this kind of challenge that it has a fairly expressive syntactic subset with just single-character tokens. Which is about halfway to a golfing language, I guess. \$\endgroup\$ Aug 14, 2017 at 16:00
  • \$\begingroup\$ Because of the Cyrillic, is this really 100 bytes? The Code Golf Graduation userscript reports 102 UTF-8 bytes, but I don't know if it's accurate/that's the right way to count the bytes here. No matter how many bytes, it's really impressive! \$\endgroup\$
    – Mark S.
    Aug 14, 2017 at 18:51
  • 2
    \$\begingroup\$ @MarkS. TIO reports 100 bytes (and 98 chars). I suspect you got caught out by the tab character, which SE displays as 3 spaces (which then gets copied as such). I think I've seen someone use pre tags to avoid that, let me try to fix it. \$\endgroup\$ Aug 14, 2017 at 23:35
  • \$\begingroup\$ @MarkS. Done. Although I suspect that might just confuse that userscript even more. \$\endgroup\$ Aug 14, 2017 at 23:50
10
\$\begingroup\$

05AB1E, 8 bytes

Code

ü‚ÒüÃP≠P

Uses the 05AB1E encoding, which gives us the following list of code points:

hex: [0xFC, 0x82, 0xD2, 0xFC, 0xC3, 0x50, 0x16, 0x50]
dec: [252,  130,  210,  252,  195,  80,   22,   80]

Try it online! or Verify the source code!

Explanation

Since the gcd operator (¿) has a prime code point I had to look for other ways to check coprimality:

ü‚          # Get an array of adjacent pairs of the input
  Ò         # Factorize both elements of each pair in the array
   üà       # For each pair, get the intersection of both prime factorization lists
     P      # Product of each intersection (this leaves 1 when there is no intersection)
      ≠     # Check for each element whether it does not equal 1
       P    # Product of the booleans
\$\endgroup\$
3
  • \$\begingroup\$ What code points does this have in 05AB1E's code page? Can you add them into the answer? \$\endgroup\$
    – Mr. Xcoder
    Aug 13, 2017 at 13:56
  • \$\begingroup\$ @Mr.Xcoder added \$\endgroup\$
    – Adnan
    Aug 13, 2017 at 14:04
  • \$\begingroup\$ Any reason for Ò over f? \$\endgroup\$ Aug 15, 2017 at 2:08
10
\$\begingroup\$

Husk, 8 bytes

For Truthy inputs it returns a positive integer, for Falsy it returns 0

←▼`Ṡt(ż⌋

Try it online! and Tested on its own codepoints

Uses Husk's codepage

Source -- [ ←  , ▼  , `  , Ṡ  , t  , (  , ż  , ⌋  ]
Hex    -- [0x06,0xbd,0x60,0xd0,0x74,0x28,0xeb,0x8d]
Dec    -- [6   ,189 ,96  ,208 ,116 ,40  ,235 ,141]

Explanation

          -- implicit input, e.g                                  [63,36,18,3]
  `       -- flip the args of the next function
   Ṡ      -- some combinator (Ṡ f g x = f (g x) x)
    t     -- tail                                                 [36,18,3]
      ż   -- zipWith (note, keeps trailing elems of longer list)  [(63,36),(36,18),(18,3),(3)]
       ⌋  -- gcd                                                  [9,9,3,3]
     (    -- used just to match restricted source criteria
 ▼        -- minimum of the list                                    3
←         -- minus 1                                                2
\$\endgroup\$
9
  • \$\begingroup\$ What is the notation called you use in the explanation for ? I see it on the docs too in the "type" column on the commands page and can't get my head around it so want to look it up so I might be able to learn it. \$\endgroup\$ Aug 13, 2017 at 15:01
  • \$\begingroup\$ @JonathanAllan That's the definition of the function in Haskell's syntax. It translates roughly to Ṡ(f,g,x) = f(g(x),x) in more mainstream languages. \$\endgroup\$
    – Zgarb
    Aug 13, 2017 at 15:35
  • \$\begingroup\$ source link \$\endgroup\$
    – H.PWiz
    Aug 13, 2017 at 15:36
  • \$\begingroup\$ Although, when flipped, it becomes `Ṡ g f x = Ṡ f g x = f (g x) x \$\endgroup\$
    – H.PWiz
    Aug 13, 2017 at 15:44
  • 1
    \$\begingroup\$ @JonathanAllan If you join the Husk chatroom, we can try to explain it better there. \$\endgroup\$
    – Zgarb
    Aug 13, 2017 at 15:53
5
\$\begingroup\$

Japt, 8 7 bytes

äj d¹¥Z

Test it online!

Code points:

Char    ä   j       d   ¹   ¥   Z
Hex    e4  6a  20  64  b9  a5  5a
Dec   228 106  32 100 185 165  90

Explanation

 äj d¹ ¥ Z
Uäj d) ==Z
             Implicit: U = input array, Z = 0
Uä           For each pair of items in the array:
  j            Return whether the two items are coprime.
    d)       Return true if any items are truthy, false otherwise.
       ==Z   Return whether this is equal to 0 (false -> true, true -> false).
             Implicit: output result of last expression
\$\endgroup\$
5
\$\begingroup\$

Jelly, 11 9 bytes

,Pnælð2\P

Saved 2 bytes thanks to @Jonathan Allan.

Try it online!

Jelly has its own code-page and the codepoints of each character are

Chr Hex Dec
,   2c   44
P   50   80
n   6e  110
æ   16   22
l   6c  108
ð   18   24
2   32   50
\   5c   92
P   50   80

This tests for non-coprime numbers by checking if lcm(a, b) != a*b. There might be a shorter solution as I just filtered for characters with even codepoints.

Explanation

,Pnælð2\P  Input: array A
      2\   For each overlapping sublist of size 2
     ð       Reduce it using this dyad
,              Pair
 P             Product
  n            Not equals, 1 if true else 0
   æl          LCM
        P  Product
\$\endgroup\$
3
  • \$\begingroup\$ Genius! This is incredible :O \$\endgroup\$
    – Mr. Xcoder
    Aug 13, 2017 at 13:45
  • \$\begingroup\$ , is even so you can do æln,P¥ð2\ for two less. Edit: I dropped the trailing P, make that one less :p) \$\endgroup\$ Aug 13, 2017 at 14:12
  • \$\begingroup\$ Oh yeah, swap the arguments even :) \$\endgroup\$ Aug 13, 2017 at 14:33
5
\$\begingroup\$

TI-BASIC, 38 bytes

Input L1:ΔList(cumSum(L1:augment(Ans+V,V+{0:2>sum(AnsL1=lcm(Ans+V,V+L1

TI-BASIC is tokenized into one- or two-byte tokens, as listed here.

The trickiest parts of this solution were:

  1. The comma token is a prime number (43), forcing me to surround it with multiples of 43 (in this case the V token, which is 86).

  2. The gcd( token is a large prime number (47881), which means it couldn't be used at all.

The tokens for this program come out to:

token     hex     dec
Input     0xDC    220
L1        0x5D00  23808
:         0x3E    62
ΔList(    0xBB2C  47916
cumSum(   0xBB29  47913
L1        0x5D00  23808
:         0x3E    62
augment(  0x14    20
Ans       0x72    114
+         0x70    112
V         0x56    86
,         0x2B    43
V         0x56    86
+         0x70    112
{         0x08    8
0         0x30    48
:         0x3E    62
2         0x32    50
>         0x6C    106
sum(      0xB6    182
Ans       0x72    114
L1        0x5D00  23808
=         0x6A    106
lcm(      0xBB08  47880
Ans       0x72    114
+         0x70    112
V         0x56    86
,         0x2B    43
V         0x56    86
+         0x70    112
L1        0x5D00  23808

Explanation

Input L1:                   Prompt the user to input L1.

ΔList(cumSum(L1:            Take the differences of the prefix sum of L1,
                            which in effect removes the first element (result in Ans).

augment(Ans+V,V+{0:         Append a 0 to the end of Ans.
                            V defaults to 0, so adding it is a no-op.
                            Ans now holds L1 shifted to the left by one element,
                            with a 0 shifted in.

      AnsL1=lcm(Ans+V,V+L1  Take the least common multiple of each corresponding element
                            of Ans and L1, and check if each is equal to their product.
                            This returns a list of booleans, each 1 corresponding to
                            a co-prime pair. The last element (having been paired with 0)
                            will always be 1.

2>sum(                      Returns 1 if there is at most one 1 in the list, else 0.
                            Since the last element is always 1, this means
                            we return 1 only if there are no co-prime pairs.
\$\endgroup\$
3
\$\begingroup\$

Pyth, 15 bytes

&F.bPiFNP.TtBQQ

Try it here or Check out Test Suite.

This is a collaborative effort between Erik the Outgolfer and Mr. Xcoder. Returns an inconsistent value (non-empty list) for truthy, and the empty list for falsy.


ASCII-values

[38, 70, 46, 98, 80, 105, 70, 78, 80, 46, 84, 116, 66, 81, 81]

Which share the following factors:

[2, 2, 2, 2, 5, 35, 2, 2, 2, 2, 4, 2, 3, 81]

Explanation

&F.bPiFNP.TtBQQ
           tBQ   Return [Q, Q[1:]] (Q = eval first line of input)
         .T      Transpose ^ without cropping absences
        P        Remove last element of ^
  .b          Q  Map in parallel on ^ (N) and Q (Y, ignored)
     iFN           GCD of N
    P              Prime factors of ^ (P(1) = [])
&F               Left fold (reduce) the result of the map with Logical AND (short-circuiting)

Without the requirement, this would've been a 7 5-byte version accomplishing the same task (-2 thanks to FryAmTheEggman):

-1iVt

Explanation

-1iVtQQ  Implicit QQ at the end
    tQ   Return Q[1:]
  iV  Q  Vectorized GCD on ^ and Q
-1       Remove every element of ^ from [1] (implicit singleton)
\$\endgroup\$
2
  • \$\begingroup\$ Out of curiosity, why do you need the Qs at the end? \$\endgroup\$ Aug 14, 2017 at 17:44
  • \$\begingroup\$ @ETHproductions Because .b has variable arities, and using implicit input means it will pick the lowest (1) instead of then intended (2). \$\endgroup\$ Aug 14, 2017 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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