A361232 Numbers m such that the increasing sequence of divisors of m, regarded as words on the finite alphabet of its prime factors, is ordered lexicographically.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 46, 47, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 61, 62, 64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 76, 77, 78, 79, 81

Offset

1,2

Comments

Let p_1^e_1 * p_2^e_2 * ... * p_r^e_r be the prime factorization of a number, with primes p_1 < p_2 < ... < p_r and e_j > 0. Then the number is in this sequence if and only if p_i > Product_{j < i} p_j^e_j for i=1..r.

Even though most small numbers belong to this sequence, this sequence has zero density (see the formula below).

Except for the first term 1, this sequence is a proper subsequence of A027855, where the condition on the prime factors only applies to the largest prime factor.

Stef and Tenenbaum call these numbers lexicographical.

Links

Table of n, a(n) for n=1..68.

A. Stef and G. Tenenbaum, Entiers lexicographiques, Ramanujan Journal, 2 (1998), 167-184.

Formula

Stef and Tenenbaum show that the count of these integers up to x is asymptotic to c*x/(log x)^b, where b is approximately 0.2228 and c is a positive constant. As a result, the n-th term of this sequence is asymptotic to (1/c)*n*(log n)^b.

Example

The number 12 is not in this sequence: Writing the divisors of 12 as 3^a*2^b where a=0,1 and b=0,1,2, the lexicographical order corresponds to (a,b)=(0,0),(0,1),(0,2),(1,0),(1,1),(1,2), i.e., 1,2,4,3,6,12, which is not the natural order.

Mathematica

list = {1}; U = 201;
For[n = 2, n <= U, n += 1, fa = FactorInteger[n]; om = Length[fa];
  r = 1; ga = 1;
  For[j = 1, j <= om, j++,
   If[fa[[j, 1]] <= r, ga = 0; Break[]];
   p = fa[[j, 1]]; A = fa[[j, 2]];
   r = r*p^A;
   ];
  If[ga == 1, AppendTo[list, n]; ];
  ];
Print[list]

Prog

(PARI) isok(n)={my(f=factor(n), h=#f~, s=0); forvec(X=vector(h, i, [0, f[h+1-i, 2]]), my(p=prod(i=1, h, f[h+1-i, 1]^X[i])); if(p<s, return(0)); s=p); 1} \\ Andrew Howroyd, Mar 05 2023

Crossrefs

Except for first term 1, this is a proper subsequence of A027855.

Sequence in context: A364531 A299702 A348577 * A027855 A031996 A023753

Adjacent sequences: A361229 A361230 A361231 * A361233 A361234 A361235

Keyword

nonn

Author

Andreas Weingartner, Mar 05 2023

Status

approved