Counting such number whose digit product multiple to itself smaller than given number

Revision en7, by SPyofgame, 2020-11-05 15:51:08

#### The problem

Lets $f(x) =$ product of digits of $x$. Example: $f(123) = 1 * 2 * 3 = 6$, $f(990) = 9 * 9 * 0 = 0$, $f(1) = 1$

The statement is, given such limitation $N$, count the number of positive $x$ that $1 \leq x * f(x) \leq N$

Example: For $N = 20$, there are 5 valid numbers $1, 2, 3, 4, 11$

#### The limitation

• Subtask 1: $N \leq 10^6$
• Subtask 2: $N \leq 10^{10}$
• Subtask 3: $N \leq 10^{14}$
• Subtask 4: $N \leq 10^{18}$

#### My approach for subtask 1

• If $(x > N)$ or $(f(x) > N)$ then $(x * f(x) > N)$. So we will only care about $x \leq N$ that $x * f(x) \leq N$
Function f(x) - O(log10(x))
Counting - O(n log10(n))

#### My approach for subtask 2

• If $x$ contains $0$ then $f(x) = 0 \Rightarrow x * f(x) < 1$. We only care about such $x$ without $0$ digit
Building function - approx O(result)

#### Here is the solution:

Let takes some $x$ satisfy $1 \leq x * f(x) \leq N$

We can easily prove that $f(x) \leq x$, and because $x * f(x) \leq N$, we have $f(x) \leq \sqrt{N}$ (notice that $x$ might bigger than $\sqrt{N}$)

Since $f(x)$ is product of digits of $x$, which can be obtain by such digits {$1, 2, \dots, 9$}. So $f(x) = 2^a \times 3^b \times 5^c \times 7^d$

So we can bruteforces all possible tuple of such $(a, b, c, d)$ satisfy ($P = 2^a \times 3^b \times 5^c \times 7^d \leq \sqrt{N}$). There are about approximately $O(\sqrt{N})$ such tuples (493 for $N = 10^9$ and 5914 tuples for $N = 10^{18}$)

Find all possible tuples - O(quartic_root(N))

#### Solving Subproblem

For each tuples, we need to counting the numbers of such $x$ that $1 \leq x \times f(x) \leq N$ and $f(x) = P$.

• We have the value $P$, so $\lceil \frac{1}{P} \rceil \leq x \leq \lfloor \frac{N}{P} \rfloor$.
• We have the value $f(x) = P$, so $x$ can be made by digits having the product exactly $P$, so we can do some DP-digit

How to this small DP-digit problem: Calculate numbers of such $x$ ($L \leq x \leq R$) whose $f(x) = P$

We try to build each digits by digits for $X$. Because $X \leq N$, so we have to build about $18$ digits.

Lets make a recursive function $magic(X, N, p2, p3, p5, p7)$. Lets make some definition

• $VL, VR$ means the range of $x$ needed to get $1 \leq x \times f(x) \leq N$
• Current prefix of building number is $X$
• We $N$ digits left to build to the right of $X$
• $p2, p3, p5, p7$ means the left factors in $f(x)$
• $min(X, N) = X * 10^N$ means the smallest possible number with prefix $X$ and $N$ left digits
• $max(X, N) = X * 10^N + 10^N - 1$ means the greatest possible number with prefix $X$ and $N$ left digits
• $cost[v][p]$ means greatest divisor $p^k$ in $v$ is when $k = cost[v][p]$
• $memo$ means current $x$ is in range $[VL, VR]$ so we can use memorization
• $save = f[N][p2][p3][p5][p7]$ means dp-table the numbers of valid number $X$ with current states
• $l_x$ means maximum $k$ that $x^k \leq 10^{18}$. Where $l2, l3, l5, l7, l10$ are such those numbers
• $pw10[x] = 10^x$

Notice that

• Initially, $X = 0$, $N = 18$, $(p2, p3, p5, p7)$ is such tuple generated by above function
• $X = 0$ means it is not build yet
• $VL \leq X \leq VR$ means $1 \leq x * f(x) \leq N$
• $N = 0$ means $X$ is built completely
• $(p2 + p3 + p5 + p7) = 0$ means $f(x) = P$
• $min(X) < VL$ means $x * f(x) < L$ always satisfy which is not desired $x$ we are considering
• $max(X) > VR$ means $x * f(x) > R$ always satisfy which is not desired $x$ we are considering
• Building such digit $v$ will reduce each $p2, p3, p5, p7$ by $cost[v], cost[v], cost[v], cost[v]$
• $memo = false$ means if we take memorization here, it is not guarantee that $1 \leq x * f(x) \leq N$
• $save = -1$ means this dp-state it is not calculated yet
Ugly precalculation code - O(1)
magic function - O(18*p2*p3*p5*p7)

• $O(g(x))$ is number of such valid tuples, which is approximately $O(\sqrt{N})$
• $O(h(x))$ is number of digits we have to build, which is $O(log_{10}{N})$
• $O(k(x))$ is product of all prime digits $p$ with its maximum power $k$ satisfy $p^k \leq MAXN$, which is $O(log_2(N) \times log_3(N) \times log_5(N) \times log_7(N))$
• The space complexity is $O(SPACE) = O(h(x) \times k(x))$
• The time complexity is $O(TIME) = O(SPACE) + O(g(x)) \times k(x))$

#### History

Revisions Rev. Lang. By When Δ Comment
en21 SPyofgame 2020-11-08 18:08:04 60
en20 SPyofgame 2020-11-07 11:02:44 132 Tiny change: '\leq N$? \n> Since my ' -> '\leq N$ ? Since my '
en19 SPyofgame 2020-11-07 10:59:37 1409 Tiny change: '4, 11$\n\n-------\n\n#### T' -> '4, 11$\n\n========\n\n#### T'
en18 SPyofgame 2020-11-06 06:29:46 3554 (published)
en17 SPyofgame 2020-11-06 06:02:44 2761 Tiny change: 'sqrt{R})^4 \times log_2(R)^4)$\n\n-' -> 'sqrt{R})^4)$\n\n-' (saved to drafts)
en16 SPyofgame 2020-11-05 18:40:17 1012
en15 SPyofgame 2020-11-05 18:39:30 3010 Tiny change: 'leq x$\n\n>$x = \ove' -> 'leq x$\n\n Proof:$x = \ove'
en14 SPyofgame 2020-11-05 18:11:26 3 Tiny change: '$p^k \leq MAXN$, which ' -> '$p^k \leq N$, which '
en13 SPyofgame 2020-11-05 17:56:06 40
en12 SPyofgame 2020-11-05 17:53:26 43
en11 SPyofgame 2020-11-05 17:42:05 84
en10 SPyofgame 2020-11-05 16:44:33 16 Tiny change: ' summary="Function f(x) - O(' -> ' summary="Calculating x * f(x) - O('
en9 SPyofgame 2020-11-05 15:53:37 88 Tiny change: 'uch those numbers\n- $pw10[' -> 'uch those variables we use\n-$pw10['
en8 SPyofgame 2020-11-05 15:52:01 107
en7 SPyofgame 2020-11-05 15:51:08 61
en6 SPyofgame 2020-11-05 15:50:12 6163 Tiny change: ' build yet)\n\n> Wher' -> ' build yet\n\n> Wher' (published)
en5 SPyofgame 2020-11-05 15:05:42 552 Tiny change: 'y $O(\sqrt{\sqrt{N}}' -> 'y$O(\sqrt{\sqrt{N}}' (saved to drafts)
en4 SPyofgame 2020-11-05 05:03:48 23
en3 SPyofgame 2020-11-05 05:03:05 12
en2 SPyofgame 2020-11-05 05:02:48 170 Tiny change: 'unction - O(result)' -> 'unction - approx O(result)' (published)
en1 SPyofgame 2020-11-05 04:54:10 1886 Initial revision (saved to drafts)