# No co-prime neighbors

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.

• 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. – Cristian Lupascu Aug 13 '17 at 13:48
• @Lynn Do Truthys have to be consistent? – H.PWiz Aug 13 '17 at 14:24
• @H.PWiz Nope! — – Lynn Aug 13 '17 at 14:25
• 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? – Lynn Aug 13 '17 at 14:56
• 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. – user202729 Oct 5 '17 at 16:13

# 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. • Try it online! • Verify all test cases. The footer code contains an if branch to test truthyness/falsyness. • Since MATL uses ASCII, the source code is encoded as [33 84 77 49 42 90 100 108 50 36 88 100 108 45]  ### 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


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


# 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.)
• I knew there had to be some non-golf language that could pull it off! – Lynn Aug 14 '17 at 8:03
• @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. – Ørjan Johansen Aug 14 '17 at 16:00
• 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! – Mark S. Aug 14 '17 at 18:51
• @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. – Ørjan Johansen Aug 14 '17 at 23:35
• @MarkS. Done. Although I suspect that might just confuse that userscript even more. – Ørjan Johansen Aug 14 '17 at 23:50

# 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]


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

• What code points does this have in 05AB1E's code page? Can you add them into the answer? – Mr. Xcoder Aug 13 '17 at 13:56
• Any reason for Ò over f? – Magic Octopus Urn Aug 15 '17 at 2:08

# Husk, 8 bytes

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

←▼Ṡt(ż⌋


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

• 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. – Jonathan Allan Aug 13 '17 at 15:01
• @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. – Zgarb Aug 13 '17 at 15:35
• source link – H.PWiz Aug 13 '17 at 15:36
• Although, when flipped, it becomes Ṡ g f x = Ṡ f g x = f (g x) x – H.PWiz Aug 13 '17 at 15:44
• @JonathanAllan If you join the Husk chatroom, we can try to explain it better there. – Zgarb Aug 13 '17 at 15:53

# 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


# 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

• Genius! This is incredible :O – Mr. Xcoder Aug 13 '17 at 13:45
• , is even so you can do æln,P¥ð2\ for two less. Edit: I dropped the trailing P, make that one less :p) – Jonathan Allan Aug 13 '17 at 14:12
• Oh yeah, swap the arguments even :) – Jonathan Allan Aug 13 '17 at 14:33

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


# Pyth, 15 bytes

&F.bPiFNP.TtBQQ


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  (implicit singleton)

• Out of curiosity, why do you need the Qs at the end? – ETHproductions Aug 14 '17 at 17:44
• @ETHproductions Because .b has variable arities, and using implicit input means it will pick the lowest (1) instead of then intended (2). – Erik the Outgolfer Aug 14 '17 at 17:45