A359243 a(1) = 1, a(2) = 2; let j = a(n-1); for n > 2, if j is prime then a(n) = least novel k such that phi(k)/k < phi(j)/j, else a(n) = least novel k such that phi(k)/k > phi(j)/j, where phi(x) = A000010(x).

1, 2, 6, 3, 4, 5, 8, 7, 9, 11, 10, 13, 12, 14, 15, 17, 16, 19, 18, 20, 21, 23, 22, 25, 29, 24, 26, 27, 31, 28, 32, 33, 35, 37, 30, 34, 38, 39, 41, 36, 40, 43, 42, 44, 45, 47, 46, 49, 53, 48, 50, 51, 55, 59, 52, 57, 61, 54, 56, 58, 62, 63, 65, 67, 60, 64, 69, 71

Offset: 1

Author

Michael De Vlieger, Jan 16 2023

Keywords

• nonn

Comments

Permutation of natural numbers.

Once we have a(n) = prime(m), we require a(n+1) = u, the smallest missing number. Thereafter, we find the smallest k new to the sequence such that phi(k)/k > phi(j)/j, where j = a(n-1) until we reach another prime. Primes appear in order, since phi(p)/p = (p-1)/p.

Sequence can be interpreted as an irregular triangle where row 0 = {1} and row m > 1 begins with prime(m). In such a triangle, we observe prime(m) > min(row m) for m > 5, yet we can find prime(m) either less than or exceeding max(row m) for 2^20 terms of this sequence, or m = 1..82032.

Since phi(k)/k ascribes to squarefree kernel K = rad(k) = A007947(k) and K < mK where mK is nonsquarefree yet rad(m) | K, squarefree k appear before mK. For example, a(3) = 6 and a(13) = 12; a(11) = 10 and a(20) = 20, etc.

Odd prime numbers tend to appear early, even numbers tend to appear late.

Examples

			Let f(x) = phi(x)/x.
a(3) = 6 since 2 is prime and f(k) >= f(2) = 1/2 for k in {3, 4, 5}.
a(4) = 3 since f(3) < f(6) = 1/3.
a(5) = 4 since 3 is prime and f(4) < f(3) = 2/3.
a(6) = 5 since f(5) > f(4) = 1/2.
a(7) = 8 since 5 is prime and f(7) >= f(5) = 4/5 but f(8) = 1/2 < 4/5, etc.
Sequence written as an irregular triangle where row 0 = {1} and row m starts with prime(m):
   1;
   2,  6;
   3,  4;
   5,  8;
   7,  9;
  11, 10;
  13, 12, 14, 15;
  17, 16;
  19, 18, 20, 21;
  23, 22, 25;
  29, 24, 26, 27;
  31, 28, 32, 33, 35; ...
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..16384
• Michael De Vlieger, Scatterplot of a(n) - n, n = 1..300, showing primes in red, odd nonprime in blue, even composites in gold, and primorials in magenta.
• Michael De Vlieger, Scatterplot of a(n) - n, n = 1..2^16 with color function as immediately above.
• Michael De Vlieger, Scatterplot of a(n) - n, n = 1..300, showing primes in red, composite prime powers (in A246547) in gold, squarefree composites (in A120944) in green, numbers neither squarefree nor prime power (in A126706) in small blue, products of composite prime powers (in A286708) in large blue, and primorials in magenta.
• Michael De Vlieger, Scatterplot of a(n) - n, n = 1..2^16 with color function as immediately above.
• Michael De Vlieger, Scatterplot of phi(a(n)) for n = 1..2^12 with color function as immediately above. This plot relates to that of A307540.

Crossrefs

Cf. A000010, A000040, A002110, A007947, A307540.

Programs

Mathematica

nn = 120; c[] = False; f[n] := EulerPhi[n]/n; Array[Set[{a[#], c[#]}, {#, True}] &, 2]; j = a[2]; m = f[j]; u = 3; Do[k = u; If[PrimeQ[j], While[Nand[! c[k], f[k] < m], k++], While[Nand[! c[k], f[k] > m], k++]]; Set[{a[n], c[k], j, m}, {k, True, k, f[k]}]; If[k == u, While[c[u], u++]], {n, 3, nn}]; Array[a, nn]