A375024 a(n) is the length of the largest sequence S of distinct integers in the range 1..n such that for any prime number p, any run of consecutive multiples of p in S has length exactly 2, and two consecutive terms in S have some common prime factor.

1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 13, 13, 16, 16, 16, 16, 19, 19, 19, 19, 19, 19

Offset: 1

Author

Rémy Sigrist, Jul 28 2024

Keywords

• nonn
• more

Comments

Sequences like A280864 can be split into segments of consecutive terms with properties similar to the sequences S that we are considering here.

Examples

			Some solutions for small n:
  n   a(n)  Solution S
  --  ----  --------------------------------------------------------------
   1     1  1
   4     2  2,4
   6     3  2,6,3
  10     4  3,6,10,5
  15     7  3,6,10,15,12,14,7
  21    10  3,6,10,15,12,14,21,18,20,5
  33    13  3,6,10,15,12,14,21,18,22,33,24,20,5
  35    16  3,6,10,15,12,14,21,18,20,35,28,22,33,24,26,13
  39    19  3,6,10,15,12,14,21,18,20,35,28,22,33,24,26,39,36,34,17
  45    22  5,10,6,15,20,12,21,14,18,33,22,24,39,26,36,45,40,28,35,30,42,7
		

Links

• Rémy Sigrist, C++ program

Crossrefs

Cf. A280864, A283832, A373797.

Formula

a(n) <= A373797(n).

a(p) = a(p-1) for any prime number p.