Retina 0.8.2, 134 bytes

.+
,$&,$&$*
+`,(.)*,(1*?)((?=\2+$)(?<=(?=(?<-1>(?=((1*)(?=\2\5+$)1)(\4*$))\6)+1$)\2).*|(?<-1>)(?<-1>\2)+|(?<-1>1)+)$(?(1)1)
1,$.2,$2
1

Try it online! Link includes faster test cases. Explanation:

.+
,$&,$&$*

Create a working area consisting of the result (initially 0), the input, and the input converted to unary.

+`

Repeat until the input has been reduced to zero ...

,(.)*,(1*?)(

count the number of digits d in the value n, and then find the smallest value that satisfies one of ...

(?=\2+$)(?<=(?=(?<-1>(?=((1*)(?=\2\5+$)1)(\4*$))\6)+1$)\2).*|

... its dth power is n, or ...

(?<-1>)(?<-1>\2)+|

... its product with d is n, or ...

(?<-1>1)+)

... its sum with d is n, and ...

$(?(1)1)

ensure that it was in fact d and not some smaller integer, and ...

1,$.2,$2

increment the output and replace n and its unary with the result.

1

Convert the output to decimal.