cp's OEIS Frontend

A366908 Lexicographically earliest infinite sequence of distinct positive integers such that, for n > 1, a(n) shares a factor with n but does not equal n, while not sharing a factor with a(n-1).

%I A366908 #18 Oct 30 2023 09:48:38
%S A366908 1,4,9,2,15,8,21,10,3,5,22,27,26,7,25,6,85,12,95,14,33,16,69,28,45,13,
%T A366908 18,35,58,39,155,24,11,17,20,51,74,19,36,55,82,49,86,77,30,23,94,57,
%U A366908 56,65,34,91,106,63,40,119,38,29,118,75,122,31,81,32,105,44,201,46,87,50,213,52,219,37
%N A366908 Lexicographically earliest infinite sequence of distinct positive integers such that, for n > 1, a(n) shares a factor with n but does not equal n, while not sharing a factor with a(n-1).
%C A366908 To ensure the sequence is infinite a(n) must be chosen so that it does not have as prime factors all the distinct prime factors of n+1. The first time this rule is required is when determining a(15); see the examples below.
%C A366908 For the terms studied the primes appear in their natural order except for 11 and 13 which are reversed. The sequence is conjectured to be a permutation of the positive integers.
%C A366908 Observation: apart from a(4) = 2, a(9) = 3, and a(33) = 11, prime a(n) is such that n is congruent to +- 2 (mod 12). - _Michael De Vlieger_, Oct 29 2023
%H A366908 Scott R. Shannon, <a href="/A366908/b366908.txt">Table of n, a(n) for n = 1..10000</a>
%H A366908 Michael De Vlieger, <a href="/A366908/a366908_1.png">Log log scatterplot of a(n)</a>, n = 1..2^12, showing primes in red, composite prime powers in gold, squarefree composites in green, and numbers neither squarefree nor prime powers in blue, with numbers in the last category that are squareful in light blue.
%H A366908 Michael De Vlieger, <a href="/A366908/a366908_2.png">List of a(n)</a>, n = 1..576, read left to right in 24 rows of 24 terms each, demonstrating the confinement of most prime a(n) to n congruent to +/- 2 (mod 12). Primes appear in red, following the color convention established immediately above.
%H A366908 Scott R. Shannon, <a href="/A366908/a366908.png">Image of the first 100000 terms</a>. The green line is a(n) = n.
%e A366908 a(4) = 2 as 2 does not equal 4, shares the factor 2 with 4 while not sharing a factor with a(3) = 9.
%e A366908 a(15) = 25 as 25 does not equal 15, shares the factor 5 with 15 while not sharing a factor with a(14) = 7. Note that 6 is unused and satisfies these requirements but as 15 + 1 = 16 = 2^4 only contains 2 as a distinct prime factor, a(15) cannot also contain 2 as a factor else a(16) would not exist.
%t A366908 nn = 1000;
%t A366908   c[_] := False; m[_] := 1;
%t A366908   f[x_] := f[x] = Times @@ FactorInteger[x][[All, 1]];
%t A366908   a[1] = 1; j = a[2] = 4; c[1] = c[4] = True; u = 2;
%t A366908   Do[k = u;
%t A366908     If[PrimePowerQ[n], p = FactorInteger[n][[1, 1]]; k = m[p];
%t A366908      While[
%t A366908       Or[c[#], ! CoprimeQ[j, #], Divisible[#, f[n + 1]], # == n] &[k p],
%t A366908        k++]; k *= p; While[c[p m[p]], m[p]++],
%t A366908     While[
%t A366908       Or[c[k], ! CoprimeQ[j, k], CoprimeQ[k, n], Divisible[k, f[n + 1]],
%t A366908         k == n], k++] ];
%t A366908     Set[{a[n], c[k], j}, {k, True, k}];
%t A366908     If[k == u, While[c[u], u++]], {n, 3, nn}];
%t A366908 Array[a, nn] (* _Michael De Vlieger_, Oct 29 2023 *)
%Y A366908 Cf. A159193, A093714, A085229, A119018, A000027.
%K A366908 nonn
%O A366908 1,2
%A A366908 _Scott R. Shannon_, Oct 27 2023