Processing math: 100%

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

Revision en19, by SPyofgame, 2020-11-07 10:59:37

The problem

Lets f(x)= product of digits of x. Example: f(123)=123=6, f(990)=990=0, f(1)=1

The statement is, given such limitation N, count the number of positive x that 1xf(x)N

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



The limitation

  • Subtask 1: N106
  • Subtask 2: N1010
  • Subtask 3: N1014
  • Subtask 4: N1018


My approach for subtask 1

  • If (x>N) or (f(x)>N) then (xf(x)>N). So we will only care about xN that xf(x)N
Calculating x * f(x) - O(log10(x))
Counting - O(n log10(n))


My approach for subtask 2

  • If x contains 0 then f(x)=0x×f(x)<1. We only care about such x without 0 digit
Building function - O(result + log10(n))


Here is the solution:

Let takes some x satisfy 1xf(x)N

We can easily prove that f(x)x, and because xf(x)N, we have f(x)N (notice that x might bigger than N)

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

So we can bruteforces all possible tuple of such (a,b,c,d) satisfy (P=2a×3b×5c×7dN). There are small amount of such tuples (493 tuples for N=109 and 5914 tuples for N=1018)

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

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

  • We have the value P, so 1PxNP.
  • 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

So now we have to solve this DP-digit problem: Calculate numbers of such x (LxR) whose f(x)=P



Solving Subproblem

We try to build each digits by digits for X. Because XN, so we have to build about 18 digits.

Lets make a recursive function magic(X,N,p2,p3,p5,p7)

Lets make some definition
Notice that
Ugly precalculation code - O(1)
magic function - O(18*p2*p3*p5*p7)


About the proving stuff

1) xN,f(x)x

  • Proof: x=¯dcba=+d×103+c×102+b×101+a×100×d×c×b×a=f(x)

2) If x satisfy then f(x)R must be satisfied

  • Proof: x×f(x)Rf(x)×f(x)Rf(x)R

3)  a,b,c,dNf(x)=2a×3b×5c×7d

  • Since x=¯dcba(0,d,c,b,a9) and f(x)=×d×c×b×a

  • And we also have digit v (vN,0v9)  a,b,c,dNv=2a×3b×5c×7d

  • And because f(x) is the product of digits of x, hence the statement is correct

4) If we know f(x) we can find such x satisfy x[L,R]

  • Proof: Since f(x) is created from factors of digits of x, so x can also be generated using the factors

5) Number of tuples (a,b,c,d) satisfy P=2a×3b×5c×7dR is very small

  • Lets O(k(x))=O(log2(x)×log3(x)×log5(x)×log7(x))

  • Since each value x have the upper bound of logx(R). So the complexity is about O(log2(R)×log3(R)×log5(R)×log7(R))=O(k(R))O(log2(R)4)

  • But actually for R1018, the complexity is just about O(k(4R))

Weak proof - N = 10^k
Weak proof - N = 2^k
Code


About the complexity:

  • O(h(x))=O(log10(R)) is number of digits we have to build
  • O(k(x))=O(log2(R)×log3(R)×log5(R)×log7(R))=O(log(R)4) is product of all prime digits p with its maximum power k satisfy pkN
  • O(g(x))=O(k(R)) is number of such valid tuples, but for 1N1018 it is about O(k(4R))O(log424R)
  • The space complexity is O(SPACE)=O(h(x)×k(x))=O(log2(R)×log3(R)×log5(R)×log7(R)×log10(R))=O(log(R)5)
  • The time complexity is O(TIME)=O(SPACE)+O(g(x)×k(x))O(log(R)4×log424R)


Other

  • Does anyone know the real complexity for O(k(x)) ? — Counting such tuples of (a,b,c,dN) that P=2a×3b×5c×7dN ?

Since my O(log2(N)) complexity seem very far than the real counting and O(log2(N)) is closer but just correct for N1018

  • Thanks for reading and sorry for updating this blog publicly so many times

History

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