4
$\begingroup$

Note: Posting in MO since it was unanswered in MSE

Let $f(x)$ be the number of digits in the decimal representation of $x$ e.g. $, f(0) = 1, f(1729) = 4$. If $n = ab$ then we can show that $f(ab) > f(a) + f(b)$ is impossible. Hence $f(ab)$ is either less than or equal to $f(a) + f(b)$. Loosely speaking if $f(ab) < f(a) + f(b)$, we are using more digits than the number itself hence the number of digits get inflated.

Definition: A number $n$ is said to be inflated if for all its divisors $n = ab$, we have $f(ab) < f(a) + f(b)$.

E.g. The divisors of $4321$ are $[1, 29, 149, 4321]$ and clearly $4321$ is wasteful. But $4324$ is not a wasteful number since $4324 = 46 \times 94$ and $f(4324) = f(46) + f(94) = 4$. Trivially, all primes $p$ are wasteful since $f(p \times 1) < f(p) + f(1)$. The first few inflated numbers are:

$$ 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 17, 19, 22, 23, 26, 29, 31, 33, 34, 37, 38, 39, 41, 43, 44, 46, 47, 50, 51, 52, 53, 55, 57, 58, 59, 60, 61, 62, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 80, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99 $$

Graph for the density of wasteful numbers below $10^9$. There are $386000005$ wasteful numbers below $10^9$.

enter image description here

Question 1: In the comments of the posts in the linked question in MSE, it as noted by different users that the sequence of inflated numbers appears to be same as OEIS A122427. This is not immediately obvious because the two sequence seems to have different definitions. Are these two sequences identical?

Question 2: What are the necessary and sufficient conditions for a number to be an inflated number? Does the natural density of inflated numbers exist? Experimental data for $n \le 10^9$ suggests that it oscillates in a regular pattern between $0.2$ and $0.4$.

$\endgroup$
4
  • 1
    $\begingroup$ why isn't $1$ wasteful, $1=1\cdot 1$? I would suggest not to consider $1$ as a factor. $\endgroup$ Feb 27, 2022 at 14:36
  • 3
    $\begingroup$ Suggestion for an additional question: can the product of two wasteful numbers that are not primes be wasteful? $\endgroup$ Feb 27, 2022 at 14:38
  • 2
    $\begingroup$ Every wasteful number $n$ must be its own lexicographically greatest divisor: otherwise, given any divisor $a$, if $n=n_1n_2$ where $n_1$ is $f(a)$ digits and $n_2$ is $f(n)-f(a)$ digits, we have $n \ge 10^{f(n)-f(a)} n_1 \ge 10^{f(n)-f(a)} a$. Thus if $n=ab$, we have $f(b) \ge f(10^{f(n)-f(a)})=f(n)-f(a)+1$. $\endgroup$
    – user7868
    Feb 28, 2022 at 1:10
  • 2
    $\begingroup$ @ManfredWeis The answer to your question is yes. The smallest example is $4 \times 22 = 88$ and all these three are wasteful numbers $\endgroup$ Apr 26, 2022 at 9:14

1 Answer 1

4
$\begingroup$

The two sequences are indeed equal.

Every wasteful number n must be its own lexicographically greatest divisor: otherwise, given any divisor $a$, if $n=n_1n_2$ where $n_1$ is $f(a)$ digits and $n_2$ is $f(n)−f(a)$ digits, we have $n≥10^{f(n)−f(a)}n_1≥10^{f(n)−f(a)}a$. Thus if $n=ab$, we have $f(b)≥f(10^{f(n)−f(a)})=f(n)−f(a)+1$.

If $n=ab$ and $f(n)\le f(a)+f(b)$, then $a$ or $b$ is greater than $n$ lexicographically: Write $a=x \times 10^{f(a)-1}$ and $b=y \times 10^{f(b)-1}$. For any two real numbers $x,y \in [1,10)$, we have $1 \le xy < 100$, so $f(\lfloor xy \rfloor) \in \{1,2\}$. In particular, $xy$ is lexicographically greater than or equal to $\max\{x,y\}$ if and only if $f(xy)=1$ (since $\max\{x,y\} \le xy < \min\{10x,10y\}$). Thus, we have $f(ab)\in \{f(a)+f(b),f(a)+f(b)-1\}$, and if $f(ab)=f(a)+f(b)$, then either $a$ or $b$ is greater than $n$ lexicographically. Thus, the two sequences are equal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.