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,2

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.

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.

Example

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

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]

Crossrefs

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

Sequence in context: A123733 A261069 A236557 * A262943 A357735 A163892

Adjacent sequences: A359240 A359241 A359242 * A359244 A359245 A359246

Keyword

nonn

Author

Michael De Vlieger, Jan 16 2023

Status

approved