No co-prime neighbors

Question

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 [a₁ a₂ … a_n], output whether

　　　　　　　gcd(a₁, a₂) > 1 && gcd(a₂, a₃) > 1 && … && gcd(a_n−1, a_n) > 1.

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

However…

This challenge is also restricted-source: 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 code-golf: the shortest code in bytes wins.

Answer 1

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]
  

  which satisfies the requirement.

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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.

Answer 8

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 restricted-source 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)