7
$\begingroup$

There is a question that has been bothering my mind for quite a while now. I will present it and my current thoughts and progress on it.

Let the prime factorization of an integer $n$ be $$n = p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3}...$$ And define $n$ to be "unstable" if there exists a prime triplet in its factorization $p_i<p_j<p_k$ $(i<j<k)$ such that $e_j>e_i,e_k$ or $e_j<e_i,e_k$, and the primes are not necessarily consecutive. The exponents of the primes are required to be positive. For example, the numbers $90=2\cdot3^2\cdot5$ and $300=2^2\cdot3\cdot5^2$ are unstable. So is $1361250 = 2\cdot3^2\cdot5^4\cdot 11^2$. It can be seen that $90$ is the only number below $100$ that is unstable. In fact it is the smallest unstable integer. Let $Z(n)$ be the count of unstable integers that do not exceed $n$. So $Z(100)=1$.

The sequence of unstable integers $Z_i$ begins as follows:

$$90,126,198,234,270,300,306,342,350,378,414,450,522,525,\ldots$$

I was wondering if there is an efficient way to enumerate such integers, or in other words, to evaluate $Z(n)$. Because I am interested in counting these integers rather than summing them, and because they solely depend on the exponents of the primes in their factorization, I assume the 'right' way to count them would be combinatorial. Due to their "unstable" nature, I thought it would be better to count them in an indirect way:

Define descending integers to be those in which the exponents of the primes in their factorization are weakly decreasing, i.e $e_j\leq e_i$ for all $i<j, p_i<p_j$. For example, $940896=2^5\cdot3^5\cdot11^2$ is one such integer, whereas $2178 = 2\cdot3^2\cdot11^2$ is not. To avoid confusion, let's arbitrarily choose all prime numbers and their powers to be 'descending'. By convention, $1$ will be considered to be descending as well.

Let $D(n)$ be the count of descending integers not exceeding $n$

Let $A(n)$ be the count of integers not exceeding $n$ that are neither descending nor unstable

This gives the general formula:

$$n = A(n)+D(n)+Z(n)$$ Because all numbers belong to one of these groups.

The reason for further defining these functions is that I suspect they are easier to evaluate than $Z(n)$, but $Z(n)$ can be directly evaluated using them. Is this the right way to approach this? If so, how can I efficiently calculate $D(n)$ and $A(n)$? Can any of these functions be efficiently calculated?


Below is a table of values for all three sequences up to $10^9$:

Values for $D(n)$ and $A(n)$ were calculated with an algorithm that generates all suitable numbers for each of the sequences and counts them. $Z(n)$ values were calculated with the formula:

$$Z(n) = n - A(n)-D(n)$$

In general, integers in $A(n)$ are relatively rare, and therefore easier to count. For instance:

$A(10^{10})= 2510593$

$A(10^{11})= 13578250$

My results for values up to $10^7$ are in line with those mentioned in the comments.

$\endgroup$
  • 3
    $\begingroup$ Your descending integers are OEIS sequence A242031 and their complement A071365. The unstable integers are not (yet) in OEIS. I encourage you to contribute this sequence. $\endgroup$ – Robert Israel Jun 7 at 14:08
  • 1
    $\begingroup$ Are you insisting exponents be positive? Otherwise 10 would be unstable. Gerhard "Unsure About Stability Of Definition" Paseman, 2019.06.07. $\endgroup$ – Gerhard Paseman Jun 7 at 16:16
  • 1
    $\begingroup$ These definitions could be far clearer. One can define descending integers as those whose exponents are decreasing (or nonstrictly decreasing, or weakly decreasing)—any of these are more correct than "not strictly increasing"—and define ascending integers as those whose exponents are increasing but not decreasing (to avoid double-counting primes and powers of squarefree numbers), and then define untable integers to be the rest. $\endgroup$ – Greg Martin Jun 7 at 19:19
  • 1
    $\begingroup$ I imagine that a modification of the sieve of Eratosthenes, with additional bookkeeping for each integer to track the exponent of the previous prime factor and a little finite-state-machine register to determine whether the integer is decreasing or increasing or neither, could compute all of $A(n),D(n),Z(n)$ exactly in essentially linear time in $n$. $\endgroup$ – Greg Martin Jun 7 at 19:24
  • 4
    $\begingroup$ I wrote a program for this purpose. If I understand your question, the number of unstable integers that do not exceed $10^k$ for $k=1,2,3,4,5,6,7$ is $0,1,36,582,6933,74067,761605$. $\endgroup$ – Freddy Barrera Jun 7 at 21:00
2
$\begingroup$

I'm not seeing a smart way (e.g. generating functions) to count these. So I will suggest a way to estimate (or overcount) them. As a nice example, let's start with 30, which is stable. Certain multiples of 30 are unstable. Let q be coprime to 30. Then (3q)(30)^n is unstable. (I assume n is positive.) Of all the numbers less than N, this gives about 8N/2700 which are multiples of 90, 8N/81000 which are multiples of 2700, and so on. So just from looking at 30, one gets about 8N/2610 unstable numbers whose exponent of three is one more than the exponents of both two and five. There is a similar count (about 3/10 as many) for certain unstable multiples of 300.

Note that while this nicely partitions some of the multiples of 90 or 300 which are unstable, it does not capture all unstable multiples of 30. Further, some unstable multiples of 42 are included in this count. Nevertheless, this captures many of the unstable multiples of 30, and can be easily estimated.

Now one can do something similar with other prime triplets, and there is a good chance of counting the overlap between the sets induced by two prime triplets. If nothing else, this gives you something to use to compare against a computer enumeration of unstable numbers.

Gerhard "Feels Pretty Solid About This" Paseman, 2019.06.07.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.