TransWikia.com

Seventeen positive integers

Puzzling Asked on September 2, 2021

Find 17 positive integers such that no four of them have, pairwise, a common divisor greater than 1, but, likewise, no four of them are, pairwise, relatively prime.

Do so in such a way that the largest of those numbers is as small as possible.

2 Answers

The following 12 numbers satisfy the conditions:

$$203,385,437,713,814,1330,1479,1495,2418,3441,11951,70499$$

Represented as a graph where the numbers are its vertices, two of which are joined by an edge if they have a common divisor greater than 1, the graph can be shown not to have a complete subgraph on four vertices ($K_4$):

graph

nor does its complement:

complement graph

In SageMath Cell Server it can be evaluated.

Answered by Freddy Barrera on September 2, 2021

I must admit that I looked this up, but the largest graph which works turns out to be unique, and is called

Now all that remains is to label the vertices appropriately. One easy way to do this is to

Of course the numbers you get are rather large. You can improve this a bit as follows:

There may be a way to reduce the numbers further.

Answered by Jaap Scherphuis on September 2, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP