Density of extended Mersenne numbers?

Question

Consider the subset of odd positive integers defined and constructed as follows by these rules :

A) $1$ is in the set.

B) if $x$ is in the set , then $2x + 1$ is in the set.

C) if $x$ and $y$ are in the set then $xy$ is in the set.

I call them extended Mersenne numbers because rule A and B alone give the Mersenne numbers $2^n - 1$.

And every product of Mersenne numbers must be in the set as well.

So the set or list of extended Mersenne numbers starts like

$$1,3,7,9,15,19,21,27,31,39,43,45,49,55,57,63,79,81,87,91,93,99,...$$

The main question is how dense is this within the odd integers ?

Secondary is there an easy and efficient test to know if an odd integer is in the list ?

I assume this sequence has no name yet but I could be wrong ?

---

*** speculation ***

I see $22$ odd elements from $1$ till $99$, which is close to the number of odd primes under $99$ (that is $24$) $$ \dfrac11 + \dfrac13 + \dfrac17 + \dfrac19 + \ldots + \ldots+\dfrac{1}{99} = 2.034980..$$

So this (subjectively I admit ) seems to imply the sequence grows quite fast. Therefore I guess maybe an asymptotic of the form

$C* x * \ln(x)^D $

for some constants $C,D$ might be an asymptotic for the counting function.

On the other hand I suspect much sharper asymptotics can be proven.

---

---

Background

This comes from abstract algebra where we want a commutative latin square with units and inverses such that "Property A"

$$ x * (y * y^{-1}) = x = (x * y) * y^{-1} $$

holds for all elements $x,y$.

( if this property has a name please tell me )

and for every element $z$

$$ z^2 = 1 $$

( not the main question here, but I wonder how dropping the $z^2 = 1$ condition effects things )

The dimensions of these are then exactly these extended Mersenne numbers + $1$.

---

edit

corrected forgotten terms and copy lulu's conjecture :

The sequence is equal to https://oeis.org/A197625 ???

( https://math.stackexchange.com/users/252071/lulu )

edit2

Greg Martin found counterexample 219 so lulu's conjecture is false.

Greg also conjectured that $D=0$ or $D$ goes to $0$.

It seems that Greg believes we will get close to linear, but I want to point out that the set is denser than the products of mersenne numbers.

On the other hand numbers like $63 = 3 * 21 = 2*31 + 1$ can be reached in $2$ ways so the rules have overlapping values, which could lower the density.

I would not be surprised if the density is slightly higher than the sum of 2 squares or the density of $a^3 + b^3 + c^3$ which are both less than linear.

---

---

It reminds me a bit of collatz, where the rules $2x$ and $(x-1)/3$ generate all integers , or so we believe.

But these rules for the extented Mersenne numbers have no deminishing rule like $(x-1)/3$ ( deminish because that is smaller than $x$) , which is why I believe they might not have linear density.

---

added

Noticed how powers of $5$ or powers of $17$ are never in the list :

$5$ and $25$ are not in.

So $125,625,…$ are not created By products. Also $125,625,…$ are of the form $4n + 1$, so they did not come from the 2x + 1 rule either.

Similar with $17$ or other primes missing of the form $4n + 1$.

This ofcourse highly influences the density.

Also notice primes of the form $4n+1$ have to come from 2x + 1 themselves , where x must be odd !!

2 x + 1 maps 1 mod 4 to 3 mod 4, and maps 3 mod 4 to 3 mod 4 !!

So primes 1 mod 4 are a key thing here !!

---

To adress Joachims extended comment/answer,

quote

" To give at least some shaky heuristic explanation for this behavior: the "average" number of divisors of an integer $n$, and with it the number of possible factorizations $n=ab$ into two factors is something like $\log(n)$. Hence if we assume that among integers smaller than $n$, the lower density of the sequence is some $c>0$, then with some probability $p(a)\cdot p(b)\approx c^2$, both of the given divisors $a,b$ are in the sequence (and hence so is $n$). But going over all divisors $a$, the probability that one never finds a pair $(a,b)$ both lying in the sequence becomes $\prod_{a|n} (1-p(a)\cdot p(n/a)) \approx (1-c^2)^{\log(n)}\to 0$. Of course this is completely unsound, since it assumes that the probabilities for the different divisors are independent, which they obviously aren't. "

Well I do not really agree with it.

Here is why.

1)

First I only consider $n = p b$ for prime $p$ as factorizations.

afterall if they factor like that and $p$ and $b$ are in the list then we are done. No need to involve the factors of $b$.

Since the set is closed by product its quite likely that the other factors of $b$ also have high chance of succes. But that seems like double counting.

This gives an estimate about the sum of reciprocal of primes or $\ln( \ln(n))$. ( see : https://math.stackexchange.com/questions/51083/estimate-the-average-number-of-prime-factors-of-a-1000-digit-number )

2. If $p(a)$ and $p(a/p)$ are close then we have to take into account that

$$(1 - 1/x^2)^x$$

is close to $1 - 1/x$, and thereby not changing the density much.

3. A multiplicative factor in the order of a double log makes some sense ; It is the reciprocal of the primes $q = 1 \mod 4$ (than cannot be reached by product or the $2x + 1$)

And indeed it seems the gap $\ln(\ln(n)) $ is a good lower bound fit, when considering the data given up to $10^{15}$.

Ofcourse none of this is very formal either, but I just wanted to communicate my doubts about those arguments.

---

Maybe helpful ?

Is this the set $S$ in R. H. Bruck, What is a loop?, pp. 59-99 in A. A. Albert, ed., Studies in Modern Algebra, Vol. 2, Mathematical Association of...

Answer 1

Not an answer, but since the graphic may not fit a comment:

The below is a plot of the value $M(n)/n$, where $M(n)$ is the $n$-th value of the sequence (in ascending order, computed such that it's guaranteed to be complete up to $n=10^5$), for $n$ up to $10^5$. These ratios initially tend to rise, seemingly indicating that the set might not quite be of positive (lower) density, but surprisingly, from some point onwards they tend to come down again, and in particular, more than every seventh natural number seems to be in the set.

Update: Below, once again the same image, but this time up to $n=10^6$. To give at least some shaky heuristic explanation for this behavior: the "average" number of divisors of an integer $n$, and with it the number of possible factorizations $n=ab$ into two factors is something like $\log(n)$. Hence if we assume that among integers smaller than $n$, the lower density of the sequence is some $c>0$, then with some probability $p(a)\cdot p(b)\approx c^2$, both of the given divisors $a,b$ are in the sequence (and hence so is $n$). But going over all divisors $a$, the probability that one never finds a pair $(a,b)$ both lying in the sequence becomes $\prod_{a|n} (1-p(a)\cdot p(n/a)) \approx (1-c^2)^{\log(n)}\to 0$. Of course this is completely unsound, since it assumes that the probabilities for the different divisors are independent, which they obviously aren't. But maybe it's possible to turn this into something sound (and indeed, in the above form, this would seem to indicate that the asymptotic proportion among odd integers is actually $1$, contrary to the first intuition, although this convergence would kick in extremely slow).

Update 2: Some further plausibility testing, checking the probability for a number $x\in \{10^k+1,\dots, 10^k+10^5\}$ to belong to the sequence (guided by the hope that an interval of this length is somewhat representative for the probability of a number of that magnitude). For $k=6,7,\dots, 14$, I get the (rounded) values $6.536$, $6.326$, $6.138$, $5.602$, $5.397$, $5.199$, $5.038$, $4.812$, $4.639$ respectively for the inverses of these probabilities, and it seems at least not completely implausible that these values might eventually converge to the (lowest possible) value $2$.

Update 3 (June 2024), to address a late edit to the question, which seems to raise concern about the non-independence of factors in the above product, running over all factorizations $n=ab$: Note that even if one estimates more conservatively by running only over those factorizations $n=ab$ with $a$ prime, one still gets a heuristical upper bound estimate $(1-c^2)^{\log\log(n)} \to 0$ for a "typical" integer $n$ (i.e., which has roughly $\log\log(n)$ different prime factors) to not belong to the set. Of course one needs to be slightly careful since (as noted in the comments) $p(a)=0$ for a prime $a\equiv 1$ mod $4$, but the same estimate goes through by considering only primes $a\equiv 3$ mod $4$. For those primes, the probability to belong to the set should be bounded away from zero, since $\frac{a-1}{2}$ should be expected to be a "typical" integer (i.e., having many prime factors) most of the time, so the probability for such typical integers should eventually propagate also to primes $p\equiv 3 \pmod 4$, which thus should eventually also have probability 1 to belong to the set!! I understand that this seems to blatantly contradict the evidence from ``low" ranges, but note again that such evidence cannot really be expected to be meaningful when the whole thing depends on such super-slow growing functions as $\log\log(n)$. At least the evidence seems to support that a correcting "multiplicative factor in the order of a double log" (and hence density zero inside odd integers (rather than $1$ as I try to propose), as suggested in the recent edit of the question, is not what happens, since the experimental data show that already from $n\approx 10^5$ onwards the density of the set is actually steadily increasing rather than decreasing!